Solve belove question base on Pigeonhole Principle.
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
Solve this problem use Pigeonhole Principle
I want to know how to solve base on the Pigeonhole Principle. Thanks beforehand.
I don't know, but you can use google.
Copy this text in google:
math.stackexchange questions 2865068 any partition of 1 to 100 into seven subsets
When you see list of results you can start from that.
To solve this problem using the Pigeonhole Principle, we consider the number of pairs of integers that can be formed from the set M.
Step 1: Count the number of possible pairs in the set M.
Since the set M has 100 elements, we can form pairs from these elements. The number of pairs in a set of n elements can be calculated using the formula n(n-1)/2.
Therefore, the number of possible pairs in set M is:
100(100-1)/2 = 4950.
Step 2: Divide the pairs into subsets.
Now, we divide the pairs of integers into seven subsets. Since each pair can only belong to one subset, and we have 4950 pairs, it means each subset will have at least 4950/7 ≈ 707 pairs.
Step 3: Applying the Pigeonhole Principle.
To prove that there is at least one subset that satisfies either condition, we consider two cases.
Case 1: There exists a subset with at least four pairs such that the sums of the pairs are equal.
If we have a subset with four pairs such that a + b = c + d, it means we have found four numbers (a, b, c, d) satisfying the condition. In this case, we are done.
Case 2: There doesn't exist a subset with four pairs such that the sums of the pairs are equal.
In this case, we need to show that there must be a subset that satisfies the condition p + q = 2r.
Assume there are no such subsets. By the Pigeonhole Principle, each subset should contain at most two pairs satisfying the condition p + q = 2r.
Since we have 707 pairs in each subset, it implies that in total, we have 707 * 7 = 4949 pairs.
However, we have previously established that we have 4950 pairs in total. This means that at least one pair must satisfy the condition p + q = 2r. So, this case is not possible.
Therefore, by proving that both cases are not possible, we conclude that there must be at least one subset that satisfies either a + b = c + d or p + q = 2r. QED (quod erat demonstrandum).