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
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 use the Pigeonhole Principle.
First, let's divide the set M = {1, 2, ..., 100} into seven subsets, each containing non-overlapping numbers. We need to show that at least one of these subsets satisfies the given conditions.
Consider any number x from 1 to 100. The possible sums of two distinct numbers from M that can be formed with x are: (x + 1), (x + 2), ..., (x + 99).
Let's define a "sum set" for a particular number x as the set of all possible sums that can be formed with x. For example, if x = 1, the sum set would be {2, 3, ..., 100}, since we can form sums ranging from 2 to 100 using 1.
Now, let's consider the sum sets for all the numbers in M. Since M has 100 numbers, we will have 100 sum sets.
According to the Pigeonhole Principle, if there are n + 1 objects (pigeons) to be placed into n boxes (pigeonholes), then there must be at least one box containing more than one object.
In our case, we have 100 sum sets (pigeons) and 99 subsets (pigeonholes). Applying the Pigeonhole Principle here, there must be at least one sum set that appears in two different subsets.
Suppose there exists a sum set X that appears in two different subsets, say Subset A and Subset B.
Case 1: X appears in Subset A but not Subset B.
In this case, Subset A contains four numbers a, b, c, and d such that a + b = X and c + d = X. Therefore, a + b = c + d, satisfying the condition.
Case 2: X appears in Subset B but not Subset A.
Similar to Case 1, Subset B contains four numbers a, b, c, and d such that a + b = X and c + d = X. Therefore, a + b = c + d, satisfying the condition.
Case 3: X appears in both Subset A and Subset B.
In this case, Subset A contains three numbers p, q, and r such that p + q = X and Subset B contains three numbers p, q, and r such that p + q = X. Therefore, p + q = 2r, satisfying the condition.
Thus, in all possible cases, we can conclude that at least one subset either contains four numbers satisfying a + b = c + d or three numbers satisfying p + q = 2r.
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 use the Pigeonhole Principle.
The Pigeonhole Principle states that if you distribute n + 1 objects into n boxes, then at least one box must contain more than one object.
In this scenario, we can consider the numbers in the set M as objects, and the seven subsets as boxes. We want to show that at least one subset satisfies the given conditions.
First, let's consider the sums of all possible pairs of numbers from the set M. Since M has 100 numbers, there are (100 choose 2) = 4950 possible pairs.
Now, let's divide these pairs into seven subsets according to their sums. Specifically, we assign each pair (a, b) to the subset corresponding to a + b. For example, if a + b = 17, we place the pair (a, b) in the subset labeled 17.
Given that we have divided 4950 pairs into seven subsets, each subset should contain approximately 4950/7 ≈ 707 pairs.
Assume for contradiction that none of the subsets contain four numbers with a + b = c + d. This means that each subset has at most three numbers. Since each subset can have at most 707 pairs (which corresponds to three numbers), the maximum number of pairs in total is 707 * 7 = 4949 pairs.
However, this contradicts the fact that we initially had 4950 pairs. Therefore, our assumption that none of the subsets contain four numbers with a + b = c + d must be false.
Hence, there exists at least one subset that contains four numbers a, b, c, and d such that a + b = c + d.
To establish the second part of the claim, we need to show that at least one subset contains three numbers p, q, and r such that p + q = 2r.
To prove this, we consider the remainders of the numbers modulo 3. Since we have 100 numbers, at least 34 numbers will have the same remainder when divided by 3 due to the Pigeonhole Principle.
In these 34 numbers, let's consider all the possible sums of pairs with the same remainder (0, 1, or 2).
For any remainder, there will be at least 17 numbers, and hence at least (17 choose 2) = 136 pairs. If we divide these pairs into seven subsets according to their sums, each subset should have approximately 136/7 ≈ 19 pairs.
Assume for contradiction that none of these subsets contain three numbers p, q, and r such that p + q = 2r. This means that each subset has at most two pairs, which implies a total maximum of 19 * 7 = 133 pairs.
However, this contradicts the fact that we initially had at least 136 pairs. Therefore, our assumption that none of the subsets contain three numbers p, q, and r such that p + q = 2r must be false.
Hence, there exists at least one subset that contains three numbers p, q, and r such that p + q = 2r.
Therefore, we have proved 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.