After the results of an election, you are told that one candidate has received the majority of the votes, but you don’t know which candidate. You have exactly one opportunity to hear the votes, but:
- The list of votes is very long
- The votes will be announced one after another in random order
- You have a poor memory (can only remember a couple of names or numbers)
- You are not allowed to write or record anything
Given these restrictions, is there a way figure out which candidate received the majority of votes?
Solution
Yes, there is a method that can determine the candidate with the majority of votes, and it only requires remembering one name and one number at a time!
- Start with the first voted candidate.
- Every time that candidate gets a vote, increase the counter by 1, otherwise decrease the counter by 1. Whenever this counter is positive, it means this candidate has received the majority of votes up until this point.
- If and when the counter reaches 0, restart from the first step using the next voted candidate.
- The candidate that is tracked at the end is the candidate with the majority of votes.
This works because when the counter reaches 0, none of the candidates have a majority of votes up until that point, which means the candidate with the overall majority of votes must still have a majority of votes in the remaining list of votes.
This method is known as the Boyer-Moore majority vote algorithm.
What counts as recording something? For example, could I take a step to the left every time candidate X is called, and a step to the right every time candidate Y is called?
Right, any method of recording something is invalid, whether that is stepping to the side, pulling out a hair, throwing something, etc. You can only rely on remembering a small number of names or numbers.
I doubt the correctness of the solution. If we have 3 candidates (#1, #2 and #3) and the sequence is 11111222223313, the answer using this Boyer-Moore algo will be 3 instead of 1.
The key is the puzzle specifies the winner received a *majority* of the votes (> 50% of all votes), not just a plurality (more than any other candidate).
So your example wouldn’t be a valid situation for this puzzle, as there are only six 1’s out of fourteen votes. If there were eight 1’s out of fourteen votes instead, there is no arrangement that reduces the count of 1’s to zero, unless the remaining votes also contains a majority of 1’s.