2013 IMO Shortlist C4

Let $n$ be a positive integer, and let $A$ be a subset of $\{1, \ldots, n\}$. An $A$-partition of $n$ into $k$ parts is a representation of $n$ as a sum $n=a_{1}+\cdots+a_{k}$, where the parts $a_{1}, \ldots, a_{k}$ belong to $A$ and are not necessarily distinct. The number of different parts in such a partition is the number of (distinct) elements in the set $\left\{a_{1}, a_{2}, \ldots, a_{k}\right\}$. We say that an $A$-partition of $n$ into $k$ parts is optimal if there is no $A$-partition of $n$ into $r$ parts with $r<k$. Prove that any optimal $A$-partition of $n$ contains at most $\sqrt[3]{6 n}$ different parts. (Germany)

令$n$ 为正整数，并令$A$ 为$\{1, \ldots, n\}$ 的子集。将 $n$ 划分为 $k$ 个部分的 $A$ 是将 $n$ 表示为 $n=a_{1}+\cdots+a_{k}$ 之和，其中 $a_{1}、\ldots、a_{k}$ 部分属于 $A$ 并且不一定不同。这种分区中不同部分的数量是集合 $\left\{a_{1}, a_{2}, \ldots, a_{k}\right\}$ 中(不同)元素的数量。如果不存在 $n$ 到 $r$ 部分且 $r<k$ 的 $A$ 分区，我们说 $n$ 到 $k$ 部分的 $A$ 分区是最优的。证明 $n$ 的任何最佳 $A$ 分区最多包含 $\sqrt[3]{6 n}$ 个不同部分。 (德国)