Did you solve it? The science of streaming

Earlier today I set the following puzzle, repeated here with its solution.

The inspiration for the problem is one of the earliest, and most important streaming algorithms, the predecessor of the tech used by streaming services such as Netflix and Spotify.

The big ballot brainteaser

An election is held between candidates A, B, C and D. You are given a set of 100 completed ballot papers and your job is to work out whether any of the candidates has an overall majority, i.e. won 51 or more votes. If a candidate has done so, you must say who it is.

But there’s a catch. You are not allowed to count the ballot papers. That is, you are not allowed to use numbers in any way. You can’t write anything down, nor are you allowed to keep track of the tally in your memory. Instead you will have to devise a clever strategy that involves making instant decisions about each ballot paper when you see it.

All you are allowed to do is to move the papers between three piles on a table. The starting position, as illustrated below, has all the papers in a stack on the first pile. The ballot papers are face up, so you can always see which candidate has received a vote on the ballot paper at the top of the pile. There are two other positions for piles, but as yet they are empty.

There are only two options to start. You move the top ballot on Pile 1 to either Pile 2 or Pile 3. For your next move you can do the same again, or you can move the ballot that is on either Pile 2 or Pile 3 to another pile. And so on. At any stage all you can do is to move the ballot paper that is at the top of one pile to the top of another pile.

Your task is to find a strategy that tells you if one candidate has an overall majority (i.e 51 or more votes) simply by shifting ballot papers between piles. Can you do it?

The hint

As is often the case, it is helpful to simplify the problem to see if it gives us any insights. Let’s consider the case when there are only 2 candidates, A and B.

A simple strategy is as follows: if we see A atop the first pile, we put it on the second pile, and if we see B atop the first pile, we put it on the third pile. After 100 moves, the first pile will be empty, the second pile will have all the As and the third pile all the Bs. We can now work out which pile has the most ballots by placing them alternately back on the first pile. If there are any ballots left on the second pile at the end, then A has at least 51 votes, and if there are any ballots left on the third pile, then B does. Call this the “two-group strategy”.

Now try scaling up to four candidates, A, B, C and D. One way to do it would be to use the two group strategy with the candidates divided into two coalitions, say A&B vs C&D. If one of the coalitions has more than 51 votes, we then do the two group strategy twice more – once for each member of the winning coalition. This strategy works, but it is not very efficient: it relies on moving papers between piles at least 500 times, as well as keeping tracks of coalitions. There is a much quicker way. Can you find it?

Solution

I’m going to explain the algorithm first, and afterwards explain the reasoning.

STEP 1. Move the top ballot on Pile 1 to Pile 2

STEP 2: Look at the candidates chosen on the top ballots of Pile 1 and Pile 2. If they are the same, place the top ballot of Pile 1 onto the top of Pile 2, as below.

If the candidates chosen on the top ballot of Pile 1 and the top ballot of pile 2 are different, place both of these ballots on Pile 3, as below.

STEP 3: If Pile 2 is empty, apply STEP 1. If Pile 2 has ballots, apply STEP 2. Carry on until there are no more ballots left in Pile 1. At the end of the process, either there will be ballots in Pile 2 or it will be empty. If it is empty, no candidate has an overall majority. If it is not empty, then all the ballots in the pile 2 will be for the same candidate, and it may or may not be the case that this candidate has an overall majority. The final step is to check whether this candidate does have an overall majority. We can do this using the two-group strategy, testing the candidate against a coalition of the other three, or slightly faster, use this second strategy again, using Pile 1 to be the ‘Pile 3’ dump.

Why this works:

What the algorithm is doing is letting Pile 2 be a ‘clicker’ for the candidate in Pile 2. When we add a ballot to this pile, the total number clicks up by one, and when we remove a ballot from this pile it clicks down by one.

It is impossible at any stage for Pile 2 to have ballots for more than one candidate. It is possible for Pile 2 to start off stacking ballots for, say A, and finish off with a stack of ballots for, say D. But this switch can only happen when the process goes through a point when Pile 2 is empty.

At the end of the process, Pile 3 must contain an even number of ballots, because ballot papers are moved there in pairs. Each pair has votes for two different candidates, and therefore no single candidate in Pile 3 has more than 50 per cent of the votes in Pile 3. (The best they can hope for is 50 per cent, i.e a ballot in every pair.)

Thus the only candidate with a chance of having an overall majority is the candidate in Pile 2. If we check this by applying the strategy again, using Pile 1 to be the ‘Pile 3’ dump, then Pile 1 will have an equal number of candidate and non-candidate ballots, and the status of Pile 2 will tell us if the candidate has a majority or not.

Neat!

This solution is the basis for the Boyer-Moore majority vote algorithm, published by Robert S Boyer and J Strother Moore in 1981. This algorithm and ones like it are used widely today in telecommunications and the analysis of web queries.

Just to make the analogy between the puzzle and streaming algorithms clear: imagine that each ballot paper is a piece of incoming data. You are not allowed to count, which is analogous to not being able to use a memory to store information. Instead, you must make an instant decision about what to do as soon as each piece of data arrives, with the hope that very quickly you can learn some overall property of the whole stream.

I hope you went with the flow! Please gush with your comments below.

Today’s puzzle was devised by Pierre Chardaire, a retired computer scientist.

I set a puzzle here every two weeks on a Monday. I’m always on the look-out for great puzzles. If you would like to suggest one, email me.

I give school talks about maths and puzzles (online and in person). If your school is interested please get in touch.