Let $p$ be an odd prime number. Let $S=a_1,a_2,\dots$ be the sequence defined as follows: $a_1=1,a_2=2,\dots,a_{p-1}=p-1$, and for $n\ge p$, $a_n$ is the smallest integer greater than $a_{n-1}$ such that in $a_1,a_2,\dots,a_n$ there are no arithmetic progressions of length $p$. We say that a positive integer is a ghost if it doesn’t appear in $S$. What is the smallest ghost that is not a multiple of $p$? Proposed by Guerrero
Problem
Source: 2021 Mexico Center Zone Regional Olympiad, problem 1
Tags: Mexico, number theory, arithmetic sequence, induction
starchan
17.01.2022 13:40
What does it mean when you say that there are no arithmetic progressions of length $p$ in a set? Does it mean that it is not possible to pick $p$ numbers from the set and arrange them in a way so that it forms a arithmetic progression?
Justpassingby
17.01.2022 13:44
starchan wrote: What does it mean when you say that there are no arithmetic progressions of length $p$ in a set? Does it mean that it is not possible to pick $p$ numbers from the set and arrange them in a way so that it forms a arithmetic progression? Yes.
starchan
17.01.2022 14:08
We show that all ghosts are multiples of $p$, showing that there is no ghost which is not a multiple of $p$. Process the numbers in their natural, increasing order. Assume $n \geqslant p$ to be the currently processed number. If $p \nmid n$, then note that adding $n$ to the current list of numbers generated by the inductive hypothesis for $n-1$ does not matter, as any arithmetic progression of length $p$, contains a multiple of $p$, and there has been no such number so far. (again proven by an easy induction) But if $n = kp$, then note that we cannot include this number in the list for then $kp-p+1, kp-p+2, \cdots, kp$ would have formed an arithmetic progression. Thus we must skip this multiple and make it a ghost. It follows that there is no ghost which is not a multiple of $p$ proving the statement in the first paragraph.
Justpassingby
17.01.2022 23:10
starchan wrote: ... any arithmetic progression of length $p$, contains a multiple of $p$,...
all positive integers congruent to 1 mod $p$, for example.