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

Конкурсная задача №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 балла