Игра

[wpoms.]

На прямоугольной доске размером `5 xx 9` играют в игру. Сначала некоторое количество дисков помещают случайным образом в квадраты доски, при этом в каждый квадрат помещают не более одного диска. Ход заключается в перемещении всех дисков из квадратов, в которых они находились, в другие квадраты, с соблюдением следующих правил: (a) каждый диск можно переместить на один квадрат вверх, вниз, влево или вправо относительно того квадрата, в котором он находится; (b) если диск переместили вверх или вниз в рамках одного хода, то следующим ходом его нужно будет перемещать влево или вправо; (c) если диск переместили влево или вправо в рамках одного хода, то следующим ходом его нужно будет перемещать вверх или вниз; (d) по завершении перемещения всех дисков в рамках одного хода ни один квадрат не должен содержать более одного диска. Игра завершается, если нет возможности переместить все диски в рамках одного хода по указанным выше правилам. Докажите, что если в начале игры на доске разместили `33` диска, то игра в конце концов завершится. Докажите, что можно разместить на доске в начале игры `32` диска таким образом, чтобы игра могла продолжалась бесконечно.

@темы: Дискретная математика

Comments

[Гость]

Пусть например в каждой клетке некоторого квадрата 3x3 стоит по диску, берем диск, который расположен в середине этого квадрата, и делаем шаг из пункта а, для определенности вниз. Вопрос как ходить теперь из этой клетки с двумя дисками?
Мои варианты:
- на клетку с диском ходить нельзя;
- перемещать только переложенный верхний диск (в данном случае по пункту b), а нижний по пункту а;
- перемещать оба диска (в данном случае по пункту b).
Какую из них надо решать?

[Дилетант]

Гость, мне кажется, достаточно каждый ход разбить на n шагов, где n — количество фишек.
Пусть все фишки на доске помечены единицами.
Фишка, помеченная единицей, может ходить в соответствии со своим предыдущим ходом (вправо-влево, либо вверх-вниз) либо на пустую клетку, либо на клетку с фишкой, помеченной единицей.
Фишка, сделавшая ход, помечается нулем. На клетку, содержащую такую фишку, уже ходить нельзя. "Полный ход" заканчивается, когда все фишки обнуляются.
Тогда им снова присваивается метка 1, и всё повторяется заново.

[Гость]

Не внимательно прочитал условие "ход заключается в перемещении всех дисков из квадратов". Все девять на строчку вниз получается переносятся.

[Дилетант]

Все девять на строчку вниз получается переносятся.

Если у вас доска 3х3, то всем вниз не получится — доска закончится раньше. Я вообще не уверена, что с полностью заполненной доской 3х3 можно сделать ход. С одним пустым полем можно, а так, кажется, нет.