- #1

NastyAccident

- 61

- 0

## Homework Statement

(The December 31 Game) Two players alternately name dates. On each move, a player can increase the month or the day of the month, but not both. The starting position is January 1, and the player who names December 31 wins. According to the rules, the first player can start by naming some day in January after the first, or the first of some month after January. For example (Jan. 10, Mar. 10, Mar. 15, Apr. 15, Apr. 25, Nov. 25, Nov. 30, Dec. 30, Dec. 31) is an instance of the game won by the first player. Derive a winning strategy for the first player. (Hint: use strong induction to describe the "winning dates".)

## Homework Equations

DATE - MONTH = 19

10-1 = 9

10-3 = 7

15-3 = 12

15-4 = 11

25-11 = 14

30-11 = 19

30-12 = 18

31-12 = 19

I figured out that the pattern to win requires the DATE-MONTH to equal 19.

## The Attempt at a Solution

My attempt at wording my proof by strong induction (criticism is welcomed!):

The strategy holds for the first player when the month is November and the day is the 30th, as the second player will either have to advance the month or the day leaving the first player the ability to swoop in and take the option he or she has left to win the game (reach december 31st). This proves the basis step.

Suppose we start with many dates d and many months m. If the first player takes the 20th of january, then regardless of what the second player does, whether it be to advance the month or the date, the first player wins.

Otherwise, if the first player takes a different m or d for some m or d. The econd player will need to take a m or d such that the difference between the days and months is not 19.

The remainder of the game is equivalent to d-m and the second player always has to have the difference between the days and months of the spot he or she moves to not equal to 19. The induction hypothesis tells us then that the first player wins this game.

Thoughts?

Should it be equivalent to n - d - m?