9. Прогулка с Майей Светловой (1 балл). Ответом на задачу является целое число. Серёже очень нравилась Майя Светлова из школы с химическим уклоном. Но Майе также нравилось общение с Электроником. Между мальчиками завязался спор, кто пойдёт гулять с Майей. И решили, что гулять пойдёт победитель игры. Перед мальчиками лежат 6 кучек камней. В каждой кучке 2, 3, 5, 8, 7, 9 камней. Ход заключается в том, что игрок выбирает любую кучку, в которой чётное число камней, и делит её на две кучки (не обязательно одинаковые). Если игрок не может сделать ход (потому что во всех кучках нечётное количество камней), он проигрывает. Определите, кто выиграет в игре, если оба игрока играют оптимально, и первым ходит Электроник? В ответе укажите 1, если выиграет Электроник, 2 если Серёжа Сыроежкин.

Это задача на теорию игр, а именно на игру Ним. В этой игре побеждает тот, кто сделает последний ход. В нашем случае, проигрывает тот, кто не может сделать ход.

Условие игры:

• 6 кучек камней с количеством: 2, 3, 5, 8, 7, 9.
• Ход: выбрать кучку с четным количеством камней и разделить её на две (не обязательно равные) кучки.
• Проигрыш: если игрок не может сделать ход (все кучки с нечетным количеством камней).
• Первый ходит Электроник.

Анализ игры:

Эта игра является вариацией игры Сим, где состояние игры характеризуется количеством камней в кучках. Цель — привести игру к состоянию, когда противник не сможет сделать ход. Такой ход возможен только из состояния, где все кучки имеют нечетное количество камней.

Давайте посмотрим на начальное состояние игры:

Кучки: [2, 3, 5, 8, 7, 9]

Доступные ходы (выбираем кучку с четным числом камней):

• Из кучки 2: можно разделить на (1, 1). Новое состояние: [1, 1, 3, 5, 8, 7, 9].
• Из кучки 8: можно разделить на (1, 7), (2, 6), (3, 5), (4, 4).

Стратегия оптимальной игры:

В играх такого типа часто используется понятие