A positive integer $n$ is given. If there exists sets $F_1, F_2, \cdots F_m$ satisfying the following conditions, prove that $m \le n$. (For sets $A, B$, $|A|$ is the number of elements of $A$. $A-B$ is the set of elements that are in $A$ but not $B$. $\text{min}(x,y)$ is the number that is not larger than the other.) (i): For all $1 \le i \le m$, $F_i \subseteq \{1,2,\cdots,n\}$ (ii): For all $1 \le i < j \le m$, $\text{min}(|F_i-F_j|,|F_j-F_i|) = 1$
Problem
Source: 2015 Korean Mathematical Olympiad P7
Tags: combinatorics, Sets
rkm0959
08.12.2015 18:13
Step 1. Reduction to 2015 KJMO P8. WLOG, $|F_1| \le |F_2| \le \cdots \le |F_m|$.
Now if $i<j$, we have $\text{min} (|F_i-F_j|,|F_j-F_i|)=|F_i-F_j|$, so we can transform this problem to KJMO P8
We proceed with strong induction on $m$ to show that $|F_1 \cup F_2 \cup \cdots F_m| \ge m$.
The result will follow since $n \ge |F_1 \cup F_2 \cdots \cup F_m|$.
The base case $m=1$ is trivial. Assume that the statement is true for all $m' \le m-1$.
Since $|F_1 \cup F_2 \cdots \cup F_m| \ge |F_1 \cup F_2 \cup \cdots \cup F_{m-1}| \ge m-1$, we must have $|F_1 \cup F_2 \cdots \cup F_m|=m-1$ for our result to be false.
From our condition, we have $|F_i-F_{i+1}|=1$. Let $\{a_i\}=F_i-F_{i+1}$.
Step 2. I claim that for all $i<j \le k <l$, $F_i-F_j \not= F_k-F_l$.
The case $j=k$ is trivial. Assume that $j \not= k$. Draw a ridiculously looking Venn-Diagram with four sets $F_i, F_j, F_k, F_l$. Then straightforward calculations give the result. (I won't go into the details)
Now, assume for the sake of contradiction that $|F_1 \cup F_2 \cdots \cup F_m|=m-1$....
Vexation
20.12.2015 09:32
Induction. Easy to check when $n\le3$. Suppose $m>n$. We can find two sets $F_i, F_j$ of same cardinality. By (ii), $F_i=A \cup \{a\}, F_j=A \cup \{b\}$ ($a, b$ are different) for some set $A$. We claim that any other sets cannot have only one of $a, b$ in their elements. Suppose $F$ has $a$ and not $b$. If $|F| \le |F_i|$, $|F-F_i|=|F-F_j|=1$. $F-F_i=(F-\{a\})-A$ and $F-F_j=(F-\{b\})-A=F-A$. $F-F_j=(F-F_i) \cup \{a\}$. Contradiction. Same way when $|F|\ge|F_i|$. Therefore, other sets have both $a,b$ or neither. It means that if $P, Q$ satisfy $ |P-Q|=1$, $P-Q$ has neither $a$ nor $b$. Remove $F_i, F_j$ and $a, b$ from every set. Those $m-2$ sets still meet the condition (ii), successfully reducing the problem to $n-2$. $m-2\le n-2$; $m\le n$.