Skip to main content
MathOverflow

Return to Question

deleted 1091 characters in body
Source Link
color
color
  • 179
  • 5

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

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

Is it true that $|P| \geq 18$$|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$, is it true thatcan we find the minimum of $|P| \geq 2(n-1)$$|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.

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.

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.

edited title
Link
color
color
  • 179
  • 5

any Smallest set such that all arithmetic progression of length 10 consisting of numbers in $S$ will always contain at least a number in $P$a set

Source Link
color
color
  • 179
  • 5

any arithmetic progression of length 10 consisting of numbers in $S$ will contain at least a number in $P$

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.