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

First, I assume that technically there could be a difference of 0.

Take the first 2 terms, {1,1} and place them in the first set, since we cannot fit any more without having a 3 term progression. Then put the second 2 in the second set, for the same reason. Then the 5th term must make the statement true whichever set it is placed in.

If the difference is greater than 0, the same principle applies. We may as well use the numbers from 1 with a common difference of 1. The first 2 terms go in the first set, the second 2 in the second set; the third 2 terms back in the first set and the 4th 2 terms back in the second set. Now the 9th term must complete a 3 term progression no matter where it is placed; either {1,5,9} or {3,6,9}.

Posted by broll on 2012-07-23 00:48:23