2
$\begingroup$

This is consequence of my earlier post. I am not very happy with earlier replies of my post. I hope, I will get good response for this post. With lot of hope, I am sending the following problem and I want to learn the best from the experts. Please discuss/prove the following one. Thank you.

Let $A$ be a subset of $\{1,2, \dots,8\}$ containing no Arithmetic Progression. Then one of the following Two must be hold:

  1. $|A \cap\{3, 5\}|\le 1$ and $|A \cap\{1, 2, 4, 6, 7, 8\}|\le 1$.
  2. $|A \cap \{4, 6\}|\le 1$ and $|A \cap\{1, 2, 3, 5, 7, 8\}|\le 1$.

Let A be a subset of $\{1, 2, \dots,10\}$ containing no Arithmetic Progression. Then one of $|A \cap \{1, 2, \dots,7\}|$ and $|A \cap \{4, 5, \dots, 10\}|$ is at most $3$.

Let $A$ be a subset of $\{1,2,\dots,13\}$ containing no Arithmetic Progression. Then one of the following Two must be hold:

  1. $|A \cap \{1, 2, 3, 4, 6\}|\le 3$ and $|A \cap \{5, 7, 8, 9, 10, 11, 12, 13\}|\le 4$.
  2. $|A \cap\{8, 10, 11, 12, 13\}|\le 3$ and $|A \cap \{1, 2, 3, 4, 5, 6, 7, 9\}|\le 4$.

Thank you all.

  • 0
    I am giving my previous post link below: http://math.stackexchange.com/questions/78474/prove-that-a-subset-of-1-2-ldots-7-which-contains-no-arithmetic-series-do2011-11-05

1 Answers 1

3

Consider the set $A=\{1,3,7\}$, which admits no arithmetic progression. Then condition (1) is not met, as $A$ contains $1$ and $7$. Additionally, condition (2) is not met, as our set contains both $3$ and $7$. Thus, your first claim is refuted.

For your second claim, we first prove that such a set must contain at most $6$ elements. Of course, this would prove your claim immediately. It may help to arrange the numbers $1$ to $9$ as

$\left(\begin{matrix} 1& 2& 3 \\4 & 5 & 6 \\ 7 & 8 &9 \end{matrix} \right)$ A set $A$ without arithmetic progressions must not contain all the elements of any row or column. Thus $A$ contains at most $5$ elements of $1,2\ldots,9$. Our desired result is immediate. With more work, one may show that $A = \{1,2,4,8,9\}$ is a set free of arithmetic progressions with $\#(A \cap \{1,2,\ldots ,9\})=5$, and that it is unique in this respect. Two more (similarly obtained) sets are $B=\{1,2,4,5,10\}$ and $C=\{2,3,5,9,10\}$. These three sets exhaust those with maximal cardinality in $\{1,\ldots, 10\}$, so your necessary conditions in claim (2) could be tightened.

While ad hoc methods (or brute force search) will continue to be effective in these types of problems, I suggest that you formulate known results into `theorems' to make your techniques more wide-reaching. For example, one may readily generalize our work on claim (2) by considering $k \times 3$ matrices. In general, results that relate to the density of arithmetic-progression-free sets will serve you well. It is known that the density of such sets approaches $0$ as they increase in cardinality; this is Szemeredi's theorem. While this won't help you here, more constructive results of the same variety would be very useful.

  • 0
    @mathew, sure - what would you like me to explain?2011-11-06