Splitting a set in two disjoint sets that satisfy a condition
Probability
Level
3
Can the set be split into two disjoint sets such that at least one of the two sets has three elements that form an arithmetic progression?
Yes, this splitting is always possible
There is 1 exception, but otherwise it can be split so it can satisfy the condition
There are 2 exceptions, but otherwise it can be split so it can satisfy the condition
There are 3 exceptions, but otherwise it can be split so it can satisfy the condition
No, the splitting can never satisfy the condition
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
This question is essentially whether it is possible to partition this set such that neither set contains 3 terms in arithmetic progression. I am going to show that no such partition is possible, i.e. the answer is ‘always possible’. To start, consider the behavior of 3 and 5. In any given partitioning, they are either in the same set, or in opposite sets. Let’s initially assume they are in opposite sets.
Next, examine 2, 4, and 6. They cannot all be in a set, 2,4 cannot be with 3, and 4,6 cannot be with 5. We then have four possibilities: {2,3,6} and {4,5}; {2,5,6} and {3,4}; {3,4,6} and {2,5}; and {2,4,5} and {3,6}.
For {2,3,6}/{4,5}, we consider 1 and 9. Neither can be in the first set, to avoid 1-2-3 and 3-6-9, but if they are both in the second, the triple 1-5-9 is formed. So, this possibility is eliminated.
Next, the hardest case: for {2,5,6}/{3,4}, call the set containing {2,5,6} A, and the other B. Then 7 and 8 are in B, so 1 is in A, so 9 is in B. 7-8-9 is formed, so this possibility is also eliminated.
For {3,4,6}/{2,5}, we consider 8, which makes the triples 4-6-8 and 2-5-8. This possibility is also eliminated.
Finally, for {2,4,5}/{3,6}, call the set with 2 A, and the set with 3 B. Then 9 must be in A, so 7 is in B. In addition, 8 must be in B, which gives 6-7-8. All possibilities are eliminated, so tracing our logic backwards, we see that 3 and 5 cannot be in different sets.
Don’t worry; the hard part is done. We now consider 5 and 7. But, if we replace every element in the argument for 3 and 5 with 10-n (e.g. the first of the four possibilities is now {4,7,8}/{5,6}), then we have proof that 5 and 10-3=7 cannot be in opposite sets.* BUT, we have just showed that 3,5,7 are all in one set, which is itself an arithmetic sequence. We have therefore proven that no division without an arithmetic sequence in one set is possible. QED
*This is because of how arithmetic sequences work: the differences between elements remain the same, so the same sequences still form. If you don’t believe me, try it with an arbitrary sequence. Replacing the terms with 10- a i will produce another arithmetic sequence.