A geeky party trick

You are at a friend’s place having good time together, watching TV, maybe playing classic video games, or whatever you are in mood for. Soon it all gets pretty boring. You are in mood for some fun and you want to have a bet with your friend over a game.

Imagine a 2-player game that you can play with your friend with following rules:-

1)     An arbitrary number is chosen as the starting number.

2)     Each of the players takes turns to play his/her turn.

3)     In a given turn, the player is allowed to subtract any prime number less than the current number, including 1, from the current number. After subtraction, this becomes the new number.

4)     The player take turns doing this and ultimately the person unable to make a move loses the game.

Now consider a sample game:-

The selected number is 52.

Player 1 starts the game and selects a prime number less than 52.

He selects 13. The new number is 52 – 13 = 39

Player 2 selects another prime number, 17

New number is 39 – 17 = 22

Player 1 selects another prime number, 19

New number is 22 – 19 = 3

Now player 2 has only 2 choices. Either to select 2 or 1. He chooses 2.

New number is 3 – 2 = 1

Now player 1 has no options(primes less than 1). Hence, he is unable to make a move and loses the game. The winner of this game is player 2.

So, now the question is, what is the best strategy to win this game?

A good strategy to win this game is to make sure your opponent does not get a chance to win. And to do this, you have to identify theWINNINGSTATESand theLOSINGSTATES.

Lets start by identifying these states.

Consider the number 1.

According to the rules, you need to subtract a prime number less than the current number. But here, there is no number less than 1. Hence, whoever ends up with number 1 has no choice to make. Hence he will definitely LOSE.

Hence, 1 is aLOSINGSTATE.

Now consider the number 2.

You have the option to subtract only 1 number from this. i.e- 1.

If you subtract 1, the other player ends up with the number 1, which is a losing state. Hence, you will win the game by subtracting 1 from 2. Hence, 2 is aWINNINGSTATE.

Similarly, consider number 3. You have the option of subtracting 1 or 2 from 3. Remember that your best strategy is to PUSH THE OTHER PERSON TO A LOSING STATE. Hence, your best bet is to subtract 2 from 3 and give 1 to other player. Hence, it is possible to win the game by subtracting 2 from 3. Hence, 3 is aWINNINGSTATE.

Similarly, for number 4, you can subtract 3 and again push the other player to losing state. Hence, 4 isWINNINGSTATE.

Now take the number 5. Here comes the twist. Now you have the options to subtract 1,2 or 3 from 5. Notice that no matter which prime number you subtract, you wont be able to push your opponent to a losing state. In other words, your opponent will always end up in a winning state if you end up with number 5.

Hence, 5 is aLOSINGSTATE.

Now if you keep identifying the states in similar manner for all numbers, you will notice the following pattern.

L indicatesLOSINGSTATESand W indicates WINNING STATES.

By analysis, you can observe that for any given number, the only numbers you ever need to subtract to push your opponent to losing states are 1,2 and 3.

Hence, you can conclude that your best bet to win the game is to try to subtract a number in your turn such that it ends up in a losing state.

In this case, subtract a number such that after subtraction, N mod 4 == 1.

As shown in the table, the numbers satisfying this relation are 1,5,9,13…

Hence, the algorithm for winning the game is

1)     Subtract a prime number such that the new number leaves a remainder of 1 when divided by 4.

2)     If no numbers exist that satisfies step 1, then subtract a random prime number less than the current number. (Hoping that the opponent will make a mistake in later stages and end up in losing state.)

3)     Continue this until your opponent ends up with number 1 and is unable to make a move.

Now play this game with your unsuspecting friend and prepare to win lots of bets. 😉