The following problem is from the USA Math Olympiad (1990):
A certain state issues license plates consisting of six digits
(from 0 through 9). The state requires that any two plates differ
in at least two places. (Thus the plates 027592 and 020592 cannot
both be used.) Determine, with proof, the maximum number of distinct
license plates that the state can use.
SPOILER
From - Mon Jan 26 13:16:26 1998
From: hansz@cs.ruu.nl (Hans Zantema)
Newsgroups: sci.math
Subject: Re: An old Olympiad problem
>the following problem is from the USA Math Olympiad (1990):
>
>A certain state issues license plates consisting of six digits
>(from 0 through 9). The state requires that any two plates differ
>in at least two places. (Thus the plates 027592 and 020592 cannot
>both be used.) Determine, with proof, the maximum number of distinct
>license plates that the state can use.
>
>I have found that the answer is 100,000 but I got this through a
>convoluted reasoning: I would like to have a more clear and concise
>proof. Is anybody out there willing to help?
One way to reach 100,000 is the following: the first 5 digits are all
numbers from 00000 to 99999, the 6th digit is the sum of the first 5
modulo 10. Then it is easily seen that any two differ in at least two
places.
On the other hand assume a solution of over 100,000 is possible. Since
the first 5 digits have only 100,000 possible values, from these over
100,000 plates at least two are equal at all 5 first positions. Even
if the 6th position is different, they will not differ at at least two
places, contradiction.
Sufficiently clear and concise?
Hans Zantema,
The Netherlands, participant of the
International Math Olympiad 1974