En las matemáticas del plegado de papel , el plegado de mapas y el plegado de sellos son dos problemas de contar el número de formas en que se puede plegar una hoja 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 de plegado del mapa, 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]
Sellos etiquetados
En el problema del plegado de sellos, el papel 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, cada sello se considera distinguible entre 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:
Estos incluyen las seis permutaciones de los sellos, pero para más de tres sellos no son posibles todas las permutaciones. Si, para una permutación p , hay dos números i y j con la misma paridad de modo 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 plegar. 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 de cuatro elementos de permutación 1324 no puede ser doblado, porque tiene este patrón prohibido con i = 1 y j = 3 . Todas las permutaciones restantes, sin este patrón, se pueden plegar. [3] El número de formas diferentes de doblar una tira de n sellos viene dado por la secuencia
- 1, 2, 6, 16, 50, 144, 462, 1392, 4536, 14060, 46310, 146376, 485914, 1557892, 5202690, ... (secuencia A000136 en la OEIS ).
Estos números siempre son divisibles por n (porque una permutación cíclica de una secuencia de sello plegable siempre es en sí misma plegable), [3] [4] y los cocientes de esta división son
- 1, 1, 2, 4, 10, 24, 66, 174, 504, 1406, 4210, 12198, 37378, 111278, 346846, 1053874, ... (secuencia A000682 en la OEIS ),
el número de formas topológicamente distintas en las que una curva semiinfinita puede hacer n cruces con una línea, denominados "semimedios".
¿Existe una fórmula o un algoritmo de tiempo polinomial para contar las soluciones al problema del plegado del sello?
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 . No obstante, 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 solo el número de posibles estados de plegado 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 se puede construir (o de manera equivalente, se puede desplegar). [11]
Sellos sin etiqueta
En otra variación del problema del plegado de sellos, se considera que la tira de sellos está 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. No se considera que girar una tira doblada al revés o de atrás hacia adelante 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
Mapas
El plegado de mapas es la cuestión de cuántas formas 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 formas de doblar un mapa de 2 × 2 a lo largo de sus pliegues, contando cada secuencia vertical diferente de cuadrados plegados como una forma distinta de doblar el mapa: [5]
Sin embargo, el problema general de contar el número de formas de plegar un mapa sigue sin resolverse. El número de formas de plegar un mapa n × n se conoce solo para n ≤ 7 . Ellos son:
Complejidad
Dada una asignación de montaña-valle para los pliegues de un mapa, ¿es posible probar de manera eficiente si se puede plegar en plano?
Los problemas de plegado de mapas y plegado de sellos están relacionados con un problema en las matemáticas del origami de si un cuadrado con un patrón de pliegue se puede plegar en 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 probar si el resultado se puede plegar 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 de tiempo polinomial en general, aunque se conoce un algoritmo polinomial para mapas 2 × n . [14] En un caso restringido en el que el mapa debe doblarse 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, las hojas de papel no rectangulares, son NP-completas . [13]
Incluso para una tira de sellos unidimensional, con sus pliegues ya etiquetados como pliegues de montaña o valle, es NP-difícil encontrar una manera de doblarla que minimice el número máximo de sellos que se encuentran entre los dos sellos de cualquier pliegue. [15]
Ver también
- Secuencia de plegado de papel regular , una secuencia infinita de 0 y 1 que describe una forma de doblar tiras de sellos
Referencias
- ^ Lucas, Édouard (1891), Théorie des nombres (en francés), I , París: Gauthier-Villars, p. 120.
- ^ Touchard, Jacques (1950), "Contribution à l'étude du problème des timbres poste", Canadian Journal of Mathematics (en francés), 2 : 385–398, doi : 10.4153 / CJM-1950-035-6 , MR 0037815.
- ^ a b c d Legendre, Stéphane (2014), "Foldings and meandros", The Australasian Journal of Combinatorics , 58 : 275–291, arXiv : 1302.2025 , Bibcode : 2013arXiv1302.2025L , MR 3211783
- ^ Sainte-Laguë, André (1937), Avec des nombres et des lignes (en francés), París: Vuibert, págs. 147-162. Citado por Legendre (2014)
- ^ a b Gardner, Martin (1983), "La combinatoria del plegado de papel", Wheels, Life and Other Mathematical Amusements , Nueva York: WH Freeman, pp. 60-73, Bibcode : 1983wlom.book ..... G. Véanse en particular las págs. 60–62.
- ^ Koehler, John E. (1968), "Doblar una tira de sellos", Journal of Combinatorial Theory , 5 (2): 135-152, doi : 10.1016 / S0021-9800 (68) 80048-1 , MR 0228364
- ^ Lunnon, WF (1968), "Un problema de plegado de mapas", Mathematics of Computation , 22 (101): 193-199, doi : 10.2307 / 2004779 , JSTOR 2004779 , MR 0221957
- ^ Jensen, Iwan (2000), "Un enfoque de matriz de transferencia para la enumeración de meandros planos" , 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
- ^ Sawada, Joe; Li, Roy (2012), "Sellos plegables, semi-meandros y meandros abiertos: algoritmos de generación rápida" , Electronic Journal of Combinatorics , 19 (2): Paper 43, 16pp, doi : 10.37236 / 2404 , MR 2946101
- ^ Di Francesco, P. (2000), "Asintótica exacta de números de meandro", Serie de potencias formales y combinatoria algebraica (Moscú, 2000) , Springer, Berlín, págs. 3-14, doi : 10.1007 / 978-3-662-04166 -6_1 , ISBN 978-3-642-08662-5, Señor 1798197
- ^ Connelly, Robert ; Demaine, Erik D .; Rote, Günter (2003), "Enderezar arcos poligonales y convexificar ciclos poligonales" (PDF) , Geometría discreta y computacional , 30 (2): 205-239, doi : 10.1007 / s00454-003-0006-7 , MR 1931840
- ^ Lunnon, WF (1971), "Plegado de mapas multidimensional", The Computer Journal , 14 : 75–80, doi : 10.1093 / comjnl / 14.1.75 , MR 0285409
- ^ a b Arkin, Esther M .; Bender, Michael A .; Demaine, Erik D .; Demaine, Martin L .; Mitchell, Joseph SB ; Sethia, Saurabh; Skiena, Steven S. (septiembre de 2004), "¿Cuándo se puede doblar un mapa?" (PDF) , Geometría computacional: teoría y aplicaciones , 29 (1): 23–46, doi : 10.1016 / j.comgeo.2004.03.012.
- ^ Morgan, Thomas D. (21 de mayo de 2012), plegado de mapas (tesis), tesis de maestría, Instituto de Tecnología de Massachusetts, Departamento de Ingeniería Eléctrica y Ciencias de la Computación, hdl : 1721.1 / 77030
- ^ Umesato, Takuya; Saitoh, Toshiki; Uehara, Ryuhei; Ito, Hiro; Okamoto, Yoshio (2013), "La complejidad del problema de plegado de sellos", Informática teórica , 497 : 13-19, doi : 10.1016 / j.tcs.2012.08.006 , MR 3084129
enlaces externos
- Eric W. Weisstein , Map Folding ( Stamp Folding ) en MathWorld .
- "Doblar una tira de sellos etiquetados" del Proyecto de demostraciones Wolfram: http://demonstrations.wolfram.com/FoldingAStripOfLa labelStamps/