A 20+ year old combinatorial problem - the cookie game

Question

Learned about this not too long after the time of the original problem publication through a classmate who visited MIT one summer.

http://faculty.uml.edu/jpropp/cookie2.pdf

The problem goes as follows: Given a set of cookies with finite time-to-expiry (in days) labels, 2 players take turns as follows: On day 1, player A chooses a "good" cookie and eats it, then on day 2 if any non-stale cookies are left player B does the same and so on. The player who eats the last "good" cookie is declared a winner. Given the set of cookies + expiry labels, who has a winning strategy and what's the strategy?

The statement of the problem is astonishingly simple, and yet this was open back then.

A quick observation is that if the set of expiry integers and the total number of cookies have the same parity (all odd or all even) then there's an "easy" strategy for one of the two players.

What if epxiry dates are all odd but the number of cookies is even (and vice versa)?

Can someone crack that particular case alone?

The general question is probably too hard and worth promoting to mathoverflow.

Answer 1

Call the number of days until expiration the "freshness" of the cookie. A cookie with freshness $1$ is here (and can be eaten) today, but will be gone tomorrow; a cookie with freshness $n+1$ will have freshness $n$ tomorrow. If all the cookies' freshnesses have the same parity, then this will persist for the entire game: one player (Eve) will only see even-freshness cookies, and the other (Otto) will see only odd-freshness cookies. Eve can win immediately only if she sees exactly one cookie (because no cookies become stale after her turn). Otto can win immediately if he sees exactly one cookie, or if he sees only freshness-$1$ cookies. We see that

• Otto wins if he sees an odd number of cookies.
• Eve loses if she sees an even number of cookies.

If Otto sees an odd number of cookies, he needs to make sure that Eve will see an even number; eating one cookie leaves an even number, and so if an even number (possibly zero) of cookies then expire, then Eve will see an even number; and Otto can guarantee this by eating a freshness-$1$ cookie only if there is an odd number of them.

The question pertains to the remaining constant-parity cases: Otto sees an even number of cookies, or Eve sees an odd number.

Otto, for his part, would like to pass an even number of cookies to Eve; he can do this if (and only if) there are any freshness-$1$ cookies, by eating one of an even number of freshness-$1$ cookies, or eating a fresher cookie when there's an odd number of freshness-$1$ cookies. So Otto will win if he ever sees a freshness-$1$ cookie. (Otherwise, he'll lose: no cookie will ever get stale, and Eve will get to eat the last one.) The best that Eve can do is to try to prevent this, by always eating the cookie with the lowest freshness. (Otto may as well eat the freshest cookie -- presumably the tastiest -- unless there are any with freshness $1$.) Let the freshnesses be $a_1 \le a_2 \le \ldots \le a_{k+1} \le \ldots \le a_{2k+1}$ on Eve's turn. Then her subsequent moves will be $[a_1, a_2, \ldots]$, and she'll win if $a_i \ge 2i$ for $i=1,2,\ldots k+1$. Otherwise she will lose. This completely characterizes the constant-parity space:

• Eve wins if she sees an odd number of cookies such that $a_i \ge 2i$ for all $i\le k+1$.
  • Her winning strategy is to always eat the stalest cookie.
• Eve loses if she sees an even number of cookies, or an odd number of cookies such that $a_i < 2i$ for some $i\le k+1$.
• Otto loses if he sees an even number of cookies such that $a_i \ge 2i+1$ for all $i\le k$.
• Otto wins if he sees an odd number of cookies, or an even number of cookies such that $a_i < 2i+1$ for some $i\le k$.
  • His winning strategy is to give Eve an even number of cookies (by choosing whether or not to eat a freshness-$1$ cookie) if possible, and otherwise always eat the freshest cookie.