The Cookie Monster Problem
by Olivier Bernardi and Tanya Khovanova
The Cookie Monster is a peculiar creature that appeared in The Inquisitive Problem Solver (Vaderlind, Guy & Larson, MAA, P34). Presented with a set of cookie jars, the Cookie Monster will try to empty all the jars with the least number of moves, where a move is to select any subset of the jars and eat the same number of cookies from each jar in the subset.
Even an untalented Cookie Monster would be able to empty n jars in n moves: to fulfill this strategy the Monster can devour all the cookies of one jar at a time. If the Monster is lucky and some jars have the same number of cookies, the Monster can apply the same eating process to all these identical jars. For example, if all the jars have the same number of cookies, the Monster can gulp down all of them in one swoop.
Now, let us limit our discussion to only cases of n non-empty jars that contain distinct numbers of cookies. If indeed all the numbers are distinct, can the Monster finish eating faster than in n moves?
The answer depends on the actual number of cookies in each jar. For example, if the number of cookies in jars are different powers of 2, then even the most talented Monsters can’t finish faster than in n steps. Indeed, suppose the largest jar contains 2N cookies. That would be more than the total number of cookies in all the other jars together. Therefore, any strategy has to include a step in which the Monster only takes cookies from the largest jar. The Monster will not jeopardize the strategy if it takes all the cookies from the largest jar in the first move. Applying the induction process, we see that we need at least n steps.
On the other hand, sometimes the Monster can finish the jars faster. If 2k−1 jars contain respectively 1, 2, 3, …, 2k−1 cookies, the Cookie Monster can empty them all in k steps. Here is how. For its first move, the Monster eats 2k-1 cookies from each of the jars containing 2k-1 cookies or more. What remains are 2k-1−1 pairs of identical non-empty jars containing respectively 1, 2, 3, …, 2k-1−1 cookies. The Monster can then continue eating cookies in a similar fashion, finishing in k steps. For instance, for k=3 the sequences of non-empty jars are: 1,2,3,4,5,6,7 → 1,1,2,2,3,3 → 1,1,1,1 → all empty.
Now we would like to prove a theorem that shows that the example above is the lowest limit of moves even for the most gifted Cookie Monsters.
Theorem. If n non-empty jars contain distinct numbers of cookies, the Cookie Monster will need at least ⌈log2(n+1)⌉ steps to empty them all.
Proof. Suppose that n jars contain distinct numbers of cookies and let f(n) be the number of distinct non-empty jars after the first move of the Cookie Monster. We claim that n ≤ 2f(n)+1. Indeed, after the first move, there will be at least n − 1 non-empty jars, but there cannot be three identical non-empty jars. That means, the number of jars plus 1 can’t decrease faster than twice each time.
Now here is something our readers can play with. Suppose a sequence of numbers represents the number of cookies in the jars. Which sequences are interesting, that is, which can provide interesting solutions for the Cookie Monster problem?
Share:
JBL:
Very cute — so fast-enough exponential growth is some sort of a barrier. I guess two natural questions are, “Suppose the sequence of size weights is given by a polynomial (or is “close” to a polynomial in some sense to be determined) — is the bound still logarithmic?” and “What about Fibonacci boxes?”
25 April 2011, 7:28 amJBL:
Wait, here’s “the” “right way” to think about what’s going on: given any set of numbers, subtract 1 from all the odds (if any); then subtract 2 from all those that are twice an odd (if any); then subtract 4 from those that are four times an odd (if any); and so on. This is essentially the same as your strategy for {1, 2, …, n} but it gives in general an upper bound of “the number of distinct powers of 2 that appear in the binary representations of all the elements of the set”, or (weaker) the ceiling of log-base-2 of one more than the largest number in the set. (Sometimes of course we can do better than this, e.g., if every number in the set 2 more than a multiple of 4 is actually 6 more than a multiple of 8, we can squish two steps into one.)
26 April 2011, 9:54 amPratik Poddar:
Another interesting variant.
Let there be (2^k-1) jars numbered 1 to (2^k-1). The jar numbered i contains ai+b cookies (a and b are non-negative integers). Again, by the same logic used above, cookie Monster can empty it in k moves. 🙂
3 May 2011, 2:26 pm