# Cutting a square into integer triangles

You are given a square piece of paper with size 10x10 units. What is the most number of triangles that can be cut from this square, such that:

1. Each triangle has integer sides.
2. Each triangle is distinct - cannot have the same lengths as another triangle.
• Do we have to use all of the square, or can we have some bits left over that aren't integer triangles?
– fljx
Apr 23, 2023 at 14:55
• you can have bits left over Apr 23, 2023 at 15:01
• @WeatherVane ok if you do that then I will give you another bounty ;) Apr 30, 2023 at 12:56
• This will keep me quiet for a while :) Apr 30, 2023 at 13:10
• @Dmitry it was a great challenge. My earlier answer found a solution of 22 in a couple of hours (not exhaustive) and I made improvements to the code to find 24 in less than 1 second, with no better found when left running overnight. But I've spent enough time on it now :) May 9, 2023 at 22:26

An optimal 26-triangle solution:

Previous manual construction of a solution with 25 triangles:

These triangles were cut from corrugated stock paper on a CAD table.

Using 25 of the 26 triangles listed by Rob Pratt. The excluded triangle is $$(3,4,4)$$.

GeoGebra construction to confirm validity:

• OMG I love this so much! Thank you for putting in the effort! Apr 27, 2023 at 2:33
• I wonder if you can shift the central big triangle to the left to make space for the last one? Apr 27, 2023 at 2:34
• I update my answer by hand, before I noticed this! Apr 27, 2023 at 7:45
• @DmitryKamenetsky Optimal solution found. Apr 28, 2023 at 1:01
• @DanielMathias superb work! Stay tuned for a bonus. Apr 28, 2023 at 1:37

Update prompted by @AxiomaticSystem, tweaked by hand to add 2 more triangles.

24 triangles.

So far: I have improved on the range of triangles available ...

Summary:
Smallest sum of areas: $$94.398979$$
Largest sum of areas: $$99.999984$$

Triangles with side length up to $$14$$ can be used, and there are $$225$$ such.
Sorted by area, they are:
$$(1,1,1),(1,2,2),(1,3,3),(2,2,2),(2,2,3),(1,4,4),(1,5,5),(2,3,3),(2,3,4),(1,6,6),(1,7,7),(2,4,5),(2,4,4),(3,3,3),(1,8,8),(3,3,5),(3,3,4),(1,9,9),(2,5,6),(2,5,5),(1,10,10),(3,4,6),(1,11,11),(3,4,4),(2,6,7),(2,6,6),(1,12,12),(3,4,5),(2,7,8),(1,13,13),(3,5,7),(4,4,7),(2,7,7),(4,4,4),(3,5,5),(2,8,9),(3,5,6),(3,6,8),(4,4,5),(2,8,8),(4,4,6),(2,9,10),(4,5,8),(3,6,6),(3,7,9),(2,9,9),(3,6,7),(2,10,11),(4,5,5),(4,6,9),(4,5,7),(5,5,9),(2,11,12),(3,8,10),(4,5,6),(2,10,10),(3,7,7),(3,7,8),(2,12,13),(5,5,5),(4,7,10),(2,11,11),(3,9,11),(4,6,6),(5,6,10),(4,6,8),(3,8,8),(3,8,9),(2,12,12),(4,6,7),(5,5,6),(5,5,8),(3,10,12),(4,8,11),(5,5,7),(2,13,13),(5,7,11),(6,6,11),(3,9,10),(3,9,9),(3,11,13),(4,7,9),(4,7,7),(5,6,6),(4,9,12),(4,7,8),(5,6,9),(3,12,14),(5,8,12),(3,10,11),(5,6,7),(3,10,10),(6,7,12),(5,6,8),(4,10,13),(4,8,10),(4,8,8),(6,6,6),(4,8,9),(5,9,13),(3,11,12),(5,7,10),(4,11,14),(5,7,7),(3,11,11),(6,6,10),(6,8,13),(7,7,13),(4,9,11),(6,6,7),(5,7,8),(5,7,9),(3,12,13),(4,9,9),(5,10,14),(6,6,9),(3,12,12),(6,6,8),(4,9,10),(5,8,11),(6,9,14),(4,10,12),(7,8,14),(6,7,11),(6,7,7),(5,8,8),(4,10,10),(5,8,10),(5,8,9),(4,10,11),(6,7,8),(5,9,12),(4,11,13),(6,7,10),(6,7,9),(7,7,7),(6,8,12),(5,9,9),(4,11,11),(7,7,12),(4,11,12),(5,9,11),(6,8,8),(5,10,13),(5,9,10),(7,7,8),(6,8,11),(6,8,9),(4,12,12),(6,9,13),(7,7,11),(6,8,10),(7,7,9),(5,10,10),(7,8,13),(5,11,14),(7,7,10),(5,10,12),(5,10,11),(7,8,8),(6,9,9),(6,10,14),(6,9,12),(6,9,10),(5,11,11),(7,8,9),(7,9,14),(5,11,13),(7,8,12),(6,9,11),(8,8,14),(5,11,12),(8,8,8),(7,8,10),(7,8,11),(6,10,10),(6,10,13),(7,9,9),(6,10,11),(8,8,9),(6,10,12),(7,9,13),(8,8,13),(7,9,10),(8,8,10),(7,9,12),(7,9,11),(8,8,12),(6,11,11),(8,8,11),(8,9,9),(7,10,10),(6,11,12),(7,10,14),(8,9,14),(8,9,10),(7,10,11),(7,10,13),(7,10,12),(9,9,9),(8,9,11),(8,9,13),(8,9,12),(7,11,11),(8,10,10),(9,9,10),(8,10,11),(9,9,11),(8,10,14),(9,9,14),(8,10,12),(8,10,13),(9,10,10),(9,9,12),(9,9,13),(9,10,11),(10,10,10),(9,10,12),(9,10,14),(9,10,13),(10,10,11),(10,10,12),(10,11,11),(10,10,13),(10,10,14)$$

The sum of the smallest $$27$$ triangles is more than $$100$$, so the most triangles that can be used in any arrangement is $$26$$. So far my brute forcing has found about $$90,000$$ permutations of triangles (without trying to pack them) having a total sum of areas in this range:

Smallest: $$94.3989794542673764$$ comprising
$$(1,1,1),(1,2,2),(1,3,3),(2,2,2),(2,2,3),(1,4,4),(1,5,5),(2,3,3),(2,3,4),(1,6,6),(1,7,7),(2,4,5),(2,4,4),(3,3,3),(1,8,8),(3,3,5),(3,3,4),(1,9,9),(2,5,6),(2,5,5),(1,10,10),(3,4,6),(1,11,11),(3,4,4),(2,6,7),(2,6,6).$$

Largest: $$99.9999838387641660$$ comprising
$$(1,1,1),(1,2,2),(1,3,3),(2,2,2),(2,2,3),(1,4,4),(1,5,5),(2,3,3),(2,3,4),(1,6,6),(1,7,7),(2,4,5),(3,3,3),(1,8,8),(3,3,5),(3,3,4),(1,9,9),(2,5,6),(1,10,10),(3,4,6),(1,11,11),(3,4,4),(1,12,12),(3,4,5),(2,7,7),(4,4,4)$$
and also having the same area is
$$(1,1,1),(1,2,2),(1,3,3),(2,2,2),(2,2,3),(1,4,4),(1,5,5),(2,3,3),(2,3,4),(1,6,6),(1,7,7),(2,4,5),(3,3,3),(1,8,8),(3,3,5),(3,3,4),(1,9,9),(2,5,6),(1,10,10),(3,4,6),(1,11,11),(2,6,7),(1,12,12),(3,4,5),(2,7,7),(4,4,4)$$
which differ by one triangle: apparently $$(3,4,4)$$ and $$(2,6,7)$$ have the same area.

The largest triangle which can be used is the 65th: $$(5,6,10)$$. The sum of this area and the first $$25$$ triangles is less than $$100$$.

My initial rough testing has found ...

... an arrangement of 22 triangles. It doesn't look very well packed and I am sure this can be improved (it hasn't finished running) – with a better approach to the problem.

Plainly I am creating chains of triangles with equal side length. An improvement could be to consider a propagation of triangles from one free side; from the other; and from both.

• Yes, we should consider side length up to $\lfloor 10 \sqrt2 \rfloor = 14$, but I get $308$ such, still yielding an upper bound of $26$ triangles. Apr 25, 2023 at 13:51
• @RobPratt yes there are 308 such triangles, but only 225 of them can can be contained in a 10x10 square, for example $(14,14,14)$ cannot. Having more, narrow triangles such as $(1,12,12)$ gives more options in packing. You can see from my area sequence that some of these have less area than some of those bound by a side length of 10. Apr 25, 2023 at 14:23
• Very nice work! You are now only a few triangles away from the upper bound. There are some big gaps, so it seems that more can still fit in. Apr 25, 2023 at 14:42
• It appears that (1,8,8), or even (1,9,9), can fit along the right side as-is, and that (1,2,2) fits inside the upper hole. Performing that move, and then moving up the cluster in the bottom left up a bit should accommodate another (1,x,x) triangle along the bottom. Apr 26, 2023 at 13:48
• Upper bound attained. See my updated answer. Apr 28, 2023 at 1:05

Not an answer, but too long for a comment.

There are $$125$$ triples $$(a,b,c)$$ with $$a,b,c\in\{1,\dots,10\}$$, $$a \le b \le c$$, and $$a+b>c$$. By considering areas only, solving a binary knapsack problem yields an upper bound of

$$26$$ triangles:

$$\{(1,1,1),(1,2,2),(1,3,3),(1,4,4),(1,5,5),(1,6,6),(1,7,7),(1,8,8),(1,9,9),(1,10,10),(2,2,2),(2,2,3),(2,3,3),(2,3,4),(2,4,4),(2,4,5),(2,5,5),(2,5,6),(2,6,6),(2,6,7),(3,3,3),(3,3,4),(3,3,5),(3,4,4),(3,4,5),(3,4,6)\}$$

that together use

$$\approx 94.905$$ units of area, which turns out to be the minimum for $$26$$ triangles.

The maximum total area at most $$100$$ for $$26$$ triangles turns out to be $$\approx 99.999858453$$.

• I make the maximum area for 26 triangles to be 99.999858 (without attempting to pack). When ordered by area, these are triangles 0 to 30 without 20, 22, 23, 24 and 26. Apr 23, 2023 at 18:53
• @WeatherVane Thanks, corrected. I had used a default optimality tolerance of 1e-4 instead of 0. Apr 23, 2023 at 19:25
• There seems to be some debate about whether this packing problem is NP-hard or NP-complete. I wonder whether the OP knows a definitive answer, or if this will turn out to be another 'race': user X finds 10 triangles, user Y finds 11, etc. Apr 23, 2023 at 19:39
• Nice work! Now we just need to pack them into the square... Apr 23, 2023 at 22:43
• These 26 triangles can indeed be packed into a 10x10 square. Apr 28, 2023 at 1:03