Question

N клеток белой таблицы 11×11 покрашены в чёрный цвет. Каждую минуту каждая белая клетка, которая граничит по стороне хотя бы с двумя чёрными, тоже становится чёрной (а чёрные клетки всегда остаются чёрными). Через некоторое время оказалось, что вся таблица стала полностью чёрной. Какое наименьшее значение могло принимать N?

Answer 1

Оценка:

Пусть операции изменения цвета клетки происходят поочерёдно (если в какой-то момент нужно изменить сразу несколько клеток, изменим их по очереди). Так как каждая новая чёрная клетка касается хотя бы двух предыдущих, то при операции изменения цвета клетки общий периметр чёрных клеток не увеличивается. В конце он должен будет стать равным 44, следовательно, он был не меньше 44 изначально (не менее 11 клеток).

Пример:

Довольно очевидным будет то, что если изначально все чёрные клетки располагались на главной диагонали, то таблица станет полностью чёрной.

Ответ: 11 клеток.

Answer 2

Давайте рассмотрим начальную ситуацию, когда все клетки N белых клеток покрашены в черный цвет, и проверим, как они будут изменяться с течением времени.

Исходно у нас есть N белых клеток, которые могут быть расположены в таблице 11x11. Минимальное значение N будет соответствовать ситуации, когда все N клеток составляют некоторый квадрат внутри таблицы. В этом случае, все N клеток будут иметь две черные соседние клетки с обеих сторон (верх и низ, лево и право), а значит, они будут менять цвет на черный на следующей минуте.

Для нахождения минимального значения N, нужно найти такой наибольший квадрат, который можно поместить внутри таблицы 11x11. Поскольку наш квадрат имеет стороны с целыми значениями, наименьший квадрат будет иметь сторону 1х1 (всего 1 клетка). Но так как этот квадрат не будет иметь две черные соседние клетки с обеих сторон, нам нужен квадрат побольше.

Наибольший квадрат, который можно поместить внутри таблицы 11x11, будет иметь сторону 9х9, а его площадь составит 9 * 9 = 81 клетка.

Следовательно, наименьшее значение N, при котором вся таблица становится полностью черной, равно 81 клетке.