Olympiad Maths Prep

Track / Stage 7 / 203 of 300 #1603 of 2000

Problem 1603

National olympiad second round; IMO P1/P4
Combinatorics Difficulty 7.4 Find the answer

Let FF be a family of subsets of S={1,2,...,n}S = \left \{ 1,2,...,n \right \} (n≥2n \geq 2). A valid play is to choose two disjoint sets AA and BB from FF and add A∪BA \cup B to FF (without removing AA and BB).

Initially, FF has all the subsets that contain only one element of SS. The goal is to have all subsets of n−1n - 1 elements of SS in FF using valid plays.

Determine the lowest number of plays required in order to achieve the goal.

Official solution

1. Base Case:
- For n=2 n = 2 :
- Initially, F={{1},{2}} F = \{ \{1\}, \{2\} \} .
- We need to obtain {1} \{1\} and {2} \{2\} , which are already in F F .
- No moves are required, so the base case holds trivially.
- For n=3 n = 3 :
- Initially, F={{1},{2},{3}} F = \{ \{1\}, \{2\}, \{3\} \} .
- We need to obtain {1,2},{1,3},{2,3} \{1, 2\}, \{1, 3\}, \{2, 3\} .
- Perform the following moves:
1. {1}∪{2}→{1,2} \{1\} \cup \{2\} \rightarrow \{1, 2\}
2. {1}∪{3}→{1,3} \{1\} \cup \{3\} \rightarrow \{1, 3\}
3. {2}∪{3}→{2,3} \{2\} \cup \{3\} \rightarrow \{2, 3\}
- Thus, 3 moves are required, and the base case holds.

2. Inductive Step:
- Assume for n=k n = k , we need at least 3k−6 3k - 6 moves to obtain all subsets of k−1 k-1 elements from {1,2,…,k} \{1, 2, \ldots, k\} .
- We need to show that for n=k+1 n = k+1 , we need at least 3(k+1)−6=3k−3 3(k+1) - 6 = 3k - 3 moves.

3. **Using {k+1} \{k+1\} in Operations:**
- We must use {k+1} \{k+1\} in at least 2 operations:
- If {k+1} \{k+1\} is used in only one operation, say with set A⊂{1,2,…,k} A \subset \{1, 2, \ldots, k\} , then we cannot obtain the set {1,2,…,k+1}−{a} \{1, 2, \ldots, k+1\} - \{a\} where a∈A a \in A , leading to a contradiction.

4. **Constructing F′ F' :**
- Let F F be the family of subsets of {1,2,…,k+1} \{1, 2, \ldots, k+1\} after m m operations.
- For each A∈F A \in F , let A′=A−{k+1} A' = A - \{k+1\} , and let F′=∪A′ F' = \cup A' .
- Initially, F F had only {1},{2},…,{k} \{1\}, \{2\}, \ldots, \{k\} and the empty set {k+1}−{k+1} \{k+1\} - \{k+1\} .
- At the end, F′ F' must have {1,2,…,k}−{t} \{1, 2, \ldots, k\} - \{t\} for t=1,2,…,k t = 1, 2, \ldots, k and {1,2,…,k}={1,2,…,k+1}−{k+1} \{1, 2, \ldots, k\} = \{1, 2, \ldots, k+1\} - \{k+1\} .

5. Number of Moves:
- By the inductive hypothesis, we need at least 3k−6+1=3k−5 3k - 6 + 1 = 3k - 5 moves to obtain F′ F' (the extra move is for the set {1,2,…,k} \{1, 2, \ldots, k\} ).
- Since we use {k+1} \{k+1\} at least twice, we need at least 3k−5+2=3k−3 3k - 5 + 2 = 3k - 3 operations.
- Thus, m≥3k−3=3(k+1)−6 m \geq 3k - 3 = 3(k+1) - 6 , and the result follows by induction.

6. Example Construction:
- We can achieve the goal with exactly 3n−6 3n - 6 operations:
1. {1},{2}→{1,2} \{1\}, \{2\} \rightarrow \{1, 2\}
2. {1,2},{3}→{1,2,3} \{1, 2\}, \{3\} \rightarrow \{1, 2, 3\}
3. {1,2,3},{4}→{1,2,3,4} \{1, 2, 3\}, \{4\} \rightarrow \{1, 2, 3, 4\}
4. Continue this process until {1,2,…,n−2},{n−1}→{1,2,…,n−1} \{1, 2, \ldots, n-2\}, \{n-1\} \rightarrow \{1, 2, \ldots, n-1\}
5. {n},{n−1}→{n,n−1} \{n\}, \{n-1\} \rightarrow \{n, n-1\}
6. {n,n−1},{n−2}→{n,n−1,n−2} \{n, n-1\}, \{n-2\} \rightarrow \{n, n-1, n-2\}
7. Continue this process until {n,n−1,…,3},{2}→{1,2,…,n}−{1} \{n, n-1, \ldots, 3\}, \{2\} \rightarrow \{1, 2, \ldots, n\} - \{1\}
8. {1,2,…,n−2},{n}→{1,2,…,n}−{n−1} \{1, 2, \ldots, n-2\}, \{n\} \rightarrow \{1, 2, \ldots, n\} - \{n-1\}
9. Continue this process until {1},{n,n−1,…,3}→{1,2,…,n}−{2} \{1\}, \{n, n-1, \ldots, 3\} \rightarrow \{1, 2, \ldots, n\} - \{2\}

The final answer is 3n−6 \boxed{ 3n - 6 }

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