A set M=(1,2,......100) is divided into seven subsets with no number in 2 or more subsets. Show that at least one subset either contains four numbers a,b,c, and d such that a+b = c+d or three number p,q and r such that p+q=2r
This sounds pretty cool. Any idea how to get started? Maybe start with a smaller set first?
To prove that at least one subset either contains four numbers (a, b, c, and d) such that a + b = c + d or three numbers (p, q, and r) such that p + q = 2r, we can make use of the Pigeonhole Principle.
The Pigeonhole Principle states that if you have more pigeons than pigeonholes, then there must be at least one pigeonhole with more than one pigeon. In this context, the pigeons represent the numbers from the set M, and the pigeonholes represent the subsets into which the set M is divided.
In this case, we have 100 numbers (pigeons) and 7 subsets (pigeonholes). Dividing 100 numbers into 7 subsets would mean that each subset can contain a maximum of ⌊100/7⌋ = 14 numbers. However, since subsets cannot have any numbers in common, each subset can contain at most 13 numbers.
Now, let's consider the possible pairwise sums of numbers within each subset. For each subset, calculate the sum of every pair of distinct numbers within that subset. Since each subset contains at most 13 numbers, the maximum number of pairwise sums possible within a subset is given by ⌊13/2⌋ = 6.
However, we have a total of 7 subsets, which means that the total number of pairwise sums is at most 6 * 7 = 42. Given that there are 100 numbers in total, it is impossible for each pairwise sum to be distinct within the given subsets.
Therefore, by the Pigeonhole Principle, there must be at least one subset with two distinct pairs of numbers that have the same sum. Let's consider one such subset:
a + b = c + d, where a, b, c, and d are distinct numbers within the subset.
Now, we need to prove that there is another subset that satisfies the condition p + q = 2r, where p, q, and r are distinct numbers within that subset.
To do this, we divide the subset into two parts: one containing odd numbers and the other containing even numbers. Since there are a total of 100 numbers and 50 of them are odd, one of the parts will have at least 25 numbers.
Again, by the Pigeonhole Principle, within the part of the subset containing at least 25 numbers, there must be at least one pair that satisfies p + q = 2r.
Therefore, we have proven that in any division of the set M=(1,2,......100) into seven subsets with no number in 2 or more subsets, there is at least one subset that either contains four numbers (a, b, c, and d) such that a + b = c + d or three numbers (p, q, and r) such that p + q = 2r.