KMO 2004 Problem 4

Let $k$ and $N$ be positive real numbers which satisfy $k\leq N$ . For $1\leq i \leq k$ , there are subsets $A_i$ of $\{1,2,3,\ldots,N\}$ that satisfy the following property.

For arbitrary subset of $\{ i_1, i_2, \ldots , i_s \} \subset \{ 1, 2, 3, \ldots, k \}$ , $A_{i_1} \triangle A_{i_2} \triangle ... \triangle A_{i_s}$ is not an empty set.

Show that a subset $\{ j_1, j_2, .. ,j_t \} \subset \{ 1, 2, ... ,k \}$ exist that satisfies $n(A_{j_1} \triangle A_{j_2} \triangle \cdots \triangle A_{j_t}) \geq k$ . ( $A \triangle B=A \cup B-A \cap B$ )