Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

Лукас (1891) приписывает изобретение проблемы складывания штампа Эмилю Лемуану . [1] Тушар (1950) приводит несколько других ранних ссылок. [2]

Маркированные марки [ править ]

В задаче сгиба штампа сгибаемая бумага представляет собой полосу квадратных или прямоугольных штампов, разделенных складками, и штампы можно складывать только по этим складкам. В одной из общепринятых версий задачи считается, что каждая марка отличается от другой марки, поэтому два сгиба полосы марок считаются эквивалентными только тогда, когда они имеют одинаковую вертикальную последовательность марок. [3] Например, есть шесть способов сложить полосу из трех разных марок:

Stampfoldings1x3.png

К ним относятся все шесть перестановок марок, но для более чем трех марок возможны не все перестановки. Если для перестановки p есть два числа i и j с одинаковой четностью, такие что четыре числа i , j , i + 1 и j + 1 появляются в p в этом циклическом порядке , то p не может быть свернут. Условие четности подразумевает, что складки между марками i и i + 1 , а также между марками j и j + 1, появляются на одной стороне стопки сложенных марок, но условие циклического упорядочения подразумевает, что эти две складки пересекаются друг с другом, что физически невозможно. Например, четырехэлементная перестановка 1324 не может быть свернута, потому что она имеет этот запрещенный образец с i = 1 и j = 3 . Все остальные перестановки, без этого шаблона, можно складывать. [3] Количество различных способов сложить ленту из n марок задается последовательностью

1, 2, 6, 16, 50, 144, 462, 1392, 4536, 14060, 46310, 146376, 485914, 1557892, 5202690, ... (последовательность A000136 в OEIS ).

Эти числа всегда делятся на n (поскольку циклическая перестановка последовательности складываемых штампов всегда сама складывается), [3] [4], а частные этого деления равны

1, 1, 2, 4, 10, 24, 66, 174, 504, 1406, 4210, 12198, 37378, 111278, 346846, 1053874, ... (последовательность A000682 в OEIS ),

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

Вопрос, Web Fundamentals.svgНерешенная задача по математике :
Есть ли формула или алгоритм с полиномиальным временем для подсчета решений проблемы складывания штампа?
(больше нерешенных задач по математике)

В 1960-х годах Джон Э. Келер и У. Ф. Ланнон реализовали алгоритмы, которые в то время могли рассчитывать эти числа для 28 марок. [5] [6] [7] Несмотря на дополнительные исследования, известные методы вычисления этих чисел принимают экспоненциальную зависимость времени от n . [8] [9] Таким образом, не существует известной формулы или эффективного алгоритма, который мог бы расширить эту последовательность до очень больших значений n . Тем не менее, эвристические методы из физики могут использоваться для предсказания скорости экспоненциального роста этой последовательности. [10]

Задача сгиба штампа обычно рассматривает только количество возможных состояний сгиба полосы штампов, не учитывая, возможно ли физически построить сгиб последовательностью движений, начиная с развернутой полосы штампов. Однако, согласно решению проблемы правила плотника , каждое сложенное состояние может быть построено (или, что эквивалентно, может быть развернуто). [11]

Марки без ярлыка [ править ]

В другом варианте задачи фальцовки штампа полоса штампов считается пустой, так что невозможно отличить один из ее концов от другого, и два фальца считаются разными, только если они имеют разные формы. Переворачивание сложенной полосы вверх ногами или изнаночной стороной вперед не считается изменением ее формы, поэтому три марки имеют только два сгиба, S-образную форму и спираль. [3] В более общем смысле, количество складок с этим определением равно

1, 1, 2, 5, 14, 38, 120, 353, 1148, 3527, 11622, 36627, 121622, 389560, 1301140, 4215748, ... (последовательность A001011 в OEIS )

Карты [ править ]

Складывание карты - это вопрос о том, сколькими способами можно сложить прямоугольную карту вдоль ее складок, чтобы каждая складка образовывала складку горы или долины. Он отличается от складывания штампа тем, что включает в себя как вертикальные, так и горизонтальные складки, а не только складки в одном направлении. [12]

Есть восемь способов сложить карту 2 × 2 вдоль ее складок, считая каждую вертикальную последовательность сложенных квадратов отдельным способом складывания карты: [5]

MapFoldings-2x2.png

Однако общая проблема подсчета количества способов сложить карту остается нерешенной. Количество способов сворачивания карты n × n известно только для n ≤ 7 . Они есть:

1, 8, 1368, 300608, 186086600, 123912532224, 129950723279272 (последовательность A001418 в OEIS ).

Сложность [ править ]

Вопрос, Web Fundamentals.svgНерешенная задача по математике :
Учитывая назначение складок карты горной долине, можно ли эффективно проверить, можно ли ее сложить?
(больше нерешенных задач по математике)

Проблемы складывания карты и штампа связаны с проблемой математики оригами : можно ли сложить квадрат со складками в плоскую фигуру. Если направление складывания ( горная складка или складка долины ) назначено каждой складке полосы марок, можно проверить, можно ли сложить результат за полиномиальное время . [13]

Для той же задачи на карте (разделенной на прямоугольники складками с заданными направлениями) неизвестно, существует ли вообще алгоритм полиномиального сворачивания по времени, хотя полиномиальный алгоритм известен для карт 2 × n . [14] В ограниченном случае, когда карта должна быть сложена последовательностью «простых» складок, которые складывают бумагу вдоль одной линии, проблема является полиномиальной. Некоторые расширения проблемы, например, на непрямоугольные листы бумаги, являются NP-полными . [13]

Даже для одномерной полосы марок, сгибы которой уже обозначены как складки гор или долин, NP-сложно найти способ сложить ее, минимизирующий максимальное количество штампов, которые лежат между двумя марками любой складки. [15]

См. Также [ править ]

  • Обычная последовательность складывания бумаги , бесконечная последовательность нулей и единиц, описывающая один способ складывания полосок марок.

Ссылки [ править ]

  1. ↑ Лукас, Эдуард (1891), Теория номеров (на французском языке), I , Париж: Готье-Виллар, стр. 120.
  2. ^ Тушар Жак (1950), "Вклад à l'Etude дю problème де тембры Poste", Canadian Journal математики (на французском языке), 2 : 385-398, DOI : 10,4153 / CJM-1950-035-6 , MR 0037815 .
  3. ^ a b c d Лежандр, Стефан (2014), «Складки и меандры», Австралазийский журнал комбинаторики , 58 : 275–291, arXiv : 1302.2025 , Bibcode : 2013arXiv1302.2025L , MR 3211783 
  4. ^ Сент-Lague, Андре (1937), Avec де nombres и др дез Lignes (на французском языке), Париж:. Vuibert, стр 147-162. Цитируется по Legendre (2014)
  5. ^ a b Гарднер, Мартин (1983), "Комбинаторика складывания бумаги", Колеса, жизнь и другие математические развлечения , Нью-Йорк: WH Freeman, стр. 60–73, Bibcode : 1983wlom.book ..... G. См., В частности, стр. 60–62.
  6. ^ Koehler, Джон Е. (1968), "Раскладной полосу марок", Журнал комбинаторной теории , 5 (2): 135-152, DOI : 10.1016 / S0021-9800 (68) 80048-1 , МР 0228364 
  7. ^ Lunnon, WF (1968), "Проблема с картой складывания", Математика вычислений , 22 (101): 193-199, DOI : 10,2307 / 2004779 , JSTOR 2004779 , МР 0221957  
  8. ^ Дженсен, Иван (2000), "Матричный подход к подсчету плоских меандров" , Journal of Physics A: Mathematical and General , 33 (34): 5953, arXiv : cond-mat / 0008178 , Bibcode : 2000JPhA .. .33.5953J , DOI : 10,1088 / 0305-4470 / 33 / 34/301
  9. ^ Савада, Джо; Ли, Рой (2012), «Складывание штампов, полумеандры и открытые меандры: алгоритмы быстрой генерации» , Электронный журнал комбинаторики , 19 (2): Paper 43, 16pp, MR 2946101 
  10. ^ Ди Франческо, П. (2000), "Точная асимптотика меандровых чисел", Формальные степенные ряды и алгебраическая комбинаторика (Москва, 2000) , Springer, Берлин, стр. 3–14, DOI : 10.1007 / 978-3-662- 04166-6_1 , ISBN 978-3-642-08662-5, MR  1798197
  11. ^ Коннелли, Роберт ; Демейн, Эрик Д .; Рота, Гюнтер (2003), "Правильная ломаные и овыпуклений многоугольных циклов" (PDF) , Дискретная и Вычислительная геометрия , 30 (2): 205-239, DOI : 10.1007 / s00454-003-0006-7 , МР 1931840  
  12. ^ Lunnon, WF (1971), "Многомерная карта складывания", Компьютер Journal , 14 : 75-80, DOI : 10,1093 / comjnl / 14.1.75 , MR 0285409 
  13. ^ a b Аркин, Эстер М .; Бендер, Майкл А .; Демейн, Эрик Д .; Демейн, Мартин Л .; Митчелл, Джозеф SB ; Сетия, Саураб; Скиена, Стивен С. (сентябрь 2004 г.), "Когда можно сложить карту?" (PDF) , Вычислительная геометрия: теория и приложения , 29 (1): 23-46, DOI : 10.1016 / j.comgeo.2004.03.012 .
  14. ^ Морган, Томас Д. (21 мая 2012 г.), складывание карт , магистерская диссертация, Массачусетский технологический институт, факультет электротехники и информатики
  15. ^ Умесато, Такуя; Сайто, Тошики; Уэхара, Рюхей; Ито, Хиро; Окамото, Yoshio (2013), "Сложность складных проблемы штемпеля", Теоретическая информатика , 497 : 13-19, DOI : 10.1016 / j.tcs.2012.08.006 , MR 3084129 

Внешние ссылки [ править ]

  • Эрик В. Вайсштейн , Складывание карт ( складывание штампов ) в MathWorld .
  • «Складывание полосы маркированных марок» из демонстрационного проекта Вольфрама: http://demonstrations.wolfram.com/FoldingAStripOfLabeledStamps/