地図の折りたたみ
紙折りの数学における概念

紙折りの数学において、地図折りと切手折りは、一枚の紙を折る方法の数を数える2つの問題です。切手折りの問題では、紙は切手が束ねられた細長いもので、その間に折り目があり、折り目は必ず折り目に沿っていなければなりません。地図折りの問題では、紙は地図で、折り目によって長方形に分割されており、折り目もこれらの折り目に沿っていなければなりません。

ルーカス（1891）は、切手折り問題の発明をエミール・ルモワーヌに帰しています。[1]タッチャード（1950）は、他にもいくつかの初期の参考文献を提供しています。[2]

ラベル付き切手

切手折り問題では、折るべき紙は正方形または長方形の切手が折り目によって区切られた帯状の紙であり、切手はこれらの折り目に沿ってのみ折ることができます。この問題の一般的なバージョンの一つでは、各切手は互いに区別可能であるとみなされるため、切手帯を2回折った場合、切手の縦方向の並びが同じである場合にのみ、同じ折り方とみなされます。[3] 例えば、3種類の異なる切手が1枚ずつ入った帯状の紙を折るには、以下の6通りの折り方があります。

これらには切手の6通りの順列すべてが含まれるが、切手が4枚を超える場合はすべての順列が可能であるわけではない。順列pにおいて、同じ奇偶を持つ2つの数iとjがあり、 i、j、i + 1、j + 1の4つの数がその循環順序でpに現れる場合、p は折りたたむことができない。奇偶条件は、切手iとi + 1の間、および切手jとj + 1の間の折り目が、折りたたまれた切手の山の同じ側に現れることを意味するが、循環順序条件は、これらの2つの折り目が互いに交差することを意味し、物理的に不可能である。例えば、4要素順列 1324 は、i = 1かつj = 3のこの禁制パターンを持つため折りたたむことができない。このパターンを持たない残りの順列はすべて折りたたむことができる。[3] n枚 の切手の帯を折りたたむ異なる折り方の数は、次の数列で与えられる。

1、2、6、16、50、144、462、1392、4536、14060、46310、146376、485914、1557892、5202690、...（OEISのシーケンスA000136）。

これらの数は常にnで割り切れる（折り畳み可能な切手列の巡回順列は常にそれ自体が折り畳み可能であるため） [3] [4]。そしてこの割り算の商は

1、1、2、4、10、24、66、174、504、1406、4210、12198、37378、111278、346846、1053874、…（OEISの配列A000682）、

半無限曲線が直線とn回交差する位相的に異なる方法の数。これは「セミメアンダー」と呼ばれます。これは、閉曲線が直線と同数の交差をするメアンダーと密接に関連しています。メアンダーは、切手折り問題において、最初の切手と最後の切手を繋いで連続したループを形成する解に対応します。

数学における未解決問題
切手折り問題の解を数える公式または多項式時間アルゴリズムはありますか?
数学におけるさらなる未解決問題

1960年代、ジョン・E・ケーラーとWF・ラノンは、当時としては最大28枚の切手に対してこれらの数値を計算できるアルゴリズムを実装しました。 [5] [6] [7] さらなる研究にもかかわらず、これらの数値を計算する既知の方法は、nの関数として指数関数的な時間がかかります。[8] [9]したがって、この数列を非常に大きなn の値に拡張できる公式や効率的なアルゴリズムは知られていません。しかしながら、物理学のヒューリスティックな手法を用いて、この数列の指数関数的増加率を予測することは可能です。[10]

切手折り問題では通常、切手帯の折り畳み状態の数のみを考慮し、展開された切手帯から一連の動作によって物理的に折り畳み状態を構築できるかどうかは考慮しません。しかし、カーペンターの規則問題の解によれば、あらゆる折り畳み状態を構築できる（あるいは、展開できる）ことが分かります。[11]

ラベルのない切手

切手折り問題の別のバリエーションでは、切手帯は空白とみなされ、その両端を区別することができず、2つの折り目は異なる形状を持つ場合にのみ別個のものとみなされます。折り畳まれた帯を上下逆さまにしたり、裏表逆にしたりしても形状は変化しないと考えられているため、3枚の切手にはS字カーブと螺旋の2つの折り目しかありません。[3]より一般的には、この定義による折り目の数は

1、1、2、5、14、38、120、353、1148、3527、11622、36627、121622、389560、1301140、4215748、…（OEISのシーケンスA001011）

地図

地図折りとは、長方形の地図を折り目に沿って何通りの折り方があり、それぞれの折り目が山折りまたは谷折りになるかという問題です。切手折りとは異なり、地図折りでは縦折りと横折りの両方が用いられ、一方が単方向の折り目であるのに対し、地図折りでは縦折りと横折りの両方が用いられます。[12]

2×2の地図を折り目に沿って折る方法は8通りあり、それぞれの折り畳まれた正方形の縦方向の順序を、地図を折る異なる方法と数える。[5]

しかし、地図の折り方の数を数えるという一般的な問題は未解決のままです。n × n の地図の折り方の数は、n ≤ 7の場合のみ知られています。それらは以下の通りです。

1、8、1368、300608、186086600、123912532224、129950723279272（OEISの配列A001418）。

複雑

数学における未解決問題
地図の折り目に山と谷の割り当てが与えられた場合、それを平らに折りたたむことができるかどうかを効率的にテストすることは可能ですか?
数学におけるさらなる未解決問題

地図折りと切手折りの問題は、折り紙の数学における問題、すなわち折り目模様のある正方形を平面図形に折ることができるかどうかという問題に関連している。切手片の各折り目に折り方向（山折りまたは谷折り）を割り当てれば、その結果が多項式時間で平面に折られるかどうかをテストすることができる。[13]

地図（方向が指定された折り目によって長方形に分割されている）上の同じ問題に対しては、2 × n 個の地図に対しては多項式時間アルゴリズムが知られているものの、一般に多項式時間アルゴリズムが存在するかどうかは不明である。[14] 紙を単一の線に沿って折る「単純な」折り目の連続によって地図を折るという限定されたケースでは、問題は多項式である。この問題の拡張、例えば長方形以外の紙への拡張はNP完全である。[13]

折り目が山折りまたは谷折りとして既に分類されている1次元の切手ストリップであっても、任意の折り目の2つの切手の間にある切手の最大数を最小化する折り方を見つけるのはNP困難です。 [15]

参照

参考文献

  1. ^ Lucas、Édouard (1891)、Théorie des nombres (フランス語)、vol. I、パリ：ゴーティエ・ヴィラール、p. 120。
  2. ^ Touchard, Jacques (1950)、「Contribution à l'étude du problème des timbres poste」、Canadian Journal of Mathematics (フランス語)、2 : 385–398、doi : 10.4153/CJM-1950-035-6、MR  0037815、S2CID  124708270。
  3. ^ abcd ルジャンドル, ステファン (2014), 「折り畳みと蛇行」, The Australasian Journal of Combinatorics , 58 : 275– 291, arXiv : 1302.2025 , Bibcode :2013arXiv1302.2025L, MR  3211783
  4. ^ Sainte-Laguë、André ( 1937)、Avec des nombres et des lignes (フランス語)、パリ: Vuibert、pp.  147–162ルジャンドル（2014）より引用
  5. ^ ab Gardner, Martin (1983)、「紙折りの組み合わせ論」、Wheels, Life and Other Mathematical Amusements、ニューヨーク：WH Freeman、pp.  60– 73、Bibcode：1983wlom.book.....G特に60～62ページを参照。
  6. ^ ケーラー、ジョン・E.（1968）「切手ストリップの折りたたみ」、コンビナトリアル理論ジャーナル、5（2）：135–152、doi：10.1016/S0021-9800（68）80048-1、MR  0228364
  7. ^ Lunnon, WF (1968)、「地図折り畳み問題」、Mathematics of Computation、22 (101): 193– 199、doi : 10.2307/2004779、JSTOR  2004779、MR  0221957
  8. ^ Jensen, Iwan (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
  9. ^ 澤田 ジョー; 李 ロイ (2012)、「スタンプ折り畳み、半蛇行、およびオープン蛇行：高速生成アルゴリズム」、Electronic Journal of Combinatorics、19 (2): Paper 43、16pp、doi : 10.37236/2404、MR  2946101
  10. ^ Di Francesco, P. (2000)、「メアンダー数の正確な漸近論」、形式冪級数と代数的組合せ論（モスクワ、2000年）、Springer、ベルリン、pp.  3– 14、doi :10.1007/978-3-662-04166-6_1、ISBN 978-3-642-08662-5、MR  1798197
  11. ^ Connelly, Robert ; Demaine, Erik D. ; Rote, Günter (2003)、「多角形弧の直線化と多角形サイクルの凸状化」(PDF) , Discrete and Computational Geometry , 30 (2): 205– 239, doi : 10.1007/s00454-003-0006-7 , MR  1931840
  12. ^ Lunnon, WF (1971)、「多次元マップフォールディング」、コンピュータジャーナル、14 : 75–80、doi : 10.1093/comjnl/14.1.75、MR  0285409
  13. ^ ab Arkin, Esther M. ; Bender, Michael A. ; Demaine, Erik D. ; Demaine, Martin L. ; Mitchell, Joseph SB ; Sethia, Saurabh ; Skiena, Steven S. (2004年9月)「いつ地図を折ることができるのか？」(PDF) , Computational Geometry: Theory and Applications , 29 (1): 23– 46, doi : 10.1016/j.comgeo.2004.03.012。
  14. ^ Morgan, Thomas D. (2012年5月21日)、「地図の折り畳み（論文）」、マサチューセッツ工科大学、電気工学・コンピュータサイエンス学部、修士論文、hdl :1721.1/77030
  15. ^ 梅里 卓也; 齋藤 俊樹; 上原 龍平; 伊藤 博; 岡本 佳夫 (2013)「切手折り問題の計算量」理論計算機科学, 497 : 13– 19, doi : 10.1016/j.tcs.2012.08.006 , MR  3084129
  • Weisstein, Eric W.、「地図の折りたたみ」（「切手の折りたたみ」）、MathWorldにて。
  • Wolfram デモンストレーション プロジェクトの「ラベル付き切手のストリップを折る」: http://demonstrations.wolfram.com/FoldingAStripOfLabeledStamps/
「https://en.wikipedia.org/w/index.php?title=地図の折りたたみ&oldid=1265671695」より取得