Given $2n$ natural numbers, so that the average arithmetic of those $2n$ number is $2$. If all the number is not more than $2n$. Prove we can divide those $2n$ numbers into $2$ sets, so that the sum of each set to be the same.
Problem
Source: INAMO Shortlist 2015 C2
Tags: combinatorics, arithmetic, Sets
10.07.2019 06:30
Translation correction: prove that you can divide into 2 sets so that the *SUM* of each set is the same, not the average. Solution: this is very similar to INAMO 2019 P3 and P8. The sum of all numbers is $4n$ so we want to find a subset whose sum is $2n$. Then consider the following lemma: Given $2n$ numbers in the interval $[1,2n]$ whose sum is $2S \in [2n,4n] \iff S \in [n, 2n]$, there exists a subset whose sum is $S$. Proof: The lemma is easy to show for $n=1,2$. Then we use induction on $n$. If all the numbers are different then it must be $(1,2,\dots,2n)$ and then easy to see that $1 + (S-1) = S$. But if not, then two numbers must be the same. Let $k$ be the largest of those duplicated numbers. If $k \geq 2$ then remove them from the set, so we are left with $2n-2$ numbers whose sum is $2S - 2k \in [2n-2k,4n-2k] \subseteq [2n-2, 4n-4]$. By induction hypothesis, there exists a subset whose sum is $S-k$ so we add the single $k$ to it to form a subset that's $S$. If $k = 1$, then remove them from the set, so we are left with $2n-2$ numbers whose sum is $2S-2 \in [2n-2, 4n-2]$ If the sum is $2S-2 = 4n-4$ then induction hypothesis still applies. But if the sum is $2S - 2 = 4n-2$ that means the sum of original numbers $2S = 4n$. Suppose there are $t$ ones in the original numbers (we already know $t \geq 2$). Consider the largest number. If it is $2n, 2n-1, \dots, 2n-t$ then we are done. If not then we have $2n-t$ numbers that must be in the interval $[2, 2n-t-1]$, which means that two numbers are the same. This contradicted our assumption that the largest duplicated number was 1, and it completes our proof.
20.12.2024 10:01
let the numbers be $a_k$ for $1\le k\le 2n$. It is suffices to prove that exist a subset of those number such that the sum of the numbers equal to $2n$. Note that if exist a number in \(a_1, a_1 + a_2, a_1 + a_2 + a_3, \ldots , a_1 + a_2 + a_3 + \ldots + a_{2n} \) that is divisible by 2n, then we are done. Else, see that there are $2n$ numbers and $2n-1$ residues mod $2n$. By Pigeonhole Principle, there exist index $i$ and $j$ with $j>i$ such that \(a_1 + a_2 + a_3 + \ldots + a_i \equiv a_1 + a_2 + a_3 + \ldots + a_j \mod 2n\). Hence \(a_{k+1} + a_{k+2} + a_{k+3} + \ldots + a_j \equiv 0 \mod 2n\). Since the sum can't be $4n$ or more, then it must be $2n$, as desired.