На столе лежат 2025 спичек. Двое по очереди делают ходы: берут по несколько спичек, причём каждый из игроков может брать по своему усмотрению в каждом ходе любое натуральное число из отрезка [1;M] спичек. Выигрывает тот, кто возьмёт последнюю спичку. Найди, сколько ходов всего будет сделано при правильной стратегии игрока-победителя, если:
a) M=2, Na — наименьшее количество ходов
b) M=6, Nb — наименьшее количество ходов.
В ответе запиши Na+Nb.
1 Ответ
Если N делится на (M+1), выигрышная стратегия у второго игрока. Первый игрок делает первый ход, взяв k спичек. Второй игрок отвечает так, чтобы забрать (M+1-k) спичек. И далее применяет ту же стратегию.
a) M=2, N=2025
2025 / (2+1) = 675. Т.к. 2025 делится на 3, выигрывает второй игрок.
В этом случае, для минимизации количества ходов при выигрыше второго игрока, первый игрок должен брать как можно больше спичек на первом ходу, то есть 2 спички. Тогда второй игрок берет 1 спичку. И каждый раз оба игрока берут в сумме 3 спички. Тогда минимальное количество ходов получится, если в начале игры первый игрок возьмет M=2 спички, а второй игрок возьмет 1 спичку. Далее, они будут брать по 3 спички, пока спичек не останется 3. Тогда первый игрок возьмет 2 спички, а второй 1 спичку.
Количество пар ходов (в сумме 3 спички) будет (2025 — 3) / 3 = 2022 / 3 = 674. Добавим первый ход каждого игрока, когда сперва было взято 2 спички, а потом 1 спичка. И последний ход второго игрока, когда осталось 3 спички, и первый игрок взял 2 спички. Общее число ходов будет 674 * 2 + 1 + 1 + 1 = 1348 + 3 = 1351. Значит, Na = 1351.
b) M=6, N=2025
2025 / (6+1) = 289 с остатком 2. Т.к. 2025 не делится на 7, выигрывает первый игрок. Первый игрок берет 2 спички. Далее оба игрока берут в сумме 7 спичек. Тогда минимальное количество ходов получится, если первый игрок возьмет 2 спички. А потом оба игрока будут брать по 7 спичек.
Количество пар ходов будет (2025 — 2) / 7 = 2023 / 7 = 289.
Тогда, общее число ходов равно 289 * 2 + 1 = 578 + 1 = 579. Значит, Nb = 579.
Ответ: Na + Nb = 1351 + 579 = 1930.