1995 USAMO Problems/Problem 1

Problem

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$ .

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

Page

Toolbox

Search

1995 USAMO Problems/Problem 1

Problem

Solution

See Also