Let be finite sets of integers whose intersection is not empty. For each non-empty the size of the intersection of the sets in is a multiple of the number of sets in . What is the least possible number of elements that are in at least sets?
Solution
Let be finite sets of integers such that their intersection is not empty. For every non-empty subset of , the size of the intersection of the sets in is a multiple of the number of sets in .
We want to determine the least possible number of elements that are present in at least of these sets.
### Analysis
Let , where is any non-empty subset of the sets. According to the problem, is a multiple of .
To solve this problem, consider:
1. Simplify the Problem: We need to ensure that the intersection of any subset of the provided sets contains an integer and it must also satisfy the condition that divides .
2. Constructing an Example:
- Suppose we take an arbitrary integer that belongs to each . This ensures that the intersection of any collection of these sets is not empty, providing the condition that their intersection contains at least one integer.
- Choose to be part of an arithmetic progression with a common difference that is a multiple of the number of sets involved, ensuring the condition of is satisfied.
3. Estimation:
- Suppose there is an integer present in exactly of the sets, i.e., is included in sets forming a combination of .
- For combinations of choosing 50 sets from 100 sets, if is the common element, then each such set combination includes .
4. Count the Minimum Elements:
- Consider each integer to be in exactly 50 sets.
- Thus, for each of the combinations , we need an integer present in all 50, giving:
- This product ensures that each combination of sets from the total sets has at least 50 in common (and subsequently multiples for larger sets).
Thus, the least possible number of integers that can be in at least 50 sets: