Wolfram Blog
Ed Pegg Jr

From Close to Perfect—A Triangle Problem

March 28, 2013 — Ed Pegg Jr, Editor, Wolfram Demonstrations Project

RootApproximant can turn an approximate solution into a perfect solution, such as for a square divided into fifty 45°-60°-75° triangles.

A square can be divided into triangles, for example by connecting opposite corners. It’s possible to divide a square into seven similar but differently sized triangles or ten acute isosceles triangles. Classic puzzles involve cutting a square into eight acute triangles, or twenty 1 – 2 – √5 triangles. The last image uses 45°-60°-75° triangles, but one triangle has a flaw.

Classic puzzle examples

It’s easy to divide a square with similar right triangles. Can a square be divided into similar non-right triangles? In his paper “Tilings of Polygons with Similar Triangles” (Combinatorica, 10(3), 1990 pp. 281–306), Laczkovich proved exactly three triangles provided solutions, with angles 22.5°-45°-122.5°, 15°-45°-120°, and 45°-60°-75°. I read his paper to try to make an image for the 45°-60°-75° case, but his construction was complex, and seemed to require thousands of triangles, so I tried to find my own solutions. All my attempts had flaws, such as the last image above, so I made a contest out of it: $200, minus a dollar for every triangle in the solution.

Lew Baxter started with a close examination of the Laczkovich solution, and got it to work with 7 trillion triangles. But he saw ways to improve it, and wrote a program to search for improvements. Within several weeks, he had a 198 triangle solution, enough to win $2 from me. He kept at it, and finally came up with a 64 triangle solution. Unfortunately, all the points were approximate. It was possible that the solution he sent, shown here, might have been close, but not perfect:

pts = {{0.0, 0.0}, {0.09007271128977927, 0.0}, {0.18014542257955854, 0.0}, {0.3973596148311608, 0.0}, {0.6675777487004985, 0.0}, {0.7783851658003322, 0.0}, {0.889192582900166, 0.0}, {0.9999999999999998, 0.0}, {0.05710381076997864, 0.05710381076997864}, {0.1471765220597579, 0.05710381076997864}, {0.23724923334953715, 0.05710381076997864}, {0.5973286611869417, 0.07024908751355644}, {0.7081360782867756, 0.07024908751355644}, {0.7635397868366925, 0.07024908751355644}, {0.8189434953866094, 0.07024908751355644}, {0.9297509124864433, 0.07024908751355644}, {0.491955029916607, 0.17562271878389113}, {0.6581661555663578, 0.17562271878389113}, {0.8243772812161086, 0.17562271878389113}, {0.1713114323099359, 0.1713114323099359}, {0.316120893811004, 0.1713114323099359}, {0.3514568548894944, 0.1713114323099359}, {0.4962663163905624, 0.1713114323099359}, {0.2855190538498932, 0.2855190538498932}, {0.33378887435024923, 0.2855190538498932}, {0.38205869485060523, 0.2855190538498932}, {0.3235882610298789, 0.3235882610298789}, {0.35145685488949435, 0.31612089381100394}, {0.35145685488949435, 0.35145685488949435}, {0.6136300186754392, 0.38636998132456046}, {0.0, 0.5543705646684832}, {0.35145685488949435,  0.6485431451105055}, {0, 1}};

triangles = {{1, 2, 9}, {10, 9, 2}, {2, 3, 10}, {11, 10, 3}, {3, 22, 4}, {4, 23, 22}, {5, 4, 23}, {12, 13, 5}, {6, 5, 13}, {13, 15, 6}, {7, 6, 15}, {15, 16, 7}, {8, 7, 16}, {9, 11, 20}, {22, 20, 11}, {17, 18, 12}, {14, 12, 18}, {18, 19, 14}, {16, 14, 19}, {20, 24, 21}, {21, 26, 24}, {23, 21, 26}, {24, 27, 25}, {25, 27, 28}, {26, 25, 28}, {29, 27, 28}, {1, 31, 29}, {31, 29, 32}, {33, 32, 31}, {19, 17, 30}, {30, 28, 17}, {32, 30, 28}};

Making the solution perfect looked like a job for RootApproximant, which finds a root of a polynomial that is close to a desired value. In geometric constructions such as these, it’s not unlikely that the exact values are indeed polynomial roots. For the problem in question, I tried the following. Multiplying by 4686 eliminated a lot of fractions. All the values were of the form a + b √3, which seemed very promising.

exactpts = 4686 RootApproximant[pts, 2]

{{0, 0}, {3 (87 + 31 √3), 0}, {6 (87 + 31 √3), 0}, {3 (903 - 163 √3), 0}, {6 (582 - 35 √3), 0}, {2 (1945 - 70 √3), 0}, {2 (2144 - 35 √3), 0}, {4686, 0}, {3 (84 + 3 √3), 3 (84 + 3 √3)}, {3 (171 + 34 √3), 3 (84 + 3 √3)}, {3 (258 + 65 √3), 3 (84 + 3 √3)}, {2 (1500 - 58 √3), 2 (246 - 47 √3)}, {2 (1699 - 23 √3), 2 (246 - 47 √3)}, {11 (327 - √3), 2 (246 - 47 √3)}, {2 (1898 + 12 √3), 2 (246 - 47 √3)}, {2 (2097 + 47 √3), 2 (246 - 47 √3)}, {2262 + 25 √3, 1230 - 235 √3}, {2859 + 130 √3, 1230 - 235 √3}, {3456 + 235 √3, 1230 - 235 √3}, {3 (252 + 9 √3), 3 (252 + 9 √3)}, {3 (738 - 141 √3), 3 (252 + 9 √3)}, {213 (6 + √3), 3 (252 + 9 √3)}, {3 (912 - 79 √3), 3 (252 + 9 √3)}, {3 (420 + 15 √3), 3 (420 + 15 √3)}, {3 (582 - 35 √3), 3 (420 + 15 √3)}, {3 (744 - 85 √3), 3 (420 + 15 √3)}, {3 (476 + 17 √3), 3 (476 + 17 √3)}, {213 (6 + √3), 3 (738 - 141 √3)}, {213 (6 + √3), 213 (6 + √3)}, {11 (180 + 47 √3), 11 (246 - 47 √3)}, {0, 213 (7 + 3 √3)}, {213 (6 + √3), 213 (16 - √3)}, {0, 4686}}

We can then take a look at the proposed 64 triangle solution.

Proposed 64 triangle solution

Then I got a new message from Lew—if triangles 6, 7, 21, and 22 are flipped, then eight of the triangles can be replaced by just one triangle.

Comparison of the 64 triangle example and 50 triangle example

It wasn’t quite that easy, but I calculated a new set of points.

exactpts = {{0, 0}, {6 (582 - 35 √3), 0}, {2 (1945 - 70 √3), 
0}, {2 (2144 - 35 √3), 0}, {4686, 0}, {2 (1500 - 58 √3), 
2 (246 - 47 √3)}, {2 (1699 - 23 √3), 
2 (246 - 47 √3)}, {11 (327 - √3), 
2 (246 - 47 √3)}, {2 (1898 + 12 √3), 
2 (246 - 47 √3)}, {2 (2097 + 47 √3), 
2 (246 - 47 √3)}, {2262 + 25 √3, 
1230 - 235 √3}, {2859 + 130 √3, 
1230 - 235 √3}, {3456 + 235 √3, 
1230 - 235 √3}, {3 (420 + 15 √3), 
3 (420 + 15 √3)}, {3 (582 - 35 √3), 
3 (420 + 15 √3)}, {3 (744 - 85 √3), 
3 (420 + 15 √3)}, {3 (476 + 17 √3), 
3 (476 + 17 √3)}, {213 (6 + √3), 
3 (738 - 141 √3)}, {213 (6 + √3), 
213 (6 + √3)}, {11 (180 + 47 √3), 11 (246 - 47 √3)}, {0, 
213 (7 + 3 √3)}, {213 (6 + √3), 213 (16 - √3)}, {0, 
4686}, {15 (87 + 31 √3), 0}, {2736 - 237 √3, 
27 (28 + √3)}, {213 (6 + √3), 27 (28 + √3)}};

triangles = {{6, 7, 2}, {3, 2, 7}, {7, 9, 3}, {4, 3, 9}, {9, 10, 4}, {5, 4, 10}, {11, 12, 6}, {8, 6, 12}, {12, 13, 8}, {10, 8, 13}, {14, 17, 15}, {15, 17, 18}, {16, 15, 18}, {19, 17, 18}, {1, 21, 19}, {21, 19, 22}, {23, 22, 21}, {13, 11, 20}, {20, 18, 11}, {22, 20, 18}, {1, 14, 24}, {2, 25, 24}, {24, 26, 25}, {25, 16, 26}, {26, 14, 16}};

That leads to a 50 triangle solution. So is that a perfect solution? With code for calculating an angle based on vertices, all the angles can be checked.

Calculating an angle based on vertices

Table[angle[RotateLeft[exactpts[[triangles[[n]]]], k]] //    FullSimplify, {n, 1, Length[triangles]}, {k, 0, 2}]

{{45, 60, 75}, {45, 60, 75}, {45, 60, 75}, {45, 60, 75}, {45, 60,    75}, {45, 60, 75}, {45, 60, 75}, {45, 60, 75}, {45, 60, 75}, {45,    60, 75}, {45, 60, 75}, {45, 60, 75}, {45, 60, 75}, {45, 60,    75}, {45, 60, 75}, {45, 60, 75}, {45, 60, 75}, {45, 60, 75}, {45,    60, 75}, {45, 60, 75}, {45, 75, 60}, {45, 60, 75}, {45, 60,    75}, {45, 60, 75}, {45, 60, 75}}

All of the triangles are exact 45°-60°-75° triangles, so Baxter’s solution is indeed exact. Now we can take a look at the 50 triangle solution.

50 triangle solution

So I owe Lew Baxter $150. If you’re ever tackling problems in numerical optimization, and the values are mysterious, it’s worth giving RootApproximant a try. You might have an exact solution.

Download this post as a Computable Document Format (CDF) file.

Posted in: Mathematics
Leave a Comment

One Comment


stan wagon

Lovely blog… these triangle problems are interesting and challenging.

Posted by stan wagon    March 28, 2013 at 6:10 pm


Leave a comment

Loading...

Or continue as a guest (your comment will be held for moderation):