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
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 |
n
