All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Pigeons again (Posted on 2012-07-22)
If a n-term arithmetic progression is split into two sets, then at least one of the sets contains a 3-terms arithmetic progression .

For what minimal value of n the above statement is true?

Based upon a proof in V. K. Balakrishnan's Theory and Problems of Combinatorics, Schaum's Outline Series, McGraw-Hill, 1995, 1.110

Comments: ( Back to comment list | You must be logged in to post comments.)
 n | Comment 1 of 2
n=8 will not work. {1, 2, 3, 4, 5, 6, 7, 8} is an 8-term arithmetic progression. It can be split into {1, 2, 5, 6} and {3, 4, 7, 8}, which have no 3-term arithmetic progression.

However, n=9 will work. Take any 9-term arithmetic progression {x1, x2, x3, x4, x5, x6, x7, x8, x9}. Suppose this set can be split into two sets without a 3-term arithmetic progression. Now, suppose x3 and x5 are in the same set. Call that set A and the other set B. A cannot contain {x1, x3, x5}, so x1 is in B. A cannot contain {x3, x4, x5}, so x4 is also in B. If x7 is in A, then A contains {x3, x5, x7}. If x7 is in B, then B contains {x1, x4, x7}. Neither of these is possible, so x3 and x5 are in different sets.

Call the set with x3 A and the set with x5 B. Suppose x4 is in A. Then, x2 has to be in B to avoid {x2, x3, x4} in A. Since x2 and x5 are both in B, x8 is in A. Since x4 and x8 are in A, x6 is in B. Since x5 and x6 are in B, x7 is in A. Since x4 and x7 are in A, x1 is in B. If x9 is in A, then A contains {x7, x8, x9}. If x9 is in B, then B contains {x1, x5, x9}. Therefore, x4 is in B. Since x4 and x5 are both in B, x6 is in A. Since x3 and x6 are in A, x9 is in B. Since x5 and x9 are in B, x7 is in A. Since x6 and x7 are in A, x8 is in B. Since x5 and x8 are in B, x2 is in A. If x1 is in A, then A contains {x1, x2, x3}. If x1 is in B, then B contains {x1, x5, x9}. Therefore, either A or B contains a 3-term arithmetic progression, so n=9.

 Posted by Math Man on 2012-07-22 12:55:40

 Search: Search body:
Forums (0)