Slick combinatorial-ish argument
by shiningsunnyday, Apr 10, 2017, 6:08 PM
1995 USAMO P1 wrote:
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 
.
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 
.
positive integers, there is at least one with a 
digit in its base 
then we simply observe that ![\[\{a, a+d, \ldots, a+(p-1)d \} \]](http://latex.artofproblemsolving.com/f/a/7/fa75bc131f32ded1314f97de8ec11fb9bfe6e010.png)
forms a complete residue class mod 
and thus the set of unit digits for the base 
If the common difference 
then the same argument can be made for the "p's" digit, which must form a complete residue class. In general, if 
we can make the same argument for the 
'
to start the sequence. Now, assume for the sake of contradiction that the statement has been proved up to 
digits, but we have a 
digit number with part of the sequence but with a ![\[X=\overline{a_{k}a_{k-1}\ldots a_1 a_0}\]](http://latex.artofproblemsolving.com/d/4/1/d41706884ce7086f3ac512c88e5cf129f70f3aed.png)
and let the culprit be 
Now consider the numbers ![\[X, X-p^j, X-2p^j, \ldots, X-(p-1)p^j.\]](http://latex.artofproblemsolving.com/2/4/6/2460b0788356abbba12cc93e385887cd8952f24b.png)
If there're multiple culprits, i.e. 
consider the numbers ![\[X, X-(p^{j_1}+p^{j_2} + \ldots + p^{j_m}), \ldots, X-(p-1)(p^{j_1}+p^{j_2} + \ldots + p^{j_m}).\]](http://latex.artofproblemsolving.com/9/e/a/9eaec5fc68a522d921c1d4347868674ff5bd45b4.png)
The motivation is that except 
each of the following numbers in the arithmetic sequence we've constructed is positive and doesn't contain a 
is the p-th term of an arithmetic progression of terms in the sequence, and we're done.
May 2017
April 2017