О вероятностях и «хороших» числах

35

О вероятностях и «хороших» числах

Г. А. Гуревич, Ж. М. Раббом

В «Кванте» публикуется много различных задач по математике. В письмах, прихождения в редакцию, часто задается вопрос: «Как придумывают задачи?» Наша заметка адресована прежде всего тем читателем, которые волнует этот вопрос.

Несмотря на каждийся «элементарный» характер многих интересных задач, большинство из них — переформулировки содержательных математических фактов. К сожалению, многие школьники часто, даже решив ту или иную задачу, и не подозревают об идеях, из которых она возникла.

Цель этой заметки — рассказать немного о теории вероятности, с которой связана задача M204 «Задачника», Кванта‘’, и дать простое решение этой задачи.

Сначала мы напомним условия задачи M204.

Назовем намуральное число «хорошим», если в его десятичной записи встречаются подряд цифры 1, 9, 7, 3, и «плохим» в промисном случае. Доказим, что существует такое намуральное число n, что среди всех n-значных чисел больше «хороших», чем «плохим».

Неколько примеров

Мы начнем с рассмотрения нескольких примеров, которые на первый взгляд никак не связаны с нашей задачей.

Пример 1. Предположим, что мы подбросили монету. Если она без изъянов, то мы с одинаковой увеличностью можно ожидать как то, что она упадет вверх «орлом», так и то, что сверху окажется «решка». Кроме того, интуция нам подсказывает, что если мы подбросим монету два раза, то наша увеличность в том, что хотя бы один из этих двух раз выпадает «орел», будет горздо больше, чем в том, что она раз выпадает «решка». И уж, наверное, все согласятся с тем, что если подбросить монету 100 раз, то почти наверняка хотя бы один раз выпадает «орел», или, другими словами, маловероятно, что все 100 раз выпадает «решка».

Пример 2. В ящиком помещили 10 красных и 2 черных шара. Если научад вынуть какой-нибудь шар из ящика, то им почти наверняка оказется красный, так как красных шаров намного больше, чем черных. Но если многоократно (скажем, это раз) повторить этот опит, каждый раз восстановливая «исходное положение», то есть возврашая вынутый шар на место и тщательно перемешивая содержимое ящика, то можно с увеличностью сказать, что рано или поздно мы вытащим черный шар.

Пример 3. Возьмем 10 000 карточек и выпишем на них все натуральные числа от 0 до 9999 (на каждой карточке одно число). Если на карточке написано однозначное, двухначное или трехзначное число, то мы припишем к нему слева соответственно три, два или один нуль. Таким образом, все выписанные на карточках числа станут четырехзначными. Сложим все карточки в пачку и тщательно перемешаем. Будем теперь производить следующий опит.

37

тарное), оно состоит из двух элементарных: «извлечение черного шара № 1» и «извлечение черного шара № 2».

В примере 3 извлечение какой-то карточки — элементарное событие. Всего здесь элементарных событий — 10 000. А вот извлечение карточки, на котором написано «истинно», четырехзначное число (то есть число, у которого первая цифра слева — не нуль) — событие, состоящее из 9000 элементарных: «извлечение карточки с числом 1000», «извлечение карточки с числом 1001», «извлечение карточки с числом 1002», …, «извлечение карточки с числом 9999».

Какому из элементарных событий $e_1, e_2, \ldots, e_n$ мы припишем (поставим в соответствии) число $\frac{1}{n}$, которое называем вероятность его элементарного события.

Отметим, что мы каждому из элементарных событий приписали по определенному одинаковому вероятность. Это и служит выражением того, что все они «равноправны».

Элементарные события, из которых складывается данное событие $A$, называются исходами, благоприятными этому событию. Вероятность $p(A)$ события $A$, состоящего из $m$ элементарных событий, определяется так:

$$p(A) = \frac{m}{n},$$

где $m$ — число благоприятствующих событий $A$ изходов, $n$ — общее число изходов.

У практики

1. При бросании игральной костей выпадания 1, 2, 3, 4, 5, 6 очков равноверятных. Какова вероятность того, что при бросании игральной костей выпадает:

a) четное число очков;
b) нечетное число очков;
b) 3 или 5 очков;
g) простое число очков?

2. Какова вероятность того, что число, написанное на выбранной карточке в примере 3, обладает следующими свойствами:

a) четрехзначное;
b) делится на 5;

b) есть полный квадрат;
g) не есть четырехзначное число?

Очевидно, что при данном определении вероятность любого события заключена между 0 и 1: $0 \leq p(A) \leq 1$.

Событие, вероятность которого равна 1, называем достоверным. Ему благоприятствует все исходы без исключения.

Событие, которая благоприятствует пустое множество элементов событий (другими словами, то, которое никакогда не произойдет), по данному определению имеет вероятность 0 и называется невозможным.

Операции над событиями

Пусть $A$ — событие. Обозначим через $\bar{A}$ событие, промивоположное $A$, то есть событие, которое благоприятствует все те элементарные исходы, которые не входят в $A$.

Пусть $A$ и $B$ — два события. Через $A + B$ обозначим событие, состоящее из исходов, благоприятствующих хотя бы одному из исходов $A$ и $B$.

Через $A \cdot B$ обозначим событие, состоящее из исходов, благоприятствующих $A$, но не благоприятствующих $B^*$).

У практики

3. Доказите, что: a) $p(\bar{A}) = 1 - p(A)$;
   b) $p(A + B) \leq p(A) + p(B)$; в) $p(A \cdot \bar{A}) = 0$; г) $p(A + \bar{A}) = 1$; д) $p((\bar{A})) = p(A)$;
   e) $p((A \setminus B) + (A \cdot B)) = p(A)$;
   ж) $p((A \setminus B) \cdot B) = 0$.

4. Пусть событие $A$ — извлечение на карточке в примере 3 четырехзначного числа, событие $B$ — извлечение числа, делается на 5. Сформулируйте, что означает каждое из

*) Те, кто читал статью: Гиндкин С. Г., Сколко существует операций над множеством? «Квант», 1973, № 7, безусловно, заметили, что операции над событиями определяются точно так же, как операции над множеством (только вместе $A \cap B$, $A \cup B$ обозначаются как $AB$, $A + B$).

38

Рис. 1.

собътий, стоящих в скобках ниже, и найдите:
a) $p(\overline{A})$; б) $p(\overline{B})$; в) $p(A + B)$; г) $p(A \cdot B)$;
д) $p(A + \overline{B})$; е) $p(A \cdot \overline{B})$; ж) $p(A \setminus \overline{B})$;
з) $p(B \setminus A)$.

5. Докажите, что для любых двух собственных $A$ и $B$ выполняется равенство
   $$p(A + B) = p(A) + p(B) - p(A \cdot B).$$

В частиности, на рисунке 1 множество элементов собственной состоит из 16 элементов, изображенных черными точками. При этом $p(A) = 5/8$, $p(B) = 3/8$, $p(A \cdot B) = 3/16$, $p(A + B) = 13/16$.

Серия независящих испытаний

В наших примерах речь шла не только об одиночных испытаниях (бросании монеты, вытаскивания шара или карточки), но и о сериях из нескольких таких испытаний. Как вычислить веротности в таких случаях? Здесь мы сталиваемся с комбинаторными задачами. Схема действия такова: сначала надо найти множество элементов собственной и определять число $N$ его элементов, затем определять число $M$ исходов, благоприятствующих $A$, и по формуле $p(A) = \frac{M}{N}$ найти ответ.

Решим, например, такую задачу. Пусть мы призадаем бросили монету. Какова веротность, что выпадения «орла» и «решки» будут веротностью второго бросания не зависит от результата первого (испытания независями), то все эти четыре исхода равноверятны.

Аналогично, если мы будем бросать монету три раза, то исходами этого броса будут всевозможные тройки из О и Р. Какдому исходу мы приписываем одинаковую веротность, равную $1/8$, а интересующей нас событие «выпадения О и Р через дугу» состоит из двух элементов собственной; его веротность равна $2 \cdot \frac{1}{8} = \frac{1}{4}$ (рис. 2).

В общем случае, если однократный опыт допускает $n$ элементов исходов, то число всехможных элементов исходов двукратного опыта равно, очевидно, $n^2$ (к любому из $n$ исходов первого опыта можно неза-

40

Общий член геометрической прогрессии $\left(\frac{9999}{10000}\right)^k$ со значением $\frac{9999}{10000}$, меньше 1, при неограниченном возрастании $k$ стремится к нулю. Поэтому найдет такое $k_0$, начная с которой $\left(\frac{9999}{10000}\right)^{k_0} < \frac{1}{2}$, то есть $1 - \left(\frac{9999}{10000}\right)^{k_0} > \frac{1}{2}$.

При $k > k_0$ среди 4$k$-значных чисел «хороших» будет больше, чем «плохих».

Из нашей решения получается следующая оценка для минимального $n = n_0$, начная с которой среди $n$-значных чисел больше хороших, чем плохих: $n_0 > 4\lg 2/\lg \left(\frac{10000}{9999}\right) \approx 30000$.

Эта оценка, конечно, довольно грубая.

Следует отметить ряд писем (H. Шербины, Днепропетровск; A. Курляндчика, Ленинград; A. Григоряна, Баку), в которых найдена более точная оценка. Наболее интересный путь здесь таков. Пусть $G(n)$ — количество хороших $n$-значных чисел: $G(1) = G(2) = G(3) = 0$, $G(4) = 1$, $G(5) = 19$, $G(6) = 280, \dots$

Докажем, что при $n > 5$
$G(n) = 9 \cdot 10^{n-5} + 10G(n-1) - G(n-4)$. (*)

Действительно, $n$-значных чисел, оканичивающих на 1973, существуют $9 \cdot 10^{n-5}$; хороших, которые остаются хорошими после вычеркивания последней цифры — $10G(n-1)$, а чисел, принадлежащих обимем этим множеством, очень удобно, $G(n-4)$.

Изrekуррентного соотношения (*) легко вывести, что минимальное $n_0$ заключено между 5000 и 10000. А если использовать ЭВМ (как поступил брат нашего читателя Л. Курляндчика), то можно быстро найти и точное значение $n_0$: оно равно 6933.

Основная ошибка, которую допустило большеинструточно читателей, состоит в следующем. Вместо того, чтобы оценить сверху количество лох и х чисел, как это делалось