Hey, this is Presh Talwalkar.
On the TV show Survivor,
contestants faced off in a winner take all competition
to try and win one million dollars.
Most of the competitions were physical,
like hiking many miles or diving underwater,
but one of the challenges was mathematical.
It involved 21 flags.
The contestants were divided into two teams that would take turns removing flags.
Each team has to remove 1, 2 or 3 flags on a turn.
The team that removed the final flag wins the game.
Mathematically one team can always win this game.
The puzzle for you is which team is it and what is that team's winning strategy.
Give this problem a try and when you're ready keep watching the video for the solution.
So what's the winning strategy when there are 21 flags?
It's not so easy to figure out,
instead we consider the game by thinking ahead and reasoning backward.
We try and imagine what would happen if we'd start a turn with a specific number of flags,
and we would decide whether we can win or lose the game on that turn.
So let's say there's just one flag.
If you start out with one flag, you can obviously pick up that flag and you will win the game for sure.
This goes for if there are 2 flags you are gonna win the game, and if there are 3 flags you are gonna win the game.
With this number of flags you can just pick them all up and you're going to be the one that removes the last flag.
But what happens if there are 4 flags?
Well you can pick up 1, 2 or 3 flags on your turn.
If you pick up 1 flag you leave 3 flags for the other team and the other team is gonna pick up all 3 flags,
if you pick up 2 flags you'll leave 2 flags for the other team,
but they again can pick up all of those flags.
If you try and pick up 3 flags you still leave 1 flag for the other team and they can pick it up and win the game.
What this means is if there are 4 flags in front of you no matter what you do you are going to lose this game.
You are going to leave a number of flags that your opponent can pick up on the next turn.
What would happen if there are 5 flags?
In this case you could pick up 1 flag and leave 4 flags for your opponent,
now your opponent is necessarily going to lose,
which means you are necessarily going to win.
Similarly if there are 6 or 7 flags.
You could pick those up and leave 4 flags for your opponent,
this would mean that your opponent is going to lose.
So this means 6 or 7 flags is also a winning number of flags.
What would happen if there are 8 flags?
On this case if you try and pick up 1, 2 or 3 flags, no matter what you do you're going to leave a winning number of flags for your opponent.
This means if there are 8 flags you are necessarily going to lose the game if your opponent plays correctly.
We can now see a pattern in what we've developed,
if the number of flags is a multiple of 4 you are going to lose the game if your opponent plays perfectly.
So we can continue this list and we can have the number of flags for when you're going to lose the game and
the number of flags for when you're going to win the game.
You can notice that 21 is in the numbers of flags for which you can win the game.
So if the game starts out with 21 flags,
that means the first team that picks up flags can win this game for sure.
By always picking up flags and leaving a multiple of 4 for the other team.
So the first team that picks up should win this game.
But let's consider what actually happened on TV.
We'll compare the optimal move to what the 2 teams could have picked up.
The first move the first team should have picked up 1 flag leaving 20 flags for the other team.
Instead they picked up 2 flags leaving 19 flags for team B.
So if team B picked understood the winning strategy,
they could now pick up 3 flags which would leave 16 flags for team A.
Instead team B also picked up 2 flags and left 17 flags.
This gives team A an opportunity to redeem itself,
they can now pick up 1 flag and be in a winning position.
What they did instead is they picked up 2 flags leaving 15.
So now team B if they picked up
3 flags they're gonna be able to leave 12 for team A,
and they're gonna be able to win the game.
What did team B do at this point?
They made another mistake! They picked up 1 flag, leaving 14 flags for team A!
Team A could pick up 2 flags and be again in a winning position,
but they made another mistake! They only picked up 1 flag here and they left 13 flags.
Team B finally makes a winning move here!
they pick up 1 flag and they leave 12 flags.
So team B is in position to win this game as long as they play correctly the rest of the way.
So team A at this point has no choice, they pick up some number of flags,
if team B plays properly,
team B is gonna win the game.
So when there're 11 flags left team B should pick up 3 flags,
to leave 8 flags for team A.
But team B messes up again!
Here they only pick up 2 flags which leaves 9 flags for team A.
So team A could redeem itself by picking up 1 flag and leaving 8.
Instead,
they make a big mistake here and pick up 3 flags which leaves 6 flags for team B.
Now with 6 flags remaining, team B is able to reason out the winning strategy.
So they do correctly pick up 2 flags here and leave 4 flags for team A.
This was actually shown on the TV show that they are discussing that they should leave 4 flags for the other team.
At this point team A realizes
that they can not win the game.
So they gracefully pick up 3 flags which leaves 1 flag for team B to pick up.
So there were many mistakes in the way the teams played.
We shouldn't judge them too harshly because they didn't have too much to figure this out.
But if you find yourself in such a situation on the game show,
you should always be able to figure out the optimal move.
Did you figure out this problem?
Thanks for watching this video, please subscribe to my channel, I make videos on math and game theory.
You can catch me on my blog "mind your decisions" which you can follow on facebook, google+ and patreon.
you can catch me on social media @preshtalwalkar.
and if you liked this video please check out my books, there are links in the video description.