Ponder This Challenge - September 2009 - Non repeating cumulative sum

Ponder This Challenge:

Diane and Monty are playing the following game:
They start with a real number s. In each turn Diane chooses two squares from a chess board and then Monty picks up a nonzero integer number c. The multiplication of c and the distance d between the centers of the two squares is added to s.

What is the longest sequence of distances Diane can choose such that Monty will not be able to make s repeat itself anywhere in the sequence?
Prove your claim by demonstrating an upper bound and proving a tight lower bound.

Update 09/04:
To clarify:

1. Diane can choose the same square many times.
2. Monty chooses its number *after* knowing Diane's choice.
3. s is updated each turn (a cumulative sum).
4. Monty wins when the current s repeats any previous value of s.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  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.

Solvers

• Adam Daire (08/31/2009 05:08 PM EDT)
• (08/31/2009 05:13 PM EDT)
• Austin Shapiro (08/31/2009 05:13 PM EDT)
• Eli Biham (08/31/2009 07:26 PM EDT)
• Yuval Filmus (09/01/2009 01:28 AM EDT)
• Andrew Holster (09/01/2009 03:40 AM EDT)
• Fred Batty (09/01/2009 05:22 AM EDT)
• Lukasz Bolikowski (09/01/2009 09:47 AM EDT)
• Tejaswi Navilarekallu (09/01/2009 11:53 AM EDT)
• Albert Stadler (09/01/2009 12:27 PM EDT)
• Michael Brand (09/01/2009 01:00 PM EDT)
• Abhiman Chatra B (01/09/2009 03:26 PM EDT)
• Razvan Gheorghita (09/02/2009 07:57 AM EDT)
• Jerome Neyrat (09/02/2009 01:44 PM EDT)
• Christian Blatter (09/02/2009 03:34 PM EDT)
• Hagen von Eitzen (09/02/2009 04:43 PM EDT)
• Yu Yat Hong (09/03/2009 01:58 AM EDT)
• Mark Mixer (09/03/2009 11:07 AM EDT)
• Corey Cerovsek (09/03/2009 06:28 PM EDT)
• Daniel Bitin (09/04/2009 02:36 PM EDT)
• Dan Dima (09/07/2009 05:08 AM EDT)
• Andrew Buchanan (09/07/2009 01:32 PM EDT)
• Greg McNulty (09/08/2009 02:32 AM EDT)
• Prodipta Ghosh (09/08/2009 03:37 PM EDT)
• David Friedman (09/08/2009 04:31 PM EDT)
• Alexander Wagner (09/08/2009 04:58 PM EDT)
• John G Fletcher (09/09/2009 03:58 PM EDT)
• Arnab Bose (09/10/2009 06:35 AM EDT)
• Bojan Basic (09/10/2009 12:48 PM EDT)
• Sylvain Becker (09/10/2009 06:40 PM EDT)
• Tom Sirgedas (09/10/2009 06:52 PM EDT)
• Nicolas Landes (09/11/2009 08:04 PM EDT)
• J (09/13/2009 06:31 PM EDT)
• oe Riel (09/13/2009 06:31 PM EDT)
• John T. Robinson (09/14/2009 05:18 PM EDT)
• Hamidreza Bidar (09/14/2009 11:21 PM EDT)
• Arthur Breitman (09/15/2009 03:50 PM EDT)
• Ashutosh Mahajan (09/15/2009 09:15 PM EDT)
• Subramanian C. A (09/16/2009 01:36 AM EDT)
• Gale Greenlee (09/16/2009 11:06 AM EDT)
• Wu Zheng Kai (09/17/2009 08:52 AM EDT)
• Joseph DeVincentis (09/17/2009 09:28 AM EDT)
• Balakrishnan V (09/17/2009 01:53 PM EDT)
• Ian Soon (09/18/2009 04:45 AM EDT)
• Clive Tong (09/19/2009 03:33 AM EDT)
• Christian Kissig (09/21/2009 05:45 AM EDT)
• Frank Mullin (09/21/2009 10:02 AM EDT)
• Hongcheng Zhu (09/21/2009 10:26 PM EDT)
• Siva Dirisala (09/22/2009 12:29 PM EDT)
• Sergei Agievich (09/22/2009 02:00 PM EDT)
• Jason L. (09/22/2009 03:04 PM EDT)
• Harald Bögeholz (09/23/2009 03:40 PM EDT)
• Kin Keung Ma (09/23/2009 06:20 PM EDT)
• Joseph Bonneau and Andrew Lewis (09/24/2009 10:06 AM EDT)
• Mutaamba Maasha (09/25/2009 04:05 PM EDT)
• Chris Shannon (09/28/2009 08:56 PM EDT)
• Nyles Heise (09/28/2009 11:02 PM EDT)
• Forest Deal (09/28/2009 11:10 PM EDT)
• Satish Kumar K N (09/29/2009 02:58 PM EDT)
• Karl D'Souza (09/29/2009 08:37 PM EDT)
• Andreas Stiller (09/29/2009 11:58 PM EDT)
• Jimmy He (09/30/2009 03:05 PM EDT)
• Slawomir Pudlis (10/01/2009 05:16 AM EDT)