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

Ответ: Начинающий всегда выигрывает.

Решение:

• Обозначим через W выигрышную позицию, а через L – проигрышную.
• Позиция, в которой все кучки состоят из одного камня, является L (проигрышной), так как никто не может сделать ход.
• Если есть кучка, в которой больше одного камня, её можно разбить на две меньшие кучки.
• База индукции: Если исходно 2 камня, то первый игрок разбивает на две кучки по 1 камню и выигрывает. Значит, 2 – это W.
• Индукционный переход: Предположим, что для всех чисел камней меньше n, мы знаем, какие позиции выигрышные и какие проигрышные. Рассмотрим случай, когда у нас n камней.
• Пусть n = 100. Первый игрок разбивает кучку на две кучки: 1 и 99 камней. После этого хода возникает две ситуации: либо второй игрок выигрывает, либо второй игрок проигрывает.
• Если он выигрывает (т.е. 1 + 99 - выигрышная позиция), то игрок мог разбить камни на 2 и 98. То есть 2+98 проигрышная позиция.

Рассмотрим позицию с n камнями:

• Первый игрок разбивает кучку на две кучки: x и n - x.
• Если существует такое x, что позиция (x, n - x) является проигрышной (L) для второго игрока, то первый игрок делает такой ход и оставляет второго игрока в проигрышной позиции, тем самым выигрывая.
• Если для любого x позиция (x, n - x) является выигрышной (W) для второго игрока, то первый игрок проигрывает.

Обоснование, что начинающий всегда выигрывает, если исходно 100 камней:

• Рассмотрим случай n = 3. Первый игрок разбивает кучку на 1 и 2 камня.
• Второй игрок может разбить 2 на 1 и 1.
• В итоге получим три кучки по 1 камню, и ход второго игрока был последним.
• Начинающий всегда может разбить кучку из 100 камней таким образом, чтобы оставить противника в проигрышной позиции.

Ответ: Начинающий всегда выигрывает.