研究人員已經(jīng)用一種新穎的方法證明，Dudeney著名分割問題的原始解決方案確實(shí)是最佳解決方案。
1907年，英國作家兼數(shù)學(xué)家亨利·歐內(nèi)斯特·杜德尼（Henry Ernest Dudeney）提出了一個(gè)有趣的難題：一個(gè)等邊三角形能否被切成盡可能少的碎片，然后重新排列成一個(gè)完全正方形？僅僅四周后，他就公布了一個(gè)優(yōu)雅的解決方案，證明只需要四個(gè)部件。這種將一個(gè)形狀切割成碎片并重新排列成另一個(gè)形狀的方法被稱為分割。分割的一個(gè)核心挑戰(zhàn)是最小化將一個(gè)多邊形轉(zhuǎn)換成另一個(gè)多邊形所需的碎片數(shù)量 —— 這個(gè)問題幾個(gè)世紀(jì)以來一直吸引著數(shù)學(xué)家、拼圖愛好者和問題解決者。
杜德尼之謎仍然是最著名的幾何分割例子之一。除了對(duì)數(shù)學(xué)家的吸引力之外，分割問題在紡織設(shè)計(jì)、工程和制造等領(lǐng)域也有實(shí)際應(yīng)用。在杜德尼提出解決方案120多年后，一個(gè)問題仍然存在：是否有可能用少于4塊的碎片解決這個(gè)難題？
一個(gè)開創(chuàng)性的數(shù)學(xué)證明
在一項(xiàng)開創(chuàng)性的研究中，來自日本先進(jìn)科學(xué)技術(shù)研究所（JAIST）的Ryuhei Uehara教授和助理教授Tonan Kamata，以及麻省理工學(xué)院的Erik D. Demaine教授終于回答了這個(gè)問題。他們證明了Dudeney的原始解是最優(yōu)的。
“一個(gè)多世紀(jì)后，我們終于解決了杜德尼之謎，證明了等邊三角形和正方形沒有三個(gè)或更少的多邊形碎片的共同分割，”Uehara教授說。“我們使用了一種利用匹配圖的新穎證明技術(shù)來實(shí)現(xiàn)這一點(diǎn)。”他們的研究于2024年12月5日發(fā)表在開放存取知識(shí)庫arXiv上，并于2025年1月在第23屆LA/EATCS-Japan理論計(jì)算機(jī)科學(xué)研討會(huì)上發(fā)表。
在他們的研究中，研究人員證明了一個(gè)關(guān)鍵定理：當(dāng)?shù)冗吶切魏腿龎K或更少的正方形被禁止翻轉(zhuǎn)時(shí)，它們之間沒有分割。Dudeney最初的解決方案也不涉及翻轉(zhuǎn)。為了建立這一點(diǎn)，研究人員首先通過分析問題的幾何約束排除了兩件式分割的可能性。
接下來，他們系統(tǒng)地探索了三段式分割的可能性。利用分割的基本特性，他們縮小了三件式分割可行的切割方法組合。最后，他們使用匹配圖的概念嚴(yán)格證明了這些三片分割的組合都是不可行的，從而證明了正方形和等邊三角形之間的分割不能用三個(gè)或更少的碎片來實(shí)現(xiàn)。
匹配圖的作用
匹配圖在他們的證明中起了核心作用。在這種方法中，用于分割的切割塊集被簡化為一個(gè)圖結(jié)構(gòu)，該圖結(jié)構(gòu)捕獲了塊的邊緣和頂點(diǎn)之間的關(guān)系，形成三角形和正方形。研究人員發(fā)現(xiàn)，這種方法不僅適用于Dudeney難題，也可以普遍應(yīng)用于其他分割問題。
據(jù)說，自從人類開始加工獸皮制作衣服以來，就存在著裁剪和重新排列形狀的問題。在使用薄材料的任何情況下也會(huì)遇到這樣的問題，”Uehara教授解釋說?！拔覀兊淖C明為理解和解決分割問題開辟了新的視野?！?/p>
盡管許多分割問題已經(jīng)通過尋找具有一定數(shù)量碎片的解來解決，但從來沒有正式的證明表明使用盡可能少的碎片的特定解是最優(yōu)的。這項(xiàng)研究開發(fā)的技術(shù)是第一個(gè)證明這種最優(yōu)性的技術(shù)?！拔覀兊募夹g(shù)表明，對(duì)于現(xiàn)實(shí)世界的切割和重排問題，最佳的分割是可能的。隨著進(jìn)一步的改進(jìn)，它也可能導(dǎo)致發(fā)現(xiàn)分割問題的全新解決方案，”Uehara教授總結(jié)道。
如果朋友們喜歡，敬請(qǐng)關(guān)注“知新了了”！
熱門跟貼