Сколько нужно перевернуть бургеров, чтобы понять теорию вероятностей?

Эта невинная на вид задача является классической проблемой дискретной оптимизации и сортировки перестановками. Долгое время точная формула (число флипов) для любого количества $N$ блинов/котлет оставалась неизвестной. Математики могли задать лишь верхние и нижние границы. Например, Гейтс в своей единственной научной статье (1979 год) доказал верхнюю границу: $(5n+5)/3$. В 2026 году нейросети, анализируя графы состояний (где узлы — это все $N!$ возможных стопок), наконец-то вычислили точные значения для сверхбольших $N$.

Но дальше вступает в дело теория вероятностей. Какова вероятность того, что если повар будет переворачивать котлеты абсолютно случайно, стопка соберется правильно? Здесь мы сталкиваемся с теоремой о бесконечных обезьянах и марковскими цепями. Вероятность случайной правильной сортировки ничтожно мала, но она отлична от нуля. Математики рассчитали время релаксации (mixing time) для этой марковской цепи — время, за которое случайные перевороты полностью "забывают" начальное состояние стопки.

Для программистов и биоинформатиков эта "бургерная математика" имеет колоссальное значение. Алгоритмы, используемые для поиска кратчайшего пути сортировки блинчиков, сегодня применяются для анализа генома человека. Когда вирусологи изучают мутации ДНК (инверсии фрагментов хромосом), они используют именно ту самую математику, которую повар применяет для сортировки котлет лопаткой. Так абстрактная игра ума спасает жизни и расшифровывает эволюцию вирусов.

1. Источники материалов: Журналы Discrete Applied Mathematics, статьи Билла Гейтса и Христоса Пападимитриу, исследования по биоинформатике.

2. Названия экспертов: Христос Пападимитриу (соавтор статьи Гейтса), Перси Диаконис (специалист по марковским цепям).

3. Что еще изучить: Алгоритмы сортировки, Марковские цепи и время релаксации, Теорема о бесконечных обезьянах, Вычислительная биология (инверсии генома).