A test of Survival

Question

In the American TV series Survivor, there was once a game in which the participants were divided into two teams,say A and B. The team which removed the last flag was declared the winner.There were 25 flags with the teams allowed to remove 1,2 or 3 flags at each try with A starting first. Also, if one team has no chances of winning, it always chooses the maximum number of flags.

If optimum play is assumed, which team wins? What if there were $n$ flags?

Bonus question: What will happen if we increase the number of teams to 3? How will the winning chances of A and B be affected?

Answer 1

The well-known answers to the first questions are:

The second player can always make his move so that the sum of both players' moves is 4. Therefore, for $n = 4k$, the first team loses, for all other $n$, first team moves to a multiple of 4 and wins. In particular, for 25 flags and optimal play, team A starts by removing one flag and wins.

Since no one answered the modified bonus yet:

First, note that who wins in any given position is determined by who wins in the positions with 1,2 or 3 less flags (since A will choose his move based on this). If A can move and leave a position in which the third player wins, they will do so, otherwise they will remove 3.

- For $1 \le n \le 3$, A wins.
- For $4 \le n \le 6$, A can't move to a C-winning position, so A removes 3 and B wins.
- For $n = 7$, C wins. A still can't win, and leaves 4 to B, who has to hand the win to C.
- For $8 \le n \le 10$, A moves to the C-position 7 and wins.

The winners for $1 \le n \le 3$ and $8 \le n \le 10$ are the same, so we have reached a cycle. In this case, A wins for $n \in \{7k + 1,7k+2,7k+3\}$, B wins for $n \in \{7k+4,7k+5,7k+6\}$ and C wins for $n=7k$.

Answer 2

You can always easily arrange

that your opponent's move, followed by yours that follows, removes a total of 4 flags.

Therefore,

if the number of flags is not a multiple of 4 you can use your move to make it a multiple of 4, and from then on your opponent can never (and you will always) reduce the number to a multiple of 4. In particular, it must be you rather than your opponent who takes the number down to 0.

So

with 25 flags, the first player (in this case A) will win; with n flags, the first player will win if n is not a multiple of 4 and the second player if n is a multiple of 4.

[EDITED to add: The following remarks about the 3-player version of the game were written before the OP changed the question to specify that a player who will definitely not win takes the maximum number of flags. Presumably we are to understand that this policy is common knowledge too. This of course invalidates what I wrote below.]

I think the main thing to say about the 3-player version is this:

The player who wins may not be completely determined given only that each player maximizes their own winning opportunities, because there might be situations where A can't win but can choose whether B or C wins (e.g., this is the case if it's A's turn and there are exactly 5 flags remaining: if A removes 1 then C will win, else B will). So the result depends on each player's preferences between the other players.

Let's be more specific. I'll call the players 0,1,2 and suppose 0 has just played and 1 is about to. We can see, considering successively larger numbers of flags, that

with 0 flags, 0 has just won
with 1-3 flags, 1 is about to win
with 4 flags, 2 will win
with 5 flags, player 1 chooses between 0,2 winning
with 6 flags, 1 will take one and then 2 chooses between 0,1 winning (the other options lead to situations where 1 will definitely not win)
with 7 flags, if 1 takes one then 0 chooses between 1,2 winning; if 1 takes two then 2 chooses between 0,1 winning; 1 will not take 3 because then 0 definitely wins

and so, in particular,

the winner even for rather small n may depend on something as subtle as whether player 1 thinks it more likely that 0 prefers 1 over 2, or that 2 prefers 1 over 0.

As n increases

the outcome will depend on increasingly multi-level considerations about whether A expects B to expect C to expect A to prefer B to C, etc. I'm pretty sure that for $n\geq7$ there are possible scenarios where any given player wins (even though in each such scenario, no player ever makes a choice that's unambiguously worse than another they could have made).

Answer 3

For 1 vs 1

no matter the n, the one who starts will always win by keeping the increase of 4 per round. The ultimate goal is that after your turn, the opponent is stuck at n-4 flags left.

For 3 players

There is no sure way for anyone to win, even with optimal play. But the second player is sure to lose. If a player plays optimal and makes the last round start at n-5 flag, the second player is basically screwed, and nothing stops him from taking 2 or 3 flags which would make the third player win, or just 1 to make the first player win, either way the second player will lose so no move will be optimal for him.

Answer 4

Let's number the flags 1 to 25.
And your can start removing from 25 to 1.
Specific answer: $N=25$.

Who removes flag 5 will remove flag 1 also no matter how many flags the other team removes. If team A removes flag 5, there are 4 left and the team B can leave 1, 2 or 3 flags. In each case team A can pick flag 1.
Who removes flag 9 will get to remove flat 5 also, hence flag 1 based on the same logic.
Going on this logic....
You have to remove flags, 5,9,13,17,21,25 So if team A starts, they should just remove 1 flag (#25) and follow the logic above and they will win for sure.

General for any $N$.

Always remove any flag numbered $4\times K+1$.
If there are N flags, team A wins if $N \neq 4 \times K$ and loses otherwise.

Bonus question.

Let's say it's A's turn to pick.

There are 4 flags left, A is a loser for sure so A picks 3 and B wins.
There are 5 flags left, A picks 1 and makes B the sure loser (case above). If they pick 2 or 3, B wins, so A is a loser for sure. So A has to pick 3.
There are 6 left, A picks 1 and make B the loser for sure (case above), So B has to pick 3 and C wins, this makes A a sure loser. If A picks 2, same thing happens. B is sure loser, C wins. If A picks 3, B wins, so in any case A is the sure loser so they have to pick 3 and B wins.
There are 7 left. A picks 1, B has to pick 3 (case above) and C wins. Same goes for A picks 2. So A is again the sure loser So they have to pick 3. In this case C wins.
There are 8 left. A picks 1, B has to pick 3 (case above) and C has to pick 3 (from the 4 left) and A wins.
There are 9/10 left. A picks 2/3, B has to pick 3 (case above) and C has to pick 3 (from the 5 left) and A wins.
There are 11 left. A picks X and makes B the winner because of the 2 cases above. So A is the loser for sure, so they have to pick 3 and B wins.
There are 12 left. A picks 1 and makes puts B in the case above so C wins. For A picks 2 and 3 B wins (cases above). So A picks 3 and B wins.

Postulating:

Still trying to find a formula.

Below is the original answer before I know what happens with the losing team.
Case 1: Alliances (yeah, that's why you watch Survivor )

If alliances are formed and you are not in an alliance you are screwed for sure.
Let's say you are on team A and B & C form an alliance, A always loses.
in order to make sure A picks #1, A has to pick #4, but here are the possible cases:
If there are 6 left after your pick, B + C pick all of them (3+3).
If there are 7 left after your pick, B picks 1 + C picks 1 so there are 5 left and you don't get a chance to play next round because B + C can pick them up.
If there are 8 left after your pick, B+C pick 3 and you end up as above.
If there are 9 left after your pick, B+C pick 4 and you end up as above.
If there are 10 left after your pick, B+C pick 5 and you end up as above.
If there are 11 left after your pick, B+C pick 2 and you are left with 9. You can bring the total down to 6,7 or 8 and you are in one of the cases above. So you lose.

Case 2: No alliances (bhuuuu).
Assuming that a losing team will just pick at random when they are sure they will lose.

Who ever picks #5 is sure of losing because the second one after you will pick #1 no matter what the first after you picks.
If there are 6 flags left, you (team A) pick 1 and you have a 33% chance of winning (if B picks 1 because B will choose at random 1 2 or 3 because they know they are going to lose).
If there are 7 flags left, you (team A) pick 1 and you have a 67% chance of winning (B will be in the case above and will choose 1 because a 33% chance is better than none, and C will be the loser for sure).
If there are 8 flags left, you (team A) pick 2 on the same logic as above.
If there are 9 left, you pick 3 on the same logic as above.
If there are 10 left just pick at random because you are going to lose. What ever you choose, B will be in one of the cases above for 9,8 or 7 and they will pick to leave it at 6, C will pick 1 to leave it at 5 not to be the sure loser and you will lose.

Conclusion:

Based on the same logic, you don't want to be left to pick when there are $5 \times K$ flags left because you are the loser for sure.
Who picks when there are $5 \times K$ left has a 0% chance of winning.
Who picks after the person above has 67% chance of winning.
The third team gets the rest of 33%.
So if A goes first with 25 flags, they lose for sure, B wins in 67% of the cases and C in 33%.

I hope I didn't miss anything in the logic.

Answer 5

Just as a general answer, if there are $2$ teams playing optimally, $F$ flags and each team is allowed to remove $1$ to $N$ flags, the winner is:

The first team if $N+1\nmid F$, and the second team if $N+1\mid F$.

This is because:

In the first case, the first team can always remove some number of flags such that the remaining number of flags is divisible by $N+1$, and the second team cannot after such a move, and $0$ is divisible by $N+1$. The second case is the same, just with the teams switching roles.