===== №66 =====

Это задача не входит в тематический конкурс.
Результат учитывется только в основном зачете Марафона.


**Конкурсная задача №66 (8 баллов)**   

Двое играют в такую игру:
Каждый игрок очередным своим ходом берет из кучки, содержащей n камней, 
некоторое количество камней. За один ход можно взять количество камней,
являющееся целой неотрицательной степенью одного из двух фиксированных
натуральных чисел (a и b). 
Выигрывает тот, кто возьмет последний камень.

1. Существуют ли такие a и b, при которых шансы на выигрыш у второго игрока
выше, чем у первого?
2. Оценить шансы игроков для случаев, когда a и b - простые числа.
3. Перед началом игры игроки делают ставки. Обе ставки забирает победитель.
Ставка первого игрока в пять раз больше. Зато первый игрок имеет право 
(до того как узнает число n) выбрать числа a и b. Кому из игроков выгодны
такие условия?


Примечания:
1. Число "камней" n для каждой игры выбирается случайно из диапазона 
[1.. 1000000] (распределение равномерное). 
2. Соперники играют наилучшим образом.


**//Решение//**

1. Нет.\\
Пусть А множество n, благоприятных для второго игрока. Тогда при начальном
числе камней n+1 выигрывает первый игрок (для этого ему достаточно взять один
камень). Поэтому при любых a и b множество А содержит не более 500000 чисел.

2. Пусть a и b нечетны. Тогда шансы игроков равны. В самом деле, при нечетном
n выигрывает первый игрок (как бы он ни играл), а при четном - второй.

Если одно из чисел равно 2, а другое нечетно и отлично от 3,
шансы первого игрока составляют 2/3 (точнее, 0.666667).\\
Действительно, если n не кратно 3, то первый игрок всегда может оставить 
в кучке число камней, кратное 3. Придерживаясь такой тактики он гарантированно
выиграет (ведь среди степеней a и b нет чисел кратных 3).\\
Если если же начальное число камней кратно 3, первый игрок оставит в кучке
не кратное 3 число камней и непременно проиграет.

Если {a,b} = {2,3}, шансы первого игрока на победу возрастают до 4/5.
При n, не кратном 5, первый игрок после каждого своего хода будет оставлять 
в кучке кратное 5 число камней (для этого ему достаточно взять 1, 2, 3 или 4 
камня). Поскольку среди возможных ходов нет кратных 5, второй игрок рано или
поздно проиграет. При n, кратном 5, роли поменяются.

3. Описанные условия выгодны первому игроку.\\
В качестве a и b первому игроку достаточно взять числа 2 и (например) 45.
Тогда его шансы на выигрыш составят 0.862408, что значительно больше 5/6,
при которых игра справедлива.  

Опишу простой и достаточно быстрый (временнАя сложность O(n*log^2(n))
алгоритм посторения множества A, состоящего из n, благоприятных для 
второго игрока:\\
Положим А = {0}. Каждого n из рассматриваемого диапазона поместим в А при
условии, что в А ни при каких k не входят n - a^k и n - b^k.


**//Обсуждение//**

Пара {2, 45} не единственная, для которой правила, описанные в пункте 3 
выгодны первому игроку. Существует целый ряд натуральных b, кратных 3,
для которых пара чисел {2, b} дает первому игроку шансы выше 5/6.
В качестве b можно взять 27, 30, 33, 51, 54, 60, 69, 75, 105, 114, 120,
123, 126, 135, 147...

Придумывая эту задачу, я первоначально полагал, что первый игрок будет иметь 
наилучшие шансы при {a,b} = {2,3}. Ведь именно при таких a и b первый игрок
имеет максимальное (при фиксированном n) количество вариантов своего первого 
хода. А именно возможность первым же ходом загнать соперника во множество А и
определяет преимущество первого игрока.\\
Строить множества A для разных a и b стал лишь в попытках найти зацепки 
для доказательства этой гипотезы. Но в результате обнаружил целый букет
пар a и b, для которых шансы первого игрока намного выше, чем при
{a,b} = {2,3}.\\
Именно эта неожиданная находка делает (на мой взгляд, но не взгляд большинства
конкурсантов) задачу красивой.
 

**//Награды//**

За правильное решение этой задачи //Олег Полубасов// получает //8// призовых баллов.
За правильное (но не совсем строгое) решение //Виктор Филимоненков// получает //7//
призовых баллов. За верное решение пунктов 1 и 2 //Андрей Богданов и Владислав
Франк получают// по //4// призовых балла. 


**//Эстетическая оценка задачи - 3.8 балла//**