3
$\begingroup$

You and 9 friends are playing a game, is there a way to force a win, if so, how, if not, what is the most optimal strategy?

Gameplay:
Each player can have a turn, or if he/she wishes, 2 turns. Each turn writing a number greater than the number wrote on the previous turn, it has to be 1 greater.

How to lose:
Write the number 10!

How to win:
Be the last one not to write the number 10!

Clarifications:

  • Turns do cycle
  • After writing 10 you restart at 1
  • Players are for themselves, nobody wishes to team up.

Example game:

  • Friend A writes 1
  • Friend A writes 2
  • Friend B writes 3
  • Friend C writes 4
  • Friend C writes 5
  • Friend D writes 6
  • Friend D writes 7
  • Friend E writes 8
  • Friend E writes 9
  • Friend F writes 10! He's out!
  • Friend G writes 1
  • etc. until one player is left.

Bonus: Can you extend this strategy for any amount of players, how?

Notes:
I'd like to let you know, I'm genuinely looking for an answer. I do not know it.

$\endgroup$
  • 4
    $\begingroup$ Generally speaking, multiplayer games do not have a winning strategy for any player, because groups of players can team up to enforce a given result. There is an area of study identifying what groups can force a win. Certainly here no one person can guarantee a win, as the other nine can make sure he loses early. $\endgroup$ – Ross Millikan Jan 28 '15 at 16:31
  • $\begingroup$ @Ross Millikan I forgot to add that clarification... $\endgroup$ – warspyking Jan 28 '15 at 16:53
  • 2
    $\begingroup$ The problem is that a player who is presented with $7$ can choose to write one or two numbers, eliminating either of the next two players. With so many players, that decision will not influence his chance of being the overall winner. No player has enough control to ensure victory. $\endgroup$ – Ross Millikan Jan 28 '15 at 17:05
  • $\begingroup$ It might be interesting if each player tries to maximize how many players are eliminated before them (rather than maximizing the chance they are the overall winner). Then there should be exactly one player with a winning strategy (assuming optimal, selfish play by all the other players). $\endgroup$ – Julian Rosen Jan 28 '15 at 17:16
  • 5
    $\begingroup$ I was confused when you wrote "10!" (twice!) and ended up thinking that the game would take a long time $\endgroup$ – lokodiz Jan 28 '15 at 17:36
7
$\begingroup$

As mentioned above, the second player in the two person game can force a win by playing perfectly.

The problem in the three person game is that there are 2 losers. Lets say that the three players are $A, B,$ and $C$ and there exists a perfect strategy for one of them to win. WLOG, lets say that this is $A$ (note we don't know who needs to go first for this to happen).

For $A$ to win, player $B$ will need to lose first making it player $C$'s turn in the final round. Thus, to make player $B$ lose, player $A$ will need to write $9$, or $8,9$. In order to do this, player $C$ will need to write $7$ or $8$. To force player $C$ to write $7$ or $8$, player $B$ will need to write $6$.

The problem is that we can't force player $B$ to write $6$. We can either end on $4$ or $5$, giving $B$ the option of writing $6$, or of writing $5$ or $7$, depending on what we give them. In fact, knowing that by writing $6$, $B$ will lose, $B$ will probably choose to write another number. $B$ may still lose, but losing to $C$ is equivalent to losing to $A$, so there is no motivation to play along with any strategy of $A$'s.

Lets say that in this situation, $A$ wrote a $5$. Knowing that writing a $6$ will lose, $B$ will write both $6$ and $7$. This hands the victory to $C$ since $C$ can now write $8$ and $9$, making $A$ drop out. $B$ goes next in the 2 person game, so $C$ wins.

If instead $A$ wrote a $4$, again, $B$ would know that writing a $6$ is death. So instead, $B$ may choose to write only $5$. But as we saw above, writing a $5$ will cause that player to be eliminated, and this would hand the win one the other two players.

Thus, if given the option to pick between $5, 6,$ or $7$, $B$ won't care because they all result in losses.

If we changed the rules to have a ranking where finishing later is better, then we could probably come up with a generic strategy for the 3 person game and extend it further.

With the Rule Change

Lets revisit the 3 person game with the new change that a player would rather come in second than lose.

3 Player Game

Players are $A,B,$ and $C$. The following are the results for player $A$ if player $A$ writes the following numbers:

  • $9$: Finish 1st. Player $B$ will be eliminated and $C$ will start the next round. Final order is $ACB$.
  • $8$: Finish 2nd. Player $B$ will write $9$ eliminating $C$ and $A$ will start the final round. Final order is $BAC$.
  • $7$: Finish 2nd. Player $B$ will write $8,9$. Final order is $BAC$.
  • $6$: Finish 3rd. Player $B$ can do no better than 2nd, and $C$ will get the win. Final order is $CBA$.
  • $5$: Finish 3rd. $B$ will write $6,7$ for same result as above. Final order $CBA$.
  • $4$: Finish 1st. Player $B$ will be forced to write either $5$ or $6$, both of which result in a 3rd place finish. This leaves $C$ to go first in the final round. Final order is $ACB$.
  • $3$: Finish 2nd. $B$ will get the win, so the final order is $BAC$.
  • $2$: Finish 2nd. Player $B$ will write $3,4$ and finish 1st again. Final order is $BAC$.
  • $1$: Finish 3rd. $B$ can do no better than 2nd, and $C$ will win. Final order is $CBA$.

Notice that to get the previous number, you simply need to figure out what $B$ will do. $B$ will have the choice of either the next number, or the next two, and will pick which ever gets the best result. Then you take the final ordering from that number and increment each player by one wrapping around to $A$ if necessary (e.g. $A$ become $B$, $B$ becomes $C$, and $C$ becomes $A$) to get the final ordering for the new number.

Thus, the person who goes second in the 3 person game can win. The person who goes first will choose to make $1,2$ as the first move and guarantee themselves second instead of third, allowing the person who goes second to write $3,4$ and put themselves in the winning position.

So if the initial setup is $ABC$ with $A$ to go first, then the final ordering will be $BAC$.

4 Player Game

Players are $A,B,C,$ and $D$. The following are the results for player $A$ if player $A$ writes the following numbers:

  • $9$: Finish 3rd. $B$ is eliminated, and the remaining players in order to start the final round are $CDA$. Final order will be $DCAB$.
  • $8$: Finish 1st. $B$ would write $9$ and finish 3rd, final order is $ADBC$.
  • $7$: Finish 2nd. $B$ would write $8$ and finish 1st. Final order is $BACD$.
  • $6$: Finish 2nd. $B$ would write $7,8$ to finish 1st. Final order is $BACD$.
  • $5$: Finish 4th. The best $B$ can do is finish 2nd. Final order is $CBDA$.
  • $4$: Finish 4th. $B$ would write $5,6$ to claim 2nd, making the final order again $CBDA$.
  • $3$: Finish 3rd. $B$ is forced to finish 4th. Final order will be $DCAB$.
  • $2$: Finish 1st. 3rd is better than 4th, so $B$ will write just $3$. Final order is $ADBC$.
  • $1$: Finish 2nd. $B$ would write $2$ and finish 1st. Final order is $BACD$.

So in the 4 person game, whoever goes first can win. If the initial order is $ABCD$ with $A$ to go first, then the final ordering is $ADBC$.

5 Player Game

Players are $A,B,C,D$ and $E$. The following are the results for player $A$ if player $A$ writes the following numbers:

  • $9$: Finish 2nd. $B$ is eliminated, and the remaining players in order to start the final round are $CDEA$. Final order will be $CADEB$.
  • $8$: Finish 4th. $B$ would write $9$ and finish 2nd. Final: $DBEAC$.
  • $7$: Finish 4th. $B$ would write $8,9$ and finish 2nd. Final: $DBEAC$.
  • $6$: Finish 3rd. $B$ would be forced to finish 4th. Final: $ECABD$.
  • $5$: Finish 1st. $B$ would write $6$ to finish 3rd instead of 4th. Final: $ADBCE$.
  • $4$: Finish 5th. $B$ would write $5$ to finish first. Final: $BECDA$.
  • $3$: Finish 5th. $B$ would write $5,6$ to finish first. Final: $BECDA$.
  • $2$: Finish 2nd. $B$ finishes last no matter what is written. Final $CADEB$.
  • $1$: Finish 4th. $B$ gets 2nd with $2$. Final: $DBEAC$.

So the only way to win the 5 person game is to be the one to write the $5$. This can be done by going third. The first player will choose to write $1,2$ since that is the better result. The second player finishes in last place no matter what they write, leaving the 3rd player to write the $5$ and win.

If the initial order is $ABCDE$ with $A$ to go first, then the final ordering is $CADEB$.

6 Player Game

Players are $A,B,C,D,E$ and $F$. The following are the results for player $A$ if player $A$ writes the following numbers:

  • $9$: Finish 4th. $B$ is eliminated, and the remaining players in order to start the final round are $CDEFA$. Final order will be $ECFADB$.
  • $8$: Finish 3rd. $B$ would write $9$ and finish 4th. Final: $FDABEC$.
  • $7$: Finish 1st. $B$ would write $8$ and finish 3rd. Final: $AEBCFD$.
  • $6$: Finish 5th. $B$ would write $7$ for the win. Final: $BFCDAE$.
  • $5$: Finish 5th. $B$ would write $6,7$ and win. Final: $BFCDAE$.
  • $4$: Finish 2nd. $B$ gets 5th. Final: $CADEBF$.
  • $3$: Finish 6th. $B$ would write $4$ to finish 2nd. Final: $DBEFCA$.
  • $2$: Finish 6th. $B$ writes $3,4$ for 2nd. Final: $DBEFCA$.
  • $1$: Finish 4th. $B$ gets 6th regardless. Final: $ECFADB$.

To win the 6 person game, you want to be the 5th player to go.

  1. Will write just $1$ since 4th place is better than 6th.
  2. Gets 6th no matter what they write.
  3. Will write $4$ to get 2nd instead of 5th.
  4. Gets 5th no matter what.
  5. Writes $7$ to win.

Final order assuming $A$ goes first in a 6 person game is $ECFADB$.

7 Player Game

Players are $A,B,C,D,E,F$ and $G$. The following are the results for player $A$ if player $A$ writes the following numbers:

  • $9$: Finish 3rd. $B$ is eliminated, and the remaining players in order to start the final round are $CDEFGA$. Final order will be $GEACFDB$.
  • $8$: Finish 1st. $B$ would write $9$ and finish 3rd. Final: $AFBDGEC$.
  • $7$: Finish 5th. $B$ would write $8$ and finish 1st. Final: $BGCEAFD$.
  • $6$: Finish 5th. $B$ would write $7,8$ for the win. Final: $BGCEAFD$.
  • $5$: Finish 2nd. $B$ gets 5th. Final: $CADFBGE$.
  • $4$: Finish 6th. $B$ gets 2nd with $5$. Final: $DBEGCAF$.
  • $3$: Finish 6th. $B$ gets 2nd again with $4,5$. Final: $DBEGCAF$.
  • $2$: Finish 4th. $B$ gets 6th. Final: $ECFADBG$.
  • $1$: Finish 7th. $B$ gets 4th with $2$. Final: $FDGBECA$.

To win the 7 person game, you want to be the 5th player to go.

  1. Will write just $1,2$ since 4th place is better than 7th.
  2. Gets 6th no matter what they write.
  3. Will write $5$ to get 2nd instead of 5th.
  4. Gets 5th no matter what.
  5. Writes $8$ to win.

Final order assuming $A$ goes first in a 7 person game is $ECFADBG$.

8 Player Game

Players are $A,B,C,D,E,F,G$ and $H$. The following are the results for player $A$ if player $A$ writes the following numbers:

  • $9$: Finish 7th. $B$ is eliminated, and the remaining players in order to start the final round are $CDEFGHA$. Final order will be $GEHCFDAB$.
  • $8$: Finish 3rd. $B$ would write $9$ and finish 7th. Final: $HFADGEBC$.
  • $7$: Finish 1st. $B$ would write $8$ and finish 3rd. Final: $AGBEHFCD$.
  • $6$: Finish 5th. $B$ would write $7$ for the win. Final: $BHCFAGDE$.
  • $5$: Finish 5th. $B$ writes $6,7$ for the win. Final: $BHCFAGDE$.
  • $4$: Finish 2nd. $B$ gets 5th. Final: $CADGBHEF$.
  • $3$: Finish 6th. $B$ writes $4$ for 2nd. Final: $DBEHCAFG$.
  • $2$: Finish 6th. $B$ writes $3,4$ for 2nd. Final: $DBEHCAFG$.
  • $1$: Finish 4th. $B$ gets 6th. Final: $ECFADBGH$.

To win the 8 person game, you want to be the 5th player to go.

  1. Will write just $1$ since 4th place is better than 6th.
  2. Gets 6th no matter what they write.
  3. Will write $4$ to get 2nd instead of 5th.
  4. Gets 5th no matter what.
  5. Writes $7$ to win.

Notice the strategy is identical to the 6 person game and very similar to the 7?

Final order assuming $A$ goes first in a 8 person game is $ECFA DBGH$.

9 Player Game

Players are $A,B,C,D,E,F,G,H$ and $I$. The following are the results for player $A$ if player $A$ writes the following numbers:

  • $9$: Finish 8th. $B$ is eliminated, and the remaining players in order to start the final round are $CDEF GHIA$. Final order will be $GEHC FDIAB$.
  • $8$: Finish 7th. $B$ would write $9$ and finish 8th. Final: $HFID GEABC$.
  • $7$: Finish 3rd. $B$ would write $8$ and finish 7th. Final: $IGAE HFBCD$.
  • $6$: Finish 1st. $B$ would write $7$ for 3rd. Final: $AHBF IGCDE$.
  • $5$: Finish 5th. $B$ writes $6$ for the win. Final: $BICG AHDEF$.
  • $4$: Finish 5th. $B$ writes $5,6$ and wins. Final: $BICG AHDEF$.
  • $3$: Finish 2nd. $B$ gets 5th. Final: $CADH BIEFG$.
  • $2$: Finish 6th. $B$ writes $3$ for 2nd. Final: $DBEI CAFGH$.
  • $1$: Finish 6th. $B$ writes $2,3$ for 2nd. Final: $DBEI CAFGH$.

To win the 9 person game, you want to be the 4th player to go.

  1. Gets 6th.
  2. Writes $3$ for 2nd place.
  3. Gets 5th no matter what.
  4. Writes $6$ to win.

Notice that player $I$ doesn't even get to play in the first round!

Final order assuming $A$ goes first in a 9 person game is $DBEIC AFGH$.

10 Player Game

Players are $A,B,C,D,E,F,G,H,I$ and $J$. The following are the results for player $A$ if player $A$ writes the following numbers:

  • $9$: Finish 4th. $B$ is eliminated, and the remaining players in order to start the final round are $CDEFG HIJA$. Final order will be $FDGAE CHIJB$.
  • $8$: Finish 9th. $B$ would write $9$ and finish 4th. Final: $GEHBF DIJAC$.
  • $7$: Finish 9th. $B$ would write $8,9$ and finish 4th. Final: $GEHBF DIJAC$.
  • $6$: Finish 8th. $B$ gets 9th. Final: $HFICG EJABD$.
  • $5$: Finish 7th. $B$ writes $6$ for 8th. Final: $IGJDH FABCE$.
  • $4$: Finish 3rd. $B$ writes $5$ for 7th. Final: $JHAEI GBCDF$.
  • $3$: Finish 1st. $B$ writes $4$ for 3rd. Final: $AIBFJ HCDEG$.
  • $2$: Finish 5th. $B$ writes $3$ for 1st. Final: $BJCGA IDEFH$.
  • $1$: Finish 5th. $B$ writes $2,3$ for the win. Final: $BJCGA IDEFH$.

To win the 10 person game, you want to be the 2nd player to go.

  1. Gets 5th no matter what they do.
  2. Writes $3$ for the win!

Neither $I$ nor $J$ get to actually play in the first round and $H$ is eliminated in the first round.

Final order assuming $A$ goes first in a 10 person game is $BJCGA IDEFH$.

Addendum

This can be extended indefinitely for groups of size $N$, but only by working out the solution for $N-1$ first. There does not seem to be a trivial formula suggested by this that can get you the solution for an arbitrary $N$ without knowing the intermediate results.

This solution, however, is very useful for every player of the game. It provides a quick lookup to see what your best move is at any stage of the game. For example, if I have survived until the round of 5 players and am presented with a $7$, I know that writing $8,9$ will get me a 2nd place finish if everyone else plays perfectly. If only one person doesn't play perfectly, then I may not do better than 2nd, but that player will definitely finish worse if the rest of the players play perfectly. This solution can continue to provide optimal responses even if things do not go according to plan.

$\endgroup$
  • $\begingroup$ Yes, but what about 10 players $\endgroup$ – warspyking Jan 28 '15 at 18:33
  • $\begingroup$ @warspyking Getting there... $\endgroup$ – Trenin Jan 28 '15 at 18:43
  • 1
    $\begingroup$ @warspyking Do you mean 10 players with the original rules of "no loss being better/worse than any other"? If so, then there is no strategy to win in that case because you have even more people who have no motivation to play along. If you mean a ranking where finishing second is better than third, then that is what I am working on. $\endgroup$ – Trenin Jan 28 '15 at 19:18
  • $\begingroup$ Well done. With more players it becomes more of a mess. I suspect you will reach a point where the strategy gets undefined because you just don't have enough control, but maybe not. $\endgroup$ – Ross Millikan Jan 28 '15 at 19:33
  • $\begingroup$ @warspyking Finished! Going 2nd in the 10 person game gets you the win. $\endgroup$ – Trenin Jan 29 '15 at 15:22
6
$\begingroup$

If only 2 people play, the person starting can always be forced to lose. Say 1 number if he says 2, and 2 if he says 1.

If there are 3 people, you would want to eliminate the person immediately after you (and win via the rule above). This would be the easiest for one of the three positions.

If there are 4 people, you would want to eliminate a person such that your position in the above scenario is optimal. This will again the easiest in one of the 4 positions.

Continue this way to 10 players. There is a programming concept called minimax game tree that can be used, as manually solving till 10 players is a lot of work. There is also a wikipedia page on 'Nim', it may or may not be of any use.

Note that none of them can play perfectly, but they all have an independent optimal play. Luck will play some role. If players are willing to team up to defeat the remaining players, the strategy depends on who makes the best (maybe perfect) agreements.

$\endgroup$
  • $\begingroup$ Make sure to check new clarification. $\endgroup$ – warspyking Jan 28 '15 at 16:57
  • $\begingroup$ That only works if the players want to finish higher. If all losses are equal (i.e. losing to you now or losing in a later round is still a loss), there is no motivation for anyone to play along with your strategy, hence there can be no strategy. However, if the players prefer high placings (even if they are losses) to lower placings (i.e. earlier losses), then you can make a strategy: go second in the round of 10 to win. $\endgroup$ – Trenin Jan 29 '15 at 17:42
2
$\begingroup$

Ok, let's say that the group is aggressive as possible about eliminating players, but wants to preserve their spot.

Player 6 will be eliminated first, then player 2. Neither can stop it.
The next player to be eliminated is player 9, who is unable to stop it either.

So, we have 10, 1, 3, 4, 5, 7, 8. With the same strat, player 7 would be eliminated, followed by player 5.
Now, player 5 is the first player who can really throw a wrench into this. If player 2 wants to preserve themselves, they'll go with 1 (first round), and at that point player 5 goes 1 as well (instead of 2), forcing player 6 into 1, taking out 7. (2-1-2-2-1-1).
Next player to be eliminated would be 3 then, followed 10.

At this stage you have 1, 2, 4, 5, 6, 8, 9. Player 8 gets eliminated, followed by player 6. Now, at this point in time, could 6 or 8 have done anything to shift the eliminations? Round 1, no, round 2, yes, with 8. Instead of offing 10, player 1 gets eliminated.
2, 4, 5, 6, 8, 9, 10. Player 9 gets eliminated, and can't change the outcome. Then 8.

Now you are left with five people: 10, 2, 4, 5, 6. At that point it's kind of a game of chicken.

Old:
I don't think there's a perfect play for this game. Generally, there's a perfect play to eliminate someone.

Let's say you are player 1, and everyone else wants to get you out.
1-2-2-2-2 Eliminates player 6 (players 6-9 can be eliminated at will the first pass)
From there 2-2-1-1-2-1 eliminates player 3
Then 2-2-1-1-1-1-2 eliminates player 1

Let's say we want to eliminate player 2
2-(1/2)-2-2-(2/1) gets player 6
Then 2-2-2-2-1 would get player 2

$\endgroup$
  • $\begingroup$ See new clarification. $\endgroup$ – warspyking Jan 28 '15 at 16:54
0
$\begingroup$

A point to make and solution:

First, your strategy depends on your starting position. If you're Friend J (10th friend), then no matter what strategy you have, you can get stuck with 10 if everyone writes only one number. Similarly, you'll probably need a different strategy if you're friend #9 versus friend #8, etc.

If you do know what position you are, you can try this solution:

Work backwards from your intended win. This is easiest to see with two people remaining. Let's say there are two people left, A and B. The person who says 1 or 2 will lose. The reason is that the person that comes after can make the total after their turn a multiple of 3. Let's say A says 1. B can say 2 numbers (2,3) to make the total 3. If A says 4,5 then B will just say 6. Then whatever A says, B says whatever makes the count to 9 forcing A with 10. Now if there are three people left, use a similar logic to try to have the person eliminated when your rival will be the one coming next. An example would be if you are A, you want B to be eliminated right after you go. You would try to get to a position where you can write 9 so B has to write 10 and C will be forced to write 1 or 2. By extending this thought process you can go to any number of people.

$\endgroup$
  • $\begingroup$ Don't think you can extend it because there is no motivation for the other players to play along with your strategy. Even in the 2 person game, there will be one winner and 2 losers. Being the first loser is equivalent to being the second loser, so there is no need to play one way or the other for that player's own personal gain, but it will greatly affect the other players. $\endgroup$ – Trenin Jan 28 '15 at 18:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.