На столе лежит N

� спичек. Двое по очереди забирают со стола 1

1, 2

2, 3

3, 4

4 или 5

5 спичек. Проигрывает тот, кто не может сделать ход. Выберите все значения N

�, при которых первый игрок имеет выигрышную стратегию.

37

37

64

64

100

100

132

132

555

555

1234

1234

ПОЖАЛУЙСТА ПРОШУ

Выигрышная стратегия для первого игрока:

первое число – количество спичек.

Последующие числа: ходы игроков, в квадратных скобках [] – указаны ходы соперника

1   1 – выигрыш

2   2 – выигрыш

3   нет выигрышной стратегии

4   1, [1 или 2], 2 или 1 – выигрыш

5   5 – выигрыш

6   1 – гарантирует выигрыш соперника (см. пункт 5 с инверсией позиций).

6   2 – гарантирует выигрыш соперника (см. пункт 4 с инверсией позиций).

6   5 – гарантирует выигрыш соперника (см. пункт 1 с инверсией позиций).

6   нет выигрышной стратегии

7   1, далее у соперника нет шансов (см. пункт 6 с инверсией позиций).

8   2, далее у соперника нет шансов (см. пункт 6 с инверсией позиций).

9   1 – гарантирует выигрыш соперника (см. пункт 8 с инверсией позиций).

9   2 – гарантирует выигрыш соперника (см. пункт 7 с инверсией позиций).

9   5 – гарантирует выигрыш соперника (см. пункт 4 с инверсией позиций).

9   нет выигрышной стратегии

10   1, далее у соперника нет шансов (см. пункт 9 с инверсией позиций).

11   2, далее у соперника нет шансов (см. пункт 9 с инверсией позиций).

12   1 – гарантирует выигрыш соперника (см. пункт 11 с инверсией).

12   2 – гарантирует выигрыш соперника (см. пункт 10 с инверсией).

12   5 – гарантирует выигрыш соперника (см. пункт 7 с инверсией).

12   нет выигрышной стратегии

Просматривается индукционный вывод.

Допустим, мы знаем, что:

3n–2   выигрыш гарантирован

3n–1   выигрыш гарантирован

3n   нет выигрышной стратегии

3n+1   выигрыш гарантирован

3n+2   выигрыш гарантирован

Это верно для n = 3.

Тогда:

3n+3   1 – гарантирует выигрыш соперника (см. пункт 3n+2 с инверсией).

3n+3   2 – гарантирует выигрыш соперника (см. пункт 3n+1 с инверсией).

3n+3   5 – гарантирует выигрыш соперника (см. пункт 3n–2 с инверсией).

3(n+1)   нет выигрышной стратегии

3(n+1)+1   1, далее у соперника нет шансов (см. пункт 3(n+1) с инверсией).

3(n+1)+2   2, далее у соперника нет шансов (см. пункт 3(n+1) с инверсией).

Значит всё сказанное в допущении верно и для n+1,

т.е. для n=4, n=5, n=6, n=7 и т.д.

О т в е т :

Первый может гарантированно выиграть, если число спичек на столе не кратно трём. Стало быть, ему нужно всегда оставлять на столе перед соперником число спичек кратное трём. Если в очередном ходе начавшего игру на столе лежит число спичек больше кратного трём на единицу (1, 4, 7, 10, 13 и т.п.), то начавший игру должен брать одну спичку, оставляя сопернику кратное трём. Если в очередном ходе начавшего игру на столе лежит число спичек больше кратного трём на двойку (2, 5, 8, 11, 14 и т.п.), то начавший игру должен брать две или пять спичек (если это возможно), оставляя сопернику кратное трём.

Второй может гарантированно выиграть, если начальное число спичек на столе кратно трём. В любом ходе ему нужно всегда оставлять на столе перед начавшим игру число спичек кратное трём. Если в очередном ходе второго игрока на столе лежит число спичек больше кратного трём на единицу (1, 4, 7, 10, 13 и т.п.), то второй игрок должен брать одну спичку, оставляя начавшему – кратное трём. Если в очередном ходе второго игрока на столе лежит число спичек больше кратного трём на двойку (2, 5, 8, 11, 14 и т.п.), то второй игрок должен брать две или пять спичек (если это возможно), оставляя начавшему – кратное трём.