## Problem 1

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: $10^{2}$.

We show by induction that we can find a set of $10^{\mathrm{n}-1}$ plates for $\mathrm{n}>1$ digits. It is true for $\mathrm{n}=2$ : take the plates $00,11,22, \ldots, 99$. Suppose it is true for $\mathrm{n}$. If $\mathrm{d}$ is a digit from 0 to 9 and $\mathrm{s}$ is a plate of $\mathrm{n}$ digits, let $[\mathrm{d}, \mathrm{s}]$ be the plate of $\mathrm{n}+1$ digits which has a as its first digit, and the remaining digits the same as those of $\mathrm{s}$, except that the last digit is that for $\mathrm{s}$ plus $\mathrm{d}$ (reduced mod 10 if necessary). Let $\mathrm{S}$ be a set of plates for $\mathrm{n}$ digits. We claim that the set $\mathrm{S}^{\prime}=\{[\mathrm{d}, \mathrm{s}]: \mathrm{d}=0,1, \ldots$ or 9 and $\mathrm{s}$ belongs to $\mathrm{S}\}$ is a set of plates for $\mathrm{n}+1$ digits. It obviously has 10 times as many members as $\mathrm{S}$, so this claim is sufficient to establish the induction.

We have to show that $[\mathrm{a}, \mathrm{s}]$ and $[\mathrm{b}, \mathrm{t}]$ differ in at least two places. If $\mathrm{a}=\mathrm{b}$, then $\mathrm{s} \neq \mathrm{t}$, so $\mathrm{s}$ and $\mathrm{t}$ differ in at least two places. The same change is made to their last digits, so $[\mathrm{a}, \mathrm{s}]$ and $[\mathrm{a}, \mathrm{t}]$ differ in at least two places. If $\mathrm{a} \neq \mathrm{b}$ and $\mathrm{s}=\mathrm{t}$, then $[\mathrm{a}, \mathrm{s}]$ and $[\mathrm{b}, \mathrm{s}]$ differ in both their first and last places. If $\mathrm{a} \neq \mathrm{b}$ and $\mathrm{s} \neq \mathrm{t}$, then $\mathrm{s}$ and $\mathrm{t}$ differ in at least two places and so the modified $\mathrm{s}$ and $\mathrm{t}$, differ in at least one place. But $[\mathrm{a}, \mathrm{s}]$ and $[\mathrm{b}, \mathrm{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 $10^{n-1}$ for $\mathrm{n}$ digits.

But any two plates which differ only in the last digit cannot both be chosen. So at most $1 / 10$ of the $10^{\mathrm{n}}$ possible plates can be chosen. That shows that $10^{\mathrm{n}-1}$ is best possible.

