MathDB
Choosing Sets, Relative Complement

Source: 2015 Korean Mathematical Olympiad P7

November 1, 2015
combinatoricsSets

Problem Statement

A positive integer nn is given. If there exists sets F1,F2,⋯FmF_1, F_2, \cdots F_m satisfying the following conditions, prove that m≤nm \le n. (For sets A,BA, B, ∣A∣|A| is the number of elements of AA. A−BA-B is the set of elements that are in AA but not BB. min(x,y)\text{min}(x,y) is the number that is not larger than the other.)
(i): For all 1≤i≤m1 \le i \le m, Fi⊆{1,2,⋯ ,n}F_i \subseteq \{1,2,\cdots,n\}
(ii): For all 1≤i<j≤m1 \le i < j \le m, min(∣Fi−Fj∣,∣Fj−Fi∣)=1\text{min}(|F_i-F_j|,|F_j-F_i|) = 1
Back to ProblemsView on AoPS