О вероятностях и черно-белом мире

Иногда так случается, что мир вокруг кажется нам черно-белым, а все окружающие нас вещи делятся на плохие и хорошие. Должно быть, это случилось в далеком 1973 году и с одним известным математиком и автором занимательных задач Г. А. Гуревичем. На самом деле, дата здесь указана не случайно: математик придумал разделить все числа на хорошие и плохие очень простым способом – если в десятичной записи числа встречались подряд цифры 1-9-7-3, то оно считалось хорошим, если нет – плохим.

С другой стороны, всем хочется, чтобы хорошего в нашей жизни было больше. Но если мы посмотрим, например, на все числа от 0 до 10000, то окажется, что «хорошее» число среди них всего одно! Так появилась наша с вами сегодняшняя задача: необходимо найти такое натуральное число n, чтобы среди всех n-значных чисел «хороших» было больше, чем «плохих».

На первый взгляд, перед нами типичная задача на комбинаторику. Что ж, возможно, нам удастся вас удивить: решать мы ее будем с помощью теории вероятностей! А для этого сначала рассмотрим небольшой пример.

Так как требуемая комбинация цифр – четырехзначная, возьмем 10000 карточек и пронумеруем их от 0000 до 9999. Таким образом, мы выписали все возможные комбинации четырех цифр. Если мы сложим карточки в мешок и будем наугад вытаскивать их по одной, то вероятность вытащить карточку «1973» окажется равной 1/10000, а вероятность не вытащить – соответственно 9999/10000. Если же мы вытащим k карточек, возвращая их обратно в мешок, то вероятность того, что среди них не окажется «1973» уже будет равна (9999/10000)^k.

Именно здесь кроется идея решения нашей задачи. Давайте расположим все вытянутые нами карточки последовательно. Мы получим 4k-значное число (и следует отметить, что таким способом мы может получить все 4k-значные числа), в котором с вероятностью меньше, чем (9999/10000)^k, не окажется последовательных цифр «1973». Почему меньше? Так получается из-за того, что наш способ оценки не учитывает тех случаев, когда цифры 1-9-7-3 окажутся на соседних карточках.

Давайте теперь присмотримся к выражению для вероятности не вытащить «1973». (9999/10000)^k – это геометрическая прогрессия со знаменателем 9999/10000 меньше единицы, а это значит, что такая вероятность будет стремиться к нулю с ростом k. По условию задачи нам достаточно, чтобы «плохих» чисел было меньше половины, а это эквивалентно тому, что вероятность «плохого» числа будет меньше 1/2 – ведь каждое 4k-значное число будет равновероятно получено при вытаскивании нами карточек из мешка. Так как настоящая вероятность «плохого» числа даже меньше, чем (9999/10000)^k, мы можем записать нестрогое неравенство:

Мы получили, что среди 27728-значных и более длинных чисел «хороших» будет больше, чем «плохих». Задача решена, и жизнь одного известного математика вновь заиграла яркими красками! Конечно, 27728 – достаточно грубая оценка, и на самом деле пороговое значение существенно ниже. Попробуйте найти более точное значение другими способами!