December 31st game (strong induction)

[NastyAccident]

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?

 

[Office_Shredder]

You didn't really describe a winning strategy in the way that it is supposed to be described. Your final description basically says: Player 1 can do whatever he wants on the first move, and then by induction he can win the game.

What are you doing induction on? The number of moves in the game? If so, why is your base case November 30th?

 

[JaredJames]

As long as you force the other player towards allowing you to name Oct 29th, Nov 30th or anything 31st, you always wins.

By using the strategy you have shown above, depending what player 2 chooses, you simply move to the next d - m = 19 date.

For example:

A: Jan 20th
B: Feb 20th
A: Feb 21st - to the next d - m = 19 point
B: Jul 21st
A: Jul 26th - next d-m=19 point
B: Oct 26th
A: Oct 29th - as above
B: Nov 29th
A: Nov 30th - as above
B: Dec 30th
A: Dec 31st - win

So the key is to move to the next d - m = 19 point. Whether it is in the same month (simply up the date) or in a different month (up the month).

By doing this you force your opponent to play towards giving you the win whilst never putting yourself in danger of allowing them Oct 29th or Nov 30th.

 

[JaredJames]

You didn't really describe a winning strategy in the way that it is supposed to be described. Your final description basically says: Player 1 can do whatever he wants on the first move, and then by induction he can win the game.

What are you doing induction on? The number of moves in the game? If so, why is your base case November 30th?

Whoever names Oct 29th, Nov 30th wins the game.

By naming Oct 29th, the opponent can only name Nov 29th giving you Nov 30th or Dec 29th giving you Dec 31st

By naming Nov 30th, the opponent can only name Dec 30th giving you Dec 31st.

They are the two key dates to the game.

I don't know what induction is in this sense so I can't comment on it.

 

[Office_Shredder]

By naming Nov 30th, the opponent can only name Dec 30th giving you Dec 31st.

I'm aware of that. But a game could easily end up at a step like Dec 17th (a bad way to play the game probably, but possible), so there's no reason to think that the end of your game is going to involve November 30th

 

[NastyAccident]

You didn't describe a winning strategy in the way that it is supposed to be described. Your final description basically says: Player 1 can do whatever he wants on the first move, and then by induction he can win the game.

What are you doing induction on? The number of moves in the game? If so, why is your base case November 30th?

I guess that's where I am really bloody confused. I know there are twelve dates that guarantee victory. 1/20, 2/21, 3/22, 4/23, 5/24, 6/25, 7/26, 8/27, 9/28, 10/29, 11/30, 12/31.

In the beginning, I choose that as the base case since I am trying to present something where no matter what the first player does he will win guaranteed.

Here is a rectified basis case statement:
The strategy holds for the first player when the month is November and the day is the 30th and it is the second players turn to move. This is because the total number of moves available to first player to win after the second player goes is just one that is to either take the 31st day or to take the month of december. This proves the basis step.

Now, changing the induction step of my proofs to align with steps:
Suppose we start with n moves available. If the first player takes the 20th of January, then the second player will be forced to take a move that allows the first player to win after a maximum of eleven moves and a minimum of one move due to the fact that the second player is stuck moving to a new day or month that's difference of days and months does not equal 19.
Otherwise, if the first player takes a k move, for some k. The second player will respond with taking k move. The remainder of the moves in the game is equivalent to a game with n-k moves in regard to each player and the first player moving to a date that's difference of days and months equals 19. The induction hypothesis tells us that the first player will win the game.

Is this at least a step in the right direction vs. my older one?

 

[NastyAccident]

I'm aware of that. But a game could easily end up at a step like Dec 17th (a bad way to play the game probably, but possible), so there's no reason to think that the end of your game is going to involve November 30th

Okay, so for the basis case just say that there is one move left and not worry about the month and day?

 

[NastyAccident]

Anybody?