N клеток белой таблицы 11×11 покрашены в чёрный цвет. Каждую минуту каждая белая клетка,...

Question

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

Answer 1

Оценка:

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

Пример:

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

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