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!

  1. Start with the first voted candidate.
  2. 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.
  3. If and when the counter reaches 0, restart from the first step using the next voted candidate.
  4. 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.

6 Comments

  1. 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.

  2. 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.

    • The way the answer was written, I’d say it was made for 2 candidates only so it’s able to handle with only one counter. For multiples candidates, you’d have to tweak a little.
      1) Hold a counter for each candidate and sum by 1 the counter of the person whose name was said. The biggest counter is the winner. Given the premises, this should be viable
      2) Hold only one counter and instead of summing, you will multiply. However, there is a catch, each candidate will have a prime number associated with him. In your example,
      let candidate 1 be prime 5, candidate 2 be prime 2 and candidate 3 be prime 3.
      This way, you final number will be 5^6*2^5*3^3=900000, which only has this one way to factor it and you’ll know exactly how many votes were for each candidate

      • The listed answer works for any number of candidates actually.

        I like your proposed solution too, but it doesn’t quite fit the requirements since you’ll have to remember which candidate is which prime number.

Leave a Reply

Your email address will not be published. Required fields are marked *