The democratic pirates are at it again! Since last time, they have become very successful and have now expanded to 100 pirates. They decide this is too large of a group for plundering, so true to their democratic roots, they want to settle it with a vote:
- They vote on whether to kick out the newest (least senior) pirate.
- If a majority votes “aye”, then the newest pirate is kicked out, and the process repeats with the remaining pirates.
- If half or more of the remaining pirates vote “nay”, then the vote is over and everyone remaining is safe.
Each pirate wants to stay in the group, but if that is assured, they would prefer to kick out as many other pirates as possible (fewer ways to split the treasure).
How many pirates will remain at the end of this process?
Solution
64 pirates
A good approach to many logic puzzles is to work backwards from the simplest scenario.
The most senior pirate (pirate 1) is always safe, and will therefore always vote to kick.
Pirate 2 is always safe since their own vote is enough to keep them safe when only two pirates are left, and will therefore always vote to kick.
Pirate 3 is not safe, since the first two will vote to kick when only three are left. Therefore pirate 3 will try avoid the situation with only three left.
Pirate 4 is safe, since pirate 3 is at risk if pirate 4 is kicked, so pirate 3 will vote “nay” and pirates 3 and 4’s two votes are enough to keep pirate 4 safe.
From this, we can deduce a pattern of “safe” numbers. When you have a “safe” number, all subsequent numbers are “unsafe” as long as those “safe” pirates outnumber the “at-risk” pirates. In other words, subsequent numbers are “unsafe” until the number of “at-risk” pirates equals the previous number of “safe” pirates (i.e., 2x the previous “safe” number). Put another way, the “safe” numbers are 2k because to prevent pirate 2k from being kicked, pirates 2k-1+1 through 2k-1 will vote “nay” (if pirate 2k is kicked, they will be outnumbered by pirates 1 through 2k-1).
The largest “safe” number before 100 is 28 = 64.