Difference between revisions of "1990 USAMO Problems/Problem 1"
m (→Solutions) |
Anyu tsuruko (talk | contribs) |
||
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. | ||
− | == | + | == 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. | ||
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 == | ||
− | {{ | + | <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== |
Latest revision as of 01:21, 25 May 2024
Contents
[hide]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 and 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 digits, for some fixed , issued with the same criteria.
We first note that by the pigeonhole principle, we may have at most distinct plates. Indeed, if we have more, then there must be two plates which agree on the first digits; these plates thus differ only on one digit, the last one.
We now show that it is possible to issue distinct license plates which satisfy the problem's criteria. Indeed, we issue plates with all possible combinations for the first 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 digits, they agree on the last digit and are thus the same plate, and if two plates differ in only one of the first digits, they must differ as well in the last digit.
It then follows that is the greatest number of license plates the state can issue. For , as in the problem, this number is .
Solution 2
Suppose for , we have a set that satisfies the condition. We need to construct such that it does not contain , denoted as . Construct: If and have exactly one difference: 1. Case 1: 2. Case 2: If for , Contradiction! If , contradiction with the same . At least two positions are different, i.e., there cannot be exactly one difference. Therefore, in the set (hypercube), there are no collinear points (parallel to the coordinate axes).
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.