Насколько водонепроницаем швейцарский сыр?

Представьте себе кубический кусок швейцарского сыра. Мы моделируем сыр через сетку 20x20x20. Для простоты мы предполагаем, что каждый сетчатый куб полностью состоит из сыра или целиком из воздуха. На верхней стороне нашего куба швейцарского сыра мы наливаем воду, которая проникает в сыр только через воздушные отверстия в кубе. Вода может протекать через непрерывный канал сверху вниз, но может протекать только от одного воздушного куба к другому, если два куба соединены через грань (а не только край или угол). Вода может также течь по объему, например, в сливной ловушке раковины, но она не может вытекать на боковые стенки кубика сыра.

Теперь давайте программно реализовать эту модель швейцарского сыра со случайным распределением кубиков воздуха и сыра, как описано выше, с вероятностью сыра p и вероятностью воздуха 1 - p и имитировать воду, текущую через сыр, чтобы чтобы выяснить, проходит ли вода на дно швейцарского кубика сыра.

Путем многократного моделирования воды, протекающей по швейцарскому сырному кубу с различной вероятностью сыра и воздуха, мы можем установить связь между p и вероятностью прохождения воды до дна швейцарского кубика сыра, пусть назовите его q. Результат выглядит следующим образом:

q
1   ************************
0.8                          *
0.6                           *
0.4                            *
0.2                             *
0                                 ***********
    0       0.2     0.4     0.6     0.8     1   p

My qustion: Почему такая странная кривая?

Этот вопрос берется из 23-го федерального конкурса информатики в Германии (2004/2005). Ответ на вопрос "почему такая странная кривая" не предоставлен в Интернете (предоставленные решения).

Надеюсь, я нахожусь в нужном месте с таким вопросом.

Ответ 1

Возможно, вы найдете следующее объяснение интуитивным:

В вашем случае 20 * 20 * 20 клеток, если у вас не менее 20 отверстий, вероятность потока воды равна 0. Если у вас есть 20 отверстий, вода может течь, если вы заказываете их в колонке, но вероятность того, что такой порядок появляется случайным образом, очень мала, 20 * 20/Греб (20 ^ 3, 20) ~ = 1е-57. По мере увеличения количества отверстий появление смежных путей становится все более вероятным.

Когда все ваши ячейки, кроме 20 * 20 из них, являются отверстиями, единственный способ блокировать поток - это упорядочить все ячейки сыра в один "блокирующий" слой, например. горизонтальный слой 20 * 20. (Есть и другие возможные конфигурации, но не слишком вероятны. Вам нужно ровно один блок сыра для каждой (x, y) координаты, и каждый блок сыра должен быть в контакте со всеми его (x, y) -соседствами. Но они могут быть распространяются вдоль оси z).

Как только у вас будет менее 20 * 20 блоков сыра, вы не можете сформировать полный слой, а вероятность потока станет ровно 1.

Ответ 2

Это продолжение комментария Жени.

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

Модель Erdős-Rényi

В модели Erdős-Rényi вы начинаете с пустой graph и соедините узлы с ребром с вероятностью p. При некотором критическом значении p структура графа изменяется от связки отключенных кластеров до одной большой структуры охвата, которая содержит большую часть узлов. Фактически, если бы вы планировали средний размер крупнейшего кластера, вы бы получили очень похожую картину, как ваша швейцарская модель сыра! Схематически это выглядит так:

и вы найдете его во многих примерах в прикладной математике и физике. Кредит к картинке проистекает из этой статьи в Frontiers, в котором это явление гораздо более подробно описано.