A 20+ year old combinatorial problem - the cookie game

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.