задачка

[utnapishti]

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

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

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

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

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

Comments

[utnapishti.livejournal.com]

Похоже, большинство людей сначала пытаются решить именно этим способом.
Т.е. пытаемся рассуждать так:
Если изначально фишек меньше, чем n, то в начальной конфигурации есть пустая строчка и пустой столбик.
Посмотрим на клетку X, являющуюся их пересечением. (По-видимому, именно её ты называешь центром пустой крестовины.)
Попытаемся доказать, что она никогда не заполнится...

После нескольких попыток обнаруживаем, что это неверно: если у нас в какой-то момент оказались занятыми все четыре клетки, граничащие с Х *углом*, то через два шага и Х окажется занятой. Для этого даже достаточно, чтобы были занятыми не все четыре соседа-через-угол, а только три из них.
Но - думаем мы - пытаясь "спасти" решение, это значит, что у нас уже (за два хода до заполнения Х) возникла "очень неэффективная" ситуация, при которой много фишек стоят в одном и том же столбце/строчке, и поэтому скорее всего проблема возникнет где-нибудь в другом месте из-за того, что там фишек не хватит.
Но - понимаем мы, ещё немного подумав - мы же не знаем, как именно эти соседи-через-угол оказались заняты.
И дальше всё усложняется.
Короче говоря, решения нет.
Более того, если в качестве начальной конфигурации ставить фишки "через одну" вдоль двух соседних сторон доски начиная с угла (я в одном из комментариев написал поля в шахматных терминах), то пустых крестовин там полным полно, а доска всё-таки заполняется.

[afuchs.livejournal.com]

что значит, нет решения?
ты ж написал, что есть идея решения и обоснование идеи решения.

[utnapishti.livejournal.com]

Я имел в виду - в том, что ты написал, решения (как мне кажется) нет.

[afuchs.livejournal.com]

а, это да