Оценка за решение задачи ММ134 учитывается дважды: в основном Марафоне и в тематическом конкурсе.

Конкурсная задача ММ134 (МИ2) (4 балла)

Позицией в игре является конечное множество чисел, записанных в двоичной системе счисления. Игроки по очереди разбивают одно из чисел этого множества на части так, чтобы выполнялись два правила: 1) оба полученных числа должны начинаться с единицы; 2) хотя бы одно из них должно заканчиваться нулём. Например, 1101 можно разбить только на 110 и 1, а 11010 - на 1 и 1010 или на 110 и 10.

Проигрывает тот игрок, кто не сможет сделать ход согласно правилам.

Кто выиграет, если игра начнётся с числа (2011)₁₀=(11111011011)₂?

Решение.

Выигрывает 2-ой игрок. Приведём решение Сергея Половинкина.

На первом ходу у 1-ого участника есть всего 2 хода:

1) 11111011011 разбивает на 111110 и 11011 Тогда у 2-ого игрока есть 5 возможных ходов, но 4 из них проигрывают, к выигрышу ведет только разбиение 111110 на 1111 и 10. Тогда у 1-ого единственный ход - разбить 11011 на 110 и 11, после этого 2-ой тоже выполняет единственный ход, разбивает 110 на 1 и 10, получаем множество чисел 1111, 10, 1, 10 и 11, у 1-ого ходов нет.

2) 11111011011 разбивает на 111110110 и 11 Тогда у 2-ого игрока есть 6 возможных ходов, но 4 из них проигрывают, к выигрышу ведет разбиение 111110110 на 1111 и 10110. Но проще выигрывает разбиение 111110110 на 1111101 и 10. Тогда все форсированно: 1-ый делает единственный ход, разбивает 1111101 на 111110 и 1, тогда 2-ой разбивает 111110 на 1111 и 10 и выигрывает.

Обсуждение

Впервые встретив задачи на математические игры, я пытался их решать путём построения дерева решений. Как правило, это приводило к комбинаторному взрыву, и в итоге я пришёл к методу вычисления выигрышных/проигрышных позиций. Однако в тематический конкурс Марафона захотелось всключить такую игру, которая бы успешно решалась построением дерева.

Участники справились с данной задачей, а некоторые заметили её связь с играми Гранди или Ним и предприняли некоторые шаги к обобщению. Это награждалось дополнительными баллами. Можно сказать, что в постоянно пополняемом после каждого марафона списке задач, ждущих своего развития, появился новый элемент :)

Награды

За правильное решение задачи Владислав Франк, Алексей Волошин, Александр Ларин и Анатолий Казмерчук и получают по 4 балла. За развитие темы Николай Дерюгин, Евгений Гужавин и Сергей Половинкин получают по 4+2=6 баллов.

Эстетическая оценка задачи 4.3 балла

Разбор задачи ММ134 подготовил Алексей Извалов

---