109
$\begingroup$

What is the smallest number of $45^\circ-60^\circ-75^\circ$ triangles that a square can be divided into?

The image below is a flawed example, from http://www.mathpuzzle.com/flawed456075.gif

math puzzle 45-60-75 triangles

Laczkovich gave a solution with many hundreds of triangles, but this was just an demonstration of existence, and not a minimal solution. ( Laczkovich, M. "Tilings of Polygons with Similar Triangles." Combinatorica 10, 281-306, 1990. )

I've offered a prize for this problem: In US dollars, (\$200-number of triangles).

NEW: The prize is won, with a 50 triangle solution by Lew Baxter.

$\endgroup$
19
  • 3
    $\begingroup$ Interesting optical illusion: I could swear the two parts of the top-left-to-bottom-right diagonal don't match up, but they do. Also, it looks more as if they do if you tilt your head $45°$ (in either direction). $\endgroup$
    – joriki
    Jun 11, 2011 at 9:00
  • 7
    $\begingroup$ Your prize has an existentialist bias; there should also be a prize for proving that there's no solution with less than $100$ triangles :-) $\endgroup$
    – joriki
    Jun 11, 2011 at 9:10
  • 28
    $\begingroup$ Perhaps it is also interesting to have lower bounds on the solution.. @EdPegg, I don't think people will be very interested in your prize money, they may end up having to pay you! $\endgroup$
    – picakhu
    Jun 17, 2011 at 18:20
  • 6
    $\begingroup$ A copy of Laczkovich's paper can be found here: springerlink.com/content/p55415826m0j01w2/fulltext.pdf $\endgroup$ Dec 7, 2011 at 3:53
  • 3
    $\begingroup$ I wonder, if there exist true asymetric solutions (not divided by the square-diagonal into two right-angled structures). This might also lower the number of triangles needed for a solution because it gives an additional degree of freedom for the structure, i think. $\endgroup$
    – FPI
    May 21, 2017 at 12:49

5 Answers 5

31
$\begingroup$

I found a minor improvement to Lew Baxter's solution. There are only 46 triangles needed to tile a square:

This is my design

Square tessellation by 46 × 45-60-75 degree triangles

(Click this SVG for Franz's original GIF version).

Actually, I tried to find an optimal solution with a minimum number of tiles by creating a database with about 26,000 unique rhomboids & trapezoids consisting of 2-15 triangles. I searched through various promising setups (where the variable width/height-ratio of one element defines a second and you just have to look, if it's in the database, too) but nothing showed up. So this 46-tiles solution was in some sense just a by-product. As there probably exist some more complex combinations of triangles which I was not able to include, an even smaller solution could be possible.

With b = $\sqrt3$ the points have the coordinates:

{
{4686, 0},
{4686, 6 (582 - 35 b)},
{4686, 4089 - 105 b},
{4686, 4686},
{4194 + 94 b, 3000 - 116 b},
{141 (28 + b), 3351 + 36 b},
{4194 + 94 b, -11 (-327 + b)},
{141 (28 + b), 141 (28 + b)},
{3456 + 235 b, 2262 + 25 b},
{3456 + 235 b, 2859 + 130 b},
{3456 + 235 b, 3456 + 235 b},
{3426 - 45 b, 45 (28 + b)},
{3426 - 45 b, 3 (582 - 35 b)},
{3426 - 45 b, 3 (744 - 85 b)},
{3258 - 51 b, 51 (28 + b)},
{2472 + 423 b, 213 (6 + b)},
{-213 (-16 + b), 213 (6 + b)},
{2754 - 69 b, 2754 - 69 b},
{-639 (-5 + b), 0},
{213 (6 + b), 213 (6 + b)},
{0, 0},
{4686, 15 (87 + 31 b)},
{3930 - 27 b, 2736 - 237 b},
{3930 - 27 b, 213 (6 + b)},
{0, 4686},
{6 (582 - 35 b), 4686},
{4089 - 105 b, 4686},
{3000 - 116 b, 4194 + 94 b},
{3351 + 36 b, 141 (28 + b)},
{-11 (-327 + b), 4194 + 94 b},
{2262 + 25 b, 3456 + 235 b},
{2859 + 130 b, 3456 + 235 b},
{45 (28 + b), 3426 - 45 b},
{3 (582 - 35 b), 3426 - 45 b},
{3 (744 - 85 b), 3426 - 45 b},
{51 (28 + b), 3258 - 51 b},
{213 (6 + b), 2472 + 423 b},
{213 (6 + b), -213 (-16 + b)},
{0, -639 (-5 + b)},
{15 (87 + 31 b), 4686},
{2736 - 237 b, 3930 - 27 b},
{213 (6 + b), 3930 - 27 b}
}

which build the 46 triangles with pointnumbers:

{
{6, 5, 2}, {3, 2, 6}, {8, 7, 3}, {4, 3, 8},
{9, 10, 5}, {5, 6, 10}, {10, 11, 7}, {7, 8, 11},
{12, 15, 13}, {13, 15, 16}, {14, 13, 16}, {17, 15, 16},
{1, 19, 17}, {19, 17, 20}, {21, 20, 19}, {11, 18, 9},
{18, 9, 16}, {20, 16, 18}, {1, 22, 12}, {2, 23, 22},
{22, 24, 23}, {23, 14, 24}, {24, 12, 14}, {4, 27, 8},
{8, 30, 27}, {30, 8, 11}, {32, 11, 30}, {11, 18, 31},
{27, 26, 29},  {28, 29, 32}, {29, 28, 26}, {31, 32, 28},
{26, 41, 40}, {40, 42, 41}, {18, 31, 37}, {20, 37, 18},
{41, 35, 42}, {35, 34, 37}, {38, 36, 37}, {34, 36, 37},
{33, 36, 34}, {42, 33, 35}, {25, 40, 33}, {25, 39, 38},
{39, 38, 20}, {21, 20, 39}
}

Here's a more colourful version, by PM 2Ring.

Square tessellation by 46 × 45-60-75 degree triangles, in colour

Here's a live version of the Python / Sage code I used to create the SVGs and PNG. It has various modes & options you can play with.

$\endgroup$
3
  • 1
    $\begingroup$ Thanks for your animation and effort @PM2Ring. interesting, are u a moderator or can anybody change posts of other users? $\endgroup$
    – FPI
    Jan 26, 2021 at 10:26
  • 1
    $\begingroup$ No, I'm not a moderator, mods have a ♦after their name; see here for general info about Stack Exchange moderators. Anyone can change a post. If you edit someone else's post and your rep score is <2000, then the edit must be approved by 3 users with rep >=2000 or the post's author. See here for details. $\endgroup$
    – PM 2Ring
    Jan 26, 2021 at 13:29
  • 1
    $\begingroup$ It was fun writing that code. You found an interesting design, and I've looked at it many times over the course of writing that code. :) I didn't create any animations (although that wouldn't be hard to do). My code makes images in SVG format, which is a vector graphics format, so you can zoom into the image without pixelization. Vector formats are ideal for images like this, and the file size is much smaller than an equivalent bitmap file. $\endgroup$
    – PM 2Ring
    Jan 26, 2021 at 13:38
26
$\begingroup$

I improved on Laczkovich's solution by using a different orientation of the 4 small central triangles, by choosing better parameters (x, y) and using fewer triangles for a total of 64 triangles. The original Laczkovich solution uses about 7 trillion triangles.

tiling with 64 triangles

Here's one with 50 triangles:

enter image description here

$\endgroup$
2
  • 13
    $\begingroup$ Can you provide some further details as to how you accomplished this? Regards. $\endgroup$
    – Amzoti
    Jan 7, 2013 at 22:25
  • $\begingroup$ It almost looks like a sierpinski triangle. $\endgroup$
    – Mr Pie
    Mar 2, 2021 at 23:28
13
$\begingroup$

The following was posted by Ed Pegg as a suggested edit to Lew Baxter's answer, but was rejected for being too substantial a change. I thought it was useful information, so I reproduce it below. If you no longer want it to be posted here, Ed, leave a comment and I'll delete it.


Exact points for the triangles are as follows, with $b=\sqrt3$:

$$\{\{0,0\}, \{261+93b,0\}, \{522+186b,0\}, \{2709-489b,0\}, \{3492-210b,0\}, \{3890-140b,0\}, \{4288-70b,0\}, \{4686,0\}, \{252+9b,252+9b\}, \{513+102b,252+9b\}, \{774+195b,252+9b\}, \{3000-116b,492-94b\}, \{3398-46b,492-94b\}, \{3597-11b,492-94b\}, \{3796+24b,492-94b\}, \{4194+94b,492-94b\}, \{2262+25b,1230-235b\}, \{2859+130b,1230-235b\}, \{3456+235b,1230-235b\}, \{756+27b,756+27b\}, \{2214-423b,756+27b\}, \{1278+213b,756+27b\}, \{2736-237b,756+27b\}, \{1260+45b,1260+45b\}, \{1746-105b,1260+45b\}, \{2232-255b,1260+45b\}, \{1428+51b,1428+51b\}, \{1278+213b,2214-423b\}, \{1278+213b,1278+213b\}, \{1980+517b,2706-517b\}, \{0,1491+639b\}, \{1278+213b,3408-213b\}, \{0,4686\}\}$$

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

Leading to the solution:

Full square solution

$\endgroup$
11
$\begingroup$

enter image description here

Here's my solution with 32 triangles.

How

enter image description here

First, I find all polygons that can be created by attaching the 45-60-75 triangle to a copy of itself, such that an edge coincides. There are twelve unique polygons comprised of two triangles like this. (The above image shows one example).

Next, I find all polygons that can be created by attaching a 1-triangle polygon to a 2-triangle polygon. Now I have 108 3-triangle polygons.

I repeat this process. For efficiency, I only keep track of the polygon outlines, and not how the polygons were created. Also, I avoid creating any polygons with more than 5 sides, and discard any polygons with coordinates with overly complicated fractions as coordinates.

Here are how many unique polygons I retain at each stage:

# triangles # polygons
2 12
3 108
4 560
5 2597
6 9594
7 34319
8 113015
9 338944
10 969019
11 2578767
12 6540652

I can search further, but searching all 14-triangle polygons takes many hours.

A shortcut

enter image description here

When the 5-sided pink polygon is generated, I also calculate what 4-sided polygon is needed to complete a big triangle. This allows solutions to be found much "earlier".

Other Details

  • All triangle coordinates are in the field Q*sqrt(3) (of the form a+b*sqrt(3), for fractional numbers a and b).

  • Side lengths are also in the same field, but with an extra factor of *sqrt(2) for lines angled at 15 degrees, 45 degrees, 75 degrees, etc (odd multiples of 15 degrees).

enter image description here

  • For finding all polygons comprised of say, 8 triangles, considering 5+3=8 gives more solutions than just adding 1 polygon. (The above image shows this idea.)

  • It's useful to canonicalize a polygon, and refer to it by a hash value

  • I store a polygon as a series of "rays" (edges), where each ray has one of 12 directions (0 degrees, 15 degree, ..., 165 degrees), and the ray "length" can be negative. This allows polygons to be stored in a "bucket" based the directions of its rays. So, only the polygon lengths need to be stored. Also, the last two lengths don't actually need to be stored, they can be calculated. (This may have been overkill, but it allowed for various optimizations).

  • Once a big 90-45-45 triangle is created, it's a pain to reconstruct how I got it. I end up running my program multiple times to re-trace the steps.

34-triangle solutions

enter image description here

Possible Improvements

I'm not too optimistic about finding a better decomposition of a 90-45-45 triangle. But maybe the square could be decomposed into two 6-triangle polygons like this.

Observations

All the solutions here have similarities. The perimeter has exactly 4 more 45-degree angles than 75-degree angles. So the opposite must be true on the interior. This can only be accomplished with a 75-75-75-75-60-degree junction.

enter image description here

Also, I noticed that if you "cut" the tiling (from the perimeter into the 75-75-75-75-60 junction) and then "warp" the tiling, you get a very regular grid.

Coordinates

1968-72√₃,396+12√₃
2340-324√₃,1152-360√₃
2220-196√₃,528+16√₃
1584+48√₃,396+12√₃
2352-192√₃,396+12√₃
2340-324√₃,0
1188+36√₃,0
2346-258√₃,198+6√₃
2544-252√₃,0
2550-186√₃,198+6√₃
2565-21√₃,693+21√₃
612+216√₃,612+216√₃
0,0
3258,0
3258,2016-630√₃
2340-324√₃,2340-324√₃
3258,3258
{{0,1,2},{3,1,0},{4,0,2},{5,3,4},{6,5,3},{7,8,9},{8,7,5},{9,4,7},{10,9,2},{11,1,6},{12,6,11},{13,10,8},{13,14,10},{15,11,1},{14,1,15},{16,15,14}}
$\endgroup$
6
  • $\begingroup$ Have a vertex list? $\endgroup$
    – Ed Pegg
    Nov 17, 2021 at 23:19
  • 1
    $\begingroup$ added a vertex list $\endgroup$ Nov 18, 2021 at 4:55
  • 1
    $\begingroup$ Beautiful work Tom! $\endgroup$ Nov 18, 2021 at 22:54
  • 1
    $\begingroup$ Can we do better when tiling a rectangle? math.stackexchange.com/questions/4045188/… $\endgroup$ Nov 18, 2021 at 22:55
  • 1
    $\begingroup$ Thanks Dmitry! Yes, much better. I just posted an answer. $\endgroup$ Nov 19, 2021 at 3:23
2
$\begingroup$

I have no answer to the question, but here's a picture resulting from some initial attempts to understand the constraints that exist on any solution.

$\qquad$ 45-60-75

This image was generated by considering what seemed to be the simplest possible configuration that might produce a tiling of a rectangle. Starting with the two “split pentagons” in the centre, the rest of the configuration is produced by triangulation. In this image, all the additional triangles are “forced”, and the configuration can be extended no further without violating the contraints of triangulation. If I had time, I'd move on to investigating the use of “split hexagons”.

The forcing criterion is that triangulation requires every vertex to be surrounded either (a) by six $60^\circ$ angles, three triangles being oriented one way and three the other, or else (b) by two $45^\circ$ angles, two $60^\circ$ angles and two $75^\circ$ angles, the triangles in each pair being of opposite orientations.

$\endgroup$
4
  • 2
    $\begingroup$ I don't understand why all the additional triangles are forced. $\endgroup$
    – Bob Hearn
    Oct 13, 2011 at 16:35
  • 1
    $\begingroup$ @Bob: forcing criterion added $\endgroup$ Dec 30, 2011 at 16:59
  • $\begingroup$ Unfortunately, there is a solution with hundreds of triangles. See the Laczkovich paper. This forcing argument doesn't work, since you're proving a known solution is impossible. $\endgroup$
    – Ed Pegg
    Jan 5, 2012 at 15:20
  • 1
    $\begingroup$ @EdPegg: Perhaps I didn’t explain it clearly enough; I only investigated a simple solution (as described in the paragraph under the image). All I’ve proved is that starting with two “split pentagons” and triangulating from then on (i.e. adding no additional vertices part way along a triangle’s edge) doesn’t work. $\endgroup$ Jan 5, 2012 at 16:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.