На клетчатой бумаге со стороной клетки 1 выделен квадрат $ABCD$ $n\times n$ клеток. Из вершины $A$ в $C$ по линиям сетки проводится случайная ломаная длины $2n$. В $n$ клетках квадрата, случайно расположенных в разных строках и разных столбцах, расставляются $n$ звёздочек. С какой вероятностью все звёздочки окажутся по одну сторону от ломаной? (Другими словами, какую долю среди всевозможных расположений ломаных и звёздочек составляют такие, что звёздочки лежат по одну сторону от ломаной?)
Ответ: вероятность того, что звёздочки лежат по одну сторону от ломаной, равна $\dfrac1{2^{n-1}}$.
Мы докажем эквивалентное утверждение: вероятность того, что все $n$ звёздочек лежат ниже ломаной, равна $\dfrac1{2^n}$. Приведём два доказательства.
Первое — по индукции — основано на прямом вычислении числа $L_n$ ломаных, числа $P_n$ всевозможных расстановок $n$ звёздочек (в разных строках и столбцах) и числа $\mathit\Pi_n$ таких пар «ломаная, расстановка», в которых звёздочки лежат ниже ломаной (при этом искомая вероятность равна $\dfrac{\mathit\Pi_n}{P_nL_n}$).
Для тех, кто знаком с началами комбинаторики, найти $L_n$ и $P_n$ не составляет труда: $L_n=C_{2n}^n=\dfrac{(2n)!}{(n!)^2}$ (каждая ломаная определяется последовательностью длиной $2n$ из стрелок двух направлений $\rightarrow$ и $\downarrow$, причём стрелок каждого типа ровно $n$), а $P_n=n!$ (каждая расстановка определяется перестановкой из $n$ номеров, указывающих, в каких строках стоят звёздочки в 1-м, 2-м, $\ldots$, $n$-м столбце). Но мы не будем опираться на эти формулы, а докажем рекуррентные соотношения
$$
\begin{align*}
P_n&=nP_{n-1},\tag1\\
L_n&=\dfrac{2(2n-1)}{n}L_{n-1},\tag2\\
\mathit\Pi_n&=(2n-1)\mathit\Pi_{n-1}.\tag3
\end{align*}
$$
Из них по индукции сразу получается нужный результат. (Проверка для $n=1$ и $n=2$ не составляет труда.) Если доказано, что для таблицы $(n-1)\times(n-1)$ нужная вероятность равна
$$
\dfrac{\mathit\Pi_{n-1}}{L_nP_{n-1}}=\dfrac1{2^{n-1}},
$$
то для таблицы $n\times n$ она равна
$$
\dfrac{\mathit\Pi_n}{L_nP_n}=\dfrac{(2n-1)\mathit\Pi_{n-1}\cdot n}{2(2n-1)L_{n-1}\cdot nP_{n-1}}=\dfrac1{2^n}.
$$
Доказательства формул (1)—(3) аналогичны. Мы устанавливаем необходимое соответствие, отрезая от таблицы $n\times n$ первый столбец и одну из строк (мы считаем, что ломаная идёт из левого верхнего в правый нижний угол). Соотношение (1) почти очевидно. Из каждой расстановки звёздочек в таблице $n\times n$ удалением первого столбца и строки, содержащей звёздочку из этого столбца, получается некоторая расстановка в таблице $(n-1)\times(n-1)$ (рис. 1). При этом к каждой из $P_{n-1}$ таких расстановок мы можем добавить первый столбец и любую (1-ю, 2-ю, $\ldots$, $n$-ю) строку, поставив на их пересечении звёздочку. Таким способом мы установили соответствие, при котором каждой из $P_{n-1}$ расстановок в таблице $(n-1)\times(n-1)$ отвечает $n$ расстановок в таблице $n\times n$, откуда следует (1).
Рис. 1Рис. 2
Докажем формулу (2). Рассмотрим лишь половину из $L_n$ ломаных, а именно те, у которых первое (выходящее из вершины $A$) звено $AA'$ горизонтально (рис. 2). Пометим красным цветом любое вертикальное звено $MM'$ ломаной (его можно выбрать $n$ способами). Удалив звено $AA'$ вместе с первым столбцом и звено $MM'$ вместе с содержащей его строкой, мы получим ломаную $A'C$ в таблице $(n-1)\times(n-1)$, в которой оставим помеченную «красную» точку $M$ (на месте звена $MM'$). Обратно, по каждой из $L_{n-1}$ ломаных с любой помеченной вершиной (а вершин у неё $2n-1$, поскольку звеньев $2(n-1)=2n-2$) однозначно восстанавливается ломаная $A'C$. Отсюда $n\cdot\dfrac{L_n}{2}=(2n-1)L_{n-1}$ — это и есть (2).
Наконец, докажем (3). Заметим, что среди $\mathit\Pi_n$ пар «ломаная, расстановка» первое звено ломаной обязательно горизонтально (иначе в первой строке не будет звёздочек ниже ломаной). Удалив первый столбец, а также строку, в которой стоит содержащаяся в нём звёздочка, мы получим одну из $\mathit\Pi_{n-1}$ пар «ломаная, расстановка» в таблице $(n-1)\times(n-1)$ (рис. 3). Обратно, пометив любую из $2n-1$ вершин такой ломаной и заменив её вертикальным звеном и новой строкой, начинающейся со звёздочки, мы однозначно восстановим пару «расстановка, ломаная» в таблице $n\times n$. Отсюда следует равенство (3).
Рис. 3
Второе доказательство объясняет, почему в этой задаче получается столь простой ответ, но требует знакомства с некоторыми понятиями теории вероятностей, которые мы не будем здесь детально объяснять.
Сначала опишем правило, которое произвольному набору из $n$ точек в квадрате $K=\{(x;y)\colon0\le x{,}~y\le1\}$, все $2n$ координат которых различны, сопоставляет пару «ломаная, расстановка».
Точки нумеруются слева направо. Затем все $2n$ координат точек располагаются в порядке возрастания, абсцисса $i$-й точки заменяется символом $X_i$, а ордината — $Y_i$. В итоге получится последовательность из символов $X_1$, $\ldots$, $X_n$ и $Y_1$, $\ldots$, $Y_n$, в которой символы идут в порядке возрастания индексов. Теперь двинемся по полученной последовательности слева направо и одновременно будем рисовать ломаную, начиная с точки $A$, и ставить звёздочки: если очередная символ последовательности — $X_i$, то делаем шаг вправо (горизонтальное звено ломаной), если это символ $Y_j$, то делаем шаг вниз (вертикальное звено) и в строке, которую мы при этом пересекаем, ставим звёздочку на $j$-м месте, т. е. на пересечении столбца $X_j$ и строки $Y_j$. (Вся эта процедура проиллюстрирована на рисунке 4.) Для того чтобы эта звёздочка оказалась под ломаной, необходимо и достаточно, чтобы звено $Y_j$ было правее звёздочки, т. е. чтобы к тому моменту, когда проводится это звено, ломаная успела сделать не менее $j$ шагов вправо ($X_1$, $X_2$, $\ldots$, $X_j$). Другими словами, в нашей последовательности буква $Y_j$ должна стоять правее $X_j$. А это значит, что ордината $j$-й точки должна быть больше её абсциссы. Если мы хотим, чтобы все звёздочки попали под ломаную, то последнее условие должно выполняться для всех точек: на рисунке 5, где ось ординат направлена вниз, все точки должны попасть под диагональ $x=y$ квадрата $K$.
Рис. 4Рис. 5
Теперь допустим, что точки в квадрате $K$ выбираются наугад, т. е. по строгой терминологии, каждая из их $2n$ координат равномерно распределена на отрезке $[0;1]$ и не зависит от остальных координат (вероятность совпадения координат при этом равна 0). Тогда все возможные порядки координат на $[0;1]$ будут равновероятны. Следовательно, равновероятны все соответствующие им последовательности символов $X_i$ и $Y_j$, т. е. все пары «ломаная, расстановка». Остаётся найти вероятность того, что все точки окажутся под диагональю квадрата. Для одной точки эта вероятность равна $\dfrac12$, для $n$ точек, в силу независимости их выбора, — произведению вероятностей для каждой из них, т. е. $\dfrac1{2^n}$. (Последний результат можно получить и иначе, не прибегая к понятию независимости. Представим, что точки выбираются поочерёдно. Выбор каждой из них характеризуется для нас двумя возможными исходами — выше или ниже диагонали она попала. Для $n$ точек число исходов равно $2^n$, нас устраивает только один из них — все точки ниже диагонали. Все исходы равновероятны, поэтому искомая вероятность — $\dfrac1{2^n}$.
