3
$\begingroup$

Suppose I'm forced to enter the game of nim with two players who are perfectly logical people. The rules is simple:

  1. We play a set number of rounds.
  2. In every round, a random number of marbles (between 25-40) are put inside the box, but the contents of the box will always be visible during the duration of the round.
  3. The first player will takes the box and can take 1, 2, or 3 marbles from the box. After that, he/she must pass the box to second player.
  4. The second player can also take 1, 2, or 3 marbles from the box and must pass the box to third player.
  5. The third player will do the same thing and the round will continue until someone takes the last marble. When that happens, the round ends.
  6. The player who takes the last marble loses 1 point and the last player who successfully passes the box gains 5 points. (Ex. If third player takes the last marble, second player will gains 5 points and third player will loses 1 point.)
  7. After a set number of rounds have been played, the player with the most points wins the game.

The problem is that I will go second in every round.

What is the strategy I must take to maximize my score and what is the minimum number of rounds to be played so I will be guaranteed to win the game, if possible?

$\endgroup$
3
  • $\begingroup$ When you say he "may takes 1, 2, or 3 marbles from the box", do you mean that he may but need not? $\endgroup$
    – msh210
    Oct 8 at 11:03
  • 5
    $\begingroup$ Is each person trying to maximize their own point gain, or are they simply trying to make you lose? $\endgroup$
    – PiGuy314
    Oct 8 at 11:42
  • 2
    $\begingroup$ Three-player games are tricky to evaluate. For example can the other two players collaborate against you? $\endgroup$ Oct 10 at 11:29
2
$\begingroup$

If everyone is trying to maximize their points:

If it was played between two players, Player 1 would have to leave one marble. They can't leave 2, 3 or 4 marbles, because then P2 could later reduce it to 1. If P1 loses a game of $n$ marbles, they win the $n+1, n+2, n+3$ games, because they can leave an $n$ game to P2, who will be the P1 of this game. An $n+4$ game will be lost, because P2 could always reduce it to an $n$ game. This means P1 must always leave $4k+1$ marbles to P2 to win.

In this more complicated version, if PX loses a game of $n$ marbles, that means PX-1 wins the $n+1, n+2, n+3$ games by leaving $n$ marbles to PX. If PX wins such a game, PX+1 loses it, so P2 loses them.

An $n+4$ game is won by P2 and lost by P3, because P1 is always forced to reduce it to an $n+1, n+2$ or $n+3$ game for P2 to be its P1.

P1 also avoids losing $n+5, n+6$ games by reducing them to an $n+3$ game for P2 to be its P1. P2 wins, P3 loses.

$n+7$ is lost by P1, who can only reduce it into a game where P3 loses. It's won by P3 instead.

To summarize, P2 wins if the game is played with $7k+5, 7k+6$ or $7k$ marbles through making P3 lose by always leaving them $7k+1$ marbles, and avoids losing if it begins with $7k+1$ marbles through helping P3 win by leaving them $7k+2,7k+3$ or $7k+4$ marbles. The rest are losses.

Unfortunately, we'll never be guaranteed to win the game when P1 wins $7k+2,3,4$ games, and only outright loses at $7k+1$ games.

If both of your opponents work together to minimize your chances to win the game itself:

You can NEVER win a point, let alone the entire game. If an $n$ game is won by P1, so will an $n+5$ game, because it can be reduced to the former in three turns if P1 and P3 play their cards right. The 2, 3 and 4 games are won by P1 with 1, 5 and 6 lost, so only $5n+0$ and $1$ games give you a chance, but they can also be reduced to a winning game if P1 takes 2 and 3 in the first turn, respectively. Except 1, 5 and 6 marble games, but the number of marbles in the range is much greater then them anyway.

$\endgroup$
1
$\begingroup$

First of all:

Between any two of your turns, there will be between 2 and 6 marbles drawn from the box. (1-3 marbles for each person)

Taking this:

If at any point there are between 2 and 4 marbles, the person whose turn it is can force a win. (Let's assume person $A$) And with 5 marbles, no matter what $A$ does, $B$ can force a win on his next turn.

With more marbles:

Logic becomes harder to work with. With 6 marbles, $A$ has two options: if he takes 2 or 3 marbles, the logic is just as above, and $B$ wins. However, if he takes 1 marble, $B$ is left with 5, and $C$ wins, causing $A$ to lose a point. This means that if there are 6 marbles and it is $A$'s turn, $B$ wins.

Following that logic:

We can continue to do this up until we reach all the numbers 25-40. Analyzing who wins given each starting position, we can calculate the optimal moves for you when playing the game. For 7 marbles, $A$ can leave 6, 5, or 4 marbles for $B$. If $A$ leaves 6 or 5, $C$ wins. So $A$ leaves 4, causing $B$ to win again.

List of winners:

(Given $A$'s turn) 1: $C$; 2, 3, or 4: $A$; 5, 6, or 7: $B$;

Patterns:

Every 3 additional marbles that are added, the next person would win the game. So 8-10 result in $C$ winning, 11-13 result in $A$ winning, and so on.

Applying to the problem:

25 results in $B$, 26-28 results in $C$, 29-31 results in $B$, 32-34 results in $C$, 35-37 results in $A$, and 38-40 results in $B$. This means that in 7 of the 16 starting numbers, you will win, giving you a $43.75\%$ chance to win a given round.

Minimum rounds:

As this is a game involving chance, you will never be guaranteed to win. However, as you have the highest probability out of the players to win any round, the more rounds that you play, the higher your chances are to win overall.

$\endgroup$
3
  • 1
    $\begingroup$ Not sure about your "With more marbles" step. It's not clear to me that A should always let B win in the 6 marble case. As the winner is determined over multiple rounds, if A and B are close in score, and C is a long way behind, it would be better for A to take a one point loss by letting C win, rather that let B take the five point gain. $\endgroup$
    – fljx
    Oct 8 at 15:38
  • $\begingroup$ I also think so. And generally when one player is ahead, the others will ally to make that player loose. $\endgroup$
    – Florian F
    Oct 10 at 10:28
  • $\begingroup$ Very good points $\endgroup$
    – PiGuy314
    Oct 11 at 19:53

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.