Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
This is not set theory. I will re-tag. – Gerry Myerson Nov 5 '11 at 2:23
In the last part of your question, don't you mean for $A$ to be a subset of $\lbrace1,2,\dots,13\rbrace$? – Gerry Myerson Nov 5 '11 at 2:26
By the way, you should include a link to your earlier question so we don't reinvent too many wheels here. – Gerry Myerson Nov 5 '11 at 2:29
It is generally a bad idea to use (non standard!) abbreviations in titles: it is impossible to know what the question is about from its title... You saved an infinitessimal amount of time writing «A.P.» and as a consequence lots of people (among who are those that will probably help you!) to lose time: when writing for others, one should be very mindful of their convenience... – Mariano Suárez-Alvarez Nov 5 '11 at 2:31
I am giving my previous post link below:… – mathew Nov 5 '11 at 8:50

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.

share|cite|improve this answer
WOW! good explanation, and thank you so much sir. – mathew Nov 5 '11 at 8:29
I don't follow "$A$ contains at most 5 elements of $1,2,\dots,9." 1, 2, 4, 6, 8, 9 does not contain all the elements of any row or column (or diagonal!), yet it has 6 elements. True, it has an AP or two, but that's beside the point. – Gerry Myerson Nov 5 '11 at 8:42
Also, 1, 2, 4, 8, 9 is not unique; 1, 2, 6, 8, 9 is also a 5-subset of the 9-set free of APs. Also 1, 3, 4, 8, 9, and 1, 2, 6, 7, 9. – Gerry Myerson Nov 5 '11 at 8:45
Gerry Myerson@ Sir, Now I am in full confusion. Could you explain more clearly sir. – mathew Nov 5 '11 at 8:51
@mathew, sure - what would you like me to explain? – Gerry Myerson Nov 6 '11 at 4:43

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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