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.
One reply on “Majority Vote Puzzle”
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?