, 2016

Solution:

The answer is 18.
First, we will show that Kristoff must carry at least 18 ice blocks. Let
$$0 < x_{1} \leq x_{2} \leq \cdots \leq x_{n}$$
be the weights of ice blocks he carries which satisfy the condition that for any $p, q \in \mathbb{Z}_{\geq 0}$ such that $p+q \leq 2016$, there are disjoint subsets $I, J$ of $\{1, \ldots, n\}$ such that $\sum_{\alpha \in I} x_{\alpha} = p$ and $\sum_{\alpha \in J} x_{\alpha} = q$.

Claim: For any $i$, if $x_{1} + \cdots + x_{i} \leq 2014$, then
$$x_{i+1} \leq \left\lfloor \frac{x_{1} + \cdots + x_{i}}{2} \right\rfloor + 1$$
Proof. Suppose to the contrary that $x_{i+1} \geq \left\lfloor \frac{x_{1} + \cdots + x_{i}}{2} \right\rfloor + 2$. Consider when Anna and Elsa both demand $\left\lfloor \frac{x_{1} + \cdots + x_{i}}{2} \right\rfloor + 1$ kilograms of ice (which is possible as $2 \times \left( \left\lfloor \frac{x_{1} + \cdots + x_{i}}{2} \right\rfloor + 1 \right) \leq x_{1} + \cdots + x_{i} + 2 \leq 2016$). Kristoff cannot give any ice $x_{j}$ with $j \geq i+1$ (which is too heavy), so he has to use from $x_{1}, \ldots, x_{i}$. Since he is always able to satisfy Anna's and Elsa's demands, $x_{1} + \cdots + x_{i} \geq 2 \times \left( \left\lfloor \frac{x_{1} + \cdots + x_{i}}{2} \right\rfloor + 1 \right) \geq x_{1} + \cdots + x_{i} + 1$. A contradiction.

It is easy to see $x_{1} = 1$, so by hand we compute obtain the inequalities $x_{2} \leq 1$, $x_{3} \leq 2$, $x_{4} \leq 3$, $x_{5} \leq 4$, $x_{6} \leq 6$, $x_{7} \leq 9$, $x_{8} \leq 14$, $x_{9} \leq 21$, $x_{10} \leq 31$, $x_{11} \leq 47$, $x_{12} \leq 70$, $x_{13} \leq 105$, $x_{14} \leq 158$, $x_{15} \leq 237$, $x_{16} \leq 355$, $x_{17} \leq 533$, $x_{18} \leq 799$. And we know $n \geq 18$; otherwise the sum $x_{1} + \cdots + x_{n}$ would not reach 2016.

Now we will prove that $n = 18$ works. Consider the 18 numbers named above, say $a_{1} = 1$, $a_{2} = 1$, $a_{3} = 2$, $a_{4} = 3$, $\ldots$, $a_{18} = 799$. We claim that with $a_{1}, \ldots, a_{k}$, for any $p, q \in \mathbb{Z}_{\geq 0}$ such that $p+q \leq a_{1} + \cdots + a_{k}$, there are two disjoint subsets $I, J$ of $\{1, \ldots, k\}$ such that $\sum_{\alpha \in I} x_{\alpha} = p$ and $\sum_{\alpha \in J} x_{\alpha} = q$. We prove this by induction on $k$. It is clear for small $k = 1, 2, 3$. Now suppose this is true for a certain $k$, and we add in $a_{k+1}$.

When Kristoff meets Anna first and she demands $p$ kilograms of ice, there are two cases.

Case I: if $p \geq a_{k+1}$, then Kristoff gives the $a_{k+1}$ block to Anna first, then he considers $p' = p - a_{k+1}$ and the same unknown $q$. Now $p' + q \leq a_{1} + \cdots + a_{k}$ and he has $a_{1}, \ldots, a_{k}$, so by induction he can successfully complete his task.

Case II: if $p < a_{k+1}$, regardless of the value of $q$, he uses the same strategy as if $p + q \leq a_{1} + \cdots + a_{k}$ and he uses ice from $a_{1}, \ldots, a_{k}$ without touching $a_{k+1}$. Then, when he meets Elsa, if $q \leq a_{1} + \cdots + a_{k} - p$, he is safe. If $q \geq a_{1} + \cdots + a_{k} - p + 1$, we know $q - a_{k+1} \geq a_{1} + \cdots + a_{k} - p + 1 - \left( \left\lfloor \frac{a_{1} + \cdots + a_{k}}{2} \right\rfloor + 1 \right) \geq 0$. So he can give the $a_{k+1}$ to Elsa first then do as if $q' = q - a_{k+1}$ is the new demand by Elsa. He can now supply the ice to Elsa because $p + q' \leq a_{1} + \cdots + a_{k}$. Thus, we finish our induction.

Therefore, Kristoff can carry those 18 blocks of ice and be certain that for any $p + q \leq a_{1} + \cdots + a_{18} = 2396$, there are two disjoint subsets $I, J \subseteq \{1, \ldots, 18\}$ such that $\sum_{\alpha \in I} a_{\alpha} = p$ and $\sum_{\alpha \in J} a_{\alpha} = q$. In other words, he can deliver the amount of ice both Anna and Elsa demand.