Двое играют в игру, делая ходы по… (вероятность и статистика)

Игра с монетами, выигрышные и проигрышные позиции

⚠️

Список вариантов обрезан внизу фото: видны только , , , , . Если ниже есть ещё варианты, их можно проверить по тому же правилу: первый игрок выигрывает, когда остаток n при делении на не равен , или . Чтобы я проверил и их, переснимите фото так, чтобы были видны все варианты.

Двое играют в игру, делая ходы по очереди. На столе лежит $n$ монет. За один ход разрешается снять со стола 1, 2, 5 или 9 монет. Выигрывает тот, кто снимет последнюю монету. При каких $n$ первый игрок может выиграть независимо от ходов другого игрока? Выберите все подходящие варианты: 62; 63; 64; 65; 66 (видны не все варианты).

Решение

Позицию назовём проигрышной, если игрок, который ходит, проигрывает при правильной игре соперника. Позиция выигрышная, если из неё есть ход в проигрышную.

Позиция монет проигрышная: ходящему нечего брать.

Разбираем по порядку:

: берём всё, выигрыш.
: ходы ведут в или , обе выигрышные, значит проигрышная.
: ход в , выигрыш.
: берём , выигрыш.
: ходы ведут в , , , все выигрышные, значит проигрышная.
: ход в , выигрыш.
: ход в , выигрыш.
: берём , выигрыш.
: ходы ведут в , , , , все выигрышные, значит проигрышная.
: ход в , выигрыш.
: ходы ведут в , , , , все выигрышные, значит проигрышная.
: ход в , выигрыш.
: ходы ведут в , , , , все выигрышные, значит проигрышная.
: ходы в , , , выигрыш.
: ходы ведут в , , , , все выигрышные, значит проигрышная.

Проигрышные позиции: , , , , , , , … Дальше они повторяются с периодом : проигрышные дают остаток , или при делении на .

Проверяем варианты:

: остаток , выигрышная.
: остаток , проигрышная.
: остаток , выигрышная.
: остаток , выигрышная.
: остаток , проигрышная.

💡 Почему так

Первый игрок побеждает, если может ходом оставить сопернику проигрышную позицию. Проигрышные позиции здесь повторяются с периодом : это с остатками , , при делении на .

Ответ

✓ dzmen.ru

, ,

Помогло?

Двое играют в игру, делая ходы по очереди. На столе лежит n…