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

[Руст]

Я извиняюсь считал только количество выигранных позиций.
Минимальная сумма равна 31. Например число 0006799 выигрывает 3 978 109 позиций, ничья с 2 083 471, проигрывает 3 938 420 позиций. Соответственно (чщтя выигрышных позиций меньше 5 000 000) это число выигрывает больше, чем проигрывает.

[VAL]

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

Суммируя получаем $N_5(a)= -390a^5+4400a^4+5200a^3+160a^2+5a$.
При а=6 не достаточно, а при а=7 с излишком.

Считать, что все ненулевые цифры одинаковы - чрезмерно грубое допущение.

Цитата:

По видимому достаточно $0066777$. Считать в ручную тяжело.

А чем Вас не устраивает подход, использованный Total'ом?

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

juna писал(а):

VAL писал(а):

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

Так ничья - это же не выигрыш... - каждый при своих.

Тогда почему Вы засчитываете ее в пользу соперника?

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

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

Я извиняюсь считал только количество выигранных позиций.
Минимальная сумма равна 31. Например число 0006799 выигрывает 3 978 109 позиций, ничья с 2 083 471, проигрывает 3 938 420 позиций. Соответственно (чщтя выигрышных позиций меньше 5 000 000) это число выигрывает больше, чем проигрывает.

Вот теперь все верно (если не считать загадочного слова "чщтя") :)

Замечу, однако, что есть номера с суммой 31 и повыгоднее, чем 0006799.

И еще ряд вопросов:
Существуют ли четные n, для которых имеются n-значные номера с суммой цифр меньше 9n/2 и положительным мат. ожиданием выигрыша?
Существуют ли n, для которых имеются n-значные номера с суммой цифр меньше [9n/2] и положительным мат. ожиданием выигрыша?

[worm2]

VAL писал(а):

Замечу, однако, что есть номера с суммой 31 и повыгоднее, чем 0006799.

Вроде бы, рекордсмен - 0007888.

[Руст]

VAL писал(а):

И еще ряд вопросов:
Существуют ли четные n, для которых имеются n-значные номера с суммой цифр меньше 9n/2 и положительным мат. ожиданием выигрыша?
Существуют ли n, для которых имеются n-значные номера с суммой цифр меньше [9n/2] и положительным мат. ожиданием выигрыша?

Упорядочим n - значные номера следующим порядком $x\ge y$ если после упорядочения цифр $a_i$ числа х $a_1\le a_2\le ...\le a_n$ и упорядочения цифр $b_1\le b_2\le ...\le b_n$ числа y выполняется $a_i\ge b_i \ \forall i$ и строго $x>y$ если $x\ge y$ и существует i: $a_i>b_i$. Определим операцию сопряжения $x=(a_1,a_2,...,a_n), \tau x =((9-a_n),(9-a_{n-1}),...,(9-a_1))$, очевидно $\tau (\tau x) =x$ (основной смысл сопряжения). Определим ещё отношение x побеждает y $xVe$ и функции $f(x)=N_{y| xVy}-N_{y| yVx}$ и $s(x)=2*\sum_i a_i -(d-1)9N$. Здесь $d$ основание исчисления, отношение $xVy$ не является порядком (как показал worm2 оно не транзитивно).
Лемма 1. Функции $f,s$ монотонны и симметричны относительно антиизоморфизма ($x\ge y\to \tau x\le \tau y$)
$ f(\tau x)=-f(x),s(\tau x)=-s(x)$.
Введём ещё одну операцию $x=(a_1,...,a_n)\to x'=(0,a_1,...,a_n,d-1)$.
Лемма 2. Операция ' сохраняет знаки функций $sign f(x')=sign f(x), \ sign s(x')=sign s(x).$
Из этих лемм получается ответ-следствие для 2 - ичной системы: При $d=2$ верно $sign(f(x))=sign(s(x))$.
Дальше всё зависит от чётности и нечётности n и d.
Рассмотрим вначале случай $n=2k+1, d=2e, e\ge 5$.
Лемма 3. Пусть $x_d=(0,[(3e-2)/2],[(3e-1)/2])$, то $f(x_d)>0>s(x_d)$.
Пусть $n=2k+1,d=2e+1,e\ge 7, \ x_d=(0,[(3e-1)/2],[3e/2])$
Лемма 4. $f(x_d)>0>s(x_d).
Для чётных n так же существуют решения типа $x_d=(0,...0,d-2,d-2,...d-2)$ здесь d-2 нулнй и d цифр d-2. При $d>10$ $f(x_d)>0>s(x_d)$.

[TOTAL]

Такое впечатление, что самый сильный номер - состоящий из наибольшего числа восьмерок.
Наилучший результат мне удалось получить для 9-значных номеров с пятью восьмерками (для этого случая отношение выигрышей к проигрышам равно 1.10276...). С ростом числа знаков все больше сказывается то, что сумма меньше средней, поэтому отношение падает (или приближается к единице). Например, для $n=1609$, и 905 восьмерками отношение равно 1.004349325. Так что для четного числа разрядов с суммой меньше средней выигрышных, похоже, нет. Для $n=5122$ получается всего 0.9981...

Для желающих поэкспериментировать вот вся программа на Maple для восьмерок
(для других наборов исправления очевидны)

p:=1;
t:=9*p+5;
n:=16*p+9;

b:=expand((x+8*x^2+1)^(t)*(x+9)^(n-t)):

win:=0: los:=0:
for i from 0 by 1 to n-1 do
    win:=win+coeff(b,x,i+1+n):
    los:=los+coeff(b,x,i):
end do:
win; los;

ratio:=evalf(win/los);

[VAL]

worm2 писал(а):

VAL писал(а):

Замечу, однако, что есть номера с суммой 31 и повыгоднее, чем 0006799.

Вроде бы, рекордсмен - 0007888.

Это верно.

[VAL]

TOTAL писал(а):

Такое впечатление, что самый сильный номер - состоящий из наибольшего числа восьмерок.

Видимо это так.
Как и более общеее утверждение Руста о том, что наименьший (по сумме цифр) выигрышный номер в системе счисления с основанием d состоит из нулей и цифр d-2.

Цитата:

Наилучший результат мне удалось получить для 9-значных номеров с пятью восьмерками (для этого случая отношение выигрышей к проигрышам равно 1.10276...). С ростом числа знаков все больше сказывается то, что сумма меньше средней, поэтому отношение падает (или приближается к единице). Например, для $n=1609$, и 905 восьмерками отношение равно 1.004349325. Так что для четного числа разрядов с суммой меньше средней выигрышных, похоже, нет.
Для $n=5122$ получается всего 0.9981...

С другой стороны, если взять n = 16k+2 и номер, состоящий из 9k+1 восьмерок и 7k+1 нулей, то с ростом k отношение выигрышей к проигрышам растет (хотя рост этот ничем, кроме частных примеров не подтвержден).

Представляется очевидным, что оно не может превысить аналогичного отношения для нечетнозначных номеров с суммой [9n/2].

Вполне вероятно,что эти отношения имеют общую асимптоту. Однако я не вижу оснований утверждать, что эта асимптота не превосходит 1.
Как верно отметил Руст, уже для 12-ричной системы счисления есть 22-значные номера с суммой цифр 120 и положительным мат.ожиданием выигрыша. Может быть, 12 не наименьшее основание системы счисления, для которой возможна такая ситуация.

[TOTAL]

VAL писал(а):

С другой стороны, если взять n = 16k+2 и номер, состоящий из 9k+1 восьмерок и 7k+1 нулей, то с ростом k отношение выигрышей к проигрышам растет (хотя рост этот ничем, кроме частных примеров не подтвержден).

Отношение растет потому, что сумма цифр (относительно максимально возможной) тоже растет.
Из-за такого объяснения роста я и не верю, что она превзойдет единицу.
В расчетах получалось, что положительная величина $1-\frac{{WIN}}{{LOS}}$ уменьшается даже менее чем в два раза с удвоением числа разрядов.

Успех для четного числа разрядов для системы счисления с большим основанием тоже объясняется тем, что в этот случае отличие на 1 от половины максимальной суммы является меньшим относительным отличием. Это маленькое относительное отличие достигается на малом числе разрядов, когда ещё срабатывает приёмчик "проиграй на одном разряде много, но выиграй с малым перевесом на нескольких разрядах". С увеличением числа разрядов этот приём быстро перестает играть роль.

[VAL]

Поскольку задачу ММ66 никто, по-видимому, не решает, приведу авторское решение.

ММ66

Двое играют в такую игру:
Каждый игрок очередным своим ходом берет из кучки, содержащей 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,b} множество А устроено периодически. Можно предположить,
что такая же картина наблюбается и для других пар, просто модуль, по которому
возникает период, значительно больше и поэтому его труднее обнаружить.

В самом деле, при $ a=2 $ и $ b \in \{9, 12, 15, 18, 24 \} $ можно
обнаружить и обосновать период. Но, например, для b = 45 этогосделать не удалось,
несмотря на определенные усилия ведущего и участников Математического марафона.

Можно предположить, что успех пар типа {2,45} связан с тем, что период для них огромен,
гораздо более 1000000, и благоприятные для первого игрока числа плотнее расположены
на начальном отрезке периода. Поэтому если не ограничиваться выбором n из первого
миллиона, шансы первого игрока снизятся и не станут превышать ожидаемые 4/5.

Однако, я сомневаюсь в истинности этой гипотезы.
Слишком уж много много паp устойчиво дают значительное пpевышение гpаницы 4/5
для pазных диапазонов n.
Пpи этом, если для pекоpдных паp {2,45} и {2,33} шансы пеpвого игpока сильно меняются
с изменением диапазона n, то для дpугих паp шансы лишь незначительно колеблятся
вокpуг некой отметки, пpевышающей 4/5.
Так, для паpы {2, 27} шансы устойчиво кpутятся у отметки 5/6, удаляясь от нее пpи
больших диапазонах n лишь на доли пpоцента.

[Руст]

Решение было понятно давно. Никому не хотелось повычислять при каких a,b максимальная выгода у первого игрока. Лично я бы пробовал а=2, b=6. Мне кажется (на прикидку без привлечения компьютера) здесь шансов больше чем при ваших. Что касается оценки вручную то я поступил так. Докажем простую лемму. Если $n$ проигрышная позиция для игрока то все позиции $k$, выигрышные для первого игрока дадут выигрышные позиции правее n $n+k$ для первого игрока, т.е. плотность выигрышных позиций для первого игрока не уменьшается. Оценев, что в ближайшем интервале при a=2,b=6 позиции $1,2,4,5,6,7,8$ выигрышны, получаем что этот набор лучше. Конечно лучше вычислить на компьютере. Мне лень.

[VAL]

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

Решение было понятно давно. Никому не хотелось повычислять при каких a,b максимальная выгода у первого игрока. Лично я бы пробовал а=2, b=6. Мне кажется (на прикидку без привлечения компьютера) здесь шансов больше чем при ваших.

Готов без всякого компьютера доказать, что это не так.

Цитата:

Что касается оценки вручную то я поступил так. Докажем простую лемму. Если $n$ проигрышная позиция для игрока то все позиции $k$, выигрышные для первого игрока дадут выигрышные позиции правее n $n+k$ для первого игрока, т.е. плотность выигрышных позиций для первого игрока не уменьшается.

Не совсем понял утверждения леммы.
Но, судя по полученному из не следствию, что-то в ней не так.

Цитата:

Оценев, что в ближайшем интервале при a=2,b=6 позиции $1,2,4,5,6,7,8$ выигрышны, получаем что этот набор лучше.

Можно было добавить еще и 9.
Но это не означает, что пара { 2,6} выгоднее пар, приведенных в моем решении.
На самом деле пара {2, 6} равносильна паре {2,3}.

При n сравнимых с 0 и 3 по модулю 10, побеждает второй игрок, а при остальных n - первый.

Доказательство.
1. Если n сравнимо 0 или 3 по модулю 10, то ни $ n-2^k $ ни $ n-6^k $ не лежат в этих классах при при каком k.
2. Для каждого n, не сравнимого ни с 0, ни с 3, найдется степень 2 или 6, вычитая которую из n, получим число, сравнимое с 3 или 0.

[juna]

Можно еще предложить немного изменить условие предыдущей задачи.
Печатают только банкноты с лексикографически упорядоченными номерами, т.е. если номер банкноты $a_1,a_2,...,a_n$, то $a_1\le a_2\le ...\le a_n$. Задача такая же.
Возможна ли здесь TOTAL-свертка ?
Расчеты показывают, что парадокса здесь не получается.
Вот некоторые факты
для 7 разрядов:
сумма цифр 29 номер с минимальным проигрышем 2345555 с шансами 2500 из 6436
сумма цифр 30 номер с минимальным проигрышем 2344449 с шансами 2737 из 6436
сумма цифр 31 номер с минимальным проигрышем 3344449 с шансами 2999 из 6436
сумма цифр 32 номер с максимальным выигрышем 3444449 с шансами 3310 из 6436
сумма цифр 33 номер с максимальным выигрышем 1116789 с шансами 3566 из 6436
и т.д.
Здесь начинаем выигрывать при сумме цифр 32
----------------------------------------------------
для 5 разрядов:
сумма цифр 22 номер с минимальным проигрышем 34555 с шансами 601 из 1288
сумма цифр 23 номер с максимальным выигрышем 24449 с шансами 655 из 1288
-----------------------------------------------------
для 6 разрядов:
сумма цифр 26 номер с минимальным проигрышем 33555 с шансами 1357 из 3004
сумма цифр 27 номер с максимальным выигрышем 111789 с шансами 1556 из 3004

Вырисовывается закономерность - при нечетном количестве разрядов минимальный номер с максимальным выигрышем выглядит примерно так ..44444..49, при четном 111...6789 (интересно, что будет при количестве разрядов больше десяти? )

[Руст]

juna писал(а):

Можно еще предложить немного изменить условие предыдущей задачи.
Печатают только банкноты с лексикографически упорядоченными номерами, т.е. если номер банкноты $a_1,a_2,...,a_n$, то $a_1\le a_2\le ...\le a_n$. Задача такая

В самом начале я уже говорил, что количество выигранных и проигранных позиций не зависит от перестановки цифр. Поэтому было предложено рассмотреть только монотонно не убывающие последовательности.
Ещё одно замечание к этой задаче: Легко доказать, что и при троичной системе счёта банктнота с номером $s(n)<0$ удовлетворяет условию $f(n)<0$, т.е не возникает ситуации $f(n)s(n)<0$ (о чём спрашивается).

[juna]

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

В самом начале я уже говорил, что количество выигранных и проигранных позиций не зависит от перестановки цифр.

Т.е.,по-вашему, конечные результаты для этой переформулировки должны совпасть с предыдущей задачей?
Так ведь не совпадают...

[Руст]

juna писал(а):

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

В самом начале я уже говорил, что количество выигранных и проигранных позиций не зависит от перестановки цифр.

Т.е. по-вашему конечные результаты для этой переформулировки должны совпасть с предыдущей задачей?
Так ведь не совпадают...

Конечно разные, так как разные множество номеров. Я говорил только о независимости от перестановки выигранных и проигранных позиций из множества всех номеров в d- ичном исчислении.
Менять множество номеров на другое мне кажется не так интересно.
Более интересно доисследовать следующие вопросы.
1. Разобраться с тем почему ответы зависят от чётности и нечётности базы системы исчисления d и количества цифр n.
2. Доказать, что если при заданном n если существует число х в d-ичном исчислении со свойством $f(x)s(x)<0$ то существует и в d+2 ичном исчислении (аналог того, что при фиксированном d если существует n-значный х удовлетворяющий указанному неравенству, то существует и n+2 значное число с этим свойством).
3. Начиная с d=4 найти минимальные чётные и нечётные n, когда существует такие числа.
4. Начиная с n=3 найти минимальные чётные и нечётные значения d, когда существуют числа с указанными свойствами.
При заданном d>=3 найти минимальное количество n, такое что среди n-значных