Suggested to me by Giridhar Addepalli (IITK CSE Alumnus, Yahoo! Sr. Software Engineer). Nice puzzle. Original Source is "Thinking Mathematically" (Amazon Link). Giridhar posts nice mathematical problems on his blog.
Interesting puzzle. It is not an easy problem. But the experience of getting stuck trying to solve the problem is in itself rewarding.
Hint: Try and specialize. Organize the results of specialising. Make a conjecture, however wild. Check and prove your conjecture.
Followup: Given by Giridhar on his blog. Using this, find an O(1) space algorithm to "rotation of array" problem where you are asked to rotate the array by a given amount k. For example, rotating Array containing 3, 5, 9, 14, 1, 2, 11 by 3 positions will yield 14, 1, 2, 11, 3, 5, 9.
O(k) space algorithm is of course trivial. Can you find an O(1) space algorithm?