Let be a positive integer, and let be a collection of finite non-empty sets such that
Prove that there exist pairwise distinct elements such that is a member of for each index .
Solution
1. Define the problem and the given condition:
We are given a collection of finite non-empty sets such that:
We need to prove that there exist pairwise distinct elements such that for each .
2. Random selection and probability calculation:
Choose a random element from for each . The probability that the chosen elements and are the same for is given by:
3. Summing the probabilities:
The probability that at least one pair are the same (i.e., there exists some such that ) is at most:
By the given condition, this sum is less than 1:
4. Conclusion using the probabilistic method:
Since the probability that some two and are the same is less than 1, there must exist a choice of such that all are distinct. This is because if the probability of an event is less than 1, then there exists a non-zero probability that the event does not occur. Hence, there exists a selection where all are distinct.