Let with .

We note that since , that every element in is greater than every element in . So for every partition , must be for some and must be . Call these values of good.

Naturally, we want to see how closely the good values can be packed into . This motivates

Lemma 1: If are both good, then .

Proof: We know from being good that , so .

This implies that as desired, since is also good.

Now lemma 1 directly motivates

Lemma 2: cannot all be good.

Proof: Suppose this were the case. By Lemma 1 applied twice, and . But this implies that for all , hence , a contradiction.

Now we are almost done. We just need one final claim:

Lemma 3: are not both good.

Proof: Suppose this were the case. Then by lemma 1 we know that , but since is good we know , a contradiction.

Now lemmas 2,3 combined tell us that to get partitions we need at least , so for we get .

We can find a construction as follows: .

This problem feels pretty natural but it's very easy to get off by one on the final answer