Похоже, большинство людей сначала пытаются решить именно этим способом. Т.е. пытаемся рассуждать так: Если изначально фишек меньше, чем n, то в начальной конфигурации есть пустая строчка и пустой столбик. Посмотрим на клетку X, являющуюся их пересечением. (По-видимому, именно её ты называешь центром пустой крестовины.) Попытаемся доказать, что она никогда не заполнится...
После нескольких попыток обнаруживаем, что это неверно: если у нас в какой-то момент оказались занятыми все четыре клетки, граничащие с Х *углом*, то через два шага и Х окажется занятой. Для этого даже достаточно, чтобы были занятыми не все четыре соседа-через-угол, а только три из них. Но - думаем мы - пытаясь "спасти" решение, это значит, что у нас уже (за два хода до заполнения Х) возникла "очень неэффективная" ситуация, при которой много фишек стоят в одном и том же столбце/строчке, и поэтому скорее всего проблема возникнет где-нибудь в другом месте из-за того, что там фишек не хватит. Но - понимаем мы, ещё немного подумав - мы же не знаем, как именно эти соседи-через-угол оказались заняты. И дальше всё усложняется. Короче говоря, решения нет. Более того, если в качестве начальной конфигурации ставить фишки "через одну" вдоль двух соседних сторон доски начиная с угла (я в одном из комментариев написал поля в шахматных терминах), то пустых крестовин там полным полно, а доска всё-таки заполняется.
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png)
timeasmymeasure
no subject
Date: 2015-02-22 11:22 am (UTC)Т.е. пытаемся рассуждать так:
Если изначально фишек меньше, чем n, то в начальной конфигурации есть пустая строчка и пустой столбик.
Посмотрим на клетку X, являющуюся их пересечением. (По-видимому, именно её ты называешь центром пустой крестовины.)
Попытаемся доказать, что она никогда не заполнится...
После нескольких попыток обнаруживаем, что это неверно: если у нас в какой-то момент оказались занятыми все четыре клетки, граничащие с Х *углом*, то через два шага и Х окажется занятой. Для этого даже достаточно, чтобы были занятыми не все четыре соседа-через-угол, а только три из них.
Но - думаем мы - пытаясь "спасти" решение, это значит, что у нас уже (за два хода до заполнения Х) возникла "очень неэффективная" ситуация, при которой много фишек стоят в одном и том же столбце/строчке, и поэтому скорее всего проблема возникнет где-нибудь в другом месте из-за того, что там фишек не хватит.
Но - понимаем мы, ещё немного подумав - мы же не знаем, как именно эти соседи-через-угол оказались заняты.
И дальше всё усложняется.
Короче говоря, решения нет.
Более того, если в качестве начальной конфигурации ставить фишки "через одну" вдоль двух соседних сторон доски начиная с угла (я в одном из комментариев написал поля в шахматных терминах), то пустых крестовин там полным полно, а доска всё-таки заполняется.