If a nterm arithmetic progression is split into two sets, then at least one of the sets contains a 3terms 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, McGrawHill, 1995, 1.110
n=8 will not work. {1, 2, 3, 4, 5, 6, 7, 8} is an 8term arithmetic progression. It can be split into {1, 2, 5, 6} and {3, 4, 7, 8}, which have no 3term arithmetic progression.
However, n=9 will work. Take any 9term arithmetic progression {x1, x2, x3, x4, x5, x6, x7, x8, x9}. Suppose this set can be split into two sets without a 3term 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 3term arithmetic progression, so n=9.

Posted by Math Man
on 20120722 12:55:40 