IBM Research | Ponder This | August 2010 challenges
Skip to main content

Ponder This

August 2010

<<July August September>>

Ponder This Challenge:

In Lilliput country, each citizen has a unique ID number with ten digits. Given a subset of citizens S, a pair of places. 1 < i < j < 10 is good if there is at least one pair of values vij, wij such that S contains no more than one citizen whose ID has digit vij in the ith place and digit wij in the jth place. The challenge for this month is to find an integer N and to describe a set S of size N for which all 45 pairs of places are good and prove that every set of size greater than N contains at least one pair which is not good.

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

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


Challenge: 08/01/2010 @ 11:14 AM EST
Solution: 09/01/2010 @ 11:14 AM EST
List Updated: 08/01/2010 @ 11:14 AM EST

People who answered correctly:

Dan Dima (08/02/2010 04:54 PM EDT)
Michael Brand (08/02/2010 08:32 PM EDT)
John T. Robinson (08/02/2010 10:48 PM EDT)
Kunal Shroff (08/03/2010 02:59 PM EDT)
Chen Wei (08/03/2010 09:41 PM EDT)
Dong-Gil Shin (08/04/2010 01:46 PM EDT)
William Heller (08/04/2010 06:11 PM EDT)
Piet Orye (08/05/2010 08:10 AM EDT)
Joseph DeVincentis (08/05/2010 10:09 AM EDT)
Marcel Caria (08/05/2010 01:15 PM EDT)
Kai Guttmann (08/05/2010 06:37 PM EDT)
Singularity Institute (08/05/2010 06:39 PM EDT)
Sylvain Becker (08/05/2010 06:39 PM EDT)
Viacheslav Chernoy (08/06/2010 04:21 AM EDT)
Clive Tong (08/06/2010 05:11 AM EDT)
Fabio Filatrella (08/06/2010 02:45 PM EDT)
Danny Antonetti (08/08/2010 08:10 PM EDT)
Stephen Herbert (08/09/2010 05:52 PM EDT)
David Friedman (08/09/2010 06:13 PM EDT)
Shmuel Menachem Spiegel (08/10/2010 01:49 AM EDT)
Albert Stadler (08/10/2010 08:57 AM EDT)
János Kramár (08/11/2010 02:39 AM EDT)
Thomas Rohr (08/11/2010 03:57 AM EDT)
Hamidreza Bidar (08/12/2010 04:57 AM EDT)
Daniel Bitin (08/15/2010 03:03 PM EDT)
Michael D Moffitt (08/15/2010 08:35 PM EDT)
Adam Daire (08/19/2010 10:54 PM EDT)
Harinarayanan.E.V (08/20/2010 02:47 PM EDT)
Erik Aas (08/27/2010 05:32 AM EDT)
Henry Shin (08/29/2010 12:38 AM EDT)
Tobias Madsen (08/30/2010 10:18 AM EDT)
Satyavarta (08/31/2010 12:04 PM EDT)
Abhishek Jha (08/31/2010 10:08 PM EDT)

Attention: If your name is posted here and you wish it removed please send email to the