Let $ S= \left\{ 1,2,3,…,100 \right\}$ be a set of positive integers from $ 1$ to $ 100$ . Let $ P$ be a subset of $ S$ such that any arithmetic progression of length 10 consisting of numbers in $ S$ will contain at least a number in $ P$ . What is the smallest possible number of elements in $ P$ ?

Denote $ |P|$ as the number of elements in $ P$ . We shall find the smallest possible value of $ |P|$ .

For $ |P|=18$ , choose $ P = \left\{ 10,19,28,37,…,91,12,23,34,…,89 \right\}$ , which consists of all integers from $ S$ that equivalent to $ 1 \pmod 9$ or $ 1 \pmod {11}$ , excluding $ 1$ and $ 100$ . Then every arithmetic progression of length 10 will contain at least a number in $ P$ .

To prove that, let $ a,a+d,a+2d,…a+9d$ be an arithmetic progression of length 10 consisting of numbers in $ S$ with $ 1 \leq d \leq 11$ .

If $ gcd(d,9)=1$ , then there exists $ 0 \leq k \leq 9$ such that $ a+kd \equiv 1 \pmod 9$ . If $ a+kd=1$ or $ 100$ then $ k=0$ or $ 9$ respectively, and thus if $ d<11$ then there exist $ 0 \leq l \leq 9$ such that $ a+ld \equiv 1 \pmod 9$ and $ a+ld \neq 1, 100$ . If $ d=11$ then the arithmetic progression is $ 1,12,23,…,100$ , in which $ 12,23,…,89 \in P$ .

If $ gcd(d,9)>1$ and all elements of $ a,a+d,a+2d,…a+9d$ do not equal to $ 1$ $ \pmod 9$ , then $ d<11$ and thus $ gcd(d,11)=1$ Hence there must be a $ 0 \leq k \leq 9$ such that $ a+kd \equiv 1 \pmod {11}$ . If not, then $ a+10d \equiv 1 \pmod {11} \Leftrightarrow a = d+1$ ; but then $ a \equiv 1 \pmod 3$ , then atleast 3 elements in $ a,a+d,a+2d,…a+9d$ equal to $ 1$ $ \pmod 9$ .

However, for $ |P|<18$ , I can neither find such set $ P$ nor prove that $ |P|$ cannot be less than $ 18$ . So my question is:

Is it true that $ |P| \geq 18$ ? How can I prove it? If not, what is the minimum amount of elements in $ P$ ?

Also, I am wondering that:

If we replace 10 with an even number $ n$ ,and $ 100$ with $ n^2$ , is it true that $ |P| \geq 2(n-1)$ ?

Any answers or comments will be appreciated. If this question should be closed, please let me know. If this forum cannot answer my question, I will delete this question immediately.