Пути на клетчатой бумаге

Попробуйте мысленно объединить клетки в блоки 2×2. Если забыть про внутреннюю структуру этих блоков, то получится задача, эквивалентная исходной. Однако в новой задаче вероятность «закрашивания» блоков не будет совпадать с исходным значением, а будет иметь новое значение p₁, зависящее от p. Первый шаг к решению задачи — отыскать это p₁.

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

Если вам удалось получить формулу для p₁, p₁ = f(p), продолжите укрупнение сетки. Можно объединять блоки в новые блоки и продолжать этот процесс до бесконечности. И на каждом следующем шаге p_n+1 будет равно f(p_n). Подумайте, как поведение p_n в зависимости от n отражает возможность муравья путешествовать на сколь угодно большие расстояния. Определите качественно эволюцию p_n для различных начальных значений. Для этого может быть очень полезно построить график y = f(x) и сравнить его c графиком функции y = x.

Как говорилось в подсказке, мысленно объединим клетки в блоки 2×2 и будем эти блоки рассматривать как новые клетки. Зададимся вопросом: в каком случае блок можно считать закрашенным? Для этого представим, что муравей находится на верхней стороне блока, и найдем такие конфигурации закрашенных клеток, при которых муравей может пройти на нижнюю сторону.

Всего существует 2⁴ = 16 конфигураций, которые различаются количеством и расположением синих клеток. Разберем по порядку случаи с разным количеством закрашенных клеток (рис. 1). Очевидно, что если закрашены четыре или три клетки, то муравей всегда может перейти с верхнего края блока на нижний. Если закрашены две клетки, то из шести возможных расположений годятся два варианта, когда клетки находятся одна над другой. Во всех остальных случаях муравей не пройдет через блок.

Рис. 1. Некоторые варианты расположения клеток в блоке. Варианты a), b), c) соответствуют проходимому блоку, d), e), f) — непроходимому

Получается следующая картина: годится одна конфигурация с 4 синими клетками, четыре — с тремя синими клетками и две — с двумя. Несложно вычислить, что если для клетки вероятность быть закрашенной равна p, то вероятность того, что через блок можно пройти, равна p₁ = f(p) = p⁴ + 4p³(1 − p) + 2p²(1 − p)² = 2p² − p⁴.

Будем продолжать процесс укрупнения сетки, то есть объединять блоки в новые блоки. Тогда на каждом шагу мы будем получать новую вероятность того, что блок очередного размера может быть закрашен, по формуле \( p_{n+1} = 2p_n^2- p_n^4 \). Это — довольно сложное рекуррентное соотношение, и едва ли здесь можно найти явную формулу для p_n. Но этого и не нужно: если построить график f(p), то можно качественно понять поведение p_n в зависимости от n.

Из графика видно, что f(p) пересекает прямую y = p в некоторой единственной точке p_crit (рис. 2). При p > p_crit выполнено соотношение f(p) > p, а при p < p_crit — соотношение f(p) < p. Значит, если начальное значение p₀ = p_crit, то и все p_n = p_crit. Если p₀ > p_crit, то вероятность будет увеличиваться с итерациями, а если p₀ < p_crit, то — уменьшаться.

Рис. 2. Лестница, изображающая итерации рекуррентного соотношения \( p_{n+1} = 2p_n^2- p_n^4 \). Синяя точка соответствует начальному значению p

Графически итерации рекуррентного соотношения p_n+1 = f(p_n), где f(x) = 2x² − x⁴, описываются лестницей, изображенной на рисунке 2. Принцип построения лестницы таков: отложим p_n на оси абсцисс. Тогда точка графика, соответствующая p_n, имеет ординату p_n+1. Чтобы отметить p_n+1 на оси абсцисс, проведем через точку графика с координатами (p_n, p_n+1) горизонтальную линию до пересечения с прямой у = p. Точка пересечения имеет абсциссу p_n+1, и можно продолжить итерации в том же духе.

Рассмотрим для определенности лестницу, соответствующую p₀ < p_crit. Из рисунка понятно, что p_n не просто уменьшается, а стремится к нулю! Точно так же при p₀ > p_crit вероятность стремится к единице. Это значит, что при p₀ < p_crit муравей почти наверняка не сможет пройти через блок достаточно большого размера и, наоборот, почти наверняка пройдет через блок при p₀ > p_crit.

Осталось найти p_crit. Для этого нужно решить уравнение p = 2p² − p⁴. Это — уравнение четвертой степени, однако два корня известны (их легко найти подбором): это 0 и 1. Если поделить многочлен p³ − 2p + 1 на p − 1, получится квадратный трехчлен p² + p − 1, который имеет положительный корень \( (\sqrt5- 1)/2 \approx 0{,}618 \). Точная критическая вероятность, найденная с помощью компьютера, равна 0,592746. Таким образом, относительная ошибка нашего ответа — 4%.

Рис. 3. Непроходимая комбинация двух блоков

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

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

Задача о перколяции в чистом виде тоже очень сложна и интересна. Ее можно ставить не только для клетчатой бумаги, но и для любой решетки и даже для любого графа. Для некоторых случаев известны точные ответы для критических вероятностей, но, как правило, их приходится искать численно. Результаты наших расчетов для вероятностей, близких к критической, приведены на рисунках ниже. Видно, что область, доступная для муравья, имеет сложную фрактальную структуру. Кроме того, малое изменение p — всего на сотые доли — очень сильно меняет картину.

Рис. 4. Результаты численного моделирования зоны проницаемости (черная) в нашей задаче для разных значений p. Слева направо: p = 0,57, p = 0,585, p = 0,6

Заметим, что моделирование перколяции и других подобных процессов — это не какие-то отвлеченные или устаревшие задачи. Их актуальность подтверждается, например, тем, что совсем недавно — в 2010 году — за работы в этой области была вручена Филдсовская медаль российскому математику Станиславу Смирнову. Читайте также статью «О современной математике и ее преподавании» («Квант» №2 за 2011 год), в которой Станислав в том числе рассказывает о моделировании перколяции и о своих результатах в этой области.

В заключение расскажем еще об одной задаче, связанной с перколяцией. А именно: как зависит глубина проникновения муравья от p, если p < p_crit? Ответ можно получить, используя наши предыдущие рассуждения. Пусть p₀ = p_crit − ε, где ε очень мало. Тогда, применяя описанную в решении итеративную процедуру, мы очень долго будем получать близкое к критическому значение вероятности. С другой стороны, ясно, что «протекание» исчезает именно тогда, когда p значительно меньше p_crit. Значит, глубина проникновения — порядка размера блока, для которого p значительно меньше p_crit.

Чтобы получить количественный ответ, нужно сделать еще одно упрощение. При p ≈ p_crit можно заменить f(p) на p_crit + df/dp·(p − p_crit), где df/dp — производная функции f. В точке p_crit она равна \( 4(p_{crit}- p_{crit}^3) = 6- 2\sqrt5 \). Значит,

Нам нужно найти такое n, что p_n − p_crit ≈ 1.

Решая уравнение, получим, что \( n = \ln(1/\Delta p_0)/ \ln(\mathrm{d}f/\mathrm{d}p) \), а соответствующий размер блока равен \( L = 2^n = (1/\Delta p_0)^{(1/\ln(6- 2\sqrt5))}. \)

К сожалению, этот ответ, как и ответ для критической вероятности, не является точным. Однако верен вывод о степенной зависимости глубины проникновения от вероятности. И это — очень важный вывод, потому что такая степенная зависимость типична для всех фазовых переходов второго рода.

В фазовых переходах второго рода, как и во всех обычных фазовых переходах, состояние вещества меняется при изменении температуры. Особое отличие фазовых переходов второго рода — в том, что в точке перехода меняется симметрия физической системы, то есть происходит в некотором смысле переход от «более симметричной» фазы к менее симметричной. Самый простой пример — переход между парамагнетиком и ферромагнетиком: при критической температуре магнитные моменты атомов выстраиваются вдоль одного направления, создавая намагниченность (и нарушая тем самым симметрию). Отметим, что, как правило, парамагнитное состояния реализуется при более высокой температуре, а ферромагнитное — при более низкой.

Явления при температуре, близкой к критической, имеют много общего с задачей перколяции. В примере про пара- и ферромагнетики при понижении температуры и приближении её к критической начинают образовываться небольшие кластеры из атомов с магнитными моментами, направленными в одну сторону. Оказывается, эта картина из кластеров очень напоминает доступные для муравья области в задаче перколяции. А характерный размер кластера (который более правильно называть корреляционной длиной) зависит от (T − T_c) по степенному закону — так же, как в задаче перколяции размер кластера зависит от p − p_crit.