2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5  След.
 
 
Сообщение11.07.2008, 21:57 
Заслуженный участник


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

 Профиль  
                  
 
 
Сообщение11.07.2008, 22:25 
Заслуженный участник


27/06/08
4058
Волгоград
Руст писал(а):
Суммируя получаем $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] и положительным мат. ожиданием выигрыша?

 Профиль  
                  
 
 
Сообщение12.07.2008, 08:18 
Заслуженный участник
Аватара пользователя


01/08/06
3049
Уфа
VAL писал(а):
Замечу, однако, что есть номера с суммой 31 и повыгоднее, чем 0006799.

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

 Профиль  
                  
 
 
Сообщение12.07.2008, 09:40 
Заслуженный участник


09/02/06
4382
Москва
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)$.

 Профиль  
                  
 
 
Сообщение12.07.2008, 13:46 
Заслуженный участник
Аватара пользователя


23/08/07
5419
Нов-ск
Такое впечатление, что самый сильный номер - состоящий из наибольшего числа восьмерок.
Наилучший результат мне удалось получить для 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);

 Профиль  
                  
 
 
Сообщение12.07.2008, 21:19 
Заслуженный участник


27/06/08
4058
Волгоград
worm2 писал(а):
VAL писал(а):
Замечу, однако, что есть номера с суммой 31 и повыгоднее, чем 0006799.

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


Это верно.

 Профиль  
                  
 
 
Сообщение13.07.2008, 09:07 
Заслуженный участник


27/06/08
4058
Волгоград
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 не наименьшее основание системы счисления, для которой возможна такая ситуация.

 Профиль  
                  
 
 
Сообщение13.07.2008, 09:28 
Заслуженный участник
Аватара пользователя


23/08/07
5419
Нов-ск
VAL писал(а):
С другой стороны, если взять n = 16k+2 и номер, состоящий из 9k+1 восьмерок и 7k+1 нулей, то с ростом k отношение выигрышей к проигрышам растет (хотя рост этот ничем, кроме частных примеров не подтвержден).
Отношение растет потому, что сумма цифр (относительно максимально возможной) тоже растет.
Из-за такого объяснения роста я и не верю, что она превзойдет единицу.
В расчетах получалось, что положительная величина $1-\frac{{WIN}}{{LOS}}$ уменьшается даже менее чем в два раза с удвоением числа разрядов.

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

 Профиль  
                  
 
 
Сообщение13.07.2008, 17:35 
Заслуженный участник


27/06/08
4058
Волгоград
Поскольку задачу ММ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оцента.

 Профиль  
                  
 
 
Сообщение13.07.2008, 18:24 
Заслуженный участник


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

 Профиль  
                  
 
 
Сообщение13.07.2008, 19:29 
Заслуженный участник


27/06/08
4058
Волгоград
Руст писал(а):
Решение было понятно давно. Никому не хотелось повычислять при каких 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.

 Профиль  
                  
 
 
Сообщение13.07.2008, 19:34 
Заслуженный участник
Аватара пользователя


07/03/06
1898
Москва
Можно еще предложить немного изменить условие предыдущей задачи.
Печатают только банкноты с лексикографически упорядоченными номерами, т.е. если номер банкноты $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 (интересно, что будет при количестве разрядов больше десяти? )

 Профиль  
                  
 
 
Сообщение13.07.2008, 19:53 
Заслуженный участник


09/02/06
4382
Москва
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$ (о чём спрашивается).

 Профиль  
                  
 
 
Сообщение13.07.2008, 20:08 
Заслуженный участник
Аватара пользователя


07/03/06
1898
Москва
Руст писал(а):
В самом начале я уже говорил, что количество выигранных и проигранных позиций не зависит от перестановки цифр.

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

 Профиль  
                  
 
 
Сообщение13.07.2008, 20:30 
Заслуженный участник


09/02/06
4382
Москва
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-значных

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 62 ]  На страницу Пред.  1, 2, 3, 4, 5  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group