All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
99 Rods #1 (Posted on 2024-07-21) Difficulty: 3 of 5
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.)

No Solution Yet Submitted by K Sengupta    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
some thoughts | Comment 2 of 5 |
This is a difficult problem. 

One thing may be said right off: the triangle 57 76 95
will be in the solution since its rods are not useful anywhere else.
But that's the only one. (That was a small joke).

That leaves 49 possible triangles interconnected in a web containing 148 links where each link means the presence of one triangle excludes the possibility of the other. 

The goal is to remove the right group of possible triangles from the 49 such that no links remain, i.e., no rod is used twice _and_ the additional goal is the right triangles are removed so that the total area is maximized. 

The solution would be possible with a supercomputer: If all possible 
triangle subsets of the 49 (2^49 = approx. 10^15) were checked for conflicts and the un-conflicted subsets were ranked by total area, the problem is solved.

An alternative approach is through a minimization - such as the Richardson-Lucy method. Here, starting with a prior (e.g. all triangles present) a weighting of the success of the result could be computed: something like the total area - 10000 * the number of remaining conflicts. On each iteration a threshold for including or excluding a triangle could come from the degree to which that triangle contributed to the success function, 
i.e., a Bayesian approach.

Given a tuned success function, this might work. 

And alternative is to optimize the triangle areas over say 1000 by ignoring the other smaller triangles. Add these in latter as possible.

I include my version of Charlie's conflict list: 

lord@rabbit 13891 % more ff.txt 

Tri#  area      triplet    conflicts with these Tri#'s
 1) [   6]   ( 3, 4, 5)    2
 2) [  30]   ( 5,12,13)    1  6 10 11 12
 3) [  24]   ( 6, 8,10)    5  8
 4) [  84]   ( 7,24,25)    8 15 19 24 25 26 27
 5) [  60]   ( 8,15,17)    3  6 14 15
 6) [  54]   ( 9,12,15)    2  5  7 10 11 14 15
 7) [ 180]   ( 9,40,41)    6 26 31 40 41
 8) [ 120]   (10,24,26)    3  4 19 24 25 26
 9) [ 330]   (11,60,61)   27 32 36 43 48
10) [  96]   (12,16,20)    2  6 11 15 16 17 20 21
11) [ 210]   (12,35,37)    2  6 10 23 35
12) [ 546]   (13,84,85)    2 35 37 41 46
13) [ 336]   (14,48,50)   20 31 36 44 45
14) [ 270]   (15,36,39)    5  6 15 28 36 37 38 39
15) [ 150]   (15,20,25)    4  5  6 10 14 20 21 27
16) [ 504]   (16,63,65)   10 17 27 33 38 48 49
17) [ 240]   (16,30,34)   10 16 19 30 31
18) [ 720]   (18,80,82)   19 39 45
19) [ 216]   (18,24,30)    4  8 17 18 24 25 26 30 31
20) [ 480]   (20,48,52)   10 13 15 21 36 38 44 45
21) [ 210]   (20,21,29)   10 15 20 22 23
22) [ 756]   (21,72,75)   21 23 30 41 43 47 49
23) [ 294]   (21,28,35)   11 21 22 29 35
24) [ 840]   (24,70,74)    4  8 19 25 26 42
25) [ 540]   (24,45,51)    4  8 19 24 26 28 29 43 46
26) [ 384]   (24,32,40)    4  7  8 19 24 25 31 32 40 41
27) [ 750]   (25,60,65)    4  9 15 16 32 33 36 38 43 48 49
28) [ 486]   (27,36,45)   14 25 29 36 37 43
29) [ 630]   (28,45,53)   23 25 28 43
30) [1080]   (30,72,78)   17 19 22 31 47 49
31) [ 600]   (30,40,50)    7 13 17 19 26 30 40 41
32) [ 960]   (32,60,68)    9 26 27 36 43 46 48
33) [ 924]   (33,56,65)   16 27 34 38 42 49
34) [ 726]   (33,44,55)   33 44
35) [1470]   (35,84,91)   11 12 23
36) [ 864]   (36,48,60)    9 13 14 20 27 28 32 37 43 44 45 48
37) [1386]   (36,77,85)   12 14 28 36 41 46
38) [1014]   (39,52,65)   14 16 20 27 33 39 49
39) [1560]   (39,80,89)   14 18 38 45
40) [ 840]   (40,42,58)    7 26 31 41 42
41) [1500]   (40,75,85)    7 12 22 26 31 37 40 43 46
42) [1176]   (42,56,70)   24 33 40
43) [1350]   (45,60,75)    9 22 25 27 28 29 32 36 41 48
44) [1320]   (48,55,73)   13 20 34 36 45
45) [1536]   (48,64,80)   13 18 20 36 39 44
46) [1734]   (51,68,85)   12 25 32 37 41
47) [1944]   (54,72,90)   22 30 49
48) [1890]   (60,63,87)    9 16 27 32 36 43
49) [2340]   (65,72,97)   16 22 27 30 33 38 4

totlinks=          148 (each listed twice above)

Edited on July 22, 2024, 9:24 pm
  Posted by Steven Lord on 2024-07-22 12:10:18

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (1)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (4)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information