На начальном этапе все клетки квадратной сетки размером 10 на 10 делятся на здоровые и заражённые. Но вирус распространяется и на каждом новом этапе клетка становится заражённой, если среди её ортогональных соседей имеется две и более инфицированных клетки. Например, на рисунке белым цветом обозначены здоровые клетки; красным - заражённые; а жёлтым - клетки, которые будут инфицированы на следующем этапе. Каким должно быть наименьшее число заражённых клеток, чтобы инфекции удалось распространиться по всей сетке?
update
Ответ
10.
Периметр зараженной площади на новых этапах не увеличивается. Так как общий периметр сетки равен 4*10=40, то и изначальный периметр всех зараженных клеток должен быть не меньше 40. То есть нам понадобится минимум 10 клеток. Простой пример их расположения - по диагонали сетки.
Периметр зараженной площади на новых этапах не увеличивается. Так как общий периметр сетки равен 4*10=40, то и изначальный периметр всех зараженных клеток должен быть не меньше 40. То есть нам понадобится минимум 10 клеток. Простой пример их расположения - по диагонали сетки.
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.
ОтветитьУдалитьКрасиво.
УдалитьТолько периметр может измениться - уменьшиться, если больше двух зараженных клеток соседствуют со здоровой.
А увеличиться он действительно не может, этого достаточно.
Да, правильно будет сказать не "не меняется", а "не увеличивается".
Удалить