There are $n$($\ge 2$) clubs $A_1,A_2,...A_n$ in Korean Mathematical Society. Prove that there exist $n-1$ sets $B_1,B_2,...B_{n-1}$ that satisfy the condition below. (1) $A_1\cup A_2\cup \cdots A_n=B_1\cup B_2\cup \cdots B_{n-1}$ (2) for any $1\le i<j\le n-1$, $B_i\cap B_j=\emptyset, -1\le\left\vert B_i \right\vert -\left\vert B_j \right\vert\le 1$ (3) for any $1\le i \le n-1$, there exist $A_k,A_j $($1\le k\le j\le n$)such that $B_i\subseteq A_k\cup A_j$
Problem
Source: FKMO 2021 Problem 4
Tags: combinatorics, Sets, FKMO, easy
12.05.2021 06:26
Let's prove this problem with mathematical induction about $n$. If $n=2$, it obviously exist $B_1$ satisfy the condition. Suppose when $n$, there exist $B_1,B_2,...B_{n-1}$ that satisfy the condition. Let's show that this is also true in $n+1$. Let there are $k=nq+r (0\le r<n)$ students. Then it must be $\left\vert B_i \right\vert =q$ or $q+1$ for all $1\le i\le n$. Let $T$ be the set of students contained in only one of $A_1,A_2,...A_{n+1}$. Then we get $\left\vert A_1\cap T\right\vert +\left\vert A_2\cap T\right\vert +...+\left\vert A_{n+1}\cap T\right\vert =\left\vert T\right\vert \le nq+r$. By pigeonhole principle, there exists that is less than $q$ among $\left\vert A_1\cap T\right\vert , \left\vert A_2\cap T\right\vert ,...\left\vert A_{n+1}\cap T\right\vert$. W.L.O.G. $\left\vert A_{n+1}\cap T\right\vert =t<q$. Now let $(A_1\cup A_2\cup \cdots A_n)-(A_{n+1}\cap T)=U$, W.L.O.G. $max(\left\vert A_1\cap U\right\vert , \left\vert A_2\cap U\right\vert ,...\left\vert A_{n+1}\cap U\right\vert )=\left\vert A_{n}\cap U\right\vert$. $\left\vert A_1\cap U\right\vert +\left\vert A_2\cap U\right\vert +...+\left\vert A_n\cap U\right\vert\ge\left\vert U\right\vert =nq+r-t>n(q-1)$, so we get $\left\vert A_{n}\cap U\right\vert\ge q$ Now we can choose $q-t$ students in $A_{n}\cap U$, and there are $t$ students in $A_{n+1}\cap T$. Let these $q$ students as $B_n$. Then $B_n\subseteq A_n\cup A_{n+1}$, so it satisfies condition (3). By inductive supposition, there exist $B_1,B_2,...B_{n-1}$ that satisfy $A_1\cup A_2\cup \cdots A_n=B_1\cup B_2\cup \cdots B_{n-1}$, $B_i\cap B_j=\emptyset$, $B_i\subseteq A_k\cup A_j$. By condition $-1\le\left\vert B_i \right\vert -\left\vert B_j \right\vert\le 1$, we also get $\left\vert B_i \right\vert =q$ or $q+1$. We can easily check that $A_1,A_2,...A_{n+1}$ and $B_1,B_2,...B_{n}$ satisfy condition too.$\blacksquare$
12.05.2021 06:33
chrono223 wrote: There are $n$($\ge 2$) clubs $A_1,A_2,...A_n$ in Korean Mathematical Society. Prove that there exist $n-1$ sets $B_1,B_2,...B_{n-1}$ that satisfy the condition below. (1) $A_1\cup A_2\cup \cdots A_n=B_1\cup B_2\cup \cdots B_{n-1}$ (2) for any $1\le i<j\le n-1$, $B_i\cap B_j=\emptyset$ (3) for any $1\le i \le n-1$, there exist $A_k,A_j $($1\le k\le j\le n$)such that $B_i\subseteq A_k\cup A_j$ +condition $-1\le\left\vert B_i \right\vert -\left\vert B_j \right\vert\le 1$ for any $1\le i<j\le n-1$
22.11.2021 17:22
I assume every club consists of a finite number of members. We will prove the problem by mathematical induction on $n$. For the base case $n=2$ choose $B_1=A_1\cup A_2$. Assume $n\ge 2$ and the problem is true for $n$. We will now prove it for $n+1$. Let $A_1,\dots,A_{n+1}$ be our given sets. Write $\left|\bigcup_{i=1}^{n+1}A_i\right|=qn+r$ where $q,r$ are nonnegative integers with $r<n$. For an index $i\in[n+1]$, let $T_i=A_i\setminus\left(\bigcup_{j\ne i}A_j\right)$. Observe that the sets $T_1,\ldots,T_{n+1}$ are disjoint. Hence $$\sum_{i=1}^{n+1}|T_i|\le\left|\bigcup_{i=1}^{n+1}A_i\right|=qn+r<(q+1)n<(q+1)(n+1).$$Hence we can assume WLOG that $|T_{n+1}|<q+1$, so $|T_{n+1}|\le q$. Moreover we have $$qn\le qn+r=\left|\bigcup_{i=1}^{n+1}A_i\right|=\left|\bigcup_{i=1}^n A_i\right|+|T_{n+1}|\le\sum_{i=1}^n |A_i|+|T_{n+1}|.$$Hence we can assume WLOG that $|A_n|+\frac{|T_{n+1}|}{n}\ge q$, so $|A_n|+|T_{n+1}|\ge q$. Pick some subset $U\subset A_n$ with $|U|=q-|T_{n+1}|$. Define $B_n=T_{n+1}\cup U$. Hence $|B_n|=q$ and $B_n\subset A_n\cup A_{n+1}$. By induction hypothesis, there exist $n-1$ sets $B_1,B_2,\ldots,B_{n-1}$ that satisfy the condition below: $\bigcup_{i=1}^{n-1}B_i=\bigcup_{j=1}^n\left(A_j\setminus U\right)$, for any $1\le i<j\le n-1$, we have $B_i\cap B_j=\emptyset$ and $-1\le\left|B_i\right| -\left|B_j\right|\le 1$, and for any $1\le i \le n-1$, there exist $A_k,A_j$ ($1\le k\le j\le n$) such that $B_i\subset \left(A_k\setminus U\right)\cup\left(A_j\setminus U\right)\subset A_k\cup A_j$. It follows that $$\bigcup_{i=1}^{n-1}B_i=\bigcup_{j=1}^n\left(A_j\setminus U\right)=\left(\bigcup_{j=1}^n A_j\right)\setminus U=\left(\bigcup_{j=1}^{n+1} A_j\right)\setminus B_n$$so $B_i\cap B_n=\emptyset$ for all $i\in[n-1]$ and $\bigcup_{i=1}^n B_i=\bigcup_{j=1}^{n+1}A_j$. Moreover $$\sum_{i=1}^{n-1}|B_i|=\left|\bigcup_{i=1}^{n-1}B_i\right|=\left|\bigcup_{j=1}^{n+1} A_j\right|-|B_n|\ge qn-q=q(n-1)$$and $$\sum_{i=1}^{n-1}|B_i|=\left|\bigcup_{j=1}^{n+1} A_j\right|-|B_n|=qn+r-q\le qn+n-1-q=(q+1)(n-1).$$Therefore $|B_i|\in\{q,q+1\}$ for all $i\in[n-1]$ so $|B_i|\in\{q,q+1\}$ for all $i\in[n]$.