HMMT November, 2024

Solution:

If Alf doesn't eat on day $100$, he could have changed his diet so that he eats on all the same days except the last day is changed to $100$. This attains strictly more apatite, and therefore an optimal diet must have Alf eating on day $100$.

Knowing this, Alf must not have eaten anything on days $51, \ldots, 99$. Now, by the same logic, Alf must have eaten on day $50$. Continuing the logic recursively gives that Alf must have eaten on days
$$100, 50, 25, 12, 6, 3, 1$$
The sum of these numbers is $197$.

Solution:

The answer is $197$, achieved by Alf eating on days $1, 3, 6, 12, 25, 50, 100$. We show that we could not do better.

Let $a_{1} > a_{2} > \cdots > a_{k}$ be the days that Alf ate apatite. By the problem's condition, $a_{i} \geq 2 a_{i+1}$ for all $i$. Thus, beginning with $a_{1} \leq 100$, we deduce that
- $a_{2} \leq \left\lfloor \frac{a_{1}}{2} \right\rfloor = 50$,
- $a_{3} \leq \left\lfloor \frac{a_{2}}{2} \right\rfloor = 25$,
- $a_{4} \leq \left\lfloor \frac{a_{3}}{2} \right\rfloor = 12$,
- $a_{5} \leq \left\lfloor \frac{a_{4}}{2} \right\rfloor = 6$,
- $a_{6} \leq \left\lfloor \frac{a_{5}}{2} \right\rfloor = 3$,
- $a_{7} \leq \left\lfloor \frac{a_{6}}{2} \right\rfloor = 1$,
and hence $k \leq 7$. Thus, $a_{1} + \cdots + a_{k} \leq 100 + 50 + 25 + 12 + 6 + 3 + 1 = 197$.