ในคณิตศาสตร์ของการพับกระดาษการพับแผนที่และการพับแสตมป์เป็นสองปัญหาเกี่ยวกับการนับจำนวนวิธีที่สามารถพับกระดาษแผ่นหนึ่งได้ ในปัญหาการพับแสตมป์ กระดาษเป็นแถบแสตมป์ที่มีรอยพับอยู่ระหว่างกัน และรอยพับจะต้องอยู่บนรอยพับเหล่านั้น ในปัญหาการพับแผนที่ กระดาษเป็นแผนที่ที่ถูกแบ่งออกเป็นสี่เหลี่ยมผืนผ้าด้วยรอยพับ และรอยพับจะต้องอยู่บนรอยพับเหล่านั้นเท่านั้น

Lucas (1891) ระบุว่า Émile Lemoineเป็นผู้คิดค้นปัญหาการพับแสตมป์^{[ 1 ]} Touchard (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 John E. Koehler และ WF Lunnon ได้นำอัลกอริทึม มาใช้ ซึ่งในขณะนั้นสามารถคำนวณตัวเลขเหล่านี้ได้ถึง 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 เท่านั้น ซึ่งได้แก่:

1, 8, 1368, 300608, 186086600, 123912532224, 129950723279272 (ลำดับA001418ในOEIS )

ปัญหาการพับแผนที่และการพับแสตมป์เกี่ยวข้องกับปัญหาในคณิตศาสตร์ของโอริกามิว่าสี่เหลี่ยมที่มีรูปแบบรอยพับสามารถพับให้เป็นรูปทรงแบนได้หรือไม่ หากกำหนดทิศทางการพับ (ไม่ว่าจะเป็นการพับแบบภูเขาหรือการพับแบบหุบเขา ) ให้กับรอยพับแต่ละรอยของแถบแสตมป์ ก็สามารถทดสอบได้ว่าผลลัพธ์นั้นสามารถพับให้แบนได้ในเวลาพหุนาม หรือ ไม่^{[ 13 ]}

สำหรับปัญหาเดียวกันบนแผนที่ (ที่แบ่งออกเป็นสี่เหลี่ยมผืนผ้าโดยรอยพับที่มีทิศทางที่กำหนด) ยังไม่เป็นที่ทราบแน่ชัดว่ามีอัลกอริทึมการพับแบบใช้เวลาพหุนามอยู่หรือไม่โดยทั่วไป แม้ว่าจะมีอัลกอริทึมแบบพหุนามสำหรับแผนที่ ขนาด 2 × n ก็ตาม ^{[ 14 ]} ในกรณีที่จำกัดซึ่งแผนที่ต้องถูกพับด้วยลำดับของการพับแบบ "ง่าย" ซึ่งพับกระดาษตามเส้นเดียว ปัญหาจะเป็นแบบพหุนาม การขยายปัญหาบางอย่าง เช่น สำหรับแผ่นกระดาษที่ไม่เป็นรูปสี่เหลี่ยมผืนผ้า จะเป็นปัญหาNP- complete ^{[ 13 ]}

แม้แต่สำหรับแถบแสตมป์แบบมิติเดียวที่มีรอยพับที่ระบุว่าเป็นแบบภูเขาหรือหุบเขา ก็ยังเป็นเรื่องยากแบบ NPที่จะหาวิธีพับที่ทำให้จำนวนแสตมป์สูงสุดที่อยู่ระหว่างแสตมป์สองดวงของรอยพับใดๆ น้อยที่สุด^{[ 15 ]}

• ลำดับการพับกระดาษปกติคือลำดับอนันต์ของเลข 0 และ 1 ที่อธิบายวิธีการพับแถบแสตมป์วิธีหนึ่ง

• ไวส์สไตน์, เอริค ดับเบิลยู. , " การพับแผนที่ " (" การพับแสตมป์ ") ที่MathWorld .
• วิดีโอสาธิต "การพับแถบแสตมป์ที่มีป้ายกำกับ" จากโครงการสาธิตของ Wolfram: http://demonstrations.wolfram.com/FoldingAStripOfLabeledStamps/