IBM Ponder This #148 · August 2010

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.

Solution

Best opened after a real attempt

To be added.