WikiDer > Удержание воды на математических поверхностях

Water retention on mathematical surfaces
Лего поливают водой.
Иллюстрация удержания воды на поверхности.

Удержание воды на математических поверхностях это улавливание воды в прудах на поверхности ячеек разной высоты на регулярном массиве, таком как квадратная решетка, где вода проливается на каждую ячейку в системе. Границы системы открыты и позволяют воде вытекать. Вода будет скапливаться в прудах, и в конечном итоге все пруды заполнятся до максимальной высоты, при этом любая дополнительная вода будет вытекать через водосбросы и за границы системы. Проблема состоит в том, чтобы определить количество воды, удерживаемой или удерживаемой на данной поверхности. Это широко изучалось для двух математических поверхностей: магических квадратов и случайных поверхностей. Модель также может быть применена к треугольной сетке.[1]

Магические квадраты

Удержание на магическом квадрате 5x5.
Магический квадрат 5 × 5 с максимальным удержанием.

Магические квадраты изучаются более 2000 лет. В 2007 году была предложена идея изучения удержания воды на магическом квадрате.[2] В 2010 году соревнования по программированию Аль Циммерманна.[3] произвел известные в настоящее время максимальные значения удерживания для магических квадратов порядка от 4 до 28.[4] Вычислительные инструменты, используемые для исследования и иллюстрации этой проблемы, находятся здесь.[5][6][7][8]


Для квадрата 7 × 7 существует 4211744 различных образца удерживания. Сочетание озера и прудов лучше всего для достижения максимального удержания. Нет известных схем максимального удержания на острове в пруду или озере.[2]

Магические квадраты максимального удержания для заказов 7-9 показаны ниже:[4]

На рисунках ниже показан магический квадрат 10х10. Можно ли взглянуть на паттерны выше и предсказать, какой будет паттерн максимального удержания для квадрата 10х10? Не было разработано теории, которая могла бы предсказать правильную комбинацию озера и прудов для всех порядков, однако некоторые принципы применимы. Первые цветные рисунки показывают принцип построения того, как наибольшие доступные числа размещаются вокруг озера и прудов. На втором и третьем рисунках показаны многообещающие модели, которые были опробованы, но не достигли максимального удержания.[2]

Несколько заказов имеют более одного шаблона для максимального удержания. На рисунке ниже показаны два шаблона для магического квадрата 11x11 с кажущимся максимальным удерживанием 3492 единиц:[4]

В самые совершенные магические квадраты требовать, чтобы все (n-1) ^ 2 или в данном случае все 121 плоское подмножество 2x2 имели одинаковую сумму. (несколько примеров отмечены желтым фоном, красным шрифтом). Области, полностью выделенные большими цифрами, показаны на синем фоне.[9]

Самый совершенный магический квадрат.jpg

До 2010 года, если вам нужен был пример магического квадрата размером более 5 × 5, вы должны были следовать хитроумным правилам построения, которые давали очень отдельные примеры. 13x13 пандиагональный магический квадрат ниже такой пример. Утилита CompleteSquare Гарри Уайта [5] позволяет любому использовать магический квадрат так же, как гончар использует кусок глины. На втором изображении показан магический квадрат 14x14, который был сформирован в виде прудов, на которых написаны даты 1514–2014 гг. В анимации показано, как была сформирована поверхность, чтобы заполнить все пруды до предела, прежде чем вода стечет с площади. Эта площадь посвящена 500-летию знаменитого магического квадрата Дюрера в Меленколия I.

13 x 13 Пандиагональная Магическая Площадь.png
Магический квадрат удержания воды. Gif

На этом рисунке также представлен пример квадрата и его дополнения, которые имеют тот же образец удерживания. Есть 137 магических квадратов 4-го и 3 254 798 5-го порядка, которые не удерживают воду.[2]

16 х 16 ассоциативный магический квадрат сохраняя 17840 единиц. Озеро на первом изображении выглядит немного уродливее обычного. Ярек Вроблевски отмечает, что хорошие шаблоны для максимального удерживания будут иметь равное или почти равное количество удерживающих ячеек на каждом периферийном крае (в данном случае 7 ячеек на каждом краю). [3] Второе изображение обработано, закрашено 37 значений верхнего и нижнего края.

Магический квадрат pattern.jpeg
Ассоциативный магический квадрат 2013.jpeg

На рисунке ниже изображен магический квадрат формата Луо-Шу 17x17.[10]Метод строительства формата Луо-Шу, кажется, позволяет создать максимальное количество прудов. Дренажный путь для ячейки, обозначенной зеленым цветом, длинный, в конечном итоге выливается из квадрата желтой водосливной ячейки.

На рисунке справа показано, какую информацию можно получить, глядя на фактическое содержание воды в каждой ячейке. Для того, чтобы квадрат не выглядел слишком загруженным, выделены только 144 значения. Сосредоточение внимания на зеленой ячейке с базовым значением 7, самым высоким. Препятствием на пути к выходу является соседняя ячейка со значением 151 (151-7 = 144 сохраненных единицы). Вода, попавшая в эту ячейку, выходит из квадрата в желтой ячейке 10.


Марио Мамзерис изобрел собственный метод построения магических квадратов нечетного порядка. Его ассоциативный магический квадрат Ордена 19 показан ниже.[11]



Заказать 19 Magic Square.png


В магическом квадрате 21 x 21 ниже все четные числа образуют плотины и пруды, а все нечетные числа указывают пути выхода.[12]

Магический квадрат Четное число Water Retention.png



Компьютерный век теперь позволяет исследовать физические свойства магических квадратов любого порядка. На рисунке ниже показан самый большой магический квадрат, изученный в конкурсе. Для L> 20 количество переменных / уравнений увеличивается до такой степени, что это делает модель максимального удержания предсказуемой.

L = 28: 219822 единиц удержания
152596592577137122822562836572556562847267252542856542532865567367447164573
96406642571726277167157142866829744303173074350681680679515267820664611
265665355722496618714849512172140077441813017629354174947910617538914823068243644
66314724356313513751891984492137758747853913932660451750461566141442638477677276
2667201645723542264911715121177762472445034358562940614463475159246212513451444672
711155651161003575791126377771084694335468055952546852622714675236855732821246671
710161531742221193536277786429745654447417847341056351533140338775340256930445670
70917703251685094457791663664018392482129338408492585529369298424754582519676275
26771915610345553178039135853776142367309522245320437632386545497224123755161675277
264718444600508781196553653524883446241042165519861637029423310141649010975647652
66218723417782310564606420483359518548246475586283855716914922333523586113733274
2636692187831274295817739913688351602538636635371220745709963354349850217348727
66119784407179184195609393495203567360576394384388137625154523229489485219314738279
26874859730750561544131558356219454244635037258831644312016289102560317110329737272
7292052117723234012841115212233424160538336141257820261973611549589587432568736278
26274668580242187558183398601594182373296460349332556205419614323547586207114735273
269745458131111783376105326126223825936555444836261382574172493466126145630734280
2617471584655982214592145241673746085334093193305953481814283054535841996176533651
6602177353656194345165204381621528447211500135452342363301396527185225764306666281
270694517772392431312240375190617151913243335202312155113475402389776341370749650
2606931054057715502953803023363116202341334271975161509060736442576248667530703271
536923001636317703761911575524144155554226265903395077918814776143030843613270254
6832239742353537976915542149432245439021751062310720059118676034134659323711524696
684232281183775753037683275344875734384724575994644391437596041381607239512432697
480691209378440504140501767812011594042104675775716975819342647093596639180701499
64825869529919220848132131876646396635068423623975734370845024317043460370662641
10649386903937689688687407323674274174073973141667357054234137046664312
266472876866852882522516582897282502492902482916552926535669869970047664284
Ярек Вроблевски 24 марта 2010 г.

Это панмагический квадрат 32x32. Дуэйн Кэмпбелл, используя методы бинарной конструкции, произвел этот интересный пример удержания воды.[13] Утилита GET TYPE, примененная к этому квадрату, показывает, что он обладает следующими свойствами: 1) нормальная магия 2) пандиагональ 3) изогнутая диагональ с двух сторон 4) самодополнение.[нужна цитата]

32 бимагический квадрат.png

Случайные поверхности

Задержка воды на случайной поверхности.
Задержка воды на случайной поверхности 10 уровней.
Пять уровней

Другая система, в которой изучается вопрос удержания, - это поверхность произвольной высоты. Здесь можно сопоставить случайную поверхность с перколяцией сайтов, и каждая ячейка сопоставлена ​​с сайтом на нижележащем графе или решетке, представляющей систему. С помощью теория перколяции, можно объяснить многие свойства этой системы. Это пример модели перколяции вторжения, в которой жидкость вводится в систему из любого случайного места.[14][15][16]

В гидрология, один касается стока и формирования водосборов.[17] Граница между разными водосборный бассейн (водоразделы в Северной Америке) образует дренажная перегородка с фрактальная размерность около 1,22.[18][19][20]

Проблема удержания может быть сопоставлена ​​со стандартной перколяцией.[21][22][23] Для системы из пяти равновероятных уровней, например, количество хранимой воды р5 это просто сумма воды, хранящейся в двухуровневых системах р2(p) с различной долей уровней p в низшем состоянии:

р5 = р2(1/5) + р2(2/5) + р2(3/5) + р2(4/5)

Типичные двухуровневые системы 1,2 с p = 0,2, 0,4, 0,6, 0,8 показаны справа (синий: влажный, зеленый: сухой, желтый: водосбросы, граничащие с влажными участками). Чистое удержание пятиуровневой системы - это сумма всего этого. Верхний уровень не улавливает воду, потому что он намного выше порог перколяции для квадратной решетки 0,592746.

Сохранение двухуровневой системы R2(p) - это количество воды, подключенной к водоемам, которое не касается границы системы. Когда p выше критического порога перколяции p c, будет просачивающийся кластер или пруд, который посещает всю систему. Вероятность принадлежности точки к перколяционному или «бесконечному» кластеру записывается как P в теории перколяции, и это связано с р2(p) пользователем р2(п)/L2п − п куда L это размер квадрата. Таким образом, сохранение многоуровневой системы может быть связано с известной величиной в теория перколяции.

Чтобы измерить удержание, можно использовать алгоритм затопления в котором вода поступает от границ и затопляется через самый низкий водосброс по мере повышения уровня. Удержание - это просто разница в уровне воды, на которой участок был затоплен, за вычетом высоты местности под ним.

Помимо систем дискретных уровней, описанных выше, можно сделать переменную ландшафта непрерывной переменной, скажем от 0 до 1. Точно так же можно сделать саму высоту поверхности непрерывной функцией пространственных переменных. Во всех случаях основная концепция отображения на соответствующий просачивание система остается.

Любопытный результат состоит в том, что квадратная система из n дискретных уровней может удерживать больше воды, чем система из n + 1 уровней, для достаточно большого порядка L> L *. Такое поведение можно понять с помощью теории перколяции, которую также можно использовать для оценки L * ≈ (p - pc)−ν где ν = 4/3, p = i * / n, где i * - наибольшее значение i такое, что i / n c, и pc = 0,592746 - это порог перколяции сайта для квадратной решетки. Численное моделирование дает следующие значения L *, которые экстраполируются на нецелые значения. Например, р2 < р3 для L ≤ 51, но R2 > р3 для L ≥ 52:[21]

пп + 1L *Удержание в L *
2351.12790
45198.126000
78440.3246300
910559.1502000
12131390.6428850
14151016.32607000

По мере увеличения n пересечение становится все реже и реже, и значение L *, где происходит пересечение, больше не является монотонной функцией от n.

Удержание, когда поверхность не является полностью случайной, но коррелирует с Показатель Херста H обсуждается в.[23]

Алгоритмы

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

2007 Определите все обходы без соседей от каждой внутренней ячейки к внешней, а затем отсортируйте все эти пути по наименьшему значению препятствий или ячеек. Наименьшее значение препятствия за вычетом значения внутренней ячейки обеспечивает удержание воды для этой внутренней ячейки (отрицательные значения устанавливаются на значение удерживания, равное 0). Количество оцениваемых обходов с избеганием соседей экспоненциально растет с размером квадрата и, таким образом, ограничивает эту методологию L <6.[2]

2009 Алгоритм затопления - вода поступает от границ и затопляет самый нижний водосброс по мере повышения уровня. Удержание - это просто разница в уровне воды, на которой участок был затоплен, за вычетом высоты местности под ним. Алгоритм затопления позволяет оценить задержку воды до L <10 000.[21] Этот алгоритм похож на Алгоритм наводнения Мейера который использовался при анализе топографических поверхностей.

2011 С осознанием того, что n-уровневая система может быть разбита на набор двухуровневых систем с различными вероятностями, стандартные алгоритмы перколяции могут использоваться для определения удержания как простого общего количества сайтов на нижнем уровне за вычетом областей слива. (кластеры низкоуровневых сайтов, соприкасающиеся с границей). Новое приложение Алгоритм Хошена-Копельмана в котором строки и столбцы добавляются по одной, позволяет L быть очень большим (до 109), но соображения времени вычислений ограничивают L порядка 107.[24]

Пути, по которым вода сливается с площади, используется в алгоритме обхода без соседей

Панель внизу слева направо показывает: 1) три уникальных внутренних положения квадрата 5 × 5; 2 и 4) правильные пути от квадрата серого цвета для внутренней угловой ячейки красного цвета; 3) неверный путь серого цвета, так как вода не может двигаться по диагоналям; 5) этот путь правильный, но между серыми ячейками возможно короткое замыкание. Прогулки с избеганием соседей определяют уникальные или неизбыточные пути, по которым вода сливается с площади.

Смотрите также

Рекомендации

  1. ^ https://oeis.org/A303295 OEIS A303295
  2. ^ а б c d е Крейг Кнехт, http://www.knechtmagicsquare.paulscomputing.com
  3. ^ а б Аль Циммерманн http://www.azspcs.net/Contest/MagicWater/FinalReport
  4. ^ а б c Харви Хайнц, http://www.magic-squares.net/square-update-2.htm#Knecht
  5. ^ а б Гарри Уайт, http://budshaw.ca/Download.html
  6. ^ Уолтер Трамп http://www.trump.de/magic-squares/
  7. ^ Йохан Офверстедт,http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-176018
  8. ^ Хасан М., Масбаул Алам Полаш М. (2020) Эффективный локальный поиск на основе ограничений для максимального удержания воды на магических квадратах. В: Хитендра Сарма Т., Санкар В., Шайк Р. (ред.) Новые тенденции в электротехнике, связи и информационных технологиях. Конспект лекций по электротехнике, том 569. Спрингер, Сингапур
  9. ^ Слоан, Н. Дж. А. (ред.). «Последовательность A270205 (количество плоских подмножеств 2 X 2 в кубе размером n X n X n)». В Он-лайн энциклопедия целочисленных последовательностей. Фонд OEIS.
  10. ^ Харви Хайнц,http://www.magic-squares.net/square-update.htm
  11. ^ https://www.oddmagicsquares.com
  12. ^ «Картирование области».
  13. ^ http://magictesseract.com
  14. ^ Chayes, J. T .; Л. Чайес; К. М. Ньюман (1985). «Стохастическая геометрия перколяции вторжений». Коммуникации по математической физике. 101 (3): 383–407. Bibcode:1985CMaPh.101..383C. Дои:10.1007 / BF01216096.
  15. ^ Дамрон, Майкл; Артем Сапожников; Балинт Вагвёльдьи (2009). «Отношения между перколяцией вторжения и критической перколяцией в двух измерениях». Анналы вероятности. 37 (6): 2297–2331. arXiv:0806.2425. Дои:10.1214 / 09-AOP462.
  16. ^ ван ден Берг, Якоб; Антал Джараи; Балинт Вагвёльдьи (2007). «Размер пруда в 2D проникающей инвазии». Электронные коммуникации в вероятности. 12: 411–420. arXiv:0708.4369. Bibcode:2007arXiv0708.4369V. Дои:10.1214 / ECP.v12-1327.
  17. ^ Tetzlaff, D .; McDonnell, J. J .; Уленбрук, С .; McGuire, K.J .; Bogaart, P.W .; Naef, F .; Baird, A.J .; Dunn, S.M .; Соулсби, К. (2011). «Осмысление водосборных процессов: слишком сложно?». Гидрологические процессы. 22 (11): 1727–1730. Bibcode:2008HyPr ... 22.1727T. Дои:10.1002 / hyp.7069.
  18. ^ Fehr, E .; Д. Кадау; Н. А. М. Араужо; Дж. С. Андраде-младший; Х. Дж. Херрманн (2011). «Масштабные соотношения для водоразделов». Физический обзор E. 84 (3): 036116. arXiv:1106.6200. Bibcode:2011PhRvE..84c6116F. Дои:10.1103 / PhysRevE.84.036116. PMID 22060465.
  19. ^ Schrenk, K. J .; Н. А. М. Араужо; Дж. С. Андраде-младший; Х. Дж. Херрманн (2012). «Ранжированные поверхности трещиноватости». Научные отчеты. 2: 348. arXiv:1103.3256. Bibcode:2012НатСР ... 2Е.348С. Дои:10.1038 / srep00348. ЧВК 3317236. PMID 22470841.
  20. ^ Fehr, E .; Д. Кадау; Дж. С. Андраде-младший; Х. Дж. Херрманн (2011). «Воздействие возмущений на водосборы». Письма с физическими проверками. 106 (4): 048501. arXiv:1101.5890. Bibcode:2011PhRvL.106d8501F. Дои:10.1103 / PhysRevLett.106.048501. PMID 21405368.
  21. ^ а б c Кнехт, Крейг; Уолтер Трамп; Даниил бен-Авраам; Роберт М. Зифф (2012). «Удерживающая способность случайных поверхностей». Письма с физическими проверками. 108 (4): 045703. arXiv:1110.6166. Bibcode:2012PhRvL.108d5703K. Дои:10.1103 / PhysRevLett.108.045703. PMID 22400865.
  22. ^ Пэк, Сын Ки; Бом Джун Ким (2012). «Критическое состояние модели водоудержания». Физический обзор E. 85 (3): 032103. arXiv:1111.0425. Bibcode:2012PhRvE..85c2103B. Дои:10.1103 / PhysRevE.85.032103. PMID 22587136.
  23. ^ а б Schrenk, K. J .; Н. А. М. Араужо; Р. М. Зифф; Х. Дж. Херрманн (2014). «Удерживающая способность коррелированных поверхностей». Физический обзор E. 89 (6): 062141. arXiv:1403.2082. Bibcode:2014PhRvE..89f2141S. Дои:10.1103 / PhysRevE.89.062141. PMID 25019758.
  24. ^ Хошен, Джозеф (1998). «О применении усовершенствованного алгоритма Хошена-Копельмана для анализа изображений». Письма с распознаванием образов. 19 (7): 575–584. Дои:10.1016 / S0167-8655 (98) 00018-х.

дальнейшее чтение

  • Пиковер, Клиффорд (2002). Дзен магических квадратов, кругов и звезд: выставка удивительных структур в разных измерениях. Принстон, Нью-Джерси: Издательство Принстонского университета. ISBN 978-0-691-11597-9.
  • Штауфер, Дитрих; Ахарони, А. (1994). Введение в теорию перколяции. Лондон Бристоль, Пенсильвания: Тейлор и Фрэнсис. ISBN 978-0-7484-0253-3.

внешняя ссылка