Question

На столе лежит N спичек. Двое по очереди забирают со стола 1 , 2, 3 или 4 спички. Проигрывает тот, кто не может сделать ход. Выберите все значения N, при которых первый игрок имеет выигрышную стратегию. 37641001325551234Дай 100 баллов!!!

Answer 1

Выигрышная стратегия строится от конца, нужно забрать со стола последнюю спичку, то есть на столе должно остаться  4 или меньше спичек.

Стратегия первого игрока - первым ходом сделать на столе число спичек, кратное 5, и при любом ходе второго "добирать" количество взятых им спичек до 5. То есть если второй берет 4, первый берет 1, если второй берет 3, первый берет 2 и так далее. Каждый ход таким образом мы уменьшаем число спичек на 5, и второй игрок ничего с этим не может сделать. Первый игрок последним ходом заберет оставшиеся спички.

Из предложенных чисел подходят все, кроме 100 и 555, потому что они уже делятся на 5. У первого игрока нет хороших ходов - все его ходы будет "добирать" до пятерки второй игрок, и непременно возьмет последнюю спичку.

Answer 2

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

Игра с двумя игроками, где они поочередно берут 1, 2, 3 или 4 спички, является разновидностью игры "Ним", и её можно решить с помощью теории групп Нима. В данной игре существует два правила:

1. Если N равно 1, 2, 3 или 4, то первый игрок может взять все спички и выиграть. Таким образом, N = 1, 2, 3 и 4 являются выигрышными позициями для первого игрока.

2. Если первый игрок находится в позиции, где N > 4, он может выбрать количество спичек таким образом, чтобы оставить второму игроку N, равное 1, 2, 3 или 4. Это возможно всегда, потому что первый игрок может взять N - 1 спичку и оставить второму игроку N - (N - 1) = 1 спичку, и так далее. Первый игрок может продолжать эту стратегию и гарантированно выиграть.

Итак, первый игрок имеет выигрышную стратегию при N = 1, 2, 3 и 4, а также при любых N > 4.

Следовательно, первый игрок имеет выигрышную стратегию при всех значениях N, начиная с 5 и выше.