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
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.
Here's my solution with 32 triangles.
How
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:
I can search further, but searching all 14-triangle polygons takes many hours.
A shortcut
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 forma+b*sqrt(3), for fractional numbersaandb).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).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
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.
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