Старые марафонские задачи с продолжением

[VAL]

Как уже упоминал Макс (maxal), я (вот уже несколько лет) веду Математический Марафон.
Сейчас Марафон ушел на каникулы до сентября.
Во время этой паузы я хочу вспомнить ряд предлагавшихся там задач.
Решение и разбор каждой из них опубликованы в Марафоне. Но...
Каждая из этих задач порождает новые вопросы, ответы на которые не удалось найти совместными усилиями ведущего и конкурсантов.
Не исключено, что открытые вопросы удасться "закрыть" здесь.

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

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


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

[Руст]

Задача полностью алгоритмический разрешаема. Начинаем с $n=0$ - проигрышная позиция нулевого уровня (для первого). Для любой проигрышной позиции n все позиции $n+a^k,n+b^m$ выигрышные - 1 го уровня. Первое натуральное число не попавшее в число позиций уровня меньше 2k является проигрышной позицией уровня 2k и т.д. естественно выигрышных позиций всегда больше. Единственное исключение $a=1=b$ в этом случае чётные проигрышные, нечётные выигрышные, т.е. примерно равная вероятность пр чётности числа N ограничивающего максимальное значение n.
Для компьютера не представляет труда вычислить $f(a,b,n)=0,1$ 0- проигрышная позиция, 1- выигрышная позиция. Аналитический в явном виде можно решит по видимому только в случае, когда одно из чисел a,b равен 1.

[VAL]

Руст писал(а):

Задача полностью алгоритмический разрешаема. Начинаем с $n=0$ - проигрышная позиция нулевого уровня (для первого). Для любой проигрышной позиции n все позиции $n+a^k,n+b^m$ выигрышные - 1 го уровня. Первое натуральное число не попавшее в число позиций уровня меньше 2k является проигрышной позицией уровня 2k и т.д. естественно выигрышных позиций всегда больше. Единственное исключение $a=1=b$ в этом случае чётные проигрышные, нечётные выигрышные, т.е. примерно равная вероятность пр чётности числа N ограничивающего максимальное значение n.

Это далеко не единственное исключение

Цитата:

Для компьютера не представляет труда вычислить $f(a,b,n)=0,1$ 0- проигрышная позиция, 1- выигрышная позиция. Аналитический в явном виде можно решит по видимому только в случае, когда одно из чисел a,b равен 1.

Отнюдь.
В частности, ответ на второй вопрос легко получить не программируя.

Интереснее обстоит дело с третьим вопросом.

[Руст]

Да очевидный анализ для случая, когда a и b нечётные. Результат такой же нечётные n выигрышны, чётные проигрышны. Если одно из чисел больше $N$ то оно эквивалентно замене этого числа 1, так как мы не можем вычесть степень большую 0. Т.е. и их (независимо от чётности) можно причислить к просто анализируемым.

[VAL]

Руст писал(а):

Да очевидный анализ для случая, когда a и b нечётные. Результат такой же нечётные n выигрышны, чётные проигрышны.

Угу.
Но среди простых чисел есть еще 2.
Для a = 2 оценки шансов другие. Но в случае, когда b тоже просто, вычисляются они не сложно.

Добавлено спустя 19 минут 21 секунду:

Выношу на рассмотрение еще одну марафонскую задачу.
С задачей ММ66 ее очевидным образом роднит принадлежность к стратегиям.
Но это не главное. Главное - это наличие строго обоснованного ответа, не желающего согласовыватья со здравым смыслом.
Такая же картина наблюдается (но пока не в этом форуме) и в ММ66.


MM41
Двое играют в такую игру:
Игроки A и B выставляют на кон по банкноте одинакового достоинства, на каждой из которых имеется семизначный номер. Игроки сравнивают соответствующие (стоящие в одинаковых позициях) цифры номеров. Если i-я цифра на банкноте игрока A больше i-й цифры на банкноте B, то A получает зачетный балл, и наоборот. Побеждает (и забирает банкноту противника) тот, кто наберет больше зачетных баллов. В случае равенства баллов игроки остаются при своих.
Например, если у A номер банкноты 4987200, а у B - 4007311, то со счетом 3:2 победит B.
Какую наименьшую сумму цифр может иметь номер банкноты, для которой математическое ожидание выигрыша положительно?

[worm2]

MM41
Задачу ещё не решил. Но то, что ответ не желает согласовываться со здравым смыслом, уже вполне верю.
Ибо тот факт, что рассматриваемое отношение между номерами банкнот не является транзитивным:
012>201>120>012
противоречит здравому смыслу.

[VAL]

worm2 писал(а):

MM41
Задачу ещё не решил. Но то, что ответ не желает согласовываться со здравым смыслом, уже вполне верю.
Ибо тот факт, что рассматриваемое отношение между номерами банкнот не является транзитивным:
012>201>120>012
противоречит здравому смыслу.

С отсутствием транзитивности подобных отношений я знаком давно и хорошо.
Может быть поэтому, моему здравому смыслу этот факт не противоречит.
Здесь другое.

[TOTAL]

worm2 писал(а):

MM41
Задачу ещё не решил. Но то, что ответ не желает согласовываться со здравым смыслом, уже вполне верю.
Ибо тот факт, что рассматриваемое отношение между номерами банкнот не является транзитивным:
012>201>120>012
противоречит здравому смыслу.

Под противоречием здравому смыслу имеется в виду побеждающий в среднем набор с суммой в менее половины от максимальной суммы.

Добавлено спустя 12 минут 24 секунды:

Например для трехзначных чисел перемножьте

$$\left(1+6x+\frac{3}{x} \right)\left(1+7x+\frac{2}{x} \right)\left(1+\frac{9}{x} \right)$$

Сумма коэффициентов перед положительными степенями больше, чем перед отрицательными

[Руст]

Если известны цифры то легко просчитывается количество вариантов когда это число выходит победителем. Для этого определим места выигрыша А, места ничьи B и места проигрыша. С. Соответственно для заданных мест находится количество позиций

$$\prod_{i\in A}a_i\prod_{i\in C}(9-a_i).$$

Так как множества не пересекаются то остается определить сумму. Вообще от перестановки цифр не зависит количество тех позиций, которых данное число побеждает. Поэтому можно считать, что цифры расположены в порядке неубывания и на компьютере перебрать все варианты их всего $C_{17}^7=19448$.
Рассмотрим случай, когда 5 цифр a и два нуля. Тогда вычислим выигрышные позиции.
1 выигрыш и ни одного проигрыша - $N_{1,6,0}=5a$.
2 выигрыша и ни одного проигрыша - $N_{2,4,0}=C_5^2a^2=10a^2$.
2 выигрыша, 3 ничьи и один проигрыш - $N_{2,3,1}=10a^2*3*(9-a)+10a^2*2*9=30a^2(5-a)$.
3 выигрыша, и ни одного проигрыша - $N_{3,4,0}=10a^3$.
(3,3,1) - $N_{3,3,1}=10a^3*2(9-a)+10a^3*2*9=20a^3(18-a)$
(3,2,2) - $N_{3,2,2}=10a^3[(9-a)^2+2*2*(9-a)*9+9^2]$
(4,3,0)- $N_{4,3,0}=5a^4$
(4,2,1) - $N_{4,2,1}=5a^4[9-a+9*2]$
(4,1,2) - $N_{4,1,2}=5a^4[(9-a)*9*2+9*9]$
(4,0,3) - $N_{4,0,3}=5a^4*81*(9-a)$
(5,2,0)- $N_{5,2,0}=a^5$
(5,1,1) - $N_{5,1,1}= 18a^5
(5,0,2) - $N_{5,0,2}=81a^5$.
Суммируя получаем $N_5(a)= -390a^5+4400a^4+5200a^3+160a^2+5a$.
При а=6 не достаточно, а при а=7 с излишком. По видимому достаточно $0066777$. Считать в ручную тяжело.

[VAL]

TOTAL писал(а):

Под противоречием здравому смыслу имеется в виду побеждающий в среднем набор с суммой в менее половины от максимальной суммы.

Именно!

Цитата:

Например для трехзначных чисел перемножьте

$$\left(1+6x+\frac{3}{x} \right)\left(1+7x+\frac{2}{x} \right)\left(1+\frac{9}{x} \right)$$

Сумма коэффициентов перед положительными степенями больше, чем перед отрицательными

Оно!
Т.е. номер 760 имеет положительное мат. ожидание выигрыша, несмотря на то, что его сумма цифр не дотягивает до средней.

Такие же номера есть для всех нечетнозначных номеров.

[juna]

TOTAL писал(а):

Под противоречием здравому смыслу имеется в виду побеждающий в среднем набор с суммой в менее половины от максимальной суммы.

А для двоичной системы при семи позициях вроде никакого парадокса не получается - при четырех единицах математическое ожидание выигрыша нулевое, соответственно положительное начиная с пяти. Ищем для какого $k$ выполняется неравенство:
$\frac{C_7^0+C_7^1+...C_7^{k-1}}{2^7}>0.5$, где $k$ - количество единиц.

[VAL]

juna писал(а):

А для двоичной системы при семи позициях вроде никакого парадокса не получается

Согласен. Причем не только при семи.

Цитата:

- при четырех единицах математическое ожидание выигрыша нулевое

А с этим утверждением не согласен категорически.

Цитата:

Ищем для какого $k$ выполняется неравенство:
$\frac{C_7^0+C_7^1+...C_7^{k-1}}{2^7}>0.5$, где $k$ - количество единиц.

А куда ничьи подевались?

[juna]

VAL писал(а):

А куда ничьи подевались?

Так ничья - это же не выигрыш... - каждый при своих.
Искажения же от среднего для других систем возникают видимо из-за того, что мы за каждое превышение вне зависимости от разницы прибавляем только балл.

[Руст]

Компьютер показывает что выигрышный в среднем номер имеющий минимальную сумму цифр есть 0006999 (на самом деле их несколько с такой же суммой) с суммой 33. Наилучшая 0008889 - побеждает 5275505 позиций. Однако это больше чем средняя сумма цифр= 7*9/2=31.5
Поэтому не понятно о каком парадоксе идёт речь.

[juna]

Руст
А какое число у Вас получается для трехзначных чисел?
Здесь заявлено 067.