## August 2010

<<July
**August**
September>>

For each one of the 45 pairs, there is at most one citizen whose ID has the v_{ij}, w_{ij} 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 9^{n} 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)} + 9^{n} = (n+1+9)*9^{n}. 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: 9^{n} + n*9^{n-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