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"

(→‎Solutions)
 
(4 intermediate revisions by 3 users not shown)
Line 3: Line 3:
 
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.
 
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 ==
+
== Solution 1 ==
  
 
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.
Line 13: Line 13:
 
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>
 
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>
  
 +
== Solution 2 ==
  
−
{{alternate solutions}}
+
<math> \text{Constructive Induction for } n=6 </math>
 +
  <cmath>
 +
  n=1 \quad \text{1 element} \quad n=2 \quad \text{10 elements}
 +
  </cmath>
 +
  Suppose for <math> n </math>, we have a set <math> \left\{ \left( a_1, \ldots, a_n \right) \right\} </math> that satisfies the condition. We need to construct <math> S_{n+1} </math> such that it does not contain <math> \left( a_1, \ldots, a_n \right) </math>, denoted as <math> \left( b_1, \ldots, b_n \right) </math>.
 +
  Construct:
 +
  <cmath>
 +
  S_{n+1} = \left\{ \left( a_1, a_2, \ldots, a_{n-k}, k \right) \mid k = 1, 2, \ldots, 10, \left( a_1, \ldots, a_n \right) \in S_n \right\}
 +
  </cmath>
 +
  If <math> \left( a_1 + k, \ldots, a_{n+k}, k \right) </math> and <math> \left( b_1, \ldots, b_{n+\ell}, \ell \right) </math> have exactly one difference:
 +
  1. Case 1: <math> k \neq \ell </math>
 +
      <cmath>
 +
      a_1 = b_1, \ldots, a_{n-1} = b_{n-1}, a_n = b_n \Rightarrow a_{n+k} \neq b_{n+\ell}, \text{contradiction}
 +
      </cmath>
 +
  2. Case 2: <math> k = \ell </math>
 +
      If <math> a_i = b_i </math> for <math> i \neq n </math>,
 +
      <cmath>
 +
      a_1 = b_1, \ldots, a_n = b_n \quad (\text{removing } i)
 +
      </cmath>
 +
      Contradiction! If <math> a_{n+k} \neq b_{n+\ell} \Rightarrow a_n \neq b_n </math>, contradiction with the same <math> k </math>.
 +
  At least two positions are different, i.e., there cannot be exactly one difference. Therefore, in the set <math> \{0, 1, \ldots, 9\}^6 </math> (hypercube), there are no collinear points (parallel to the coordinate axes).
 +
  <cmath>
 +
  \text{1 dimension: 1 element}
 +
  </cmath>
 +
  <cmath>
 +
  \text{2 dimensions: 10 elements}
 +
  </cmath>
 +
  <cmath>
 +
  \text{3 dimensions: 100 elements}
 +
  </cmath>
 +
  <cmath>
 +
  10^6 \text{ points can be covered by } 10^5 \text{ lines} \Rightarrow \text{At most } 10^5 \text{ elements.}
 +
  </cmath>
  
−
==See also==
+
==See Also==
  
−
{{USAMO newbox|year=1990|before=First question|num-a=2}}
+
{{USAMO box|year=1990|before=First question|num-a=2}}
 
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=63538#63538 Discussion on AoPS/MathLinks]
 
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=63538#63538 Discussion on AoPS/MathLinks]
 +
{{MAA Notice}}
  
  
 
[[Category:Olympiad Combinatorics Problems]]
 
[[Category:Olympiad Combinatorics Problems]]

Latest revision as of 01:21, 25 May 2024

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.

Solution 1

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$

Solution 2

$\text{Constructive Induction for } n=6$ 

  \[n=1 \quad \text{1 element} \quad n=2 \quad \text{10 elements}\]
  Suppose for $n$, we have a set $\left\{ \left( a_1, \ldots, a_n \right) \right\}$ that satisfies the condition. We need to construct $S_{n+1}$ such that it does not contain $\left( a_1, \ldots, a_n \right)$, denoted as $\left( b_1, \ldots, b_n \right)$.
  Construct:
  \[S_{n+1} = \left\{ \left( a_1, a_2, \ldots, a_{n-k}, k \right) \mid k = 1, 2, \ldots, 10, \left( a_1, \ldots, a_n \right) \in S_n \right\}\]
  If $\left( a_1 + k, \ldots, a_{n+k}, k \right)$ and $\left( b_1, \ldots, b_{n+\ell}, \ell \right)$ have exactly one difference:
  1. Case 1: $k \neq \ell$
     \[a_1 = b_1, \ldots, a_{n-1} = b_{n-1}, a_n = b_n \Rightarrow a_{n+k} \neq b_{n+\ell}, \text{contradiction}\]
  2. Case 2: $k = \ell$
     If $a_i = b_i$ for $i \neq n$,
     \[a_1 = b_1, \ldots, a_n = b_n \quad (\text{removing } i)\]
     Contradiction! If $a_{n+k} \neq b_{n+\ell} \Rightarrow a_n \neq b_n$, contradiction with the same $k$.
  At least two positions are different, i.e., there cannot be exactly one difference. Therefore, in the set $\{0, 1, \ldots, 9\}^6$ (hypercube), there are no collinear points (parallel to the coordinate axes).
  \[\text{1 dimension: 1 element}\]
  \[\text{2 dimensions: 10 elements}\]
  \[\text{3 dimensions: 100 elements}\]
  \[10^6 \text{ points can be covered by } 10^5 \text{ lines} \Rightarrow \text{At most } 10^5 \text{ elements.}\]

See Also

1990 USAMO (Problems • Resources)
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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1990_USAMO_Problems/Problem_1&oldid=219668"