Difference between revisions of "1990 USAMO Problems/Problem 4"
(problem and solution) |
m (→Resources) |
||
(3 intermediate revisions by 3 users not shown) | |||
Line 16: | Line 16: | ||
&= -n + \sum_{j=1}^n (2^k-1) = - 2n -1 + \sum_{j=0}^n 2^k, | &= -n + \sum_{j=1}^n (2^k-1) = - 2n -1 + \sum_{j=0}^n 2^k, | ||
\end{align*} </cmath> | \end{align*} </cmath> | ||
− | which is equal to <math>2^{n+1} - 2(n+ | + | which is equal to <math>2^{n+1} - 2(n+1)</math>, our answer. <math>\blacksquare</math> |
{{alternate solutions}} | {{alternate solutions}} | ||
− | == | + | == See Also == |
− | + | {{USAMO box|year=1990|num-b=3|num-a=5}} | |
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=258568#258568 Discussion on AoPS/MathLinks] | * [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=258568#258568 Discussion on AoPS/MathLinks] | ||
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=364433#364433 More Discussion] | * [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=364433#364433 More Discussion] | ||
+ | {{MAA Notice}} | ||
[[Category:Olympiad Combinatorics Problems]] | [[Category:Olympiad Combinatorics Problems]] |
Latest revision as of 19:15, 18 July 2016
Problem
Find, with proof, the number of positive integers whose base- representation consists of distinct digits with the property that, except for the leftmost digit, every digit differs by
from some digit further to the left. (Your answer should be an explicit function of
in simplest form.)
Solution
Let a -good sequence be a sequence of distinct integers
such that for all integers
,
differs from some preceding term by
.
Lemma. Let be an integer. Then there are
-good sequences starting on
, and furthermore, the terms of each of these sequences constitute a permutation of
consecutive integers.
Proof. We induct on . For
, the lemma is trivially true. Now, suppose the lemma holds for
. If
is a
-good sequence, then
is a
-good sequence which starts on
, so it is a permutation of
consecutive integers, say
. Then the only possibilities for
are
and
; either way,
constitutes a permutation of
consecutive integers. Since there are
possible sequences
, and 2 choices of
for each of these sequences, it also follows that there are
-good sequences which start on
. Thus the lemma holds by induction.
We now consider the number of desired positive integers with digits. Evidently,
must be less than or equal to
. We also note that the digits of such an integer must constitute a
-good sequence. Since the minimum of this sequence can be any of the digits
, unless the minimum is 0 and is the first digit (in which case the only possible sequence is an increasing arithmetic sequence), and there are
-good sequences up to translation, it follows that there are
desired positive integers with
digits. Thus the total number of desired positive integers is
which is equal to
, our answer.
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 Problem 3 |
Followed by Problem 5 | |
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.