На поле 10×10 9 клеток поросло бурьяном. Каждый год на всех клетках, у которых есть хотя бы две соседние по стороне клетки, поросшие бурьяном, вырастает бурьян. Если клетка поросла бурьяном, то он на ней будет всегда. Найти максимальное число клеток, на которых через 100 лет будет расти бурьян.

Объяснение так себе. Ну а если они не по линии и не по диагонали? Где гарантия, что не получится больше?

Знаешь, я эту задачу видел на одном сайте головоломок, причем там она оценивалась на 5 баллов, то есть очень трудная. Я их тоже не смог убедить. Может, ты придумаешь доказательство получше, а оно и мне там пригодится? :)

Трудность в том, чтобы дать внятное объяснение. Тут можно писать про всякие "островки", что если между ними по вертикали и горизонтали есть одна пустая клетка, то такие островки тут же объединяются до их выпуклой оболочки. Если два "островка" касаются углом, то они тоже объединяются до прямоугольника их обоих содержащего. Ну и отсюда, как бы очевидно, что любые k начальных клеток могут дать максимум k^2 заросших. Но такое объяснение мне самому не нравится.

Заметим, что периметр поросшей бурьяном территории не увеличивается. Если рядом с клеткой, которая на которой вырастает бурьян, было три или четыре поросших бурьяном клетки, то он уменьшается, а если только две, то остаётся неизменным. Изначально он не больше, чем 9⋅4=36. Наибольшая площадь прямоугольник при данном периметре достигается в случае, когда прямоугольник — квадрат со стороной 9. Примером изначальной рассады бурьяна служит поросшая бурьяном главная диагональ без угловой клетки.

Ledi82, спасибо, это очень дельная мысль! Попробую с ней на тот сайт пробиться, может, примут?

81 клетка. Если эти 9 клеток - это одна полоска 1х9, то они так 9 и останутся навсегда.Потому что остальные клетки имеют 0 или 1 соседей с бурьяном.Ни на одной новой клетке он уже не вырастет. Это минимум.А если расположить их по диагонали, то они заполнят квадрат 9х9 за 9 лет.Получится 81 клетка. Это максимум. Тут я нарисовал. Черные клетки - начальные, дальше каждый год все светлее и светлее.