8
$\begingroup$

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.
$\endgroup$
9
  • 1
    $\begingroup$ Do we have to use all of the square, or can we have some bits left over that aren't integer triangles? $\endgroup$
    – fljx
    Apr 23 at 14:55
  • $\begingroup$ you can have bits left over $\endgroup$ Apr 23 at 15:01
  • 1
    $\begingroup$ @WeatherVane ok if you do that then I will give you another bounty ;) $\endgroup$ Apr 30 at 12:56
  • 1
    $\begingroup$ This will keep me quiet for a while :) $\endgroup$ Apr 30 at 13:10
  • 1
    $\begingroup$ @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 :) $\endgroup$ May 9 at 22:26

3 Answers 3

12
+50
$\begingroup$

An optimal 26-triangle solution:

GeoGebra link
26 Triangles


Previous manual construction of a solution with 25 triangles:

These triangles were cut from corrugated stock paper on a CAD table.
enter image description here
Using 25 of the 26 triangles listed by Rob Pratt. The excluded triangle is $(3,4,4)$.

GeoGebra construction to confirm validity:

GeoGebra link
enter image description here

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

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

24 triangles.
enter image description here

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.
enter image description here
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.

$\endgroup$
8
  • $\begingroup$ 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. $\endgroup$
    – RobPratt
    Apr 25 at 13:51
  • 1
    $\begingroup$ @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. $\endgroup$ Apr 25 at 14:23
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 25 at 14:42
  • 2
    $\begingroup$ 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. $\endgroup$ Apr 26 at 13:48
  • 1
    $\begingroup$ Upper bound attained. See my updated answer. $\endgroup$ Apr 28 at 1:05
4
$\begingroup$

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$.

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$ Apr 23 at 18:53
  • 1
    $\begingroup$ @WeatherVane Thanks, corrected. I had used a default optimality tolerance of 1e-4 instead of 0. $\endgroup$
    – RobPratt
    Apr 23 at 19:25
  • $\begingroup$ 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. $\endgroup$ Apr 23 at 19:39
  • 1
    $\begingroup$ Nice work! Now we just need to pack them into the square... $\endgroup$ Apr 23 at 22:43
  • 1
    $\begingroup$ These 26 triangles can indeed be packed into a 10x10 square. $\endgroup$ Apr 28 at 1:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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