Складывание карты
В математике складывания бумаги складывание карты и складывание марки — это две задачи подсчета количества способов, которыми можно сложить лист бумаги. В задаче о складывании марок бумага представляет собой полосу марок со складками между ними, причем складки должны лежать на складках. В задаче о складывании карты бумага представляет собой карту, разделенную складками на прямоугольники, причем складки опять же должны лежать только по этим складкам.
Лукас (1891) приписывает изобретение проблемы складывания марок Эмилю Лемуану . [1] Тушар (1950) приводит еще несколько ранних упоминаний. [2]
Маркированные марки
[ редактировать ]В задаче о складывании марок сгибаемая бумага представляет собой полосу квадратных или прямоугольных марок, разделенных складками, и марки можно сгибать только вдоль этих складок.В одном обычно рассматриваемом варианте проблемы каждая марка считается отличной друг от друга, поэтому два сгиба полосы марок считаются эквивалентными только тогда, когда они имеют одинаковую вертикальную последовательность марок. [3] Например, существует шесть способов сложить полоску из трех разных марок:
К ним относятся все шесть комбинаций марок, но для более чем трех марок не все комбинации возможны. Если для перестановки 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 пересечений с линией, называемых «полумеандрами». Они тесно связаны с меандрами — способами, позволяющими замкнутой кривой совершать одинаковое количество пересечений с линией. Меандры соответствуют решению задачи складывания марок, в которой первая и последняя марки могут быть соединены друг с другом, образуя непрерывную петлю марок.
В 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]
Однако общая проблема подсчета количества способов сложения карты остается нерешенной. Число способов сложения карты размера n × n известно только для n ≤ 7 . Они есть:
Сложность
[ редактировать ]Проблемы складывания карт и штампов связаны с математической задачей оригами : можно ли сложить квадрат со складками в плоскую фигуру.Если каждой складке полосы марок присвоено направление сгиба (либо горный , либо долинный сгиб ), можно проверить, можно ли сложить результат ровно за полиномиальное время . [13]
Для той же задачи на карте (разделенной на прямоугольники складками с заданными направлениями) неизвестно, существует ли вообще алгоритм свертывания за полиномиальное время:хотя известен полиномиальный алгоритм для карт размера 2 × n . [14] В ограниченном случае, когда карту необходимо сложить с помощью последовательности «простых» складок, которые складывают бумагу по одной линии, задача является полиномиальной.Некоторые расширения задачи, например, на непрямоугольные листы бумаги, являются NP-полными . [13]
Даже для одномерной полосы марок со складками, уже помеченными как складки горы или долины, NP-трудно найти способ сложить ее, который минимизирует максимальное количество марок, лежащих между двумя марками любой складки. [15]
См. также
[ редактировать ]- Обычная последовательность складывания бумаги , бесконечная последовательность нулей и единиц, описывающая один из способов складывания полосок марок.
Ссылки
[ редактировать ]- ^ Лукас, Эдуард (1891), Теория чисел (на французском языке), том. Я, Париж: Готье-Виллар, с. 120 .
- ^ Тушар, Жак (1950), «Вклад в изучение проблемы почтовых марок», Canadian Journal of Mathematics (на французском языке), 2 : 385–398, doi : 10.4153/CJM-1950-035-6 , MR 0037815 , S2CID 124708270 .
- ^ Jump up to: а б с д Лежандр, Стефан (2014), «Складки и меандры», Австралазийский журнал комбинаторики , 58 : 275–291, arXiv : 1302.2025 , Bibcode : 2013arXiv1302.2025L , MR 3211783
- ^ Сент-Лаге, Андре (1937), С цифрами и линиями (на французском языке), Париж: Vuibert, стр. 147–162 . Цитируется Лежандром (2014).
- ^ Jump up to: а б Гарднер, Мартин (1983), «Комбинаторика складывания бумаги», « Колеса, жизнь и другие математические развлечения » , Нью-Йорк: WH Freeman, стр. 60–73, Бибкод : 1983wlom.book.....G . См., в частности, стр. 60–62.
- ^ Келер, Джон Э. (1968), «Складывание полосы марок», Журнал комбинаторной теории , 5 (2): 135–152, doi : 10.1016/S0021-9800(68)80048-1 , MR 0228364
- ^ Ланнон, В.Ф. (1968), «Проблема складывания карт», Mathematics of Computation , 22 (101): 193–199, doi : 10.2307/2004779 , JSTOR 2004779 , MR 0221957
- ^ Дженсен, Иван (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 , S2CID 14259684
- ^ Савада, Джо; Ли, Рой (2012), «Складки штампов, полумеандры и открытые меандры: алгоритмы быстрой генерации» , Electronic Journal of Combinatorics , 19 (2): Paper 43, 16pp, doi : 10.37236/2404 , MR 2946101
- ^ Ди Франческо, П. (2000), «Точная асимптотика чисел меандра», Формальные степенные ряды и алгебраическая комбинаторика (Москва, 2000) , Springer, Berlin, стр. 3–14, doi : 10.1007/978-3-662-04166 -6_1 , ISBN 978-3-642-08662-5 , МР 1798197
- ^ Коннелли, Роберт ; Демейн, Эрик Д .; Роте, Гюнтер (2003), «Выпрямление многоугольных дуг и выпуклость многоугольных циклов» (PDF) , Дискретная и вычислительная геометрия , 30 (2): 205–239, doi : 10.1007/s00454-003-0006-7 , MR 1931840
- ^ Ланнон, В.Ф. (1971), «Многомерное складывание карт», The Computer Journal , 14 : 75–80, doi : 10.1093/comjnl/14.1.75 , MR 0285409
- ^ Jump up to: а б Аркин, Эстер М .; Бендер, Майкл А.; Демейн, Эрик Д .; Демейн, Мартин Л .; Митчелл, Джозеф С.Б .; Сетия, Саураб; Скиена, Стивен С. (сентябрь 2004 г.), «Когда можно сложить карту?» (PDF) , Вычислительная геометрия: теория и приложения , 29 (1): 23–46, doi : 10.1016/j.comgeo.2004.03.012 .
- ^ Морган, Томас Д. (21 мая 2012 г.), Складывание карт (Диссертация), магистерская диссертация, Массачусетский технологический институт, факультет электротехники и информатики, hdl : 1721.1/77030
- ^ Умесато, Такуя; Сайто, Тошики; Уэхара, Рюхей; Ито, Хиро; Окамото, Ёсио (2013), «Сложность проблемы складывания марок», Theoretical Computer Science , 497 : 13–19, doi : 10.1016/j.tcs.2012.08.006 , MR 3084129
Внешние ссылки
[ редактировать ]- Вайсштейн, Эрик В. , « Складывание карты » (« Складывание штампа ») в MathWorld .
- «Складывание полоски марок с этикетками» из демонстрационного проекта Wolfram: http://demonstrations.wolfram.com/FoldingAStripOfLabeledStamps/