Решение задачи MM134 IV открытой интернет-олимпиады по математике: XIV тура Математического марафона

главная страница сайта Приглашение в мир математики
==================== 134 ===============

ММ134 (МИ2) (4 балла)

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

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

Кто выиграет, если игра начнётся с числа с числа (2011)_{10}=(11111011011)_2?


Решение.

Выигрывает 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 подготовил Алексей Извалов

Задайте вопрос на блоге о математике