На начальном этапе все клетки квадратной сетки размером 10 на 10 делятся на здоровые и заражённые. Но вирус распространяется и на каждом новом этапе клетка становится заражённой, если среди её ортогональных соседей имеется две и более инфицированных клетки. Например, на рисунке белым цветом обозначены здоровые клетки; красным - заражённые; а жёлтым - клетки, которые будут инфицированы на следующем этапе. Каким должно быть наименьшее число заражённых клеток, чтобы инфекции удалось распространиться по всей сетке?
update
Ответ
10 - главная либо побочная диагональ.
ОтветитьУдалитьНе очень сторого, но:
Новая клетка может появиться, при условии что уже в столбце/строке есть зараженные. Заражение не может выйти из ограничивающего прямоугольника.
Не обязательно именно диагональ, есть и другие конфигурации.
УдалитьНапример, взять 5 непересекающихся квадратов 2х2, стоящих по диагонали, и у каждого заразить любые две диагональные клетки. После первой итерации получим зараженными все эти 5 квадратов, и дальше инфекция распространится на все поле.
Но меньше 10 не получается действительно :)
В каждой строке и каждом столбце нужно иметь зараженную клетку. Она там может появиться только если зажата двумя зараженными с противоположных сторон, но тогда в какой-то строке (столбце) получается две. Тоже не очень строго, но идея вроде прослеживается :)
Действительно, наименьшее число равно 10. Но есть доказательство построже.
УдалитьЧто-то у меня мысль крутится примерно в таком направлении.
УдалитьЕсли предположить, что изначально зараженных клеток меньше 9, то найдутся полностью чистые строка и столбец. Если они крайние (или строка, или столбец) - то их заразить возможности нет. Значит, они делят сетку на четыре прямоугольные области.
Далее, если из этих четырех областей зараженные клетки есть только в двух (или меньше), то несложно доказать, что всю сетку заразить не получится.
Дальше пока простого и понятного продвижения не получилось :)
1) Вирус не может выйти за прямоугольник, очерчивающий имеющиеся заражённые клетки.
ОтветитьУдалить2) При добавлении одной дополнительной зараженной клетки к имеющемуся прямоугольнику, к нему можно добавить максимум две в будущем зараженные линии - либо вертикальную и горизонтальную, если добавить наискосок к угловой клетке, либо две одного направления, если добавить через одну клетку от стороны.
3) Пусть имеем зараженную клетку - занимает 2 линии (1 верт и 1 гориз). Постепенно добавляя зараженные клетки, можно увеличивать прямоугольник шагами максимум на 2 линии. квадрате 10х10 - 20 линий. То есть нужно прибавить 18 - добавить минимум 9 зараженных клеток, то есть в общем минимум 10.
У меня такой вариант. Периметр зараженной площади на новых этапах не меняется. А мы в итоге должны получить зараженный прямоугольник с периметром 4*10=40. Минимальное количество клеток нужных для этого 40/4=10.
ОтветитьУдалитьКрасиво.
УдалитьТолько периметр может измениться - уменьшиться, если больше двух зараженных клеток соседствуют со здоровой.
А увеличиться он действительно не может, этого достаточно.
Да, правильно будет сказать не "не меняется", а "не увеличивается".
Удалить