Задача о педантичном пассажире

18 июля 2023 года, 00:10

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

$Иллюстрация к задаче о педантичном пассажире$

Условие

В автобусе n пронумерованных мест. Пассажиры занимают места в случайном порядке, не обращая внимание на номера в билетах. Последний пассажир оказывается педантичным — он хочет сидеть на своем месте. Если место педантичного пассажира занято, он заставляет сидящего там пассажира пересесть. Пересаживающийся пассажир тоже становится педантичным и идет на свое место. Процесс пересаживания продолжается до тех пор, пока последний педантичный пассажир не усядется в пустое место. Сколько в среднем пассажиров пересядет?

Математическая природа задачи

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

Сидящие в каком-то порядке пассажиры описываются перестановкой — отображением множества из n элементов на это же множество. Действительно, каждая рассадка пассажиров задает взаимно однозначное соответствие (биективную функцию) номеров мест на номера билетов пассажиров. Рассмотрим пример из задачи для n=8:

$$\begin{pmatrix} \text{места}\\ \text{билеты} \end{pmatrix}=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 4 & 6 & \bf{1^*} & 2 & 5 & 3 & 8 & 7 \end{pmatrix}.$$

Для удобства рассуждений будем считать, что педантичный пассажир имеет билет номер 1. (Интуитивно понятно, что ответ в задаче не зависит от конкретного номера билета у педантичного пассажира, но вы попробуйте это доказать в качестве упражнения.) Если бы пассажир не был педантичным, он просто занял бы свободное место с номером 3. Но поскольку пассажир педантичный, он заставляет пересесть пассажира 4, тот заставляет пересесть пассажира 2, дальше пересаживается пассажир 6 и, наконец, пассажир 3 идет на свое свободное место:

$$\tikzcdset{arrow style=tikz,diagrams={>=stealth}} \begin{matrix} \left(\begin{tikzcd}[row sep=14pt,column sep=12pt] 1\ar[d] & 2\ar[d] & 3\ar[d] & 4\ar[d] & 5 & 6\ar[d] & 7 & 8 \\ 4\ar[urrr,dotted,looseness=1,in=155] & 6\ar[urrrr,dotted,looseness=1,in=160] & 1\ar[ull,dotted] & 2\ar[ull,dotted] & 5 & 3\ar[ulll,dotted] & 8 & 7 \end{tikzcd}\right) \end{matrix}$$

Получившаяся цепочка (1 4 2 6 3) называется циклом.

Таким образом, в задаче фактически нужно найти среднюю длину цикла, содержащего случайно выбранный элемент случайной перестановки.

Погружение в теорию

Любая перестановка распадается на один или несколько циклов. В нашем примере это циклы $$(1\ 4\ 2\ 6\ 3)(5)(7\ 8)$$. Циклы могут иметь произвольную положительную длину. Единственное ограничение на циклы — сумма их длин равна n. Фактически циклическая структура перестановки описывается разбиением чисел.

Разбиения чисел, как и циклы в перестановках, изображают графически в виде диаграмм Юнга. Каждая строка этой диаграммы соответствует своему циклу, строки расположены в порядке убывания длины. В нашем примере диаграмма Юнга имеет вид:

$$\begin{tikzpicture}[scale=0.5]\small \draw[line width=0.22mm] (0,0) grid (5,-1) (0,-1) grid (2,-2) (0,-2) grid (1,-3); \end{tikzpicture}$$

Каждой диаграмме Юнга, в которой $$m_1$$ циклов длины 1, $$m_2$$ циклов длины 2 и т. д. соответствует следующее количество перестановок:

$$N={n!\over 1^{m_1}m_1!\cdot 2^{m_2}m_2!\cdot\ldots\cdot n^{m_n}m_n!}.$$

Давайте для тренировки проверим, что получится для нашей диаграммы Юнга:

$$N_{8 = 5 + 2 + 1}={8!\over 1^{1}1!\cdot 2^{1}1!\cdot 5^{1}1!}={8!\over 10}=4032.$$

Выходит, среди всех 8! = 40320 перестановок из 8 элементов десятая часть имеет структуру, описываемую разбиением 8 = 5 + 2 + 1.

Теперь надо перебрать все диаграммы Юнга, для каждой вычислить вес по этой формуле и усреднить длину строк с такими коэффициентами. Осталась «небольшая» проблема — я не знаю простого аналитического способа перебора диаграмм Юнга. Такой метод решения задачи заводит в тупик, особенно если решать в уме. Поэтому забудем всё, что здесь было написано, и будем решать задачу с нуля без каких-либо предварительных знаний о циклах.

Решение «на пальцах»

Как было написано выше, мы будем вычислять среднюю длину цикла, содержащего первый элемент в случайной перестановке длины n. (Вместо первого элемента можно брать любой: из формул дальше видно, что ответ от этого не зависит.) Под средней длиной понимается математическое ожидание — усреднение длины цикла с весами, равными вероятностям:

$$L=P_1\cdot 1+P_2\cdot 2 +\ldots+P_n\cdot n,$$

где $$P_1$$ — вероятность того, что цикл имеет длину 1, $$P_2$$ — что имеет длину 2 и т. д. Ясно, что циклов с длиной больше чем полное количество элементов n не бывает, и слагаемые в формуле останавливаются на n.

В этой формуле легко подсчитать $$P_1$$. Так как перестановки случайные, элемент 1 с равной вероятностью может переводиться перестановкой в любой другой элемент от 1 до n. Если 1 переходит в 1, мы получаем цикл длины 1:

$$\begin{pmatrix} 1 & 2 & \ldots & n\\ 1 & * & \ldots & * \end{pmatrix}.$$

В противном случае длина цикла будет больше. Таким образом, $$P_1=1/n$$ — с такой вероятностью можно выбрать число 1 из первых n чисел.

Попробуем теперь вычислить $$P_2$$. Чтобы получился цикл длины 2, элемент 1 должен переходить в элемент $$k\neq 1$$, а элемент k — в 1:

$$\begin{pmatrix} 1 & \ldots & k & \ldots & n\\ k & \ldots & 1 & \ldots & *\\ \end{pmatrix}.$$

Есть $$n-1$$ способ выбрать первый элемент $$k\neq1$$, что дает вероятность $$(n-1)/n$$ (действительно, в противном случае мы бы получили цикл длины 1 с вероятностью $$P_1=1/n$$). Вторым элементом должен быть 1, его можно выбрать из оставшихся $$n-1$$ элементов с вероятностью $$1/(n-1)$$. Таким образом,

$$P_2={n-1\over n}\cdot{1\over n-1}={1\over n}.$$

Удивительно, но мы получили, что $$P_1=P_2=1/n$$. Давайте проверим, совпадение ли это, или закономерность. Цикл будет иметь длину 3, если его длина не 1 и не 2, и если третьим элементом мы выберем 1. Вероятность этого

$$P_3=\left(1-P_1-P_2\right)\cdot{1\over n-2}={n-2\over n}\cdot{1\over n-2}={1\over n}.$$

Аналогично все остальные вероятности тоже совпадают: $$P_i=1/n$$. Таким образом, средняя длина цикла $$L=(n+1)/2$$.

Вывод

В автобусе с количеством мест n педантичный пассажир спровоцирует $$(n+1)/2$$ пересадок. Или, если исключить его самого из этого числа, пересядет $$(n-1)/2$$ других пассажиров. Мы не только вычислили среднее количество пересаживающихся пассажиров, а еще и нашли распределение этого количества: оно оказалось равномерным. Иными словами, с равной вероятностью педантичный пассажир сядет в свое пустое место, или заставит пересесть одного пассажира, или двух и т. д. Все эти исходы оказываются равновероятными.

Послесловие

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

И, наконец, если вы сомневаетесь в правильности ответа, можете запустить скрипт, вычисляющий ответ методом полного перебора. Алгоритм перебора перестановок взял из книжки. Сконвертировал код из Perl в PHP с помощью ChatGPT. Усреднение длины цикла делается тривиально.

<?php

function nextShuffle(array $shuffle): ?array {
    for ($i = 1, $count = count($shuffle); $i < $count; $i++) {
        if ($shuffle[$i] < $i) {
            $shuffle[$i]++;
            return $shuffle;
        }

        $shuffle[$i] = 0;
    }
    return null;
}

// Длина цикла, содержащего элемент 1.
function cycleLength(array $p): int {
    $num    = 1;
    $result = 0;
    while ($p[$num - 1] !== 1) {
        $num = $p[$num - 1];
        $result++;
    }
    return $result;
}

$n = (int)$argv[1];
if ($n <= 0) {
    die("$argv[0]: Нужно неотрицательное число!\n");
}

$shuffle = array_fill(0, $n, 0);

$totalLength       = 0;
$totalPermutations = 0;
while ($shuffle !== null) {
    // Начальная перестановка
    $p = range(1, $n);
    // Применение транспозиций
    for ($i = 0; $i < $n; $i++) {
        $temp            = $p[$i];
        $p[$i]           = $p[$shuffle[$i]];
        $p[$shuffle[$i]] = $temp;
    }

    $length      = cycleLength($p);
    $totalLength += $length;
    $totalPermutations++;
    // echo implode(" ", $p), "  | ", $length, "\n";

    // Генерирование следующего набора транспозиций
    $shuffle = nextShuffle($shuffle);
}

echo "Всего перестановок (факториал) = ", $totalPermutations, "\n", 
     "Среднее количество пересадок = ", $totalLength / $totalPermutations, "\n";

Пример результата запуска:

> php script.php 8
Всего перестановок (факториал) = 40320
Среднее количество пересадок = 3.5

математика · PHP