A license plate has six digits from 0 to 9 and may have leading zeros. If two plates must always differ in at least two places, what is the largest number of plates that is possible?
Solution
Answer: 105.
We show by induction that we can find a set of 10n-1 plates for n > 1 digits. It is true for n = 2: take the plates 00, 11, 22, ... , 99. Suppose it is true for n. If d is a digit from 0 to 9 and s is a plate of n digits, let [d, s] be the plate of n+1 digits which has a as its first digit, and the remaining digits the same as those of s, except that the last digit is that for s plus d (reduced mod 10 if necessary). Let S be a set of plates for n digits. We claim that the set S' = { [d, s] : d = 0, 1, ... or 9 and s belongs to S} is a set of plates for n+1 digits. It obviously has 10 times as many members as S, so this claim is sufficient to establish the induction.
We have to show that [a, s] and [b, t] differ in at least two places. If a = b, then s ≠ t, so s and t differ in at least two places. The same change is made to their last digits, so [a, s] and [a, t] differ in at least two places. If a ≠ b and s = t, then [a, s] and [b, s] differ in both their first and last places. If a ≠ b and s ≠ t, then s and t differ in at least two places and so the modified s and t, differ in at least one place. But [a, s] and [b, t] also differ in the first place, so they differ in at least two places.
So we have established that the largest number is at least 10n-1 for n digits.
But any two plates which differ only in the last digit cannot both be chosen. So at most 1/10 of the 10n possible plates can be chosen. That shows that 10n-1 is best possible.
© John Scholes
jscholes@kalva.demon.co.uk
11 May 2002