Problem of Serkanus
All the participants sit down on a round table that has ascending numbers on it. Last person sitting is the winner and claimer of the magnificent banana cake.
Game can have as many players as wanted.
When players sit, each and every one of them gets a number between 1 and the #of players.
Elimination always starts from player 1 and goes clockwise.
Every second player gets eliminated. In other words, if it is your turn, you’ll eliminate the person who is after you in clockwise direction.
Game 1: One player.
It means that there is only one player who is the winner naturally.
Game 2: Two players.
There are two numbers at the table: 1 and 2. Player 1 starts eliminating the player that is on his/her clockwise direction. This means player 1 eliminates player 2.
Since there is no other player left, player 1 claims victory.
Game 3: Three players.
There are 1, 2 and 3 sitting at the table. Game starts with player 1 eliminating player 2. Now it is player 3’s turn.
Player 3 eliminates the player that sits on his/her clockwise direction. That means player 1 is eliminated and player 3 is the last one sitting at the table.
Game 4: Four players.
Numbers 1, 2, 3 and 4 are sitting at the table. Player 1 starts the game with eliminating player 2. Now it is player 3’s turn and he/she eliminates player 4 who is sitting on the clockwise direction.
It is clear to see that only player 1 and 3 are left at the table and it is player 1’s turn to make a move. Player 1 eliminates player 3 and claims him/herself as the owner of the cake.
Game 5: Five players.
Player 1 eliminates player 2 and player 3 eliminates player 4. After these moves, it is player 5’s turn and he/she eliminates player 1 who is sitting at the clockwise direction.
Finally player 3 and 5 are left alone. Since it is player 3’s turn, player 5 gets eliminated. Hence player 3 wins the game.
Game 6: Six players.
Player 1 eliminates 2, 3 eliminates 4 and 5 eliminates 6.
In the second tour there are only 1, 3 and 5 left at the table and it is player 1’s turn.
Player 1 eliminates player 3.
Now it is player 5’s turn and he/she will eliminate player 1 to claim the righteous owner of the cake.
Game 7: Seven players.
Player 1 eliminates 2, 3 eliminates 4 and 5 eliminates 6 which gives player 7 right to eliminate.
Second tour at the table starts with Player 7 eliminating player 1 and player 3 eliminating player 5.
It the third tour it is again player 7’s turn and he/she eliminates the only player left: Player 5. That means player 7 wins the game.
Game 8: Eight players.
In the first tour player 1 eliminates 2, 3 eliminates 4, 5 eliminates 6 and 7 eliminates 8.
Second tour begins with player 1 and players 3, 5 and 7 are the ones who survived the first tour. Player 1 eliminates 3 and 5 eliminates 7.
Now only player 1 and 5 left at the table and it is player 1’s turn which makes him/her the victor.
Game 9: Nine players.
In the first tour player 1 eliminates 2, 3 eliminates 4, 5 eliminates 6 and 7 eliminates 8 which means player 9 will be starting the second tour.
In the second tour player 9 eliminates 1 and 3 eliminates 5. This means it is player 7’s turn.
Player 7 eliminates player 9 which leaves player 3 and player 7 are the survivors. But since it is player 3’s turn, he/she will win the game with eliminating player 7.
Game 10: Ten players.
In the first tour player 1 eliminates 2, 3 eliminates 4, 5 eliminates 6, 7 eliminates 8 and 9 eliminates 10. Player 1, 3, 5, 7 and 9 will advance to the second tour.
Second tour starts with player 1 eliminating 3 and player 5 eliminating 7. Now it is player 9’s turn who will eliminate player 1.
Finally, player 5 and 9 are left at the table and player 5 eliminates player 9.
Let’s make a table and find out which player won in the first ten games.
This table tells us really interesting facts. First of all, you probably realized that there is no chance for an even numbered player to win the game. In fact, they always get eliminated in the first tour. If you are a good observer, you might find two patterns in this table:
First one is the whenever number of players and winner of the game has the same number, in case you add one more player to the game player 1 will win. Here lies the second pattern which is (if you exclude 1 player game) winners of the games will have odd ascending numbers until number of player will be equal to the number of winner. Check after game 3:
Winner of game 4 is player 1.
Winner of game 5 is player 3.
Winner of game 6 is player 5.
Winner of game 7 is player 7. They are equal so winner will be player 1 in the game 8.
If these two patterns are true, then we can write down on paper who will win in the next games even without playing the game. When it is applied it turns out the winner of game 15 is player 15. If our pattern is correct then winner of game 16 must be player 1.
Let’s check it out:
In the first tour players 2, 4, 6, 8, 10, 12, 14 and 16 will get eliminated.
Since it will be player 1’s turn, players 3, 7, 11 and 15 will get eliminated in the second tour.
Now only players survived are 1, 5, 9 and 13. It is player 1’s turn in the third tour as well, so players 5 and 13 get eliminated.
In the forth tour only survivors are 1 and 9 with player 1 has the right to start. Player 9 gets eliminated.
Player 1 claims that he/she is the king of 16 players!
In other words: We have found a pattern that works!
This is a famous problem that is named after Flavius Josephus, an important figure in the Jewish history who lived in the 1st century AD.
Story is kind of a myth which was supposedly lived during the Roman-Jewish war. Josephus was trapped in a cave with his 40 soldiers and they were at the mercy of Roman army. Those 41 men had two choices: Surrender or commit suicide. They decided to commit suicide but Josephus his friend thought it was nonsense and therefore he quickly found a solution.
He convinced all men to make a circle. He suggested that when it is his turn; every man should kill the man who is third in the clockwise position. Josephus thought if they could be in the right position, he and his friend would be the last ones survived in the circle.
Question is: Where should Josephus and his friend locate inside the circle of 41 men?
M. Serkan Kalaycıoğlu