1995 USAMO Problems/Problem 1
Problem
Let be an odd prime. The sequence is defined as follows: and, for all is the least positive integer that does not form an arithmetic sequence of length with any of the preceding terms. Prove that, for all is the number obtained by writing in base and reading the result in base .
Solution
I have to make the assumption that (without this assumption, I can have the sequence
)
All of the following work are in base otherwise stated
Lemma 1: for an arithmetic sequence of length to exist, there must be a number in the sequence with as a digit.
A arithmetic sequence of length can be represented as
Since no number repeats, . Thus, d must have a rightmost non-zero digits, and every term in the sequence have the same number of tailing zeros, let's say there are tailing zeros.
and let
since p is an odd prime and the operation divide by has remove all factors of p in S
Thus, there must be a number with as a digit if a length-p sequence exist.
Now, I'm going to prove the statement by strong induction.
I'm going to assume that for all less than
is the number obtained by writing in base and reading the result in base .
(which is true for already)
Or in another word, the terms precede contains all number less than written in base and reading the result in base .
Lemma 2: Any term containing the digit will form an arithmetic sequence of length-p with preceding terms
let be the digit from the right (There may be more than 1 )
the number with all replaced by 0 (e.g: , the number, then )
(for all 's)
all precede , thus, can't be in the sequence
Therefore, any term containing the digit can't be a term in the sequence
Since the digit won't appear (lemma 2) and as long as it doesn't appear, the arithmetic sequence of length won't be formed (lemma 1), and must be as small as possible,
Therefore, for all is the number obtained by writing in base and reading the result in base .
See Also
1995 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.