Let $a_1, a_2, \cdots, a_{2n}$ be $2n$ elements of $\{1, 2, 3, \cdots, 2n-1\}$ ($n>3$) with the sum $a_1+a_2+\cdots+a_{2n}=4n$. Prove that exist some numbers $a_i$ with the sum is $2n$.
Problem
Source:
Tags: combinatorics
29.09.2021 12:02
It is well-known that among any $n$ integers we can find a non-empty subset with sum divisible by $n$. Apply this to $a_1,\dots,a_n$ to find that (w.l.o.g.) $a_1+\dots+a_k$ is divisible by $n$ for some $1 \le k \le n$. If $a_1+\dots+a_k=2n$, we are done. If $a_1+\dots+a_k=3n$, then we must have $k=n$ and the remaining $n$ numbers $a_{n+1},\dots,a_{2n}$ all must be equal to $1$. Now just take any subsum of $a_1+\dots+a_n$ which is in $[n,2n]$ (this surely exists) and add as many of the ones as necessary. Finally, assume that $a_1+\dots+a_k=n$. But now we can just apply the same reasoning to the numbers $a_{n+1},\dots,a_{2n}$ and find that the only remaining case is that $a_{m}+\dots+a_{2n}=n$ for some $m \ge n+1$. But then these two sums together give the desired $2n$. Done.
29.09.2021 16:20
thank you ))
01.03.2022 20:12
wlog $1<=a_1<=.....<=a_{2n}<=2n-1$ Consider the numbers $a_1,a_1+a_2,....,a_1+...+a_{2n-1}<4n$ and the sets$(1,2n+1),(2,2n+2),...,(2n-1,4n-1)$ if one of the numbers equal to $2n$ we are done. Otherwise we have $2n-1$ numbers and $2n-1$ sets. If two numbers go to the some set we are done. If $a_{2n}=2$ we are done. Otherwise$a_{2n}>=3$ which means that$a_1+...+a_{2n-1}<4n-2$ so we must have take the numberw $2n-1,2n-2$ whicj means that we have $2n-1$ ones contradiction.
01.03.2022 22:20
P2nisic wrote: wlog $1\le a_1\le \cdots \le a_{2n}\le2n-1$ Consider the numbers $a_1,a_1+a_2,\cdots,a_1+\cdots+a_{2n-1}<4n$ and the sets$(1,2n+1),(2,2n+2),\cdots,(2n-1,4n-1)$ if one of the numbers equal to $2n$ we are done. Otherwise we have $2n-1$ numbers and $2n-1$ sets. If two numbers go to the some set we are done. If $a_{2n}=2$ we are done. Otherwise$a_{2n}\ge3$ which means that$a_1+\cdots+a_{2n-1}<4n-2$ so we must have take the numberw $2n-1,2n-2$ whicj means that we have $2n-1$ ones contradiction.