Два игрока играют в следующую игру. Перед ними лежит куча из N камней. Игроки берут камни по очереди, за один ход можно взять 1, 2 или 3 камня. Проигрывает тот, кто забирает последний камень. Кто выигрывает при безошибочной игре обоих игроков - игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте (Заметьте, не 6 камней как в стандартной задаче,а N. (Граф)

Предыдущий
вопрос Следующий
вопрос

При анализе данной игры можно заметить, что если количество камней в куче кратно 4, то первый игрок всегда выигрывает. Действительно, он может взять 1 камень, после чего второй игрок не сможет взять 3 камня (или он проиграет) и возьмет 1 или 2 камня, после чего первый игрок сможет забрать все оставшиеся камни.

Если же количество камней в куче не кратно 4, то первый игрок не сможет гарантированно выиграть. Однако он может сыграть так, чтобы оставить кучу камней, кратную 4, после своего хода. Для этого ему достаточно взять такое количество камней, чтобы оставшееся количество было кратно 4 (если количество камней не кратно 4, то у первого игрока всегда есть выигрышная стратегия).

Таким образом, выигрывает первый игрок, если количество камней в куче изначально кратно 4, иначе выигрывает второй игрок.