Question

В левом нижнем углу доски 16х16 стоит шахматный король. Три игрока, Вася, Петя и Коля, по очереди делают им ходы по шахматным правилам. Начинает Вася. Игрок, который поставит короля на клетку, где он уже когда-либо был, проигрывает. Докажите, что Петя и Коля могут, объединившись, сделать так, чтобы Вася проиграл.

Answer 1

Докажем сперва, что доску размера 16 на 16 клеток с вырезанной угловой клеткой можно разрезать на уголки из трёх клеток. Действительно, саму клетку можно "огородить" таким уголком, далее уже полученный квадратик 2 на 2 клетки "огородить" новым уголком, состоящим из маленьких уголков (смотрите картинку), и так далее, делая с каждым разом уголки всё больше. Так как 16 - степень двойки, уголки поместятся.

Теперь посмотрим на пустой маленький уголок из трёх клеток. Любые две клетки такого уголка соединены ходом короля. Пусть Вася сходил в какую-то его клетку, тогда Петя и Коля могут своими ходами сходить в две оставшиеся клетки, так как уголок до этого был пустым (в него никто не ходил).

Стратегия: Петя и Коля своими ходами "закрывают" уголок, в который сходил Вася (каким угодно образом). Действительно, в начале все уголки "пустые", после же трёх ходов (Васи, Пети и Коли) по данной стратегии все уголки будут либо полностью "пустыми", либо полностью "полными". Так как количество уголков конечно, в какой-то момент Вася не сможет сделать ход (поставит короля на клетку, где он уже был) и проиграет.

Answer 2

Давайте рассмотрим ситуацию на доске и попробуем найти стратегию, которая позволит Пете и Коле победить Васю.

Обозначим доску так: каждая клетка будет иметь координаты (x, y), где x - номер строки, y - номер столбца. Левый нижний угол доски будет иметь координаты (1, 1), а правый верхний угол - (16, 16).

Начнем с того, что Петя и Коля могут ограничить движение Васи так, чтобы он двигался только внутри определенной зоны доски. Это можно сделать следующим образом:

1. Ход 1: Петя делает ход с клетки (8, 8) на клетку (8, 7). Теперь король не может пойти налево от начальной позиции.

2. Ход 2: Коля делает ход с клетки (8, 8) на клетку (7, 8). Теперь король не может пойти вниз от начальной позиции.

3. Ход 3: Петя делает ход с клетки (8, 8) на клетку (9, 8). Теперь король не может пойти вверх от начальной позиции.

Таким образом, король ограничен движением внутри квадрата, вершины которого имеют координаты (7, 7), (7, 9), (9, 7) и (9, 9).

Далее, Петя и Коля могут следовать стратегии, которая заключается в том, чтобы зеркально отражать ходы Васи относительно центра квадрата, таким образом, ограничивая его возможности и приводя к проигрышу. Каждый ход Васи, который он делает внутри квадрата, будет повторен ими на противоположной стороне квадрата.

Поскольку король не может выйти за пределы этого квадрата, рано или поздно Вася будет вынужден сделать ход, который приведет его на клетку, где он уже был. Таким образом, Вася проиграет.

Петя и Коля могут объединиться, следуя этой стратегии, и выиграть у Васи.