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.)
(In reply to
some thoughts by Steven Lord)
I thought I would see what a basic greedy algorithm would get: take the largest triangle possible and remove any conflicting triangle. With the cross references I did this by hand.
From the list of 49 I ended up with these 13 triangles.
2) [ 30] ( 5,12,13) 1 6 10 11 12
5) [ 60] ( 8,15,17) 3 6 14 15
8) [ 120] (10,24,26) 3 4 19 24 25 26
21) [ 210] (20,21,29) 10 15 20 22 23
31) [ 600] (30,40,50) 7 13 17 19 26 30 40 41
29) [ 630] (28,45,53) 23 25 28 43
42) [1176] (42,56,70) 24 33 40
44) [1320] (48,55,73) 13 20 34 36 45
35) [1470] (35,84,91) 11 12 23
39) [1560] (39,80,89) 14 18 38 45
46) [1734] (51,68,85) 12 25 32 37 41
48) [1890] (60,63,87) 9 16 27 32 36 43
49) [2340] (65,72,97) 16 22 27 30 33 38 47
The add in the uncontested (57,76,95) for a set of 14 triangles.
re: some thoughts
