You are given 99 thin rigid rods with lengths 1, 2, 3, ..., 99. You are asked to assemble these into as many right triangles as you wish. What is the largest total area that can be obtained? (Each side of a triangle must be one entire rod.)
Total area= 15,858
I took the very trackable 'greed algorithm' of Brian Smith and
'cooked' the data a bit to get the algorithm to explore alternative
paths. Specifically, I introduced "false" areas F_Area, for each triangle that
were different from the true areas by +/- 40%, as uniformly distributed by
a random variable. I ran the greed algorithm from a sorted list of the
false areas but kept track of the accumulation of the actual areas. After about
20 simulations a winner appeared and this solution persisted even with 1000
random trials. Changing to a +/- 95% alteration in areas yielded the same
solution, so it seams very robust and likely right.
15 triangles:
Total area= 15858
Tri# Area F_Area Triplet
---------------------------
1) [1944][1253](54,72,90)
2) [1734][1151](51,68,85)
3) [1890][1242](60,63,87)
5) [1470][1998](35,84,91)
6) [1320][ 953](48,55,73)
7) [1560][1540](39,80,89)
10) [ 840][ 736](40,42,58)
16) [ 924][ 629](33,56,65)
20) [ 630][ 675](28,45,53)
29) [ 840][ 580](24,70,74)
35) [ 210][ 245](20,21,29)
36) [ 240][ 215](16,30,34)
44) [ 60][ 42]( 8,15,17)
47) [ 30][ 32]( 5,12,13)
and 2166 from (57,76,95)
Later: further proof - doing the boil without the greed:
I tried the experiment making the fake areas completely random -
I just assigned a random number to each area and ran the algorithm,
constructing allowed remaining triangles in any order. The maximum area subset remained the same solution: 15,858. Out of 1,000,000 random realizations, this maximum occurs about 7 +/- 4 times.
Edited on July 24, 2024, 11:12 am
soln (boiled greed)
