1990 USAMO Problems/Problem 4
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.)
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.
|1990 USAMO (Problems • Resources)|
|1 • 2 • 3 • 4 • 5|
|All USAMO Problems and Solutions|