En las matemáticas del plegado de papel , el plegado de mapas y el plegado de sellos son dos problemas que consisten en contar la cantidad de formas en que se puede doblar un trozo de papel. En el problema del plegado de sellos, el papel es una tira de sellos con pliegues entre ellos, y los pliegues deben estar sobre los pliegues. En el problema del plegado de mapas, el papel es un mapa, dividido por pliegues en rectángulos, y los pliegues deben estar nuevamente solo a lo largo de estos pliegues.
Lucas (1891) atribuye la invención del problema del plegado de sellos a Émile Lemoine . [1] Touchard (1950) proporciona varias otras referencias tempranas. [2]
En el problema de plegado de sellos, el papel que se va a doblar es una tira de sellos cuadrados o rectangulares, separados por pliegues, y los sellos solo se pueden doblar a lo largo de esos pliegues. En una versión comúnmente considerada del problema, se considera que cada sello se puede distinguir de los demás, por lo que dos pliegues de una tira de sellos se consideran equivalentes solo cuando tienen la misma secuencia vertical de sellos. [3] Por ejemplo, hay seis formas de doblar una tira de tres sellos diferentes:
Estas incluyen las seis permutaciones de los sellos, pero para más de tres sellos no todas las permutaciones son posibles. Si, para una permutación p , hay dos números i y j con la misma paridad tales que los cuatro números i , j , i + 1 y j + 1 aparecen en p en ese orden cíclico , entonces p no se puede doblar. La condición de paridad implica que los pliegues entre los sellos i e i + 1 , y entre los sellos j y j + 1 , aparecen en el mismo lado de la pila de sellos doblados, pero la condición de orden cíclico implica que estos dos pliegues se cruzan entre sí, una imposibilidad física. Por ejemplo, la permutación de cuatro elementos 1324 no se puede doblar, porque tiene este patrón prohibido con i = 1 y j = 3 . Todas las permutaciones restantes, sin este patrón, se pueden doblar. [3] El número de formas diferentes de doblar una tira de n sellos está dado por la secuencia
Estos números son siempre divisibles por n (porque una permutación cíclica de una secuencia de sellos plegables siempre es en sí misma plegable), [3] [4] y los cocientes de esta división son
el número de formas topológicamente distintas en que una curva semiinfinita puede hacer n cruces con una línea, llamados "semimeandros". Estos están estrechamente relacionados con los meandros , formas en que una curva cerrada puede hacer el mismo número de cruces con una línea. Los meandros corresponden a soluciones del problema del plegado de sellos en el que el primer y el último sello se pueden conectar entre sí para formar un bucle continuo de sellos.
En la década de 1960, John E. Koehler y WF Lunnon implementaron algoritmos que, en ese momento, podían calcular estos números para hasta 28 sellos. [5] [6] [7] A pesar de la investigación adicional, los métodos conocidos para calcular estos números toman un tiempo exponencial en función de n . [8] [9] Por lo tanto, no se conoce ninguna fórmula o algoritmo eficiente que pueda extender esta secuencia a valores muy grandes de n . Sin embargo, se pueden utilizar métodos heurísticos de la física para predecir la tasa de crecimiento exponencial de esta secuencia. [10]
El problema del plegado de sellos generalmente considera únicamente el número de posibles estados plegados de la tira de sellos, sin considerar si es posible construir físicamente el pliegue mediante una secuencia de movimientos a partir de una tira de sellos desplegada. Sin embargo, de acuerdo con la solución del problema de la regla del carpintero , cada estado plegado puede construirse (o equivalentemente, puede desplegarse). [11]
En otra variación del problema de plegado de sellos, la tira de sellos se considera en blanco, de modo que no es posible distinguir uno de sus extremos del otro, y dos pliegues se consideran distintos solo cuando tienen formas diferentes. Dar vuelta una tira doblada al revés o al revés no se considera que cambie su forma, por lo que tres sellos tienen solo dos pliegues, una curva en S y una espiral. [3] De manera más general, el número de pliegues con esta definición es
El plegado de mapas es la cuestión de cuántas maneras hay de doblar un mapa rectangular a lo largo de sus pliegues, permitiendo que cada pliegue forme un pliegue de montaña o de valle. Se diferencia del plegado de sellos en que incluye pliegues tanto verticales como horizontales, en lugar de solo pliegues en una sola dirección. [12]
Hay ocho maneras de doblar un mapa de 2 × 2 a lo largo de sus pliegues, contando cada secuencia vertical diferente de cuadrados doblados como una forma distinta de doblar el mapa: [5]
Sin embargo, el problema general de contar la cantidad de formas de plegar una función sigue sin resolverse. La cantidad de formas de plegar una función n × n se conoce solo para n ≤ 7. Son:
Los problemas de plegado de mapas y sellos están relacionados con un problema matemático del origami que consiste en determinar si un cuadrado con un patrón de pliegues se puede doblar hasta formar una figura plana. Si se asigna una dirección de plegado (ya sea un pliegue de montaña o un pliegue de valle ) a cada pliegue de una tira de sellos, es posible comprobar si el resultado se puede doblar hasta quedar plano en tiempo polinomial . [13]
Para el mismo problema en un mapa (dividido en rectángulos por pliegues con direcciones asignadas) se desconoce si existe un algoritmo de plegado en tiempo polinomial en general, aunque se conoce un algoritmo polinomial para mapas 2 × n . [14] En un caso restringido donde el mapa se debe plegar mediante una secuencia de pliegues "simples", que pliegan el papel a lo largo de una sola línea, el problema es polinomial. Algunas extensiones del problema, por ejemplo a hojas de papel no rectangulares, son NP-completas . [13]
Incluso para una tira unidimensional de sellos, con sus pliegues ya etiquetados como pliegues de montaña o de valle, es NP-difícil encontrar una forma de doblarla que minimice el número máximo de sellos que se encuentran entre los dos sellos de cualquier pliegue. [15]