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.
Since 100 numbers are divided into 7 subsets such that no number appears in two or more subsets, each subset will have at most 100/7 = 14 integers.
Now, let's consider the possible sums of pairs of numbers within each subset. Since there are at most 14 numbers in each subset, the number of different sums of pairs will be at most (14 * 13) / 2 = 91.
Consider the numbers 1, 2, 3, ..., 13. Each of these integers can be paired with any of the remaining 13 integers, resulting in a total of 13 * 12 = 156 different sums.
However, since we have at most 91 different sums of pairs and 156 different possible sums, according to the Pigeonhole Principle, there must be at least one sum that occurs at least twice.
Now, let's assume that none of the subsets contain four numbers with the property a + b = c + d. In this case, we need to show that at least one subset must have three numbers p, q, and r such that p + q = 2r.
Let's label the subsets as S1, S2, S3, S4, S5, S6, and S7.
Without loss of generality, assume that S1 contains the two numbers a and b, where a + b is the sum that occurs at least twice.
If any of the other subsets, let's say S2, contains a number c such that a + c = b, then we have a + b = a + c, which implies b = c. This means that S1 and S2 have at least one number in common, which contradicts the given condition.
Therefore, none of the other subsets can have a number that satisfies a + c = b. In this case, S2, S3, S4, S5, S6, and S7 must contain all the remaining 98 numbers from M.
Now, consider the set {a-b, 2a, 2b} for each possible pair of distinct subsets. There are a total of 21 pairs (S1, S2), (S1, S3), ..., (S6, S7).
Since there are only 6 distinct subsets excluding S1, and each subset can contain at most 14 numbers, there are only 6 * 14 = 84 possible distinct values for a-b.
However, we have 21 pairs, which means at least one of the pairs must have the same value for a-b.
Let's assume (S1, S2) have the same value for a-b. This means that the subsets S1 and S2 contain the numbers a and b, and also the numbers 2a and 2b.
Therefore, we have a + b = (2a) + (2b), which simplifies to a = b. This contradicts the assumption that a and b are distinct numbers.
Hence, our initial assumption that none of the subsets contain four numbers with the property a + b = c + d must be false. Therefore, there exists at least one subset that contains four numbers a, b, c, and d such that a + b = c + d.
Since we have already shown that if none of the subsets contain four numbers with the property a + b = c + d, then there must be a subset that contains three numbers p, q, and r such that p + q = 2r, we can conclude that at least one of these conditions must hold for the given set M=(1,2,......100) divided into seven subsets with no number in 2 or more subsets.
To prove this, we can use the Pigeonhole Principle, which states that if there are more pigeons than pigeonholes, then at least one pigeonhole must contain more than one pigeon. In this case, the pigeons are the pairs of numbers in the given set and the pigeonholes represent the subsets.
Let's consider the numbers in the set M=(1,2,......100). We need to divide these numbers into seven subsets such that no number exists in two or more subsets. Our goal is to find a subset that satisfies either the condition a+b = c+d or the condition p+q=2r.
First, we consider the condition a+b = c+d. We have to find four numbers a, b, c, and d such that their sums are equal. We can calculate the maximum sum of two numbers from the set M, which is 99 + 100 = 199. Note that the minimum sum of two distinct numbers is 1 + 2 = 3. Thus, all possible sums of two numbers lie between 3 and 199 (inclusive).
Now, let's divide the set M= (1,2,......100) into subsets based on the possible sums of two numbers:
Subset 1: Contains all numbers whose sum of pairs lies between 3 and 27 (inclusive).
Subset 2: Contains all numbers whose sum of pairs lies between 28 and 55 (inclusive).
Subset 3: Contains all numbers whose sum of pairs lies between 56 and 83 (inclusive).
Subset 4: Contains all numbers whose sum of pairs lies between 84 and 111 (inclusive).
Subset 5: Contains all numbers whose sum of pairs lies between 112 and 139 (inclusive).
Subset 6: Contains all numbers whose sum of pairs lies between 140 and 167 (inclusive).
Subset 7: Contains all numbers whose sum of pairs lies between 168 and 199 (inclusive).
With these subsets, we have divided the set M into seven disjoint subsets based on the possible sums of two numbers. Since there are only seven subsets, and the sums of pairs range from 3 to 199, there must be at least one subset that contains more than one pair with the same sum (due to the Pigeonhole Principle).
Let's assume that subset A contains two pairs (a, b) and (c, d) with the same sum a+b = c+d. In this case, we have found a subset that satisfies the condition a+b = c+d.
Next, let's consider the condition p+q=2r. We need to find three numbers p, q, and r such that their sums satisfy this equation. Note that the maximum sum of two numbers from the set M is 99 + 100 = 199, which means that the maximum value for 2r is 198. Thus, we need to consider sums ranging from 1 to 198 (inclusive).
Now, let's divide the set M=(1,2,......100) into subsets based on the possible sums of three numbers:
Subset 1: Contains all numbers whose sum of triples lies between 1 and 67 (inclusive).
Subset 2: Contains all numbers whose sum of triples lies between 68 and 134 (inclusive).
Subset 3: Contains all numbers whose sum of triples lies between 135 and 201 (inclusive).
With these subsets, we have divided the set M into three disjoint subsets based on the possible sums of three numbers. Since there are only three subsets, and the sums of triples range from 1 to 201, there must be at least one subset that contains more than one triple with the same sum (due to the Pigeonhole Principle).
Let's assume that subset B contains two triples (p, q, r) and (p', q', r') with the same sum p+q = 2r = p'+q' = 2r'. In this case, we have found a subset that satisfies the condition p+q=2r.
Thus, by applying the Pigeonhole Principle, we have shown that for any division of the set M=(1,2,......100) into seven subsets, there will always be at least one subset that either contains four numbers (a, b, c, d) satisfying a+b = c+d or three numbers (p, q, r) satisfying p+q=2r.