задачка

[utnapishti]

Недавно я наткнулся в жж на математическую задачку, которая мне очень понравилась. Потом расскажу, почему именно, а пока пересказываю её своими словами.

Дана квадратная решётка n×n. (Пояснение: Она состоит из n² клеток. Например, шахматная доска - это квадратная решётка 8×8).
В некоторые клетки мы ставим фишку. Таким образом, мы имеем "начальную конфигурацию".
Клетки, в которых стоит фишка, называем "занятыми"; а те, в которых фишки нет - "свободными".
После этого начинается "эволюционный процесс": если есть свободная клетка, с которой граничат как минимум две занятые клетки, то в эту свободную клетку мы тоже ставим фишку (таким образом, эта клетка становится "занятой").
(ПОЯСНЕНИЕ: клетки считаются граничащими, если у них есть общая сторона. Если только общий угол - не считаются.)
Этот процесс продолжается, пока есть куда ставить новые фишки согласно правилу.
Поставленные фишки никогда не снимаются (т.е. однажды занятая клетка больше никогда не становится свободной).

Легко проверить, что, если в качестве начальной конфигурации мы поставим n фишек в клетки, образующие диагональ решётки, то в ходе описанного процесса заполнится вся решётка - т.е. все клетки окажутся занятыми.

Есть и другие возможности поставить в качестве начальной конфигурации n фишек так, чтобы в ходе процесса заполнилась вся решётка.

Доказать: Если в качестве начальной конфигурации мы поставим меньше чем n фишек, то - как бы мы это ни сделали - в ходе процесса вся решётка не заполнится.

Comments

[jenya444.livejournal.com]

Я мог бы объяснить лучше, что имелось в виду, но второй пример опровергает эти соображения: блоки расположены "неправильно", а система всё равно заполняется.