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

Home > Numbers > Sequences
Pigeons again (Posted on 2012-07-22) Difficulty: 3 of 5
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

No Solution Yet Submitted by Ady TZIDON    
Rating: 5.0000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution 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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (6)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information