Using a novel approach, researchers have proved that the original solution to Dudeney’s famous dissection problem is the optimal solution
Ishikawa, Japan -- In 1907, the English author and mathematician Henry Ernest Dudeney posed a puzzle: Can any equilateral triangle be cut into as few pieces as possible that will fit together to form a perfect square? Four weeks later, he presented an elegant solution, showing that only four pieces were needed. This process of transforming one shape into another by cutting the first shape into pieces and rearranging them is called dissection. A key challenge in dissections is minimizing the number of pieces required to transform one polygonal shape into another, a problem that has intrigued mathematicians, puzzle makers, and solvers for centuries.
Dudeney’s puzzle remains one of the most famous dissection problems. Dissection problems not only interest mathematicians but also have practical applications in fields such as textile design, engineering, and manufacturing. Since Dudeney first posed his solution over 120 years ago, a lingering question has remained: Is there a better solution that requires cutting the triangle into fewer than four pieces?
In a groundbreaking study, Professor Ryuhei Uehara and Assistant Professor Tonan Kamata, from Japan Advanced Institute of Science and Technology (JAIST), along with Professor Erik D. Demaine from Massachusetts Institute of Technology, have finally answered this question. They proved that Dudeney’s original solution was optimal. “
Over a century later, we have finally solved Dudeney's puzzle by proving that the equilateral triangle and square have no common dissection with three or fewer polygonal pieces,” says Prof. Uehara. “
We achieved this using a novel proof technique that utilizes matching diagrams.” Their study was published on the
open-access repository arXiv on December 05, 2024, and
presented at the 23rd LA/EATCS-Japan Workshop on Theoretical Computer Science in January 2025.
In their study, the researchers proved a key theorem: There is no dissection between an equilateral triangle and a square with three or fewer pieces, when the pieces are forbidden to be flipped. Dudeney’s original solution also did not involve flipping. To establish this, the researchers first ruled out the possibility of two-piece dissection by analyzing the geometrical constraints of the problem.
Next, they systematically explored the possibility of a three-piece dissection. Using the fundamental properties of dissection, they narrowed down the feasible combinations of cutting methods for the three-piece dissection. Finally, they used the concept of a matching diagram to rigorously prove that none of these combinations for three-piece dissections were feasible, hence proving that a dissection between a square and an equilateral triangle cannot be achieved with three or fewer pieces.
The matching diagram played a central role in their proof. In this method, the set of cut pieces used in the dissection is reduced to a graph structure that captures the relationship between the edges and vertices of the pieces, forming both the triangle and the square. The researchers found that this method is not only applicable to Dudeney’s puzzle but can also be applied generally for other dissection problems.
“
The problem of cutting and rearranging shapes is said to have existed since humans began processing animal hides to make clothing. Such problems are also encountered in any situation where thin materials are used,” explains Prof. Uehara. “
Our proof opens new horizons for understanding and solving dissection problems.”
Although many dissection problems have been solved by finding solutions with a certain number of pieces, there has never been a formal proof showing that a specific solution is optimal, using the fewest pieces possible. The technique developed in this study is the first to prove such optimality.
“Our technique demonstrates that an optimal dissection is possible for real-world cut-and-rearrange problems. With further refinement, it could also lead to the discovery of entirely new solutions for dissection problems,” concludes Prof. Uehara.
###
Reference
| Title of original paper: |
Dudeney’s Dissection is Optimal |
| Authors: |
Erik D. Demaine, Tonan Kamata, and Ryuhei Uehara |
| Journal: |
arXiv |
| DOI: |
10.48550/arXiv.2412.03865 |
About Japan Advanced Institute of Science and Technology, Japan
Founded in 1990 in Ishikawa prefecture, the Japan Advanced Institute of Science and Technology (JAIST) was the first independent national graduate school in Japan. Now, after 30 years of steady progress, JAIST has become one of Japan’s top-ranking universities. JAIST strives to foster capable leaders with a state-of-the-art education system where diversity is key; about 40% of its alumni are international students. The university has a unique style of graduate education based on a carefully designed coursework-oriented curriculum to ensure that its students have a solid foundation on which to carry out cutting-edge research. JAIST also works closely with both local and overseas communities by promoting industry–academia collaborative research.
About Professor Ryuhei Uehara from Japan Advanced Institute of Science and Technology, Japan
Ryuhei Uehara is currently a Professor at the Computing Science Research Area, Japan Advanced Institute of Science and Technology (JAIST). He received his M.S. and Ph.D. degrees from the University of Electro-Communications, Japan, in 1991 and 1998, respectively. At JAIST, he leads the UEHARA laboratory. He has published over 250 articles that have received over 2,100 citations. He is also the author of the books:
Introduction to Computational Origami and
First Course in Algorithms Through Puzzles. His research interests include computational complexity, algorithms and data structures, and graph algorithms. His research is specifically focused on computational origami, games, and puzzles from the point of view of theoretical computer science.
Funding information
Tonan Kamata is mainly supported by JSPS KAKENHI Grants Number 22J10261 and 24K23857, and partially supported by Grants Number 20H05961 and 20H05964.
Ryuhei Uehara is mainly supported by JSPS KAKENHI Grants Number 24H00690 and partially supported by Grants Number 22H01423, 20H05961, and 20H05964.