In the tree below, the objective is to find the path, left-to-right, which yields the highest sum.
The solution sieve, expanded, not optimized or simplified:
Take the largest number in each final choice of nodes, last column
1 4 2 1 2 1 4 2 -> (1/4) 4 (2/1) 2 (2/1) 2 (4/2) 4 -> 4 2 2 4
Add to the parent node value to simplify to largest possible branch value
4 2 2 4 -> 4+1 2+4 2+2 4+5 -> 5 6 4 9
Reduce the row again by eliminating the small node in each branch
5 6 4 9 -> (5/6) 6 (4/9) 9 -> 6 9
Repeating these steps, right to left, we continue:
6 9 -> 6+3 9+1 -> 9 10
To conclude at the largest possible path sum:
9 10 -> (9/10) -> 10
The path is 1 -> 5 -> 4; 1+5+4=10
Tree sums
I was reversing the sieve for finding the lowest summing path (quite simple, just choose the lowest number instead of the highest), when I discovered this could also be applied to path products!
Simply multiply the highest numbers instead of adding, working your way right to left as usual. In this case, the solution is:
3 -> 4 -> 2 (left to right) ; 3*4*2=24
The next step?
This also works for exponents, as well, although you'll be dealing with some very large numbers. Seemed too simple, though. There must be something more challenging, like finding a formula for the instantaneous frequency of f(x)=sin(x^2), cryptography, patterns in prime numbers (impossible), or even more impossible, installing Linux on a GameCube (PowerPC = BAD processor, maybe M*c OS X?)
That was COOL.
Very fun. I wish to work for Clay Mathematics Instutute when I grad!
