There are $n$ (an even number) bags. Each bag contains atleast one apple and at most $n$ apples. The total number of apples is $2n$. Prove that it is always possible to divide the bags into two parts such that the number of apples in each part is $n$.
Problem
Source: NMTC 2023 Junior P4
Tags: nmtc, combinatorics
15.11.2023 13:25
For $k\in\{1,2,...,n-1,n\}$ denote $B_k$ the bag $k$ and $a_k$ the number of apples in the bag $B_k$. We arrange the bags in the ascending order of $a_k:\;a_1\le a_2\le...\le a_{n-1}\le a_{n}\le n$. Denote $S_k$ the partial sums $S_k=\sum_{i=1}^k a_i$. From the initial conditions: $S_{n}=2n$. $2n=S_{n}=\sum_{i=1}^{n} a_i\ge n\cdot a_1\Longrightarrow a_1\le2$. $\textbf {Case 1) }a_1=2$. $n=2m,\,m\in\mathbb{N}\Longrightarrow a_1=a_2=...=a_{2m}=2\Longrightarrow a_1+a_2+...+a_m=a_{m+1}+a_{m+2}+...+a_{2m}=2m=n$. $\textbf {Case 2) }a_n=n\Longrightarrow a_1+a_2+...+a_{n-1}=a_n=n$. $\textbf {Case 3) }$ exists $p\in\{2,3,...,n-1\}$ such that $S_p=n$. In this case: $\sum_{i=1}^p a_i=\sum_{i=p+1}^{n}a_i=n$. $\textbf {Case 4) }$ exists $i,j\in\{1,2,...,n-1,n\},\;i<j$ such that $S_j-S_i=n\Longrightarrow a_{i+1}+a_{i+2}+...+a_{j-1}+a_j=n$. In the previous cases it is possible to divide the bags into two parts such that the number of apples in each part is $n$. We will prove: are not possible other cases. Equivalently, it is not possible the $\textbf{case 5}:\;1=a_1\le a_2\le...\le a_{n-1}\le a_{n}\le n-1;\;S_p\ne n,\;\forall p\in\{2,3,...,n-1\};\;S_j-S_i\ne n,\;\forall i,j\in\{1,2,...,n-1,n\}$. Assume by contrary these conditions are satisfied simultaneously. Property P1: $S_p\ne n,\;\forall p\in\{2,3,...,n-1\};\;S_j-S_i\ne n,\;\forall i,j\in\{1,2,...,n-1,n\}\Longrightarrow \forall c\in\{1,2,...,n-1\}$, exist at most one value $i\in\{1,2,...,n-1\}$ such that $S_i\in\{c,n+c\}$. The numbers $c$, respectively $i$ can take each exactly $n-1$ distinct values. Results: $\forall c\in\{1,2,...,n-1\}$, exist exactly one value $i\in\{1,2,...,n-1\}$ such that $S_i\in\{c,n+c\}$. Equivalently, either $S_i=c$ or $S_i=n+c$. Property P2: $|S_j-S_i|\ge|j-i|;\;\forall i,j\in\{1,2,...,n\}$. WLOG, consider $i<j.\;S_j-S_i=a_{i+1}+a_{i+2}+...+a_j\ge j-i$. Property P3: $a_{n}\ge3$. Assuming $a_n\le 2$, results $a_1=1,\;a_2\le a_3\le....\le a_n\le2\Longrightarrow S_n\le 1+2(n-1)=2n-1<2n$, contradiction. $P3\Longrightarrow S_{n-1}=2n-a_n\le 2n-3\overset{\text{P1}}\Longrightarrow \exists i,j\in\{1,2,...,n-1\}$ such that $S_j=n-1;\;S_{i}=n-2\overset{\text{P2}}\Longrightarrow 1=S_j-S_i\ge j-i\Longrightarrow i=j-1.\;a_j=S_j-S_{j-1}=(n-1)-(n-2)=1\Longrightarrow a_k=1,\;\forall k\in\{1,2,...,j\}\Longrightarrow S_j=j\Longrightarrow j=n-1$. $S_{n-1}=n-1\Longrightarrow a_n=2n-S_{n-1}=n+1>n$, contradiction. Hence, the $\textbf{case 5}$ cannot occur and the proof is complete.
17.01.2024 13:47
Here is a very clean solution communicated to me by Rawlat_vanak: If the number of apples in each bag is equal (i.e. $2$), then the problem trivially follows since $n$ is even. Otherwise, we can reorder the bags in such a way that $a_1 \ne a_2$. Then, consider $a_1, a_2, a_1 + a_2, a_1 + a_2 + a_3, \cdots, a_1 + a_2 + \cdots + a_n = 2n$. By Pigeonhole, since there are $n + 1$ numbers, there must be two equal modulo $n$. Note that $a_1 \equiv a_2 \pmod{n}$ isn't possible, since we assumed $a_1 \ne a_2$, and thus the problem follows.