Ponder This Challenge - August 2010 - Lilliput unique ID numbers

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 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

  For each one of the 45 pairs, there is at most one citizen whose ID has the vij, wij values.
  Thus, removing them will reduce the set of IDs by no more than 45 and will get us a set where every pair has a value that does not appear at all. Denote such set as "very good".

  Claim: A very good set for n-digits ID numbers has no more than (n+9)*9(n-1) elements.

  Proof: By induction: for n=1. It is easy to see that the bound is trivial (10). Assume correct for n, then for n+1 digits project the set on its first n digits. We can get each value no more than 10 times, but actually only 9n values can have 10 duplicates without violating the "very good" status of the set. So the number of elements is no more than 9*(n+9)*9(n-1) + 9n = (n+1+9)*9n. QED

  An example of a set of citizens that matches the above upper bound is the set of all IDs that contain less than two zeros: 9n + n*9n-1.
  Adding the 45 citizens with ID numbers with ID numbers with two zeros and 9s as all the other gives us 7,360,989,336.

Solvers

• 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)
• (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)