Let $A$ be a set consist of finite real numbers,$A_1,A_2,\cdots,A_n$ be nonempty sets of $A$, such that (a) The sum of the elements of $A$ is $0,$ (b) For all $x_i \in A_i(i=1,2,\cdots,n)$,we have $x_1+x_2+\cdots+x_n>0$. Prove that there exist $1\le k\le n,$ and $1\le i_1<i_2<\cdots<i_k\le n$, such that \[|A_{i_1}\bigcup A_{i_2} \bigcup \cdots \bigcup A_{i_k}|<\frac{k}{n}|A|.\] Where $|X|$ denote the numbers of the elements in set $X$.
Problem
Source:
Tags: ceiling function, inequalities, integration, calculus, combinatorics proposed, combinatorics
Lei Lei
17.01.2011 21:44
Quote: (2) For all $ x_{i}\in A_{i}(i=1,2,\cdots,n) $,we have $ x_{1}+x_{2}+\cdots+x_{n}>0 $. <del>I dun get it.... Does it mean the sum of all elements in each $A_i$ is positive or</del> pick $x_1 \in A_1, x_2 \in A_2, \ldots ,x_n \in A_n$ and we have $ x_{1}+x_{2}+\cdots+x_{n}>0 $? Edit: never read condition (1) D:
TheIronChancellor
17.01.2011 23:52
I Think That Its The Second One ... Can Anyone Post Solution For Studying ?
motal
18.01.2011 00:16
This is my thought so far: prove the converse, that is \[ |A_{i_{1}}\bigcup A_{i_{2}}\bigcup\cdots\bigcup A_{i_{k}}|\ge\frac{k}{n}|A|. \] for all choices and of $k$ and $i_k$, and apply the second hypothesis. Then try to prove that the first one is wrong. Try to prove that we can partition $A$ into $n$ sets $B_i$ of cardinality $\frac{|A|}{n}$ so that $B_i\in A_i$ for $1\le i\le n$. The conclusion would follow.
ocha
18.01.2011 05:28
Suppose $A$ has elements $a_1 \ge a_2 \ge ... \ge a_m$. Order the set $A_i$ such that $\min\{A_1\} \ge \min\{A_2\} \ge ... \ge \min\{A_n\}$. Condition 2 says that $\sum_{i=1}^n \min\{A_i\} >0$. However we also have $\sum_{a\in A} a = 0$. If the claim was false then $\left|\bigcup_{i=1}^kA_i\right| \ge \frac{k}{n}|A|$. And consequently $\min \left\{\bigcup_{i=1}^kA_i\right\} \le a_{k'}$ where $k' = \left\lceil \textstyle\frac{k|A|}{n}\right\rceil$. But from how we ordered the sets this implies that $\min\{A_k\} \le a_{k'}$ Therefore $\sum_{k=1}^n \min\{A_k\} \le \sum_{k=1}^n a_{k'} \le \frac{n}{|A|} \sum_i a_i = 0$ which is a contradiction. The claim is proven.
TheIronChancellor
18.01.2011 20:58
Could you be more clear in your steps please. What is required to solve this kind of problem ?
thesamyaandoctor
19.01.2011 19:34
is this easy for p.3 China? after I read the solution nothing left to do
hungnguyenvn
20.01.2011 12:49
If $ \left|\bigcup_{i=1}^{k}A_{i}\right|\ge\frac{k}{n}|A| $ for all k, then We prove that $ \sum_{a\in A}a >0 $ |A|= mn+r ; (r <= n-1). Apply Koning-hall theorem we have $ x_{1i}\in A_{1}, x_{2i}\in A_{2},\ldots ,x_{ni}\in A_{n} $ 1<=i<=m. Sum theres >0. And r element in A, we can prove that sum >0.
agzqu
29.01.2011 14:33
ocha wrote: Therefore $\sum_{k=1}^n \min\{A_k\} \le \sum_{k=1}^n a_{k'} \le \frac{n}{|A|} \sum_i a_i = 0$ which is a contradiction. The claim is proven. the second inequality requires more explanation, it is not obvious.
dnkywin
25.04.2011 03:59
agzqu wrote: ocha wrote: Therefore $\sum_{k=1}^n \min\{A_k\} \le \sum_{k=1}^n a_{k'} \le \frac{n}{|A|} \sum_i a_i = 0$ which is a contradiction. The claim is proven. the second inequality requires more explanation, it is not obvious.
Let $f(x)=a_{\lceil x\rceil }$. Clearly $f$ is nonincreasing. Thus
\[\sum_{i=1}^{|A|} a_i = \int_0^{|A|} f(x) dx = \sum_{k=1}^n \int_{(k-1)|A|/n}^{k|A|/n} f(x) \ge \sum_{k=1}^n \int_{(k-1)|A|/n}^{k|A|/n} f(k|A|/n) = \sum_{k=1}^n \frac{|A|}n a_{k'}\]
from which the desired inequality follows.
Note that it is not hard to get an elementary solution by just evauating each integral
mathaddiction
22.09.2021 05:27
Let $y_i=\min A_i$, and $y_{n+1}=\max A$, without loss of generality assume $y_1<y_2<...<y_n$, then $$y_1+...+y_n>0$$Notice that if $A_1\cup ...\cup A_n\neq A$ we can simply take $k=n$. Therefore, we may assume $A_1\cup...\cup A_n=A$. Now let $c_i$ be the number of elements in $A_i$ in the interval $[y_0,y_{i+1})$, also define $c_0=0$. Notice that if $$|A_{i+1}\cup ...\cup A_n|\geq\frac{n-i}{n}|A|=\frac{n-i}{n}c_n$$Then $$c_i\leq|A|-|A_{i+1}\cup...\cup A_n|\leq \frac{i}{n}|A|\hspace{20pt}(1)$$Now, we have $$0=\sum_{x\in A}x=\sum_{i=1}^n\sum_{x\in[y_i,y_{i+1})}x\geq \sum_{i=1}^n y_i(c_i-c_{i-1})\hspace{20pt}(2)$$By Abel Summation Formula we have $$\sum_{i=1}^ny_i(c_i-c_{i-1})=c_ny_n-c_0y_0-\sum_{i=1}^{n-1}c_i(y_{i+1}-y_i)=c_ny_n-\sum_{i=1}^{n-1}c_i(y_{i+1}-y_i)\hspace{20pt}(3)$$Combining $(1),(2),(3)$, $$0\geq \sum_{i=1}^ny_i(c_i-c_{i-1})=c_ny_n-\sum_{i=1}^{n-1}c_i(y_{i+1}-y_i)\geq c_n\left(y_n-\sum_{i=1}^n\frac{i}{n}(y_{i+1}-y_i)\right)=\frac{ic_n}{n}(y_1+...+y_n)$$contradiction.