12
$\begingroup$

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|=16$, we have the answer by @RobertIsrael below.

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

Is it true that $|P| \geq 16$? 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$, can we find the minimum of $|P|$ ?

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.

$\endgroup$
  • 1
    $\begingroup$ it is not too unusual that questions here get answered, say, after a year, and not immediately. $\endgroup$ – Dima Pasechnik Jun 27 at 6:24
  • $\begingroup$ @DimaPasechnik Thanks. I just afraid that my question will be forgotten and cannot be answered. $\endgroup$ – color Jun 27 at 7:02
  • 2
    $\begingroup$ good questions don't get forgotten. they pop up in searches, etc. $\endgroup$ – Dima Pasechnik Jun 27 at 8:21
  • 1
    $\begingroup$ This can be considered as a set-covering problem. Although set covering is NP-complete, I suspect this one is within the reach of current technology. $\endgroup$ – Robert Israel Jun 27 at 12:37
  • $\begingroup$ For the last question (replacing 10 with $n$), have you computed the optimal number for $n\le 9$ and checked the OEIS? $\endgroup$ – Timothy Chow Jun 27 at 14:44
12
$\begingroup$

Considering the complement of $P$ in $[1,100]$, you are asking how large can a subset of $[1,100]$ be given that it does not contain any $10$-term arithmetic progression. The more general question

How large can a subset of $[1,N]$ be given that it does not contain any $k$-term arithmetic progression?

is one of the central problems in combinatorial number theory. There is no chance to give a precise answer, as an "explicit" function of $N$ and $k$, and it quite likely that this is impossible already in your special situation where $N=n^2$ and $k=n$.

Here is an argument showing that if $P\subset[1,n^2]$ meets every $n$-term progression contained in $[1,n^2]$, then $|P|>n+n^{0.5+o(1)}$. (See also the paragraph at the very end for the estimate $|P|\ge 12$ in your special case where $P\subset[1,100]$ and we want to block all $10$-term progressions.) It would be interesting to improve these estimates or at least to decide whether $|P|>Cn$ holds true with an absolute constant $C>1$.

Write $K:=|P|$, $\Delta:=K-n$, and $P=\{p_1,\dotsc,p_K\}$ where $1\le p_1<\dotsb<p_K\le n^2$. Notice that $p_1\le n$ and $p_K\ge n^2-(n-1)$, whence $p_K-p_1\ge(n-1)^2$.

For any $d\in[1,n]$, the set $P$ contains an element from every residue class modulo $d$, and it follows that there are at most $K-d$ pairs of consecutive elements of $P$ with the difference equal to $d$; also, if $d>n$, then there are no such pairs at all. Let $a$ and $r$ be defined by \begin{align*} K-1 &= \Delta+(\Delta+1)+\dotsb+(\Delta+(a-1))+r \\ &= a\Delta+\frac{a(a-1)}2 + r,\quad 0\le r<\Delta+a. \tag{1} \end{align*} Since there are totally $K-1$ pairs of consecutive elements of $P$, of them at most $\Delta$ pairs at distance $n$, at most $\Delta+1$ pairs at distance $n-1$, etc, we conclude that \begin{align*} p_K-p_1 &\le n\Delta+(n-1)(\Delta+1)+\dotsb+(n-(a-1))(\Delta+(a-1))+(n-a)r \\ &= \Delta na+(n-\Delta)\cdot\frac{a(a-1)}2-\frac{a(a-1)(2a-1)}{6}+(n-a)r. \end{align*} Recalling the estimate $p_K-p_1\ge(n-1)^2$, and using ($1$), we get \begin{align*} (n-1)^2 &\le \Delta na+(n-\Delta)\cdot\frac{a(a-1)}2-\frac{a(a-1)(2a-1)}{6}+(n-a)r \\ &= n\Big(a\Delta+\frac{a(a-1)}2 + r\Big) - \Delta\cdot\frac{a(a-1)}2 - \frac{a(a-1)(2a-1)}{6} - ar \\ &= n(K-1) - \Delta\cdot\frac{a(a-1)}2 - \frac{a(a-1)(2a-1)}{6} - ar. \tag{2} \end{align*}

We now assume, aiming at a contradiction, that $\Delta<n^c$ with an absolute constant $0<c<0.5$. From (1) we get then $$ K-1 \ge \Delta a + \frac{a(a-1)}2 \ge \frac12\,a^2 - 1 $$ implying $a\le\sqrt{2K}$; hence, $\Delta a=O(n^{0.5+c})$ and $r=a+\Delta=O(n^{0.5})$. As a result, $$ \frac12\,a^2 = K-1+\frac12\,a-\Delta a - r > K - O(n^{0.5+c}), $$ leading to $a>(1-o(1))\sqrt{2K}$.

With these estimates in mind, from (2) we obtain $$ n^2 + O(n) \le nK - \frac12\,\Delta a^2 - \frac13\,a^3; $$ that is, $$ \Delta n \ge \frac12\,\Delta a^2 + \frac13\,a^3 + O(n). $$ Consequently, $$ n^{1+c} \ge \Delta n \ge \frac13\,a^3 + O(n) \ge (1-o(1))(2K)^{1.5} + O(n) > n^{1.5} + O(n), $$ a contradiction.


As an illustration of this approach, let's show that one needs at least $12$ elements to block every $10$-term progression in $[1,100]$. Suppose for a contradiction that $P\subset[1,100]$ is an $11$-element set blocking all such progressions. There are $|P|-1=10$ pairs of consecutive elements of $P$. Of these ten pairs, there is at most one pair with distance $10$ between its two elements, at most two pairs with distance $9$, at most three pairs with distance $8$, and at most four pairs with distance $7$. Therefore the largest element of $P$ exceeds the smallest one by at most $1\cdot 10+2\cdot 9 + 3\cdot 8 + 4\cdot 7=80$. It follows that either the smallest element of $P$ is at least $11$, or its largest element is at most $90$; but then $P$ does not block at least one of the progressions $[1,10]$ and $[91,100]$, a contradiction.

$\endgroup$
11
$\begingroup$

Using a tabu search procedure, I have found a solution for $|P|=17$, namely ${1, 11, 18, 25, 31, 32, 33, 36, 44, 51, 58, 65, 69, 70, 77, 84, 91}$. I don't know if this is optimal.

EDIT: Found a solution for $|P|=16$, namely $$10, 15, 22, 29, 36, 43, 53, 55, 56, 57, 58, 68, 73, 74, 84, 91$$

$\endgroup$
  • 1
    $\begingroup$ I'm working on $|P|=16$. So far I've found a $P$ with $|P|=16$, namely $\{9, 18, 28, 29, 31, 40, 42, 51, 53, 56, 65, 69, 70, 77, 84, 91\}$, that intersects all but one of these arithmetic progressions, the exception being $({36, 43, 50, 57, 64, 71, 78, 85, 92, 99})$. $\endgroup$ – Robert Israel Jun 27 at 16:50
  • $\begingroup$ I'm using a tabu search over sets of a given size to maximize the number of a.p.'s that intersect the set. Possible moves consist of replacing a member of the set with a nonmember. $\endgroup$ – Robert Israel Jun 27 at 17:00
  • $\begingroup$ Thank you. Your answer is correct. How long did it take to find those numbers? Can you find the boundary of $|P|$? $\endgroup$ – color Jun 28 at 8:00
  • $\begingroup$ So is 16 optimal? $\endgroup$ – EGME Jun 28 at 20:43
  • 1
    $\begingroup$ My brute-force confirms that there no 15. $\endgroup$ – Mikhail Tikhomirov Jul 2 at 5:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.