Maths Olympiad Prep

Library / /80 of 115

Combinatorics Difficulty 7.5 National olympiad, round 2 Find the answer

Let S1,S2,,S100S_1, S_2, \ldots, S_{100} be finite sets of integers whose intersection is not empty. For each non-empty T{S1,S2,,S100},T \subseteq \{S_1, S_2, \ldots, S_{100}\}, the size of the intersection of the sets in TT is a multiple of the number of sets in TT. What is the least possible number of elements that are in at least 5050 sets?

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let S1,S2,,S100 S_1, S_2, \ldots, S_{100} be finite sets of integers such that their intersection is not empty. For every non-empty subset T T of {S1,S2,,S100} \{S_1, S_2, \ldots, S_{100}\} , the size of the intersection of the sets in T T is a multiple of the number of sets in T T .

We want to determine the least possible number of elements that are present in at least 50 50 of these sets.

### Analysis

Let nT=SiTSi n_T = | \bigcap_{S_i \in T} S_i | , where T T is any non-empty subset of the 100 100 sets. According to the problem, nT n_T is a multiple of T |T| .

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 T |T| divides nT n_T .

2. Constructing an Example:
- Suppose we take an arbitrary integer c c that belongs to each Si S_i . 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 c c 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 TnT |T| \mid n_T is satisfied.

3. Estimation:
- Suppose there is an integer a a present in exactly 50 50 of the sets, i.e., a a is included in sets forming a combination of 50 50 .
- For (10050) \binom{100}{50} combinations of choosing 50 sets from 100 sets, if a a is the common element, then each such 50 50 set combination includes a a .

4. Count the Minimum Elements:
- Consider each integer to be in exactly 50 sets.
- Thus, for each of the combinations (10050) \binom{100}{50} , we need an integer present in all 50, giving:
50×(10050) 50 \times \binom{100}{50}
- This product ensures that each combination of 50 50 sets from the total 100 100 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:
50(10050) \boxed{50 \cdot \binom{100}{50}}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.