View source

==Problem==

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 <math>\boxed{027592}</math> and <math>\boxed{020592}</math> cannot both be used.) Determine, with proof, the maximum number of distinct license plates that the state can use.

== Solutions ==

Consider license plates of <math>n</math> digits, for some fixed <math>n</math>, issued with the same criteria.

We first note that by the pigeonhole principle, we may have at most <math>10^{n-1}</math> distinct plates.  Indeed, if we have more, then there must be two plates which agree on the first <math>n-1</math> plates; these plates thus differ only on one digit, the last one.

We now show that it is possible to issue <math>10^{n-1}</math> distinct license plates which satisfy the problem's criteria.  Indeed, we issue plates with all <math>10^{n-1}</math> possible combinations for the first <math>n-1</math> digit, and for each plate, we let the last digit be the sum of the preceding digits taken mod 10.  This way, if two plates agree on the first <math>n-1</math> digits, they agree on the last digit and are thus the same plate, and if two plates differ in only one of the first <math>n-1</math> digits, they must differ as well in the last digit.

It then follows that <math>10^{n-1}</math> is the greatest number of license plates the state can issue.  For <math>n=6</math>, as in the problem, this number is <math>10^5</math>.  <math>\blacksquare</math>


{{alternate solutions}}

==See also==

{{USAMO newbox|year=1990|before=First question|num-a=2}}
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=63538#63538 Discussion on AoPS/MathLinks]


[[Category:Olympiad Combinatorics Problems]]