Преобразование пекаря

Квант 1989, №4 с. 19-22 Тег 52LL

ПРЕОБРАЗОВАНИЕ ПЕКАРЯ

Кандидат физико-математических наук
В. А. ЧУЛАЕВСКИЙ

Если приходится слишать слова «вероятность», «случайность», то, пожалуйста, чаще всего мы вспоминаем об игре в «орлянику», бросаний игralных костей или тасовании карт. Да и сам термин «азартные игры» происходит от французского слова hasard, что означает «случай». Попытки найти скрытые механизмы, управляющие слуаем, предпринимались во все времена. Однако кончались они, как правило, печально — вспомним пущинского Германна!. Да и есть ли чтоибудь общее между полной предопределностью («тройка, семерка, туз») и слуаейность? Не будем спешить с ответом, а займется пока… кулинарией.

Задача о несоленом пироге. Итак, давайте испечем пирог. Откроем кулинарную книгу и выберем рецепт по своему вкусу. Замещиваем тесто, ждем, пока оно поднимется нарожжах, раскатываем его в виде квадрата скалкой. Принимаемся за начинку… Погодите, а ведь тесто-то мы не посолили. Что же, попытаемся исправить свою оплошность: возьмем чайную ложку соли и… Ах, как неаккуратно! Вся соль высыпалась в уголок будущего пирога (рис. 1). Но это не должно нас смущать (как, впрочем, и то, что «квадрат» на наших рисунках «выглядит» прямого угловиком). На помощь приходит опыт хлебопекаров: растягаем квадрат вдвое по горизонтали, режим пополам по вертикали и снова составляем квадрат так, как изображено на рисунке 2.

To, что мы проделали с квадратом, называется иногда преобразование пекаря. Любая хозяйка знает, что таким способом можно сделать тесто очень однородным. Но как вы думаете, сколько раз надо повторить эту процедуру, чтобы соль, высыпанная в уголок, распределилась практическими поровну между всеми кусочками будущего пирога, — два? Десять? сто? тысячу?

Геометрия преобразования пекаря. Давайте разделим квадрат пополам по вертикали. Будем играть в такую игру: выберем точку в квадрате и, если после преобразования пекаря она оказывается в левой половине квадрата, мы выиграли, в противном случае — проиграли.

— Игра для детского сада,— скажете вы. — Совершенно очевидно, что точку нужно выбирать на двух вертикальных полосах, закрашенных на рисунке 2, a.

Верно. Придется усложнить правила игры; выбрав точку, повторяем преобразование пекаря 10 раз и только после этого смотрим, в какую половину квадрата она попала. Теперь выигрышная стратегия не столбец видна. Чтобы произвольного n найти множество точек, которые после n-кратного применения преобразования пекаря оказывается в левой половине квадрата, удобно проследить за движением точки под действием обрат-

Рис. 3

ного преобразования пекаря, т. е. преобразования пекаря, выполненого в образном порядке. Как оно выглядит, показано на рисунке 3. Применяя это после $n$ -кратного повторения преобразования пекаря. И хотя «выигрышное» множество явно указано, стоит ошибиться в определении абсциссы точки на $2^{-n-1}$ (а эта величина доволь–

преобразование несколько раз подряд к единному квадрату, у которого левая половина закрашена, мы получим последовательность картинок, изображенных на рисунке 4. На $n$ -м шаге оказываются закрашенныеми все вертикальные полоски шириной $2^{-n-1}$ с нечетными номерами, если считать слева направо. Именно эти точки перейдут в левую половину квадрата

Рис. 4.

но мала уже при небольших значении n), и мы проигralли. Наличие даже небольший ошибки делает игру очень похожей на орлянку: ведь выигрышное множество всегда имеет площадь 1/2, так что если выбирать точку нагад, веряность выиграть также равна 1/2.

Переменшивание. Мы уже забили, что в кухне насжет несостоящийся пирог. Оdnako время не прошло даром. Теперь мы знаем, что поправить дело совсем несложно. Достаточно повторить преобразование пекаря 15—20 раз, и тесто будет посолено практическим равномерно. Проследим за эвольюцией кругто посоленого участка пирога — рисунок 5. Можно начинать не только с квадратика, но и с фигуры произвольной формы. В любом случае через небольшее число повторений образ этой фигуры равномерно «размажется» по квадрату. Более точно это можно сформировать так. Обозначим преобразование пекаря через T,

и путь $A$ и $B$ — две фигуры неулевой площади, лежащие внутри квадрата, например два многоугольника. Тогда с ростом $n$ относение площад $(T^n(A) \cap B)/$ площад $(A)$ стремится к доле площади множество $B$ от площади всего квадрата. Значит, при больших $n$ шансы попасть из $A$ в $B$ за $n$ шагов под действием $T$ практически не зависит от $A$ , т. е. от начального положения точки, а зависит только от площади множество $B$ .

Сформированное нами свойство называют переменшанем. Оно означает, что любая фигура с течением времен равномерно распливается по квадрату.

Неколько формул. Хотелось бы научиться описывать преобразование пекаря формулами. Деление пополам, которое участвует в определении преобразования, подсказывает, что в таком описании может быть полезной двойная система счисления. Напомним, что каждое число $\alpha$ из интервала $[0;1)$ можно записать как $0, \alpha_1 \alpha_2 \alpha_3...$ , где каждое $\alpha_i$ равно 0 или 1. Такая запись означает, что $\alpha = \alpha_1/2 + \alpha_2/2^2 + \alpha_3/2^3 +...$ ; например, 1/2 можно записать в двойной системе как 0,1, а 1/3 — как 0,010101… Геометрический смысл такой записи следует. Разделим интервал $[0;1)$ пополам. Если $\alpha_1 = 0$ , то число $\alpha$ лежит в левой половине интервала: $[0;1/2)$ , а если $\alpha_1 = 1$ , то в правой: $[1/2;1)$ . Пусть для определности $\alpha_1 = 0$ . Тогда $\alpha_2$ указывает, в какой половине интервала $[0;1/2)$ лежит $\alpha$ — в левой ( $\alpha_2 = 0$ ) или в правой ( $\alpha_2 = 1$ ). Все остальные цифры двойной записи имеют аналогичный смысл.

Упражнения

Докажите, что $1/3 = 0,010101$ …

Подсказка: воспользуйтесь формулой суммы бесконечной геометрической прогрессии: $q + q^2 + q^3 +... = q/(1-q)$ .

Запишите 1/7 в виде двойной дроби.
Запишите 0,110110110… в виде объективной дроби.

Возьем точку $m$ в единичном квадрате $K = \{(x;y):0 \leqslant x < 1, 0 \leqslant y < 1\}$ с координатами $(x;y)$ , записанных в двойной форме: $x = 0, x_1 x_2..., y = 0, y_1 y_2...$ . Посмотрим, как изменится двойная запись координат точки $m$ , если к ней применить преобразование пекаря. Если $x_1 = 0$ , т. е. $m$ расположена в левой половине квадрата, то ее абсцисса уvelичится вдвое. Именно по этой причине мы предопили двойную запись десятичной: в десятичной системе счисления очень просто умножать дроби на 10 — достаточно сдинуть дробь относительно запятой влево на 1 позицию, а в двойной системе точного так же действует умножение на 2.

Итак, абсцисса точки $T(m)$ равна 0, $x_2 x_3...$ . Если же $x_1 = 1$ , то на первом этапе преобразования пекаря (рис. 2, б) точка $m$ перейдет в точку с абсциссой $1, x_2 x_3...$ , а после разрезания (рис. 2, е) — сдинится на 1 влево, так что и в этом случае абсцисса точки $T(m)$ равна 0, $x_2 x_3...$ . Проследим теперь за изменением ordinаты точки $m$ . На первом этапе она уменьшится вдвое: $y \rightarrow 0,0 y_1 y_2...$ , а затем либо останется неизменной (при $x_1 = 0$ ), либо уvelичится на 1/2 (при $x_1 = 1$ ). Значит, можно написать, что ordината точки $T(m)$ равна 0, $x_1 y_1 y_2...$ . Для нагладности запищем координаты точки $m$ в одну строку следующим образом:

$m \leftrightarrow (\dots y_3 y_2 y_1, x_1 x_2 x_3...).$