Let $n \geqslant 2$ be an integer. There are $n$ finite sets ${A_1},{A_2},\ldots,{A_n}$ which satisfy the condition \[\left| {{A_i}\Delta {A_j}} \right| = \left| {i - j} \right| \quad \forall i,j \in \left\{ {1,2,...,n} \right\}.\] Find the minimum of $\sum\limits_{i = 1}^n {\left| {{A_i}} \right|} $.
Problem
Source: 2013 China Mathematical Olympaid P4
Tags: floor function, induction, inequalities, combinatorics proposed, combinatorics
13.01.2013 10:05
Another easy problem. We deal the case when null sets are not allowed. The minimum of $ \sum\limits_{i = 1}^n{\left|{{A_i}}\right|} =\lfloor\frac{n^2}{4}\rfloor+2$.(If null sets are allowed, the answer is $\lfloor\frac{n^2}{4}\rfloor$) if $n=2k+1$, we can choose ${{A_i}}=\{1,3,...,2(k-i)+1\}$ for $1\le i \le k$, ${{A_{k+1}}}=\{1,2\}$, ${{A_i}}=\{2,4,...,2(i-k-1)\}$,for $k+2 \le i \le 2k+1$ if $n=2k$, we can choose ${{A_i}}=\{1,3,...,2(k-i)+1\}$ for $1\le i \le k$,${{A_{k+1}}}=\{1,2\}$, ${{A_i}}=\{2,4,...,2(i-k-1)\}$,for $k+2 \le i \le 2k$ In both cases, the condition holds and $ \sum\limits_{i = 1}^n{\left|{{A_i}}\right|} =\lfloor\frac{n^2}{4}\rfloor+2$. We can use induction to prove $ \sum\limits_{i = 1}^n{\left|{{A_i}}\right|} \ge \lfloor\frac{n^2}{4}\rfloor+2$. When $n=2$, $ \sum\limits_{i = 1}^2{\left|{{A_i}}\right|} \ge 3$, since two sets with one element each either have $ \left|{{A_1}\Delta{A_2}}\right|=0$ or $ \left|{{A_1}\Delta{A_2}}\right|=2$. When $n=3$, with the same way we have $ \sum\limits_{i = 1}^3{\left|{{A_i}}\right|} \ge 4$. Suppose the inequality holds for $n \le k$. We consider the case when $n=k+1$. $ \left|{{A_1}\Delta{A_{k+1}}}\right|=k$, so $|A_1|+|A_{k+1}| \ge k$. By the assumption $ \sum\limits_{i = 2}^k{\left|{{A_i}}\right|} \ge =\lfloor\frac{(k-1)^2}{4}\rfloor+2$, So $ \sum\limits_{i = 1}^{k+1}{\left|{{A_i}}\right|} \ge \lfloor\frac{(k+1)^2}{4}\rfloor+2$.
14.01.2013 02:16
Well done, veyron. I do it in an Constructive way in Chinese.
18.03.2022 09:08
Note: This version assumes emptysets are allowed, but the main idea stays the same Let $\{x_i\}=A_i\Delta A_{i+1}$ Claim: $\{x_i\}$ are pairwise distinct. Proof: Assume $x_i=x_j$ where $i<j$. Then $A_i\Delta A_{i+1}\Delta A_j\Delta A_{j+1}=\emptyset$. However, $(A_i\Delta A_{j+1}) \Delta (A_j\Delta A_{i+1})=\emptyset$, which implies $j-i+1=|A_i\Delta A_{j+1}|=|A_{i+1}\Delta A_j|=j-i-1$, contradiction. Note this condition is necessary, but also sufficient. I claim the answer is $\frac{n^2}{4}$ if $n$ is even and $\frac{n^2-1}{4}$ otherwise. Proof of optimality: sum opposite ends XD. If $n$ is even, $\sum_{j=1}^n |A_j|=\sum\limits_{j=1}^{n/2} |A_j|+|A_{n+1-j}| \ge \sum\limits_{j=1}^{n/2} |A_j \Delta A_{n+1-j}| =\sum\limits_{j=1}^{n/2} (n+1-2j)$, which proves the optimality. For $n$ odd it's similar. Construction: Let $k=\lceil \frac n2 \rceil$. Let $A_k=\emptyset$. We have for $l<k, A_l=\{x_l, \cdots, x_{k-1} \}$ and for $l>k$, $A_l=\{x_{k+1}, \cdots, x_l \}$Let $\{x_i\}=A_i\Delta A_{i+1}$ Claim: $\{x_i\}$ are pairwise distinct. Proof: Assume $x_i=x_j$ where $i<j$. Then $A_i\Delta A_{i+1}\Delta A_j\Delta A_{j+1}=\emptyset$. However, $(A_i\Delta A_{j+1}) \Delta (A_j\Delta A_{i+1})=\emptyset$, which implies $j-i+1=|A_i\Delta A_{j+1}|=|A_{i+1}\Delta A_j|=j-i-1$, contradiction. Note this condition is necessary, but also sufficient. I claim the answer is $\frac{n^2}{4}$ if $n$ is even and $\frac{n^2-1}{4}$ otherwise. Proof of optimality: sum opposite ends XD. If $n$ is even, $\sum_{j=1}^n |A_j|=\sum\limits_{j=1}^{n/2} |A_j|+|A_{n+1-j}| \ge \sum\limits_{j=1}^{n/2} |A_j \Delta A_{n+1-j}| =\sum\limits_{j=1}^{n/2} (n+1-2j)$, which proves the optimality. For $n$ odd it's similar. Construction: Let $k=\lceil \frac n2 \rceil$. Let $A_k=\emptyset$. We have for $l<k, A_l=\{x_l, \cdots, x_{k-1} \}$ and for $l>k$, $A_l=\{x_{k+1}, \cdots, x_l \}$