The Cookie Monster Problem

Suppose that we have a number of cookie jars, each containing a certain number of cookies. The Cookie Monster wants to eat all the cookies, but he is required to do so in a number of sequential moves. At each move, the Cookie Monster (CM) chooses a subset of the jars, and eats the same (nonzero) number of cookies from each jar. The goal of the CM is to empty all the cookies from the jars in the smallest possible number of moves, and the Cookie Monster Problem is to determine this number for any given set of cookie jars.

Since the CM has an unlimited appetite, there is essentially no difference between eating three cookies from one jar, and eating three cookies from each of 10 jars. It turns out that there is no advantage to depleting these 10 jars at different rates, so the 10 jars may as well be one jar, and we may as well reduce to the case where no two jars contain the same number of cookies. It is also safe to ignore any empty jars. This means that the starting state of the problem may be described by a set of positive integers, S. The Cookie Monster Number of S, CM(S), is the smallest number of moves in which this set of jars can be completely emptied.

Let's look at an example. Suppose that S is the set {15, 13, 12, 4, 2, 1}, meaning that there are six jars, containing 1, 2, 4, 12, 13 and 15 cookies each. Here are three possible strategies open to the CM.

1. The Empty the Most Jars algorithm
In the given configuration, there are six different numbers of cookies in the various jars. In the "Empty the Most Jars" algorithm, the CM should try to minimize this number of six. For example, if the CM eats 11 cookies from each jar containing more than 11 cookies, every jar will end up with 1, 2 or 4 cookies. That's only three different numbers, which we regard as an improvement.

2. The Take the Most Cookies algorithm
The goal of the "Take the Most Cookies" algorithm is to take as many cookies as possible in each step. For example, if the CM eats 12 cookies from each jar containing more than 12 cookies, that's a total of 36 cookies. The resulting jar state is described by the set {4, 3, 2, 1}; note that there will be two jars with 1 cookie each.

3. The Binary algorithm
The "Binary" algorithm finds x as large as possible and takes 2^x cookies from each jar that contains at least that many. In our situation, we would take x = 3, and remove 8 cookies from each jar containing at least that many, resulting in the state described by {7, 5, 4, 2, 1}.

So what can be said about the value of CM(S)? One inefficient strategy available to the CM is to empty the jars one at a time. This would empty the configuration {15, 13, 12, 4, 2, 1} in 6 steps, where S has size 6 (which we write as |S| = 6). It follows that CM(S) is less than or equal to |S|.

Less obviously, there is a lower bound for CM(S) given by taking |S|, adding 1, taking logarithms to base 2 and rounding up to the nearest integer. This may be easier to explain with an example. Suppose now that S is given by the set {7, 6, 5, 2, 1}. Let's create a new list of numbers, A, given by (1, 2, 5). (The set A is allowed to contain repeats, which is why I call it a list, not a set.) Why 1, 2 and 5? Because every element in S can be written as a sum of elements from this list: for example, 7 = 5+2, 6 = 5+1. The set A is as small as possible with this property. But A gives a strategy for emptying S: first remove 5 cookies from every jar with at least 5, then remove 2 cookies from every jar with at least 2, then remove 1 cookie from every jar with at least 1. Now the jars are empty! Since A only has 3 elements, the number of different nonzero quantities that can be formed by adding its elements together cannot exceed 2^3 - 1. The base 2 logarithm lower bound comes from this argument.

The recent paper http://arxiv.org/abs/1304.7508 by Megan Belzner gives a good introduction to the Cookie Monster Problem. The paper looks at some special cases of the problem, including the case where the set S has size 3. In this case, it takes three moves to empty S, unless the sum of the cookies in two of the jars equals the number in the third, in which case it only takes two moves. Some other cases examined in the paper are arithmetic progressions (which sometimes achieve the lower bound), geometric progressions (which sometimes achieve the upper bound) and the Fibonacci sequence (which can be emptied in a number of moves roughly equal to half the number of jars). The problem can also be altered to form a two-player game, similar to the game of Nim, and the author discusses this to some extent.

This post has been brought to you by the letter C, and the number log_2(|S|+1).

#mathematics  
Photo
Shared publiclyView activity