Двое играют в следующую игру. Первоначально гора состояла из N камней. За ход каждый из игроков выбрасывает один камень и какую-нибудь кучу камней делит на две (любые) кучи. Проигрывает игрок, который не может сделать очередной ход. Кто выигрывает при правильной игре?
Рассмотрите такой параметр: количество оставшихся камней минус количество куч
Ответ: Если (N – 1) кратно трем, то выигрывает второй, если (N – 1) не кратно трем, то выигрывает первый. Рассмотрим параметр K: количество оставшихся камней минус количество куч. Отметим, что остаток от деления K на 3 меняется при ходе игрока. Чтобы проиллюстрировать это утверждение рассмотрим ситуацию 4 камня в одной куче плюс несколько куч по одному камню: 4 + … (K =3). После хода игрока возникнет одна из следующих ситуаций: 3 + … (K = 2) 2 + … (K = 1) 2 + 2 + … (K = 2). Отметим, что значение параметра кратное трем является проигрышным, что можно проиллюстрировать на элементарных проигрышных ситуациях: 2 + 2 + 2 + … (K = 3) 2 + 3 + … (K = 3) 3 + 3 + 3 + ... (K = 6) 4 + … (K = 3). Напротив, если K не кратно трем, то игрок может сделать так, чтобы после его хода K стало кратно трем. Иллюстрация: 5 + … (K = 4) => 4 + … (K = 3) 6 + … (K = 5) => 4 + … (K = 3)
