Ponder This

September 2009

<<August September October>>

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

  

Challenge: 08/31/2009 @ 15:00 PM EST
Solution: 10/01/2009 @ 15:00 PM EST
List Updated: 10/14/2009 @ 15:00 PM EST

People who answered correctly:

Adam Daire (08/31/2009 05:08 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)
Joe 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)

Attention: If your name is posted here and you wish it removed please send email to the ponder@il.ibm.com.