September 2009
Diane can choose 17 different distances, up to an integer multiplicative factor: for example, 3*sqrt(22+42)=2*sqrt(62+32).
Monty can find integers which would allow him to choose alternating signs each time the same radical appears thus guaranteeing that the sum of any consecutive subsequence which appears an even number of times is zero.
No nontrivial linear combination of square-free integers can be an integer and therefore the game reduces to finding the longest sequence of letters from a 17-long character that does not contain any consecutive non-empty subsequence in which any character appears an even number of times.
Gray code (abacabadabacabaeabacabadabaf...) demonstrates the upper bound of 217-1. A simple counting argument proves a tight upper bound: if there are more than 217 characters, then the parity of the number of appearances should repeat and thus the corresponding subsequent sum is zero.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com