Difference between revisions of "1990 USAMO Problems/Problem 1"

m (See Also)
m (Solutions)
 
Line 7: Line 7:
 
Consider license plates of <math>n</math> digits, for some fixed <math>n</math>, issued with the same criteria.
 
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 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> digits; 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.
 
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.

Latest revision as of 13:28, 20 November 2019

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

Solutions

Consider license plates of $n$ digits, for some fixed $n$, issued with the same criteria.

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

We now show that it is possible to issue $10^{n-1}$ distinct license plates which satisfy the problem's criteria. Indeed, we issue plates with all $10^{n-1}$ possible combinations for the first $n-1$ 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 $n-1$ digits, they agree on the last digit and are thus the same plate, and if two plates differ in only one of the first $n-1$ digits, they must differ as well in the last digit.

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


Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

See Also

1990 USAMO (ProblemsResources)
Preceded by
First question
Followed by
Problem 2
1 2 3 4 5
All USAMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Invalid username
Login to AoPS