Alice and Carla are playing a game often learned in elementary school known as Twenty One . The rules for the game are as follows:
Each player takes turns saying between and consecutive numbers, with the first player starting with the number . For example, Player could say the numbers and , then Player can say " , , ", then Player can say " " and so on.
The goal of the game is to get the other person to say " ", meaning that you have to be the one to say " ".
Carla begins to get bored with the game, so she decides to make it a little bit more challenging. The name of the new game is Two Hundred Thirty Nine , where the goal is now to get the other person to say " ". Carla decides that she'll go first and that Alice will go second. Also, each player is now able to say up to " " numbers per turn. Is there a way to tell which player is going to win before the game even starts?
Details and Assumptions :
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
The key to the solution is to begin by looking at smaller cases and generalizing to bigger cases. Let's start by analyzing the game Twenty One.
Our goal in this game is to say the number "20". It's easy to show that no matter what Player 1 does, if Player 2 is playing perfectly it is impossible for Player 1 to win.
Consider the following strategy. Allow Player 1 to play whatever they want and have Player 2 play up to only multiples of 4 . For example, Player 1 says "1, 2, 3" and Player 2 says "4". Player 1 says "5, 6" and Player 2 says "7, 8". It's always possible to hit a multiple of 4 because the maximum number of terms each player can say is 3 , so if Player 1 say 1 number then Player 2 plays 3, or they can each play 2 and 2 or 3 and 1. Notice that 2 0 is a multiple of 4, so as long as Player 2 follows this method they'll win every time.
What happens we increase the length of the game? Let's let N be the length of our game, and we'll try to analyze N = 2 2 , AKA the game Twenty Two. Now you want to say "21" to win. In this scenario, Player 1 will always win because the numbers we want to say are of the form 4 m + 1 . All Player 1 has to do is say "1" and the game is already over. He plays 1, 5, 9, 13, 17, and finally 21 and Player 2 can't stop him. This should be sufficient to show that Player 2 can only win when 4 ∣ N − 1 .
Now what happens if we increase the number of terms? Let T be the number of terms each person can say each turn. We'll let T=4 and let N = 2 1 for our example. We can now guarantee that we can say every 5 th number, because if one person says 1 number, the other says 4, if one says 2 the other says 3, and so on. 2 1 is a multiple of 5 , so Player 2 will win every time. If we generalize this idea for T terms, Player 2 can only win when ( T + 1 ) ∣ 2 0 , because otherwise the first number in the sequence of multiples will be a number that Player 1 can say.
Combining the conditions together, we have the following formula:
If ( T + 1 ) ∣ ( N − 1 ) , then Player 2 wins. Otherwise, Player 1 wins.
Finally, let's plug in our values of T and N to see who wins.
( 6 + 1 ) ∣ ( 2 3 9 − 1 )
7 ∣ 2 3 8
Since 7 × 3 4 = 2 3 8 , Player 2 will always win this game, or in this case, Alice is the winner.