世界初！120年以上未解決だった難解パズルの証明に成功

【ポイント】

• 120年以上にわたり未解決であった古典的な裁ち合わせパズルの解の最適性を世界で初めて証明しました。
• 証明の技法から独自に開発したものであり、今後、多くの同種の問題が解けると期待できます。

　裁ち合わせパズルとは、与えられた多角形をなるべく少ないピースに切り分けて並べ替え、別の多角形に変えるパズルです。これは古典的なパズルであり、その中で最も有名なものが、正三角形を4つのピースに切り分けて正方形を作る「デュードニーの裁ち合わせパズル」です（上図）。これは、イギリスの著名なパズル作家であるデュードニーが1902年に発表したものですが、この4ピースよりも少ない解があるかどうかは、120年以上にわたって未解決のままでした。
　北陸先端科学技術大学院大学の上原研究室とマサチューセッツ工科大学のDemaine研究室は数年前からこの難問に挑戦してきました。そして、鎌田助教が新しい証明技法を考案し、ついに「この4ピースの解が最適で、3ピース以下の解が存在しない」ことを世界で初めて証明しました。
　この証明技法は、裁ち合わせに関する新たな地平を切り拓くものです。裁ち合わせパズルは古典的な人気パズルとして数多く考案されてきましたが、どれも具体的な切り方を示すことで「存在する」ということしか示せず、最適解を数学的に証明するのは難しいとされてきました。今回、世界で初めて「裁ち合わせできない」という不可能性を数学的に証明できるということが明らかになりました。この技法により、今後は他のパズルでも不可能性が示せる可能性があるとともに、この技法をさらに精緻化すれば、今まで示されたことのない、新たな裁ち合わせの発見にもつながります。また、裁ち合わせはパッチワークなどの工芸にも関係が深く、今後の多様な応用にも期待できます。

　本研究成果は、「arXiv」（物理学、数学、計算機科学、数量生物学、数量ファイナンス、統計学、電子工学・システム科学・経済学のプレプリントを含む様々な論文が保存・公開されているウェブサイト）にて2024年12月5日に公開されました。また、2025年1月27日から29日まで京都大学にて開催された「冬のLAシンポジウム」にて口頭発表を行い、「LA/EATCS-Japan発表論文賞」を受賞しました。

【論文情報】

令和7年3月10日