1995 USAMO Problems/Problem 1
Problem 1
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 a 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 contains the digit will form a arithmatic 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 contains 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,
for all
is the number obtained by writing
in base
and reading the result in base
.
Resources
1995 USAMO (Problems • Resources) | ||
Preceded by First Question |
Followed by Problem 2 | |
1 • 2 • 3 • 4 • 5 | ||
All USAMO Problems and Solutions |