Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(→‎See also: first question)
(reverted to original wording; removed induction from solution)
Line 1: Line 1:
 
==Problem==
 
==Problem==
−
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==
+
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.
−
We show by induction that we can find a set of <math>10^{n-1}</math> plates for <math>n > 1</math> digits. It is true for <math>n = 2</math>: take the plates <math>00, 11, 22, ... , 99</math>. Suppose it is true for <math>n</math>. If d is a digit from <math>0</math> to <math>9</math> and <math>s</math> is a plate of <math>n</math> digits, let <math>[d, s]</math> be the plate of <math>n+1</math> digits which has a as its first digit, and the remaining digits the same as those of <math>s</math>, except that the last digit is that for <math>s</math> plus <math>d</math> (reduced <math>\pmod {10}</math> if necessary). Let <math>S</math> be a set of plates for <math>n</math> digits. We claim that the set <math>S' = { [d, s] : d = 0, 1, ...</math> or <math>9</math> and <math>s</math> belongs to <math>S</math>} is a set of plates for <math>n+1</math> digits. It obviously has <math>10</math> times as many members as <math>S</math>, so this claim is sufficient to establish the induction.
 
  
−
We have to show that <math>[a, s]</math> and <math>[b, t]</math> differ in at least two places. If <math>a = b</math>, then <math>s \ne t</math>, so s and t differ in at least two places. The same change is made to their last digits, so <math>[a, s]</math> and <math>[a, t]</math> differ in at least two places. If <math>a ≠ b</math> and <math>s = t</math>, then <math>[a, s]</math> and <math>[b, s]</math> differ in both their first and last places. If <math>a \ne b</math> and <math>s \ne t</math>, then <math>s</math> and <math>t</math> differ in at least two places and so the modified s and t, differ in at least one place. But <math>[a, s]</math> and <math>[b, t]</math> also differ in the first place, so they differ in at least two places.
+
== Solutions ==
  
−
So we have established that the largest number is at least <math>10^{n-1}</math> for <math>n</math> digits.
+
Consider license plates of <math>n</math> digits, for some fixed <math>n</math>, issued with the same criteria.
  
−
But any two plates which differ only in the last digit cannot both be chosen. So at most <math>\frac{1}{10 }</math> of the <math>10^n</math> possible plates can be chosen. That shows that <math>10^{n-1}</math> is best possible.  
+
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==
 
==See also==
 +
 
{{USAMO newbox|year=1990|before=First question|num-a=2}}
 
{{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]]
 
[[Category:Olympiad Combinatorics Problems]]

Revision as of 17:50, 11 January 2008

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$ plates; 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 (Problems • Resources)
Preceded by
First question 		Followed by
Problem 2
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1990_USAMO_Problems/Problem_1&oldid=22327"