В математике складывания бумаги складывание карты и складывание марки — это две задачи на подсчет количества способов, которыми можно сложить лист бумаги. В задаче складывания марки бумага представляет собой полоску марок со сгибами между ними, и сгибы должны лежать на сгибах. В задаче складывания карты бумага представляет собой карту, разделенную сгибами на прямоугольники, и сгибы должны снова лежать только вдоль этих сгибов.
Лукас (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 марок задается последовательностью
Эти числа всегда делятся на n (потому что циклическая перестановка складной последовательности марок сама по себе всегда складная), [3] [4] и частные этого деления равны
число топологически различных способов, которыми полубесконечная кривая может сделать n пересечений с линией, называемых «полумеандрами». Они тесно связаны с меандрами , способами, которыми замкнутая кривая может сделать то же самое число пересечений с линией. Меандры соответствуют решениям задачи о складывании штампа, в которой первый и последний штамп могут быть соединены друг с другом, образуя непрерывную петлю штампов.
В 1960-х годах Джон Э. Келер и У. Ф. Ланнон реализовали алгоритмы , которые в то время могли вычислять эти числа для 28 марок. [5] [6] [7] Несмотря на дополнительные исследования, известные методы вычисления этих чисел требуют экспоненциального времени как функции от n . [8] [9] Таким образом, не существует формулы или эффективного алгоритма, которые могли бы расширить эту последовательность до очень больших значений n . Тем не менее, эвристические методы из физики могут быть использованы для прогнозирования скорости экспоненциального роста этой последовательности. [10]
Задача о складывании штампа обычно рассматривает только количество возможных сложенных состояний полосы штампов, не принимая во внимание, возможно ли физически построить складку последовательностью ходов, начиная с развернутой полосы штампов. Однако, согласно решению задачи о правиле плотника , каждое сложенное состояние может быть построено (или, что эквивалентно, может быть развернуто). [11]
В другом варианте задачи о складывании марок полоса марок считается пустой, так что невозможно отличить один из ее концов от другого, и два сложения считаются различными, только если они имеют разную форму. Переворачивание сложенной полосы вверх дном или задом наперед не считается изменением ее формы, поэтому три марки имеют только два сложения, S-образную кривую и спираль. [3] В более общем смысле, количество сложений с этим определением равно
Складывание карты — это вопрос о том, сколько существует способов сложить прямоугольную карту вдоль ее складок, позволяя каждой складке сформировать либо гору, либо долину. Это отличается от сгибания штампа тем, что включает в себя как вертикальные, так и горизонтальные складки, а не только складки в одном направлении. [12]
Существует восемь способов сложить карту 2 × 2 вдоль ее складок, считая каждую различную вертикальную последовательность сложенных квадратов отдельным способом складывания карты: [5]
Однако общая задача подсчета количества способов сложить карту остается нерешенной. Количество способов сложить карту n × n известно только для n ≤ 7. Они таковы:
Задачи складывания карты и складывания марки связаны с проблемой в математике оригами , можно ли сложить квадрат с рисунком сгиба в плоскую фигуру. Если направление складывания (либо складка горой , либо складка долиной ) назначается каждому сгибу полосы марок, можно проверить, можно ли сложить результат в плоскую форму за полиномиальное время . [13]
Для той же задачи на карте (разделенной на прямоугольники сгибами с заданными направлениями) неизвестно, существует ли вообще алгоритм складывания за полиномиальное время, хотя для карт 2 × n известен полиномиальный алгоритм . [14] В ограниченном случае, когда карту нужно сложить последовательностью «простых» сгибов, которые сгибают бумагу вдоль одной линии, задача является полиномиальной. Некоторые расширения задачи, например, на непрямоугольные листы бумаги, являются NP-полными . [13]
Даже для одномерной полосы марок, складки которой уже обозначены как складки «горы» или «долины», NP-трудно найти способ сложить ее так, чтобы максимальное количество марок, которые лежат между двумя марками любой складки, было минимальным. [15]