MathDB
Existence of a subset of S_n

Source: 2004 Korea Junior Math Olympiad

June 28, 2024
SetsExistenceSubsetscombinatorics

Problem Statement

For n≥3n\geq3 define Sn={1,2,...,n}S_n=\{1, 2, ..., n\}. A1,A2,...,AnA_1, A_{2}, ..., A_{n} are given subsets of SnS_n, each having an even number of elements. Prove that there exists a set {i1,i2,...,it}\{i_1, i_2, ..., i_t\}, a nonempty subset of SnS_n such that
Ai1ΔAi2Δ…ΔAit=∅A_{i_1} \Delta A_{i_2} \Delta \ldots \Delta A_{i_t}=\emptyset
(For two sets A,BA, B, we define Δ\Delta as AΔB=(A∪B)−(A∩B)A \Delta B=(A\cup B)-(A\cap B))
Back to ProblemsView on AoPS