2014-06-08
На бесконечной во все стороны клетчатой доске, на которой первоначально расставлены фишки, заполняющие в точности прямоугольник размер $3k \times n$, происходит игра по следующим правилам: любой фишкой можно перепрыгнуть через любую соседнюю (по вертикали или по горизонтали) фишку, за которой следует незанятая клетка, после чего фишка, через которую перепрыгнули, должна быть убрана с доски. Доказать, что на доске никогда не останется ровно одна
Решение:
Разобьем все клетки бесконечной доски на 3 множества, как показано на рис. (разными цифрами обозначены клетки разных множеств). Топа при каждом ходе количество фишек в двух множествах уменьшается на единицу, а в одном - увеличивается на единицу. При этом четность количества фишек в каждом множестве меняется на противоположную. Если сначала фишки занимали прямоугольник $(3k) \times n$, то их количества в каждом множестве были равны. Следовательно, после каждого хода четности количеств фишек в каждом из трех множеств должны совпадать. Если бы после какого-то хода на доске осталась одна фишка, то в двух множествах количество фишек было бы четно, а в одном - нечетно. Поэтому такая ситуация возникнуть не может.