$\text{Solution to Problem 13}$

Lemma: Let $S$ be a set of $m$ integers. Let $T$ be the set of integers that can be written as a sum of $t$ distinct elements of $S$. Then $|T|\ge t(m-t)+1$.

Proof: Let $a_1<a_2<a_3<\ldots <a_m$ be the elements of $S$. Now, take the sum $a_1+a_2+\ldots +a_t$. Now, we define a move as taking the last number, and increase its indice by $1$. If its not possible because of crossing the limit of variables or overlapping of numbers, go to the second last and so on. It increases the value of the sum, and we can do $t(m-t)$ moves, from which the lemma follows.

Now, we tackle the original problem. Let there be an optimal partition for some $n,A,k$ as stated in the question. Let $|A|=m$. Now, take $t$ distinct element of $A$ and find there sum. All such numbers form the set $A_t$. Now, because of the definition, $n$ doesn't belong to any of the sets $A_1, A_2, A_3,\ldots A_{k-1}$. If two of them have different size but an element that is the same, we run into a contradiction if we substract the numbers with bigger size and add the numbers with small size. So each of them together can at least cover $|A_1|+|A_2|+|A_3|+\ldots +|A_{k-1}|$ integers. So we have $n\ge |A_1|+|A_2|+|A_3|+\ldots +|A_{k-1}|\ge 1(m-1)+1+2(m-2)+1+3(m-2)+1$ $+\ldots +(k-1)(m-k+1)+1=m(1+2+3+\ldots k-1)-(1^2+2^2+3^2+\ldots (k-1)^2)$ $+k-1\ge \dfrac{k(k-1)(3m-2k+1)}{6}\ge\dfrac{k(k-1)(3k-2k+1)}{6}+k-1=\dfrac{k^3+5k-6}{6}>\dfrac{k^3}{6}$ for $k>1$. The $k=1$ case is trivial.

Now, $n>\dfrac{k^3}{6}\Rightarrow k<\sqrt[3]{6n}$.

Hammer with tact.

Because destroying everything mindlessly isn't cool enough.