1995 USAMO Problems/Problem 1

Revision as of 11:20, 11 August 2009 by Moplam (talk | contribs) (Solution)

Problem 1

Let $\, p \,$ be an odd prime. The sequence $(a_n)_{n \geq 0}$ is defined as follows: $\, a_0 = 0,$ $a_1 = 1, \, \ldots, \, a_{p-2} = p-2 \,$ and, for all $\, n \geq p-1, \,$ $\, a_n \,$ is the least positive integer that does not form an arithmetic sequence of length $\, p \,$ with any of the preceding terms. Prove that, for all $\, n, \,$ $\, a_n \,$ is the number obtained by writing $\, n \,$ in base $\, p-1 \,$ and reading the result in base $\, p$.

Solution

I have to make the assumption that $a_{n+1}>a_{n}$ (without this assumption, I can have the sequence

${1,\cdots,p-2,1,1,\cdots,1,2,1,\cdots}$)

All of the following work are in base $p$ otherwise stated


Lemma 1: for a arithmetic sequence of length $\, p \,$ to exist, there must be a number in the sequence with $(p-1)$ as a digit.

A arithmetic sequence of length $\, p \,$ can be represented as

$a,a+d,a+2d,\cdots,a+(p-1)d$

Since no number repeats, $d\neq0$. Thus, d must have a rightmost non-zero digits, and every term in the sequence $0,d,2d,\cdots,(p-1)d$ have the same number of tailing zeros, let's say there are $x$ tailing zeros.

and let $\dfrac{{0,d,2d,\cdots,(p-1)d}}{p^x}=S$

$S\equiv{1,2,...,(p-1)}(mod)p$ since p is an odd prime and the operation divide by $p^x$ has remove all factors of p in S

Thus, there must be a number with $(p-1)$ 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 $\, k \,$ less than $\, n \,$

$\, a_k \,$ is the number obtained by writing $\, k \,$ in base $\, p-1 \,$ and reading the result in base $\, p$.

(which is true for $n=p-2$ already)

Or in another word, the terms precede $a_n$ contains all number less than $n$ written in base $\, p-1 \,$ and reading the result in base $\, p$.


lemma 2: Any term contains the digit $p-1$ will form a arithmatic sequence of length-p with preceding terms

let $p-1$ be the $x^{th}$ digit from the right (There may be more than 1 $(p-1)$)

$a=$the number with all $(p-1)$ replaced by 0 (e.g: $p=7$, the number$=1361264$, then $a=1301204$)

$d=\sum10^{x-1}$ (for all $x$'s)

$a,a+d,a+2d,\cdots,a+(p-2)d$ all precede $a_n$, thus, $a+(p-1)d$ can't be in the sequence $(a_n)_{n \geq 0}$

Therefore, any term contains the digit $p-1$ can't be a term in the sequence ${(a_n)}_{n\ge0}$


Since the digit $p-1$ won't appear (lemma 2) and as long as it doesn't appear, the arithmetic sequence of length $\, p \,$ won't be formed (lemma 1), and $a_n$ must be as small as possible,

for all $\, n, \,$ $\, a_n \,$ is the number obtained by writing $\, n \,$ in base $\, p-1 \,$ and reading the result in base $\, p$.

Resources

1995 USAMO (ProblemsResources)
Preceded by
First Question
Followed by
Problem 2
1 2 3 4 5
All USAMO Problems and Solutions