33
$\begingroup$

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.

$\endgroup$
9
  • 1
    $\begingroup$ This may be obvious, but there's a straightforward isomorphism to a Nim-like piles-of-counters game: a move is to remove one pile entirely, and one counter from each of the other piles (counters represent 'days left until expiration'). As such, it seems like one of the 'extended' theories from Winning Ways (which covers, among other things, sums of games where players must move in all games) should apply here, though it would likely take some modification to take account of the different moves. $\endgroup$
    – Steven Stadnicki
    Feb 11, 2013 at 22:50
  • 3
    $\begingroup$ I think the fact that the numbers of the other "piles" change but you can only select one pile to remove entirely (aside from others that happen to expire at the same time) would actually be a big problem. I think it throws a nontrivial wrench in those theories because it's no longer quite like any of the 12 "ways to play multiple games". That's not to say there wouldn't be a separate slick way to handle this, but I don't think it would be a trivial modification. $\endgroup$
    – Mark S.
    Feb 12, 2013 at 1:42
  • $\begingroup$ Even if you restrict the expiry dates to distinct integers, is there an obvious solution? $\endgroup$
    – user7530
    Feb 14, 2013 at 7:26
  • $\begingroup$ @user7530 : there is a simple strategy, but the proof of its correctness is not obvious, see the paper linked in the OP. $\endgroup$
    – Ewan Delanoy
    Feb 14, 2013 at 9:46
  • $\begingroup$ @Meina222 would using probability to devise an optimal strategy be acceptable ? $\endgroup$
    – Comic Book Guy
    Feb 16, 2013 at 23:01

1 Answer 1

Reset to default
29
+100
$\begingroup$

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.
$\endgroup$
6
  • $\begingroup$ +1 -- not only, but also, for renaming Winnie and Lucy as Eve and Otto! :-) $\endgroup$
    – joriki
    Feb 19, 2013 at 1:00
  • $\begingroup$ If I read mjqxxx's answer correctly, the following is losing for Eve (assuming it's Eve's turn) since she sees an odd number (=5) of cookies and we have $a_5 = 6 < 2*5 = 10$: 2 4 6 6 6 (Eve eats f-2) 3 5 5 5 (Otto eats f-5) 2 4 4 (Eve eats f-2) 3 3 (Otto eats f-3) 2 (Eve eats last) But Eve Wins. The problem is that Otto runs out of his "excess supply" of fresh cookies due to being forced to make a move, so mjqxxxx's idea may not be enough. Am I wrong? $\endgroup$
    – Meina222
    Feb 19, 2013 at 16:58
  • $\begingroup$ @Meina222: You are: Eve only requires $a_i\ge2i$ up to $i=k+1$. In your example $k=2$, and $a_i=2i$ up to $i=3$. $\endgroup$
    – joriki
    Feb 19, 2013 at 17:20
  • $\begingroup$ You're right. I missed the "up-to" restriction. $\endgroup$
    – Meina222
    Feb 19, 2013 at 17:31
  • 8
    $\begingroup$ Nice to see Eve finally take a break from snooping on Alice & Bob and enjoy some cookies instead. $\endgroup$
    – user856
    Feb 19, 2013 at 20:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .