IBM Research | Ponder This | July 2000 challenges

Ponder This

July 2000

<<June July August>>

Ponder This Challenge:

As a summer treat (or a winter treat for our Australian friends),
an old puzzle by J. H. Conway.

You have an infinite two dimensional grid.
The vertices are given by pairs of integers (x,y).
You have a large but finite collection of coins,
which you place on some of the vertices, at most one coin per vertex, and initially restricted to the sites with nonnegative y
(that is, the upper half plane, including the x-axis).

Now you "jump" coins: if two coins are adjacent either vertically or horizontally, with an empty space adjacent, then
you are allowed to pick up the first coin, jump
over the second coin, and land in the next space (the empty one). The "second coin" is removed from the grid.
During the jumping phase, coins are allowed to stray into the territory of negative y.

Your objective is to push a coin as far "down" as possible into the territory of negative y.

If we started with coins at (0,0), (0,1), (1,0) and (2,0), the second
coin could jump over the first into position (0,-1), leaving us with
three coins at (0,-1), (1,0), (2,0). The coin at (2,0) jumps over the
coin at (1,0), leaving us with two coins at (0,-1), (0,0). One
final jump leaves us with a single coin at (0,-2). But you can
do better than that, can't you?

A complete solution will be of the form: "(0,-yyy) is achievable by starting with coins at (0,0), (0,1), ..., . But (0, -zzz) is not achievable because ... ". Here yyy and zzz are consecutive integers.

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: 07/05/00 @ 10:00 AM EST
Solution: 08/02/00 @ 9:30 AM EST
List Updated: 07/21/00 @ 5:00 PM EST

Tim Edmonds (7.5.2000 @ 5:26 PM EDT)
Ionel Santa* (7.7.2000 @ 6:22 AM EDT)
Mohit Sauhta (7.7.2000 @ 3:15 PM EDT)
Jessica Lang Jones* (7.10.2000 @ 3:41 PM EDT)
Jimmy Hu* (7.10.2000 @ 4:07 PM EDT)
Héctor Ferazza (7.10.2000 @ 8:31 PM EDT)
Didier Bizzarri* (7.11.2000 @ 5:23 AM EDT)
Markus Kuhn (7.11.2000 @ 10:14 AM EDT)
Samantha Levin (7.11.2000 @ 11:56 AM EDT)
Sam Flores (7.11.2000 @ 2:14 PM EDT)
Prithu Bharti Tiwari (7.13.2000 @ 3:58 AM EDT)
Ming Song (7.13.2000 @ 10:13 PM EDT)
Lucy Xu (7.14.2000 @ 7:14 PM EDT)
Gabriel Simon (7.16.2000 @ 4:39 AM EDT)
Philippe Fondanaiche (7.16.2000 @ 11:00 AM EDT)
Tim Wilkin (7.16.2000 @ 11:54 PM EDT)
Shmuel Spiegel (7.17.2000 @ 10:03 AM EDT)
Amos Guler (7.19.2000 @ 4:26 AM EDT)
Thomas Rohr (7.21.2000 @ 8:19 AM EDT)

* indicates respondent included the reason why (0,-zzz) is not achievable.

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