===== ММ134 =====

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

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

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

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

Кто выиграет, если игра начнётся с числа (2011)<sub>10</sub>=(11111011011)<sub>2</sub>?

**Решение**.

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


----