Maths Olympiad Prep

Track / Stage 6 / 336 of 400 #1336 of 1964

Problem 1336

National olympiad, first round
Combinatorics Difficulty 6.7 Find the answer

If XX is a finite set, let XX denote the number of elements in XX. Call an ordered pair (S,T)(S,T) of subsets of {1,2,,n} \{ 1, 2, \cdots, n \} admissible \emph {admissible} if s>T s > |T| for each sS s \in S , and t>S t > |S| for each tT t \in T . How many admissible ordered pairs of subsets {1,2,,10} \{ 1, 2, \cdots, 10 \} are there? Prove your answer.

A number or a short expression. Spacing, $ signs and \frac vs / are all fine.

Official solution

To solve the problem, we need to count the number of admissible ordered pairs (S,T)(S, T) of subsets of {1,2,,10}\{1, 2, \cdots, 10\} such that s>Ts > |T| for each sSs \in S and t>St > |S| for each tTt \in T.

1. Understanding the conditions:
- For each element sSs \in S, s>Ts > |T|.
- For each element tTt \in T, t>St > |S|.

2. Analyzing the constraints:
- If SS is non-empty, let m=Sm = |S|. Then, for each tTt \in T, t>mt > m. This means TT can only contain elements greater than mm.
- Similarly, if TT is non-empty, let n=Tn = |T|. Then, for each sSs \in S, s>ns > n. This means SS can only contain elements greater than nn.

3. **Considering the possible values for SS and TT**:
- If SS and TT are both non-empty, the smallest element in SS must be greater than the size of TT, and the smallest element in TT must be greater than the size of SS. This creates a contradiction unless both sets are empty.

4. Counting the admissible pairs:
- The only way to satisfy both conditions without contradiction is if both SS and TT are empty. Therefore, the only admissible pair is (,)(\emptyset, \emptyset).

5. Conclusion:
- There is exactly one admissible ordered pair of subsets of {1,2,,10}\{1, 2, \cdots, 10\}.

The final answer is 1\boxed{1}.

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