# December 31st game (strong induction)

• NastyAccident
In summary, the game involves two players taking turns naming dates, with the starting position being January 1. The player who names December 31 wins. The first player can start by naming a date after the first day in January or the first day in a month after January. The key to winning is to force the other player towards allowing you to name October 29th, November 30th, or December 31st. This can be achieved by moving to the next date where the difference between the day and the month is 19. By doing this, the first player can guarantee a win in the game.
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?

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?

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.

Office_Shredder said:
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.

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

Office_Shredder said:
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?

Office_Shredder said:
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?

Anybody?

## 1. What is strong induction?

Strong induction is a proof technique used in mathematics to prove that a statement is true for all natural numbers. It involves using the fact that if a statement is true for a specific number, it is also true for all smaller numbers.

## 2. How is strong induction different from regular induction?

Regular induction only uses the fact that a statement is true for a specific number and its immediate successor. Strong induction, on the other hand, uses the fact that a statement is true for a specific number and all smaller numbers as well.

## 3. What is the December 31st game?

The December 31st game is a mathematical game that involves players taking turns saying numbers from 1 to 31. The goal is to be the first player to say the number 31. The catch is that if a player says a number that is a multiple of 3 or contains the digit 3, they must say "December 31st" instead of the number.

## 4. How is strong induction used in the December 31st game?

Strong induction is used to prove that the first player can always win the December 31st game, regardless of the number chosen by the second player. This is done by showing that if the statement "the first player can always win" is true for a specific number, it is also true for all smaller numbers.

## 5. Are there any other applications of strong induction?

Yes, strong induction is a powerful proof technique that can be used in various areas of mathematics, such as graph theory, number theory, and combinatorics. It is also commonly used in computer science to prove the correctness of algorithms and data structures.

Replies
18
Views
1K
Replies
1
Views
2K
Replies
1
Views
3K
Replies
23
Views
2K
Replies
7
Views
6K
Replies
1
Views
5K
Replies
3
Views
2K
Replies
7
Views
2K
Replies
1
Views
2K
Replies
93
Views
12K