|
6AKJIAH
|
|
прапор
|
|
|
|
|
|
|
Рег.: 06.01.2005
|
|
Сообщений: 126
|
|
Из: Китай.
|
|
Рейтинг: 45
|
|
Первые цифры числа 2^n
08.01.2006 22:37
|
|
|
Довольно интересная и известная задача. Дана последовательность первых цифр числа 2^n, надо исследовать статистику этих цифр. В частности ответить на вопрос встречается ли в этой последовательности цифра 7? и что встречается чаще 7 или 8? (Арнольд). Как вы думаете можно ли на экзамене за минут сорок эту задачу расколоть, учитывая что максиму до чего вы можете догадаться, следуя логики курса , что этой задачи можно сопоставить датчик случайных чисел.
|
|
|
Grue
|
|
Praise Lord Smooze
|
|
|
|
|
|
|
Рег.: 12.09.2005
|
|
Сообщений: 2977
|
|
Из: Юго Западная
|
|
Рейтинг: 869
|
|
Re: Первые цифры числа 2^n
[re: 6AKJIAH]
08.01.2006 23:31
|
|
|
Чем больше цифра, тем меньше встречается - это факт
|
BOUNCING BABY BUNNIES BURNING BRIGHT |
|
|
6AKJIAH
|
|
прапор
|
|
|
|
|
|
|
Рег.: 06.01.2005
|
|
Сообщений: 126
|
|
Из: Китай.
|
|
Рейтинг: 45
|
|
Re: Первые цифры числа 2^n
[re: Grue]
08.01.2006 23:37
|
|
|
Да, да а вот доказать сам бы смог?
|
|
|
Krasin
|
|
|
|
|
|
|
|
|
Рег.: 23.06.2004
|
|
Сообщений: 7039
|
|
Из: Калифорния
|
|
Рейтинг: 3386
|
|
Re: Первые цифры числа 2^n
[re: 6AKJIAH]
08.01.2006 23:51
|
|
|
До решения этой задачи догадается меньше половины (если, конечно, исключить из рассмотрения диффузию решений). Задача экзамена не выявить самых крутых, а проверить то, как масса закрепила материал, т.е. данная задача совершенно не для экзамена (если, конечно в курсе не решалось очень похожих задач).
|
|
|
|
Re: Первые цифры числа 2^n
[re: 6AKJIAH]
09.01.2006 00:18
|
|
|
если у тебя есьт точная постановка зачади, попробуй у гугла спросить - авось она где-то висит...
|
|
|
Symmetry
|
|
|
|
|
|
|
|
|
Рег.: 25.10.2005
|
|
Сообщений: 73
|
|
|
|
Рейтинг: 0
|
|
Re: Первые цифры числа 2^n
[re: 6AKJIAH]
09.01.2006 00:20
|
|
|
Я не силен в тервере, но могу решить задачу с некоторыми предположениями.
1. Если вторую цифру числа считать случайной величиной, равномерно распределенной и независимой от предыдущих значений второй цифры.
2. Если при больших n вероятности того, что значения будут 1, ..., 9 есть p1, ..., p9
стабилизируются и от n не зависят, то:
Поскольку если у нас на n-том шаге первые цифры были XY, то на n+1 первая цифра будет Z
10-14=>2
15-19=>3
20-24=>4
25-29=>5
30-34=>6
35-39=>7
40-44=>8
45-49=>9
50-99=>1
На шаге n
вероятности того, что первая цифра
(1, 2, ..., 9) равны соответственно (p1, ..., p9)
Тогда на n+1 шаге вероятности будут
(p1/2, p1/2, p2/2, p2/2, p3/2, p3/2, p4/2, p4/2, p5+p6+p7+p8+p9)
и в то же время останутся прежними. Если считать p1 = x
то p2=p3=x/2; p4=p5=p6=p7=x/4; p8=p9=x/8
Из того, что p1+...+p9=1 получаем 13/4 x = 1
x = 4/13
Итого:
вероятность 1 равна 4/13
вероятность 2,3 равна 2/13
вероятность 4,5,6,7 равна 1/13
вероятность 8,9 равна 1/26
Если это правильное решение, то я решил за 7 минут.
|
|
|
Krasin
|
|
|
|
|
|
|
|
|
Рег.: 23.06.2004
|
|
Сообщений: 7039
|
|
Из: Калифорния
|
|
Рейтинг: 3386
|
|
|
В ответ на:
1. Если вторую цифру числа считать случайной величиной, равномерно распределенной и независимой от предыдущих значений второй цифры.
Предположение является неочевидным фактом. При решении основной задачи, его надо будет доказывать экзаменуемым.
|
|
|
Symmetry
|
|
|
|
|
|
|
|
|
Рег.: 25.10.2005
|
|
Сообщений: 73
|
|
|
|
Рейтинг: 0
|
|
Re: Первые цифры числа 2^n
[re: Krasin]
09.01.2006 00:38
|
|
|
|
|
|
Rott
|
|
|
|
|
|
|
|
|
Рег.: 07.09.2005
|
|
Сообщений: 4403
|
|
|
|
Рейтинг: 2885
|
|
Re: Первые цифры числа 2^n
[re: Krasin]
09.01.2006 05:06
|
|
|
Пусть N - некоторое число (степень двойки). Возьмем десятичный логарифм этого числа, и построим отображение на круг этих чисел. Возьмем дробную часть (то есть остаток от деления на единицу). Очевидно, что первый разряд в десятичной записи будет определяться однозначно по этому остатку. Отобразим (линейно) этот отрезок на круг. Тогда последовательность из степеней двоек будет отображаться на круг в виде последовательности точек, отстающих друг на друга на один и тот же угол, при этом - этот угол будет иррационален относительно 2pi (полного угла окружности). В ТЧ (а может и в матане) где-то по этому поводу доказывалась какая-то теорема/лемма, что такие точки будут равномерно покрывать всю окружность. Из чего следует, что плотность распределения будет пропорциональна длинам соответствующих сегментов, и величина эта легко вычисляется.
Я не помню, в каком курсе и как доказывалось утверждение о распределении, хотя интуитивно оно очевидно. Задача, конечно, немного олимпиадного стиля, хотя для курса, где в качестве вопроса присутствовал воспрос про такую лемму/теорему (если присутствовал) - imho вполне адекватна, по крайней мере если она давалась бы тому, у кого про эту лемму/теорему что-либо спрашивали.
|
|
Список
Плоский
Дерево
