Assume that there are $x$ different parts, $a_{1},a_{2},...,a_{x}$ It's easy to know that if $T$ and $T'$ are different subsets of$ \{1,2,...,x\}$ and $\sum_{i\in T} a_{i}=\sum_{i\in T'} a_{i}$, then $|T|=|T'|$, or else it's a contradiction, since this partition is optimal. Suppose that $ b_{k}=\#\{\sum_{i\in T} a_{i}| |T|=k,T\subseteq {1,2,...,x}\}(k=1,2,...,x)$, and $b=\#\{\sum_{i\in T} a_{i}| T\subseteq {1,2,...,x}\}$ Then $b=b_{1}+...+b_{x}$, and $b \leq n$. Now, it's easy to show that $b_{k} \geq k(x-k)+1=-k^{2}+xk+1$ So $n \geq b = \sum_{k=1}^{x} (-k^{2}+xk+1)=\frac{-x(x+1)(2x+1)}{6}+\frac{x^{2}(x+1)}{2}+x=\frac{1}{6}x^{3}+\frac{5}{6}x>\frac{1}{6}x^{3}$. Hence $ x<\sqrt[3]{6n}$

Solution found with pi37: Let $c_1, c_2, ..., c_j$ be the distinct elements of $a_1, a_2, ..., a_k$ with $c_1 < c_2 < \cdots < c_j$. Let $c_i$ show up $b_i$ times. Therefore, \[n= a_1 + a_2 + \cdots + a_k = b_1c_1 + b_2c_2 + \cdots + b_jc_j\] We want to show that $j^3 \le 6n$. Therefore, we want $b_1c_1 + \cdots + b_jc_j \ge \frac{j^3}{6}$ given that $\{ a_1, a_2, ... a_k \}$ is optimal i.e. $b_1 + b_2 + \cdots + b_j$ is as small as possible. Suppose there are subsets $S$ and $T$ of $\{ c_1, c_2, ..., c_j \}$ such that $|S| < |T|$ and $\sum_{x \in S} x = \sum_{y \in T} y$. This would contradict the minimality of $b_1 + b_2 + \cdots + b_j$, because $b_1c_1 + \cdots + b_jc_j - \sum_{y \in T} y + \sum_{x \in S} x$ clearly keeps the sum constant while decreasing the quantity $b_1 + b_2 + \cdots + b_j$. Therefore, we know that if we have two different-sized subsets of $\{ c_1, c_2, ..., c_j \}$, then they have distinct sums. We will now show that $c_1 + c_2 + \cdots + c_j \ge \frac{j^3}{6}$ because this will directly imply $b_1c_1 + \cdots + b_jc_j \ge \frac{j^3}{6}$. It suffices to show that we can choose at least $\frac{j^3}{6}$ subsets of $\{ c_1, c_2, ..., c_j \}$ such that the sum of all of them are distinct (since $c_1 + \cdots + c_j$ will have the largest sum). For convenience, let $[x_1, x_2, ...] = c_{x_1} + c_{x_2} + \cdots$. Recalling that $c_1 < c_2 < \cdots < c_j$, we can take the following sums: \[[1] \qquad [2] \qquad [3] \qquad \cdots \qquad [j] \\ \ [1, 2] \qquad [1, 3] \qquad [1, 4] \qquad \cdots \qquad [1, j] \\ \ [2, j] \qquad [3, j] \qquad [4, j] \cdots [j-1, j] \\ \] For sums of size $3$ we take \[[1, 2, 3]; [1, 2, 4]; \cdots [1, 2, j]; [1, 3, j]; [1, 4, j]; \\ \cdots [1, j-1, j]; [2, j-1, j]; [3, j-1, j]; \cdots [j-2, j-1, j]\]. Then, we do the exact same thing for $4$ sums and get $[1, 2, 3, 4]; [1, 2, 3, 5];...[1, 2, 3, j]$ and so on, mimicking the three-element sum but when we reach $[1, j-2, j-1, j]$, we then keep going to $[2, j-2, j-1, j]; [3, j-2, j-1, j]; \cdots [j-3, j-2, j-1, j]$. And we just keep going on like this recursively. We just have to count these up now. Let $z_i$ be the number of sums with $i$ terms there are. Then, we have $z_1 = j$, $z_2 = 2j-3$ and $z_3 =2(j-1) - 3 + j-3 = 3j - 8$. $z_4 = 3(j-1) - 8 + j - 4 = 4j - 15$. Basically to get $z_i$ you plug in $j-1$ into the $z_{i-1}$ then add $j-i$ (this can be verified easily). It can be proven with induction that $z_i = ij - i^2 + 1$. Therefore, \[z_1 + z_2 + \cdots + z_j = j \cdot \frac{j(j+1)}{2} - \frac{j(j+1)(2j+1)}{6} + j = \frac{j^3 + 5j}{6} > \frac{j^3}{6}\] This therefore tells us that $b_1c_1 + \cdots + b_jc_j \ge c_1 + c_2 + \cdots + c_j > \frac{j^3}{6}$, as desired. 600th post!

We will prove the result by strong induction on $n.$ The base case $n = 1$ is trivial. Now suppose the result true for $1, 2, \cdots, n - 1$, and we'll prove it true for $n \ge 2.$ To do so, we use strong induction on $|A|.$ The base case $|A| = 1$ is trivial. Now, suppose the result true for $|A| = 1, 2, \cdots, k - 1$, and we'll prove it true for $k \ge 2.$ Let $A = \{x_1 < x_2 < \cdots < x_k\}$ and consider an optimal $A$-partition $\pi$ of $n.$ Suppose that $\pi$ does not use $x_i.$ Then if $B = A \setminus \{x_i\}$, clearly $\pi$ is an optimal $B$-partition of $n.$ Since $|B| < |A|$, the result now follows by the inductive hypothesis. Henceforth, assume that $\pi$ uses each of the $x_i$'s. Note that $s \equiv x_1 + x_2 + \cdots + x_k$ appears in $\pi.$ Therefore, $x_1 + x_2 + \cdots + x_k$ must be an optimal $A$-partition of $s$, for if there were an $A$-partition $\sigma$ of $s$ with fewer parts, then we could replace $s$ with $\sigma$ in $\pi$, thus yielding an $A$-partition of $n$ with fewer parts than $\pi$, impossible. Now, if $s < n$, then since $x_1 + x_2 + \cdots + x_k$ is an optimal $A$-partition of $s$, the inductive hypothesis yields $k \le \sqrt[3]{6s} < \sqrt[3]{6n}$, as desired. Henceforth, assume that $s = n.$ Thus, every subset of $S$ appears in $\pi.$ Therefore, if $X, Y \subseteq S$ with $|X| < |Y|$, we can replace $Y$ with $X$ in $\pi$, yielding an $A$-partition of $n$ with fewer parts than $\pi$, impossible. Therefore, any two subsets of $S$ with distinct sizes have distinct sums. Now, fix some $1 \le m \le k$ and consider forming subsets of $S$ of size $m$ as follows: Start with $S_m = \{x_1, x_2, \cdots, x_m\}.$ Then iteratively increase the largest element of $S_m$ not equal to $x_k$ by $1.$ This process terminates when we arrive at the subset $\{x_{k - m + 1}, \cdots , x_k\}.$ It is clear that the sum of each subset formed in this way is $1$ more than the sum of the previous subset. Moreover, it is easy to calculate that precisely $1 + m(k - m)$ subsets are formed in this way. Summing over all $m$, we create $\sum_{m = 1}^k \left[1 + m(k - m)\right] = \frac{k^3 + 5}{6}$ subsets in this manner. Each subset has a distinct sum, and each sum does not exceed $s = n.$ Therefore, \begin{align*} n \ge \frac{k^3 + 5}{6} > \frac{k^3}{6} \implies \sqrt[3]{6n} > k. \quad \square \end{align*}

Easily killed by this Link : 19993 ISL C2

Suppose the distinct elements of the optimal $A$-partition are $a_1<a_2<\cdots<a_m$. Note that any two subsets of $\{a_1,a_2,\ldots,a_m\}$ of different sizes cannot have the same sum, as otherwise we may replace the larger sized subset in the partition with the smaller sized subset to obtain an $A$-partition with smaller parts. But note that we may produce at least $nk-k^2+1$ subsets of $\{a_1,a_2,\ldots,a_m\}$ of size $k$ with distinct sums by the following process: Start with $a_1+a_2+\cdots+a_k$, and at each step replace $a_i$ with $a_{i+1}$, where $i$ is the largest index for which $a_{i+1}$ is not a term in our sum. Indeed, at each step we strictly increase the sum and increment the sum of the indices by 1, and we increment $k(n-k)+1$ times because we start with the index sum $1+2+\cdots+k$ and end with the sum $(n-k+1)+(n-k+2)+\cdots+n$. Thus, at the end we must have at least $\sum_{k=1}^mnk-k^2+1=\frac{m^3+5m}6$ distinct sums of subsets. As these sums must all be at most $n$, it follows that $\frac{m^3+5m}6\le n\implies m\le\sqrt[3]{6n}$.

lyukhson wrote: Let $n$ be a positive integer, and let $A$ be a subset of $\{ 1,\cdots ,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 , \cdots , 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 $\{ a_1 , a_2 , \cdots , a_k \} $. 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]{6n}$ different parts. We first prove the following lemma. Lemma. [ISL 1993 C2] Let $X$ be a $k$-element subset of $I=\{x_1, \dots, x_n\}$ for some $k \le n$. Let $S$ be the set of all values taken by $\sum_{x \in X} x$ as $X$ varies over all $k$-subsets of $I$. Then $|S| \ge k(n-k)+1$. (Proof) WLOG $x_1<\dots<x_n$. Now consider the family of sets $$\mathcal{F}=\{ \{1,2, \dots, k\}, \{1,2, \dots, k-1, k+1\}, \dots, \{1,2, \dots, k-1, n\}, \{1,2, \dots, k-2, k, n\}, \dots, \{1,2, \dots, k-2, n-1, n \} \dots, \{n-k+1, \dots, n-1, n\}\}$$then $|\mathcal{F}|=k(n-k)+1$. Now for all $J \in \mathcal{F}$ consider the set $\{x_j \, | \, j \, \in J\}$. All these sets have a different sum hence $|S| \ge |\mathcal{F}|$ and we're done. $\blacksquare$ Let $\{a_1, a_2, \dots, a_k\} \subset A$ be parts of an optimal $A$-partition of $n$. Thus, we can write $$n=a_1b_1+a_2b_2+\dots+a_kb_k$$where $b_1, \dots, b_k \ge 1$ are integers. WLOG assume $b_1+\dots+b_k$ is minimum. Pick any subset $T$ of $\{1,2, \dots, k\}$. Then $\sum_{x \in T} a_x \le n$ and for any other subset $S$ of $[k]$; we conclude that if $\sum_{s \in S} a_s=\sum_{t \in T} a_t$ then $|S|=|T|$. Indeed we see that both these sums occur in the $A$-partition of $n$ and so if either has lesser cardinality, we could've replaced the other by it; decreasing $b_1+\dots+b_k$ in the process. So let $f(s)$ denote the number of distinct values taken by sums of elements of $s$-element subsets of $\{a_1, \dots, a_k\}$ for all $s \le k$. By the lemma we know $f(s) \ge s(k-s)+1$. However $\sum^k_{s=1} f(s) \le n$ as subsets of distinct sizes yield distinct sums and all of these are less than $n$. Therefore, $$k\left(\frac{k(k+1)}{2}\right)-\frac{k(k+1)(2k+1)}{6}+k \le n \implies \frac{k^3}{6}<\frac{k^3+5k}{6} \le n$$proving $k \le \sqrt[3]{6n}$ as desired. $\blacksquare$ Remark. I think making the claim about the lemma is the hardest part if one hasn't seen it before (proving the lemma and the problem thereafter is quite feasible). The way I proved it initially was to discover the bound inductively. We fix $k$ and induct on $n \ge k$ to show that $|S| \ge f(n,k)$. For $n=k$ we get $f(n,k) \ge 1$ and $n=k+1$ we get $f(n,k) \ge k+1$. Now for $n \mapsto n+1$; WLOG, say the newly added element is the smallest. Ignore it for now and pick $f(n-1, k)$ subsets by IH. Now among these; pick the one with least possible sum. Exclude any one element from it and include the new one. Thus, we obtain $f(n, k) \ge f(n-1, k)+k$. Now we know where the unusual $k(n-k)+1$ came from; and even have an algorithm to pick it! It was useful to apply the heuristic that "sets with obviously different sums must be because of size reasons".

Can someone check this for me? I got a stronger result than $\sqrt[3]{6n}$, and I'm not sure... Suppose that $n=n_1a_1+n_2a_2+\dots+n_ma_m$, where $a_1,\dots ,a_m$ are the different parts of the partition. $(\{a_1,\dots ,a_n\}$ is optimal.$)$ We will prove that there are no two distinct subsets of $ \{1,2,...,m\}$ $(S=\{i_1,\dots ,i_k\}$ and $T=\{j_1,\dots ,j_l\})$ such that $\sum_{x=1}^k a_{i_{x}}=\sum_{y=1}^{l} a_{j_{y}}$. Assume the contrary and WLOG $S=\{1,2,\dots , k\}, T=\{k+1,\dots ,k+l\}$ and $n_1=\min_{1\le x\le k} (n_x)$ for convenience. Then we have $$n=n_1a_1+n_2a_2+\dots +n_ma_m=(n_2-n_1)a_2+\dots +(n_k-n_1)a_k+(n_{k+1}+n_1)a_{k+1}+\dots +(n_{k+l}+n_1)a_{k+l}+n_{k+l+1}a_{k+l+1}+\dots +n_ma_m$$which contradicts the fact that the partition is optimal. Hence the sum of the elements of all non-empty subsets of $\{a_1,\dots,a_m \}$ are pairwise distinct. Note that $a_1+\dots +a_m\le n_1a_1+\dots +n_ma_m=n$, so $2^m-1\le n \Longrightarrow m\le log_2(n+1)$ @below Sorry, I misread the definition of optimal partitions

MNJ2357 wrote: $$n=n_1a_1+n_2a_2+\dots +n_ma_m=(n_2-n_1)a_2+\dots +(n_k-a_1)a_k+(n_{k+1}+a_1)a_{k+1}+\dots +(n_{k+l}+a_1)a_{k+l}+n_{k+l+1}a_{k+l+1}+\dots +n_ma_m$$ How do you ensure the newly obtained linear combination of $a_2,...,a_m$ has less (not necessarily distinct) parts than before? You increase the number of parts by $la_1-kn_1$, why is this always negative?

Solved with william122. Let $\sigma(S)$ denote the sum of the elements of $S$. Say a subset $A$ is $n$-antidisuninasuboptimal if there is an optimal $A$-partition of $n$ into $|A|$ parts; that is, all elements of $A$ are used in the optimal $A$-partition. Claim: Let $A$ be an $n$-antidisuninasuboptimal set. For any subsets $C$, $D$ of $A$, if $\sigma(C)=\sigma(D)$, then $|C|=|D|$. Proof. Assume $|C|>|D|$ but $\sigma(C)=\sigma(D)$. Each element of $C$ appears in the optimal $A$-partition, so we may repeatedly remove one instance of each element of $C$ and add an instance of each element of $D$. Eventually the number of parts decreases, and $A$ is not antidisuninasuboptimal. $\blacksquare$ Claim: For each $0<i\le k$, there are at least $ik-i^2+1$ distinct values of $\sigma(T)$ among $T\subseteq A$ with $|T|=i$. Proof. Let $A=\{a_1,a_2,\ldots,a_k\}$, with $a_1<a_2<\cdots<a_k$. Start with the subset $T=\{a_1,\ldots,a_i\}$; then repeatedly apply the following process: choose an index $t$ such that $a_t\in T$ but $a_{t+1}\notin T$, and replace $a_t$ with $a_{t+1}$, thereby increasing the sum of the elements of $T$. The process terminates when $T=\{a_{k-i+1},\ldots,a_k\}$, and we apply the process $i(k-i)$ times. $\blacksquare$ For $n$-antidisuninasuboptimal sets $A$, we may compute \[n\ge\sigma(A)\ge\left\lvert\{\sigma(T):\varnothing\ne T\subseteq A\}\right\rvert=\sum_{i=1}^k\left(ik-i^2+1\right)=\frac{k^3}6+\frac{5k}6>\frac{k^3}6,\]and we are done.

Posting for storage. Solved with eisirrational, goodbear, and nukelauncher. Let $\sum S$ denote the sum of the elements of the set $S$. Let $A = \{x_1, x_2, \dots, x_m\}$ be sorted and pick any optimal $A$-partition of $n$. Without loss of generality this partition covers all elements of $A$; thus, we wish to show $n \geq m^3/6$. To do this, we prove a few structural claims regarding $A$. Claim 1. We cannot have two subsets $S, T \subseteq A$ for which $|S| = |T|$ and $\sum S = \sum T$. Proof. Suppose we can pick such $S$ and $T$, and say $|S| < |T|$. Then within the optimal $A$-partition of $n$, replace a copy of $\sum T$ with the sum $\sum S$, which strictly decreases the number of parts as desired. $\square$ Claim 2 (1993 C2). For any set $A$, there are at least $q(m-q)+1$ distinct values of $\sum S$ given $|S| = q$. Proof.Begin with the set $S = \{x_1, x_2, \dots, x_q\}$ and perform the following operation repeatedly: take the largest $i$ for which $x_i \in S$ but $x_{i+1} \not\in S$, and replace $x_i$ in $S$ with $x_{i+1}$. This strictly increases $\sum S$. This process terminates at the set $\{x_{m-q+1}, x_{m-q+2}, \dots, x_{m}\}$, and each operation increases the sum of the indices by $1$. So along the way we make \[( (m-q+1) + \dots + m) - (1+\dots q) + 1 = q(m-q)+1\]subsets along the way, each with a different total sum. $\square$ To finish, consider the union of the $q(n-q)+1$ sets generated in Claim 2 for $q=1,2,\dots,m$. Then each of these sets has distinct total sum, implying the largest sum \[x_1+x_2+\dots+x_m \quad \text{is at least}\quad \sum_{q=1}^m q(m-q)+1 = \binom{m+1}{3} + m \geq m^3/6.\]This total sum is at most $n$, as desired.

Suppose $e_1a_1+...+e_ka_k=n$ is an optimal $A$-partition of $n$,where $a_1<a_2<...<a_k$ we show that $k^3\leq 6n$. Consider the set $$S=\{b_1a_1+...+b_ka_k: 0\leq b_i\leq 1\}$$and $$S_j=\{b_1a_1+...+b_ka_k: 0\leq b_i\leq 1: b_1+...+b_k=j\}$$Claim. (i) For each $j_1,j_2$ we have $S_{j_1}\cap S_{j_2}=\emptyset$ (ii) $|S|\geq \frac{k^3}{6}+1$ Proof. (i) WLOG assume $j_1<j_2$ and $$\sum_{i=1}^nc_ia_i=\sum_{i=1}^n d_ia_i$$where $\sum c_i= j_1$ and $\sum d_i=j_2$, then $$\sum_{i=1}^n (e_i-d_i+c_i) a_i=\sum_{i=1}e_ia_i=n$$but this partition has $j_2-j_1+\sum e_i$ different parts, contradicting the fact that the partition is optimal. (ii) From (i) we have $$|S|=\sum_{i=0}^k|S_j|$$Obviously $|S_j|=|S_{k-j}|$. We first show that $|S_j|\geq ik-i^2+1$ for all $2i\geq k$ by induction. The base case is obvious. Suppose the case $j$ holds, then by inductive hypothesis, the set $$T=\{b_2a_2+...+b_ka_k: 0\leq b_i\leq 1: b_1+...+b_k=j\}$$has at least $j(k-1)-j^2+1$ elements, and for all $b_2a_2+...+b_ka_k\in T$, it corresponds to $$a_1+b_2a_2+...+b_ka_k\in S_{j+1}$$meanwhile, they are all smaller than $$a_m+a_{k-j+1}+...+a_k\in S_{j+1}$$where $2\leq m\leq k-j$, as a result, $$|S_{j+1}|\geq |T|+k-j-1=(j+1)k-(j+1)^2+1$$as desired. Therefore, if $k=2m$, we have $$|S|\geq m^2+1+2\sum_{i=0}^{m-1}ik-i^2+1=\frac{m(4m^2+5)}{3}+1\geq \frac{k^3}{6}+1$$and if $k=2m+1$ we have $$|S|\geq 2\sum_{i=0}^m ik-i^2+1=\frac{(k+1)(k^2-k+6)}{6}\geq \frac{k^3}{6}+1$$as desired. $\blacksquare$ Now obviously $S\subset\{0,...,n\}$ hence $k^3\leq 6n$ as desired.

Consider an optimal partition such that the element $a_{i}$ is used $b_{i}$ times, and that this partition contains $t$ different parts. WLOG, assume that each element in $A$ is part of this partition. We will show that $t \leq n$. We will first prove the following lemma: Lemma: Consider the set of integers that are the sum of $r$ elements from $a_{1}, a_{2}, \ldots a_{t}$. I claim that this set has size at least $rt - (r+1)(r-1)$. Proof: We can show this by induction on $t$. Our base case is $t = r$, in which case there is exactly one element in the set: $a_{1} + a_{2} + \ldots + a_{r}$. We also have $1 = r^{2} - (r+1)(r-1)$, so this completes our base case. Now, assume that there are at least $rt - (r+1)(r-1)$ distinct sums for $a_{1}, a_{2}, \ldots a_{t}$. Now, if we consider $a_{t+1}$, such that $a_{t+1}$ is greater than $a_{1}, a_{2}, \ldots a_{t}$, we have \[-a_{j} + \sum_{i=t+1-r}^{t+1} a_{i} > a_{t-r+1} + \ldots + a_{t}\]for $t+1-r \leq j \leq t$. Since we have $r$ choices for $j$, which will all result in distinct sums greater than the maximal sum for $t$, we get that for $t+1$, there are at least $rt + t - (r+1)(r-1) = r(t+1) - (r+1)(r-1)$ distinct sums. This proves our induction. Now, in the optimal partition, if there were two sums, $M, N$, such that $M$ is the sum of $m$ distinct elements in $A$ and $N$ is the sum of $n$ distinct elements, where $m < n$, since every element is used in our partition, this means the elements that make up $N$ are also in our partition. We can now replace the elements that make up $N$ in the partition with the elements that make up $M$, which results in a partition with smaller size. This contradicts optimal, which means this can never happen. Now, since for each $r$ there are $rt - (r+1)(r-1)$ distinct sums, between $1$ and $n$, and we can not have a sum with $r$ elements the same as a sum with $s\neq r$ elements, this means that \[n \geq \sum_{r=1}^{t} rt - (r+1)(r-1) = \sum_{r=1}^{t}rt - r^{2} + 1 = \frac{t^{2}(t+1)}{2} + t - \frac{t(t+1)(2t+1)}{6}\]\[\Longleftrightarrow n \geq \frac{t(t^{2} + 5)}{6} \Rightarrow t \leq \sqrt[3]{6n}\]This completes the proof.

Suppose we have an optimal partition \[ n = e_1 \cdot a_1 + \dots + e_m \cdot a_m. \]In order for this to be optimal, it follows that for any subsets $I$ and $J$ of the index set $\{1, \dots, m\}$ if $|I| \neq |J|$ then $\sum_{i \in I} a_i \neq \sum_{j \in J} a_j$. Otherwise, we could replace one sum with the other in our optimal partition and get one with fewer total parts. This will be enough. Claim: There are at least $k(m-k)+1$ possible values of $\sum_{i \in I} a_i$ across index sets $I \subseteq \{1, \dots, m\}$ of cardinality $k$. Proof. Sort $a_1 < \dots < a_m$. Start with \begin{align*} a_1 + \dots + a_k &< a_1 + \dots + a_{k-1} + a_{k+1} \\ &< a_1 + \dots + a_{k-1} + a_{k+2} \\ &< \cdots \\ &< a_1 + \dots + a_{k-1} + a_{n} \end{align*}which one can visualize as ``moving $a_k$ to $a_n$''. Then move $a_{k-1}$ to $a_{n-1}$, and so on. $\blacksquare$ Vary $k$. The sums we get must all be different between layers, and bounded by $n$. So we have \begin{align*} n+1 &\ge \sum_{k=0}^m [k(m-k)+1] \\ &= m \cdot \frac{m(m+1)}{2} - \frac{m(m+1)(2m+1)}{6} + m \\ &= \frac{m(m+1)}{2} \cdot \frac{m-1}{3} + m \\ &= \frac{m(m^2-1)}{6} + m \ge \frac{m^3}{6} + 1 \end{align*}so $m \le \sqrt[3]{6n}$.

Do not ask how long I spent being confused about this problem until I realized that "different parts" and "parts" do not mean the same thing. Consider an optimal partition $$b_1a_1+\cdots+b_ka_k=n$$where $a_1<\cdots<a_k$ and $b_1,\ldots,b_k>0$, which has $k$ different parts and $b_1+\cdots+b_k$ parts (!!!!!!). For a set $S \subseteq \{1,\ldots,k\}$, define $s(S)=\sum_{i \in S} a_i$. Due to optimality, there cannot exist $A,B \subseteq \{1,\ldots,k\}$ with $|A|>|B|$ and $s(A)=s(B)$. Otherwise, we could subtract one from $b_i$ for all $i \in A$ and add one to $b_i$ for all $i \in B$, which strictly decreases the number of parts while keeping the sum constant. The key claim is now the following: Claim: If $A \subseteq \{1,\ldots,k\}$ and $|A|=c$, then there are at least $c(k-c)+1$ values for $s(A)$. Proof: We replicate the proof of $|A+B| \geq |A|+|B|-1$. Since $a_1<\cdots<a_k$, we consider the following values for $A$, which all yield distinct (increasing) $s(A)$: \begin{align*} &\{1,\ldots,c-1,c\},\{1,\ldots,c-1,c+1\},\ldots,\{1,\cdots,c-1,k\}\\ &\{1,\ldots,c-2,c,k\},\{1,\ldots,c-2,c+1,k\},\ldots,\{1,\ldots,c-2,k-1,k\}\\ &\vdots\\ &\{1,k-c+2,\ldots,k\},\{2,k-c+2,\ldots,k\},\ldots,\{k-c+1,\ldots,k\}. \end{align*}The first row contains $k-c+1$ terms, and the other $c-1$ rows each contain $k-c$ terms, yielding the desired result. Because the values of $s(\bullet)$ should be different for differently sized sets, it follows that we should have at least $$\sum_{i=1}^{k} (i(k-i)+1)=k+\sum_{i=1}^k (ki-i^2)=k+\frac{k^2(k+1)}{2}-\frac{k(k+1)(2k+1)}{6}=\frac{k^3}{6}+\frac{5k}{6}>\frac{k^3}{6}$$different values of $s(A)$ across all $A \subseteq \{1,\ldots,k\}$. On the other hand, since $s(A) \leq s(\{1,\ldots,k\}) \leq n$ for all such $A$, there are $n$ possible values for $s(A)$. Hence $k^3/6 \leq n \implies k \leq \sqrt[3]{6n}$, as desired. $\blacksquare$

Solved with v4913. Suppose that $n=e_1a_1+\cdots+e_ma_m$ is an optimal partition of $n$, where $a_1<\cdots<a_m$. It suffices to prove that $n>\tfrac{m^3}{6}$. We make the following reduction. Claim: Let $X=\{x_1,\ldots,x_r\}$ and $Y=\{y_1,\ldots,y_s\}$ be subsets of $\{a_1,\ldots,a_m\}$ with $r \ne s$. Then, $x_1+\cdots+x_r \ne y_1+\cdots+y_s$. Proof: If not, assume WLOG that $r>s$. Then, we have \[n=e_1a_1+\cdots+e_ma_m-x_1-\cdots-x_r+y_1+\cdots+y_s.\]This partition has less parts, contradicting optimality. We construct tiers of sets in the following way: for $x=1,\ldots,m$, tier $x$ contains all sets \[S_{x,y,z}=\{a_1,\ldots,a_{x-y-1},a_z,a_{m-y+1},\ldots,a_m\}\]over all integers $y$ and $z$ with $0 \le y \le x-1$ and $x-y \le z \le m-y$. (Notice that some of these sets are counted twice.) By our claim, no two sets from different tiers can have elements with equal sum, and since $a_1<\cdots<a_m$, no two sets from the same tier can have elements with equal sum. It's easy to see that there are $xm-x^2+1$ sets in tier $x$, so we have \[\sum_{x=1}^m xm-x^2+1=\frac{m(m+1)}{2} \cdot m-\frac{2m^3-3m^2+m}{6}+m=\frac{m^3+5m}{6}\]sets. Thus, the set where the sum of the elements is largest, namely $S_{m,0,m}=\{a_1,\ldots,a_m\}$, must have sum at least $\tfrac{m^3+5m}{6}$. However, since $n \ge a_1+\cdots+a_m$, we have $n \ge \tfrac{m^3+5m}{6}>\tfrac{m^3}{6}$, so we are done.

Let the optimal $A$-partition have elements $\{a_1,a_2,\dots, a_k\}$ with $a_1<a_2<\dots < a_k$. For each $r\le k$, the sum of all distinct parts, $a_{i_1}+a_{i_2}+\dots + a_{i_r}$, can take on at least $r(k-r)+1$ different values. To get the first $r+1$ of those values, take $a_1+a_2+\dots + a_r$ and increase $a_r$'s index by $1$, then $a_{r-1}$'s index, and so on until we have $a_2+a_3+\dots + a_{r+1}$. Repeat this process to get $r(k-r)+1$ different sums. Suppose for some $r<s$ we have \[a_{i_1}+a_{i_2}+\dots + a_{i_r}=a_{i_1}+a_{i_2}+\dots + a_{i_s}\]then we can replace $a_{i_1}+a_{i_2}+\dots + a_{i_s}$ in the optimal partition with less parts, contradiction. Thus, for each $r\le k$, the $r(k-r)+1$ different sums are different. However, these sums can only take on the values $1,2,\dots,n$. Thus, \[\sum_{r=1}^{k}{r(k-r)+1}\le n\]which implies the result.

Redacted (fakesolve)

Consider an optimal partition $e_1a_1+\ldots+e_ka_k=n$, where $a_1<\dots<a_k$. By optimality, for each ordered pair $(S, T) \in [k]^2$ with $|S|<|T|$, $\small\sum_{s \in S} a_s \neq \small\sum_{t \in T} a_t$. Claim: For any $A \subseteq [k]$, the number of distinct possible values of $\sum_{i \in A} a_i$ is at least $1+|A|(k-|A|)$. Proof. The idea is that we can smooth the sum $a_1+\dots+a_{|A|}$ into $\small\sum_{i \in A} a_i$ for any subset $A$ by a sequence of index shifts. We can do this by shifting the largest index to match $\max A$, and then shift the second largest index to the second largest element of $A$, and so on, and in each shift the sum increases. These shifts induce $1+|A|(k-|A|)$ sums, as required. Now we look at each $|A| \in [0, k]$ and apply the claim to obtain the number of distinct possible values of $\small\sum_{i \in A} a_i$ over all subsets $A \in [k]$ is at least \[ \sum_{i=0}^k 1+i(k-i) = k + \tbinom{k+1}{3} = \tfrac{k^3+5k}{6} > \frac{k^3}{6}. \]Since $\small\sum_{i \in A} a_i$ is at most $n$, the number of possible values of the sum is at most $n+1$ (as $A$ can possibly be the empty set), and therefore we have $k^3/6 \le n+1$, or $k \le \sqrt[3]{6n}$, and we are done.

Consider a subset $\{a_1, a_2, \ldots, a_m\}$ of $\{1, 2, \ldots, n\}$. Suppose that this is an optimal partition. We need to show that $m\leq\sqrt[3]{6n}$. Suppose the partition of $n$ is as follows: \[c_1a_1+c_2a_2+\cdots+c_ma_m=n\]We have $c_i\geq1$. Note that since this partition is optimal, it means \[\text{sum of some }x\text{ distinct }a_i\text{'s}=\text{sum of some }y\text{ distinct }a_i\text{'s}\]is possible only if $x=y$, else if $x>y$ then we can simply replace the LHS sum with RHS sum and get a better summation with lesser parts, which contradicts minimality of $c_1+c_2+\cdots+c_m$. We now prove a lemma. Lemma: For any set $A$ of $m$ distinct real numbers, we have that the set $\underbrace{A+A+\cdots+A}_{k\text{ times}}$ has at least $k(m-k)+1$ elements. Here, $\underbrace{A+A+\cdots+A}_{k}$ refers to the set $A'=\{s_1+s_2+\cdots+s_k : \ \ \ s_i\in A, s_i\ne s_j \text{ for }i\ne j\}$ Proof. Let $A=\{a_1<a_2<\cdots<a_m\}$. Consider the tuples \[(1,2,3,\ldots,k-1,k),(1,2,3,\ldots,k-1,k+1),\ldots,(1,2,3,\ldots,k-1,m)\]\[(1,2,3,\ldots,k,m),(1,2,3,\ldots,k+1,m),\ldots,(1,2,\ldots,m-1,m)\]\[\vdots\]\[(1,m-k+2,m-k+3,\ldots,m),(2,m-k+2,m-k+3,\ldots,m),\ldots,(m-k+1,m-k+2,\ldots,m)\]Counting, this gives us exactly $1+(m-k)+(m-k)+\cdots+(m-k)=k(m-k)+1$ tuples. Note that if we take any of these tuples $(t_1,t_2,\ldots,t_k)$ and $(t_1',t_2',\ldots,t_k')$, with $t_1'+t_2'+\cdots+t_k'>t_1+t_2+\cdots+t_k$ then $t_i'\geq t_i$ for every $1\leq i\leq k$ (equality does NOT hold for at least one $i$) and as a result, $a_{t_1}+a_{t_2}+\cdots+a_{t_k}<a_{t_1'}+a_{t_2'}+\cdots+a_{t_k'}$. Using these tuples as indices, the lemma is true. $\blacksquare$ We know that for any $k$, there are at least $k(m-k)+1$ distinct sums of exactly $k$ $a_i$'s possible. Also, if the number of $a_i$'s added are different, the sums obtained are different. Varying the numbers of $a_i$'s from $1$ to $m$, we obtain a whole lot of distinct sums, and we obtain at least \[\sum_{k=1}^{m}k(m-k)+1=\frac{m^3+5m}6\]distinct sums, all lying between $1$ and $a_1+a_2+\cdots+a_m$. It follows that \[n\geq a_1+a_2+\cdots+a_m\geq\frac{m^3+5m}{6}>\frac{m^3}{6}\Longrightarrow m<\sqrt[3]{6n},\]as desired. $\blacksquare$

Suppose we have a partition with $d$ different parts $a_1,a_2,\dots a_d$. We will show that if $d>\sqrt[3]{6n}$, then we can improve it. The idea is to try to "merge": if any subset has the same sum as any other subset, we can replace one with the other. Thus, as long as these two subsets have different sizes, we can improve it. Thus, assuming this is optimal, we know that no two subsets of different sizes have the same sum. Now, the idea is to construct $O(d^3)$ different-sum subsets given this information. Consider subsets of size $s$. Claim: Out of subsets of size $s$, at least $s(d-s)+1$ different sums can be achieved. Consider starting with the $s$ smallest, and repeatedly moving one element one slot forwards. This goes until we have the $s$ largest, after which we have moved $s(d-s)$ positions. The sum achieved at each step is distinct since it always increases. Thus, there are at least $$\sum_{s=1}^d s(d-s)+1={d+2\choose 3}+d>\frac{d^3}{6}$$different sums that are achieved. Clearly, all of these sums are at most $n$, since $n$ is made up of at least one of each different part. Thus, $n>\frac{d^3}{6}$, as desired. Remark: In general, it is very difficult to determine whether or not a solution exists. This suggests that the solution takes the form "assume we magically have a solution, try to improve it if it has too many different parts", rather than actually trying to make a solution. Once you realize this, the first thing you think of is to "merge" many numbers into one. However, one realizes that this doesn't work, you can still have large sets as long as the largest is less than twice the smallest, you can't merge like this. However, one then realizes that there is nothing forcing you to only merge into one number, and the solution follows.