August 2010
<<July August September>>
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.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com