2014-06-08
«Дельфин» - фигура, которая ходит на одно поле вверх, вправо или по диагонали налево вниз, как показано на рис. Может ли «дельфин», начиная из левого нижнего угла доски размером $8 \times 8$, обойти всю эту доску, побывав в каждой клетке ровно по одному разу?
Решение:
Занумеруем горизонтали доски снизу вверх числами $0, 1, \cdots, 7$ и вертикали доски слева направо теми же числами. Каждой клетке доски поставим в соответствие сумму номеров вертикали и горизонтали, на пересечении которых эта клетка находится. «Дельфин» начинает свой путь в клетке, которой соответствует число 0. При каждом ходе «дельфина» число $x$, соответствующее клетке, на которой он находится, либо увеличивается на 1, либо уменьшается на 2, поэтому остаток от деления на 3 числа $x$ изменяется в следующей последовательности: $0, 1, 2, 0, 1, 2, \cdots$. Предположим, что «дельфин» обошел всю доску, побывав в каждой клетке по одному разу. Разобьем оставшиеся (после отбрасывания начальной клетки) 63 клетки на 21 тройку клеток, подряд идущих по ходу «дельфина». Тогда в каждой тройке ровно одной клетке соответствует число, кратное 3. Однако таких клеток (заштрихованных на рис.) имеется лишь 20. Полученное противоречие доказывает, что «дельфин» не может обойти всю доску.