12
$\begingroup$

Consider a two-player game. The players move in turns to pick either a month or a day. The winner is the player who picks the date December 31 ($12/31$). The following rules apply:

  • The game starts at January 1 ($1/1$).
  • The first player can increase the value of the month ($m>1$) or the value of the day ($d>1$), but not both.
  • All subsequent moves involve raising the value of either the month or the day (but not both) of the previously chosen date.
  • The amount of increase in either $m$ or $d$ can be anything as long as the result is a valid date. For example, if one player picks 1/30, then the next player can only choose from $m\in\{3,4,\dots,12\}$ or $d\in\{31\}$ (note that $m=2$ is not feasible); likewise, if one player chooses 5/31, the next player can only choose the month value $m\in\{7,8,10,12\}$.

I'd like to verify whether the following strategy guarantees winning of the first mover. If so, is this the unique winning strategy?

Let $(m_0,d_0)$ be the date picked by the previous player. I claim the following response function guarantees the winning of the first mover:
\begin{equation}R(m_0,d_0)=\begin{cases}(m_0,m_0+19) & \text{if }d_0<m_0+19\\[6pt](d_0-19,d_0) & \text{if }d_0\ge m_0+19\end{cases}\end{equation}
In words, this strategy says:
- If the day value is strictly less than the month value plus 19, raise the day value to that level (i.e. month value plus 19);
- If the day value is no less than the month value plus 19, raise the month value to the day value minus 19.

$\endgroup$
  • 4
    $\begingroup$ This is (with a few special cases) a game of two-pile Nim, so the usual proof method is to start enumerating the losing positions, starting from the last moves. $\endgroup$ – Bass Mar 9 '18 at 18:20
14
$\begingroup$

I think that your proposed method is correct. Here's a quick visual representation of the same method (by no means a formal proof):

Here's a rough calendar of the entire year. Black squares are invalid dates. You start in the upper left corner, and your goal is to get to the lower right corner. On your turn, you can either move down any number of spaces, or right any number of spaces. Visual representation of method

To win, you need to make sure your turn always ends on one of the blue squares. If it does, your opponent can't get to any of the other squares on the diagonal on their turn, but no matter what they do, you'll always be able to get back onto that diagonal! Since the winning square is on this same diagonal, if you always end your turn on this diagonal, you'll be guaranteed a win.

This diagonal can be defined as the set of dates $(m, d)$ where $d=m+19$, so your method is a mathematical way of saying "move to the blue square that's in your same row/column (whichever one is a valid move)"

$\endgroup$
  • $\begingroup$ I just realised I used a modified version of your diagram without asking for permission first. May I? (With the prettiest retroactive please?) $\endgroup$ – Bass Mar 10 '18 at 0:00
5
$\begingroup$

For completeness' sake, here's @DqwertyC's diagram adapted for the misére version, where you lose if you play December 31st. The "missing" day at the end of November complicates the endgame a little, but up to September and up to the 28th, the exact same strategy still works.

enter image description here

Again, the winning strategy is to only choose the blue dates, one of which is always available.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.