International Mathematical Olympiad Shortlisted Problems

If there are no $A$-partitions of $n$, the result is vacuously true. Otherwise, let $k_{\text{min}}$ be the minimum number of parts in an $A$-partition of $n$, and let $n=a_1+\cdots +a_{k_{\min }}$ be an optimal partition. Denote by $s$ the number of different parts in this partition, so we can write $S=\left\{a_1,\dots ,a_{k_{\text{min}}}\right\}=\left\{b_1,\dots ,b_s\right\}$ for some pairwise different numbers $b_1<\cdots <b_s$ in $A$. If $s>\sqrt[3]{6n}$, we will prove that there exist subsets $X$ and $Y$ of $S$ such that $|X|<|Y|$ and ${\sum }_{x\in X}x={\sum }_{y\in Y}y$. Then, deleting the elements of $Y$ from our partition and adding the elements of $X$ to it, we obtain an $A$-partition of $n$ into less than $k_{\text{min}}$ parts, which is the desired contradiction. For each positive integer $k⩽s$, we consider the $k$-element subset $$S_{1,0}^k:=\left\{b_1,\dots ,b_k\right\}$$ as well as the following $k$-element subsets $S_{i,j}^k$ of $S$ : $$S_{i,j}^k:=\left\{b_1,\dots ,b_{k-i},b_{k-i+j+1},b_{s-i+2},\dots ,b_s\right\},i=1,\dots ,k,j=1,\dots ,s-k$$ Pictorially, if we represent the elements of $S$ by a sequence of dots in increasing order, and represent a subset of $S$ by shading in the appropriate dots, we have: Denote by ${\Sigma }_{i,j}^k$ the sum of elements in $S_{i,j}^k$. Clearly, ${\Sigma }_{1,0}^k$ is the minimum sum of a $k$-element subset of $S$. Next, for all appropriate indices $i$ and $j$ we have $${\Sigma }_{i,j}^k={\Sigma }_{i,j+1}^k+b_{k-i+j+1}-b_{k-i+j+2}<{\Sigma }_{i,j+1}^k\text{ and }{\Sigma }_{i,s-k}^k={\Sigma }_{i+1,1}^k+b_{k-i}-b_{k-i+1}<{\Sigma }_{i+1,1}^k.$$ Therefore $$1⩽{\Sigma }_{1,0}^k<{\Sigma }_{1,1}^k<{\Sigma }_{1,2}^k<\cdots <{\Sigma }_{1,s-k}^k<{\Sigma }_{2,1}^k<\cdots <{\Sigma }_{2,s-k}^k<{\Sigma }_{3,1}^k<\cdots <{\Sigma }_{k,s-k}^k⩽n.$$ To see this in the picture, we start with the $k$ leftmost points marked. At each step, we look for the rightmost point which can move to the right, and move it one unit to the right. We continue until the $k$ rightmost points are marked. As we do this, the corresponding sums clearly increase. For each $k$ we have found $k(s-k)+1$ different integers of the form ${\sum }_{i,j}^k$ between 1 and $n$. As we vary $k$, the total number of integers we are considering is $$\sum _{k=1}^s(k(s-k)+1)=s\cdot \frac{s(s+1)}{2}-\frac{s(s+1)(2s+1)}{6}+s=\frac{s\left(s^2+5\right)}{6}>\frac{s^3}{6}>n.$$ Since they are between 1 and $n$, at least two of these integers are equal. Consequently, there exist $1⩽k<k^{\prime }⩽s$ and $X=S_{i,j}^k$ as well as $Y=S_{i^{\prime },j^{\prime }}^{k^{\prime }}$ such that $$\sum _{x\in X}x=\sum _{y\in Y}y,\text{ but }|X|=k<k^{\prime }=|Y|$$ as required. The result follows.

---

Alternative solution.

Assume, to the contrary, that the statement is false, and choose the minimum number $n$ for which it fails. So there exists a set $A\subseteq \{1,\dots ,n\}$ together with an optimal $A$ partition $n=a_1+\cdots +a_{k_{\text{min}}}$ of $n$ refuting our statement, where, of course, $k_{\text{min}}$ is the minimum number of parts in an $A$-partition of $n$. Again, we define $S=\left\{a_1,\dots ,a_{k_{\text{min}}}\right\}=\left\{b_1,\dots ,b_s\right\}$ with $b_1<\cdots <b_s$; by our assumption we have $s>\sqrt[3]{6n}>1$. Without loss of generality we assume that $a_{k_{\min }}=b_s$. Let us distinguish two cases.

Case 1. $b_s⩾\frac{s(s-1)}{2}+1$. Consider the partition $n-b_s=a_1+\cdots +a_{k_{\text{min}}-1}$, which is clearly a minimum $A$-partition of $n-b_s$ with at least $s-1⩾1$ different parts. Now, from $n<\frac{s^3}{6}$ we obtain $$n-b_s⩽n-\frac{s(s-1)}{2}-1<\frac{s^3}{6}-\frac{s(s-1)}{2}-1<\frac{(s-1{)}^3}{6}$$ so $s-1>\sqrt[3]{6\left(n-b_s\right)}$, which contradicts the choice of $n$.

Case 2. $b_s⩽\frac{s(s-1)}{2}$. Set $b_0=0,{\Sigma }_{0,0}=0$, and ${\Sigma }_{i,j}=b_1+\cdots +b_{i-1}+b_j$ for $1⩽i⩽j<s$. There are $\frac{s(s-1)}{2}+1>b_s$ such sums; so at least two of them, say ${\Sigma }_{i,j}$ and ${\Sigma }_{i^{\prime },j^{\prime }}$, are congruent modulo $b_s$ (where $(i,j)\ne \left(i^{\prime },j^{\prime }\right)$ ). This means that ${\Sigma }_{i,j}-{\Sigma }_{i^{\prime },j^{\prime }}=r{b}_s$ for some integer $r$. Notice that for $i⩽j<k<s$ we have $$0<{\Sigma }_{i,k}-{\Sigma }_{i,j}=b_k-b_j<b_s,$$ so the indices $i$ and $i^{\prime }$ are distinct, and we may assume that $i>i^{\prime }$. Next, we observe that ${\Sigma }_{i,j}-{\Sigma }_{i^{\prime },j^{\prime }}=\left(b_{i^{\prime }}-b_{j^{\prime }}\right)+b_j+b_{i^{\prime }+1}+\cdots +b_{i-1}$ and $b_{i^{\prime }}⩽b_{j^{\prime }}$ imply $$-b_s<-b_{j^{\prime }}<{\Sigma }_{i,j}-{\Sigma }_{i^{\prime },j^{\prime }}<\left(i-i^{\prime }\right)b_s$$ so $0⩽r⩽i-i^{\prime }-1$. Thus, we may remove the $i$ terms of ${\Sigma }_{i,j}$ in our $A$-partition, and replace them by the $i^{\prime }$ terms of ${\Sigma }_{i^{\prime },j^{\prime }}$ and $r$ terms equal to $b_s$, for a total of $r+i^{\prime }<i$ terms. The result is an $A$-partition of $n$ into a smaller number of parts, a contradiction.