В. Болтянский
Часто ли степени двойки начинаются с единицы?



Постановка задачи

Среди степеней двойки вновь и вновь встречаются числа, начинающиеся с единицы. Как часто они встречаются? Иными словами, какова вероятность того, что произвольно взятая степень двойки начинается цифрой 1?

Уточним постановку задачи. Среди выписанных (см. заставку) пятнадцати чисел четыре начинаются с единицы. Напишем эти числа на пятнадцати карточках, перетасуем их и выберем наудачу одну карточку. Вероятность того, что на ней будет число, начинающееся цифрой 1, равна 4/15 (рис. 1).


Рис. 1

Возьмём теперь n первых степеней двойки, т.е. числа 21, 22, ..., 2n; пусть среди них аn чисел начинаются (в десятичной записи) с единицы. Тогда вероятность того, что число, наудачу выбранное из чисел 21, 22, ..., 2n, начинается цифрой 1, равна an/n. Эта вероятность зависит от n, т.е. от того, сколько первых степеней двойки было взято. Предел

 p1 =  lim   an

 n

 ,
n → ∞
(1)

(если он существует) и называется вероятностью того, что произвольно взятая степень двойки начинается цифрой 1.


 Задачи 
1.

Какова вероятность того, что произвольно взятое натуральное число делится на 3?

2.

Какова вероятность того, что произвольно взятая цифра десятичного разложения числа 161/222 является пятеркой? Двойкой?

3.

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


Вычисление предела (1)

Среди двузначных чисел, являющихся степенями двойки, ровно одно (а именно, 16) начинается с единицы. Среди трёхзначных степеней двойки тоже ровно одно число (а именно, 128) начинается с единицы. То же верно для четырёхзначных степеней двойки.

Вообще, при k>1 среди k-значных чисел, являющихся степенями двойки, имеется ровно одно, начинающееся цифрой 1. В самом деле, наименьшее k-значное число, являющееся степенью двойки, обязательно начинается с единицы (иначе, разделив на 2, мы получили бы, что и предыдущая степень двойки является k-значным числом). Другого же числа, начинающегося цифрой 1, среди k-значных степеней двойки нет: следующая степень двойки будет иметь на первом месте цифру 2 или 3, следующая — ещё большую цифру, пока мы не получим k+1-значное число.

Из сказанного следует, что если число 2n является m-значным, то среди чисел 21, 22, ..., 2n имеется ровно m–1 чисел, начинающихся с единицы, т.е. an = m–1. Но утверждение «число 2n является m-значным» означает, что

10m–1 ≤ 2n < 10m,

то есть

m–1 ≤ n lg 2 < m.

Вспоминая, что an = m–1, получаем

lg 2 –  1

 n 

 <   a

 n 

 ≤ lg 2,

и, следовательно,

 p1 =  lim   an

 n

 = lg 2 = 0,30103...
n → ∞

Итак, чуть больше 30% степеней двойки начинаются с единицы.


 Задачи 
4.

Обозначим через pq вероятность того, что произвольно взятая степень двойки начинается цифрой q *. Докажите равенства

p2 + p3 = p1,   p4 + p5 = p2,
p6 + p7 = p3,   p8 + p9 = p4.
 
5.

Докажите, что p4 = 1 – 3·lg 2 = 0,096... Как видите, степени двойки начинаются цифрой 4 в три с лишним раза реже, чем цифрой 1 (рис. 2).


Рис. 2

Общая задача

А какова вероятность того, что произвольно взятая степень данного натурального числа l начинается (в десятичной записи) цифрой q?

Пусть число ln начинается в десятичной записи цифрой q, т.е.

q·10mln < (q+1)·10m,

где m — некоторое натуральное число. Разделив эти неравенства на q·10m и прологарифмировав по основанию 10, получим:

0 ≤ (n lg l – lg q) – m < lg   q+1 

q

 = lg  ( 1 +   1 

 q

)  ,
(2)

Так как число, стоящее справа, меньше единицы (1 + 1/q ≤ 2 < 10), то неравенства (2) означают, что дробная часть числа  n lg l – lg q  меньше lg (1+1/q) (напомним, что дробной частью числа x называется разность между числом x и его целой частью: {x} = x – [x], а целая часть x — это наибольшее целое число, которое не превосходит x). Обратно, если дробная часть числа  n lg l – lg q  меньше lg (1+1/q), т.е. если при некотором натуральном m выполнены неравенства (2), то ln начинается в десятичной записи цифрой q. Таким образом, поставленная задача эквивалентна следующей: какова вероятность того, что для произвольно взятого натурального числа n

{n lg l – lg q} < lg  ( 1 +   1 

 q

)  ?

Решить эту последнюю задачу нам поможет

Теорема о дробных частях. Пусть α, β — действительные числа, причём число α — иррациональное, и I — некоторый промежуток длины h, содержащийся в отрезке [0, 1]. Рассмотрим бесконечную последовательность α+β, 2α+β, ..., nα+β, ... Вероятность того, что произвольно взятое число этой последовательности имеет дробную часть, принадлежащую промежутку I, равна h.

Доказательство этой теоремы мы приведём в конце статьи, а сейчас покажем, как она применяется к решению нашей задачи.

Прежде всего заметим, что если l является степенью десяти, то все степени числа l начинаются цифрой 1, т.е. в этом случае задача тривиальна.

Если же l не является степенью десяти, то число  α = lg l  иррационально. По теореме о дробных частях вероятность того, что произвольно взятое число из последовательности  n lg l – lg q  (n = 1, 2, ...) имеет дробную часть, принадлежащую промежутку [0, lg (1+1/q)[ равна lg (1+1/q). Это и даёт решение рассмотренной выше задачи: вероятность того, что произвольно взятая степень натурального числа l (не являющегося степенью десяти) начинается цифрой q, равна lg (1+1/q).

Обратите внимание на то, что эта вероятность не зависит от l! Например, степени двойки и степени тройки одинаково часто (а именно, с вероятностью lg 2) начинаются цифрой 1.


 Задачи 
6.

Докажите, что если натуральное число l не является степенью десяти, то число lg l иррационально.

7.

Вычислите вероятности p2, ..., p9, указанные в задаче 4. Дайте новое доказательство содержащихся там равенств.

8.

Какова вероятность того, что произвольно взятая степень двойки начинается комбинацией цифр 1000 (рис. 3)?


Рис. 3
9.

Какова вероятность того, что произвольно взятая степень числа l (не являющегося степенью десяти) начинается комбинацией цифр q1q2...qr (где q1 ≠ 0)? Выведите отсюда, что степени числа l могут начинаться любой комбинацией цифр q1q2...qr (q1 ≠ 0).

10.

Докажите следующие утверждения:

а) Вероятность того, что у произвольно взятой степени числа l, не являющегося степенью десяти, вторая слева цифра есть 0, равна

 p0(2) = lg (11·21·31·...91) – lg (9!) – 9.

Указание: p0(2) есть сумма вероятностей того, что произвольная степень числа l начинается комбинациями 10, 20, ..., 90.

б) Вероятность того, что у произвольно взятой степени числа l, не являющегося степенью десяти, k слева цифра есть q (где k>1, q=0, 1, ..., 9), равна:
10k–1–1
 pq(k) = Σ  lg  ( 1 +  1

 10i + q

)  .
i=10k–2

11.

Используя результат задачи 10 б), докажите, что

 lim   pq(k) 1

10

 .
k → ∞

Таким образом, при достаточно большом k каждая из вероятностей p0(k), p1(k), ..., p9(k) как угодно мало отличается от 1/10.

Указание: докажите, что для натурального логарифма верно следующее неравенство: ln (1+x) < x при x>0; затем воспользуйтесь соотношениями:

lg  ( 1 +  1

 10i 

)  – lg  ( 1 +  1

 10i + q

)  <
< lg  ( 1 +  q

 100i(i – 1) 

)  =  1

ln 10

  ln  ( 1 +  q

 100i(i – 1) 

)  <
1

ln 10

 ·  q

 100i(i – 1) 

 =  q

100 ln 10

 ( 1

 i – 1 

 –  1

 i 

)  .

12.

Обобщите результаты задач 9 и 10 б) на случай, когда степени числа l записываются в системе счисления с основанием b>1. В частности, для двоичной системы счисления формулы задачи 10 б) принимают следующий вид:

 p0(k) = log 2  ( 2k–1 + 1

2k–1

 ·  2k–1 + 3

2k–1 + 2

 · ... ·  2k – 1

2k – 2

)  .
 p1(k) = log 2  ( 2k–1 + 2

2k–1 + 1

 ·  2k–1 + 4

2k–1 + 3

 · ... ·  2k

2k – 1

)  .

Ещё одна задача

В качестве ещё одного примера применения теоремы о дробных частях рассмотрим следующую задачу: число α иррационально; нужно доказать, что существует натуральное n, для которого  cos nαπ > 0,999.

Заметим, что неравенство  cos nαπ > 0,999  равносильно следующим:

2mπ – arccos 0,999 < nαπ < 2mπ + arccos 0,999

(при некотором целом m), т.е.

 m α

2

 n 1

 arccos 0,999 < m 1

π

 arccos 0,999.

Иными словами, неравенство  cos nαπ > 0,999  выполняется в том и только в том случае, если число {(α/2)·n + (1/π)·arccos 0,999} принадлежит промежутку [0, (1/π)·arccos 0,999]. По теореме о дробных частях произвольно выбранное натуральное n удовлетворяет этому условию с вероятностью (1/π)·arccos 0,999 » 0,014. Таким образом, если N достаточно велико, то примерно 1,4% чисел 1, 2, ..., N удовлетворяют поставленному требованию.


 Задачи 
13.

От произвольной точки, окружности радиуса 1 откладываются друг за другом дуги длины 1. Обозначим через A1, A2, ..., An, ... последовательные концы откладываемых дуг. Докажите, что, какова бы ни была дуга Q этой окружности, найдется точка Ai Î Q (рис. 4).


Рис. 4
14.

Докажите, что если α иррационально, то функция cos x + cos αx не является периодической.

15.

Даны две бесконечные арифметические прогрессии:

a1 + d1, a1 + 2d1, a1 + 3d1, ...;
a2 + d2, a2 + 2d2, a2 + 3d2, ...;
 

причем числа d1 и d2 положительны, и отношение d1/d2 иррационально. Найдется ли такой член первой прогрессии и такой член второй прогрессии, что модуль их разности меньше 0,000001?

16.

Лесом радиуса ε назовем объединение всех кругов радиуса ε, центрами которых служат точки с целочисленными координатами. Докажите, что если прямая образует с осью абсцисс угол φ, тангенс которого иррационален, то она обязательно пересекает лес (как бы ни было мало ε; рис. 5).


Рис. 5

Доказательство теоремы

Перейдём теперь к доказательству теоремы о дробных частях.

Возьмём произвольное натуральное число r. Точки 1/r, 2/r, ..., (r–1)/r разбивают отрезок [0, 1] на r отрезков длины 1/r. Назовём эти отрезки «клетками», а дробные части чисел α, 2α, ..., (r+1 назовём «зайцами» **. Так как «клеток» r, а «зайцев» r+1, то найдутся два «зайца», попавшие в одну клетку, т.е. найдутся такие натуральные p' и p'' (p' > p''), что дробные части чисел p'α и p''α отличаются менее чем на 1/r. Значит, |(p'α – p''α) – m| < 1/r при некотором целом m. Положив p = p'p'', мы можем написать: pα – m| = ε, где ε < 1/r. Заметим, что ε≠0, так как α иррационально. Обозначим через s наименьшее натуральное число, превосходящее 1/ε, т.е. s–1 ≤ 1/ε < s.

Рассмотрим s последовательных членов арифметической прогрессии с разностью  pα:

γ + pα,   γ + 2pα,   ...   γ + spα, (3)

где γ — некоторое действительное число. Обозначим дробные части чисел (3) через x1, x2, ..., xs. В силу равенства pα – m| = ε числа x1, x2, ..., xs отстоят друг от друга на ε (рис. 6). В силу неравенств 1/s < ε ≤ 1/(s–1) расстояние между x1 и xs на рисунке 6 б меньше ε. Из сказанного вытекает, что число точек x1, x2, ..., xs, попадающих на отрезок I длины h, заключено между числами h/ε – 1 и h/ε + 2, т.е. между sh – 2 и sh + 2 (заметим, что h<1).



Рис. 6

Рис. 7

Возьмем теперь ps последовательных членов b1, b2, ..., bps какой-либо арифметической прогрессии с разностью α (т.е. bi+1 = bi + α). Расположим их в виде таблицы, изображённой на рисунке 7. Очевидно, что каждая строка этой таблицы представляет собой прогрессию вида (3). Так как число строк равно p, то количество тех членов рассматриваемой прогрессии b1, b2, ..., bps, дробные части которых попадают в промежуток I, заключено между числами p(sh – 2) и p(sh + 2).

Пусть, наконец, n — произвольное натуральное число, большее rps. Разделив n на ps с остатком, получим n = lps + q, где lr, 0≤q<ps. Следовательно, из чисел α+β, 2α+β, ..., nα+β можно взять l раз по ps последовательных членов арифметической прогрессии с разностью α, и ещё останется q чисел. Поэтому

lp(sh – 2) ≤ anlp(sh + 2) + q,

где an — количество тех чисел α+β, 2α+β, ..., nα+β, дробные части которых попадают в промежуток I. Это неравенство можно переписать в виде

(nq)h – 2lpan ≤ (nq)h + 2lp + q,

откуда (в силу соотношений 0≤h<1, q<ps) получаем

nh – 2lppsannh + 2lp + ps,

т.е.

  an

n

 – h  ≤  2lp + ps

n

 ≤  2lp + ps

lps

 =  2

s

 +  1

l

 <  3

r


(поскольку lr и 1/s<ε<1/r). Итак, существует такое натуральное N (а именно, N=rps), что при n>N выполнено неравенство

  an

n

 – h  <  3

r

 .

Ввиду произвольности натурального числа r, отсюда следует, что

 lim   an

 n

 = h.
n → ∞


 Задачи 
17.

Докажите следующее «двумерное» обобщение теоремы о дробных частях. Пусть на плоскости фиксирована система координат. Дробной частью вектора a с координатами xy будем называть вектор, координатами которого являются дробные части чисел x и y (рис. 8). Пусть M — некоторый многоугольник, содержащийся в квадрате с вершинами (0; 0), (0; 1), (1; 0), (1; 1). Будем говорить, что некоторый вектор b попадает в M, если b = OB, где O — начало координат, а BÎM. Пусть α, β — произвольные векторы на плоскости, причём координаты x0y0 вектора α и число x0/y0 иррациональны. Рассмотрим бесконечную последовательность векторов α+β, 2α+β, ..., nα+β, ... Вероятность того, что произвольно взятый вектор этой последовательности имеет дробную часть, попадающую в многоугольник M, равна площади S(M) этого многоугольника ***.



Рис. 8

Рис. 9

18.

По бесконечной шахматной доске с полями в виде квадратов со стороной 1 прыгает блоха, перемещаясь за каждый прыжок на x0 влево и на y0 вверх (рис. 9). Докажите, что, если числа x0, y0 и x0/y0 иррациональны, то блоха обязательно попадёт когда-нибудь на чёрное поле.

19.

Числа λ1, λ2 и λ12 иррациональны. Докажите, что система неравенств
ì  sin nλ1 > 0,999999,
í
î  sin nλ2 > 0,999999

имеет натуральное решение n.


ПРИМЕЧАНИЯ
*

Существование чисел pq вытекает из дальнейшего. назад к тексту

**

Эта терминология связана с принципом Дирихле («Квант», 1977, № 2, с. 17). Теорему о дробных частях можно назвать «принципом Дирихле для бесконечного числа зайцев». назад к тексту

***

Аналогичное обобщение справедливо также для n-мерного пространства (вектор α должен обладать тем свойством, что все его координаты иррациональны и ни одна из них не представляется в виде линейной комбинации остальных координат с рациональными коэффициентами). назад к тексту



Добавлю ещё задачу аналогичной тематики, которая была опубликована в Задачнике «Кванта». E.G.A.


 М501.  Выберем из последовательности степеней тройки 3, 9, 27, 81, 243, 729, 2187, 6561, ... все числа, начинающиеся с цифры 9; пусть эти числа (по порядку) 3 f (1), 3 f (2), 3 f (3), ... (в частности,  f (1) = 2, так как первое из таких чисел 32 = 9).

а) Найдите  f (2) и  f (3) — номера второго и третьего такого числа.

б) Докажите, что таких чисел бесконечно много.

в) Докажите, что  f (n) при n > 1 удовлетворяет условиям:

f (n) – n нечётно;(1)
 f (n) –  n – lg 9

 1 – lg 9 

   < 1,
(2)

и определяется этими условиями однозначно.

Решение.

Докажем сначала такое утверждение: для любого k>1 существуют две или три k-значные степени тройки, причём в том и только в том случае, когда их три, одна из них начинается цифрой 9 (если последовательность степеней тройки дополнить числом 30 = 1, то это утверждение будет верно и при k=1). Пусть 3mнаименьшая k-значная степень тройки; тогда 10k–1 ≤ 3m < 3·10k–1. Отсюда 3·10k–1 ≤ 3m+1 < 9·10k–1, то есть 3m+1k-значное число, не начинающееся с девятки. Далее, 9·10k–1 ≤ 3m+2, то есть если 3m+2k-значное число, то оно обязательно начинается цифрой 9. (В любом случае, 3m+3 ≥ 27·10k–1 — не k-значное число.)

Пусть теперь 3 f (n)k-значная степень тройки, начинающаяся с девятки, то есть

9·10k–1 < 3 f (n) < 10k (*)

(оба неравенства строгие, поскольку 3 f (n) — число нечётное). Подсчитаем двумя способами количество степеней тройки, меньших С одной стороны, кроме тех n–1 степеней, которые начинаются цифрой 9, есть ещё ровно две l-значные степени тройки для каждого l = 1, 2, ..., k, то есть их всего 2k + (n – 1) штук. С другой стороны, количество степеней тройки, меньших 3 f (n), равно  f (n): это числа 30, 31, ..., 3 f (n)–1. Значит, 2k + (n – 1) = f (n), откуда

k  f (n) – n + 1

2

 .
(**)

Поскольку k — натуральное, из этого следует, что  f (n)–n — нечётное число. Условие (1) пункта в) доказано.

Из (*) и (**) имеем
 f (n)–n–1

2

 f (n)  f (n)–n+1

2

9·10   < 3   < 10 ,
(***)

или

lg 9 +   f (n) – n – 1

2

 < f (n) lg 3 <   f (n) – n + 1

2

 .

Выполнив несколько равносильных преобразований, получим

2 lg 9 + f (n) – n – 1 < f (n) lg 9 < f (n) – n + 1,

lg 9 – 1 < f (n) lg 9 – f (n) – lg 9 + n < 1 – lg 9,

то есть

–(1 – lg 9) < –(1 – lg 9) f (n) + (n – lg 9) < 1 – lg 9,

и поскольку 1 – lg 9 > 0, имеем

–1 < – f (n) +  n – lg 9

 1 – lg 9 

 < 1,

то есть

 f (n) –  n – lg 9

 1 – lg 9 

   < 1,

— условие (2) пункта в) задачи.

Число

n – lg 9

 1 – lg 9 

 = n – 1

 1 – lg 9 

 + 1

иррациональное (n>1 и lg 9 иррационально). Поэтому при любом n>1 условию (2) удовлетворяют ровно два последовательных натуральных числа; одно из них чётно, другое нечётно. Но так как для каждого n чётность  f(n) известна (разность  f (n)–n нечётна), то при каждом n число  f (n) определяется однозначно. Остаётся доказать, что для  f (n), определённого условиями (1) и (2), степень тройки 3 f (n) действительно начинается с цифры 9 (все условия на  f (n) мы получили в предположении, что  f (n) существует). Проведя выполненные выше преобразования в обратном порядке, из условия (2) легко получим (***), то есть 3 f (n) в самом деле начинается с девятки.

Теперь уже нетрудно найти  f (2) и  f (3):

 f (2) = 23,        f (3) = 44.

Наконец, поскольку  f (n) определено для всех натуральных n, получаем, что степеней тройки, начинающихся цифрой 9, бесконечно много.

Замечание. Из неравенства (2) в условии задачи следует, что величина  f (n) растёт примерно как n/(1 – lg 9). Этот результат можно вывести из того факта, что при больших значениях N среди N первых степеней тройки количество степеней, начинающихся цифрой 9, примерно равно (1 – lg 9)N (см. рис.; тут совершенно неважно, рассматриваем ли мы степени двойки, тройки или другого числа α с иррациональным lg α; см. статью В. Болтянского). В самом деле, если  f (n) = N, то среди чисел 31, 32, ..., 3N ровно n » (1 – lg 9)N начинаются с 9; поэтому  f (n) » n/(1 – lg 9). Результат задачи М501 позволяет найти точное значение  f (n) для любого n.

Э. Туркевич

Круг разбит на девять секторов: 1, 2, ..., 9, показывающих, какую долю (в пределе при N→∞) среди чисел α, α2, ..., αn составляют те, которые начинаются цифрой 1, 2, ..., 9 соответственно.


Hosted by uCoz