Bob
BAN USERMy example is not a complete proof because I fixed the length of a, b, and c. If you change the length, then you should change the number of repeats as well. In my example, length(aaaaaa) = length(bbbb) = length(ccc), and that's the invariant you need to keep when use different numbers.
In your example, length(107) = 3, length (10) = 2, so you repeat 107 2 times, and 10 3 times. cc = 107107 > 101010 = aaa.
A formal way is to compare aa....a (repeat length(b)*length(c) times) , bb...b (repeat length(a)*length(c) times), cc...c (repeat length(a)*length(b) times).
I just found the proof. For ease of explanation, let's assume length(a) = 2, length(b) = 3 and length(c) = 4.
With ab > ba, we have aaabb > aabab > abaab > baaab > ... > bbaaa and therefore aaa > bb. Similarly, we have bbbb > ccc.
If ca > ac, then we have ccc > aaaaaa > bbbb > ccc. By contradiction, ac > ca.
If the input is {1, 10, 1000, 10}, then the optimal strategy is to pick the 1. Picking the best of left and right doesn't work.
- Bob February 19, 2013