Can you solve it? The science of streaming

Today’s puzzle is tricky! I mean trickle-y. It is all about streams.

The source of the puzzle is a ‘streaming algorithm’, which is a type of procedure in computer science that analyses data as it arrives in a stream, rather than waiting for the data to be stored in a memory.

The first streaming algorithms were devised in the 1980s. The idea behind them was to get an overall readout of incoming data as fast as possible, using as little memory as possible. Since data streams are ubiquitous in the digital world – phone calls, credit card transactions and Netflix movies, for example, are all data streams – this kind of algorithm is too.

You are about to meet one of the most important early streaming algorithms. Well, you are if you solve today’s puzzle. Buffering now!

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?

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?

I’ll be back at 5pm UK with a solution and a discussion. PLEASE NO SPOILERS instead discuss your favourite streaming services.

If you are wondering what moving ballot papers has got to do with streaming, here’s the analogy. 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: whether or not there is a majority value, and if there is, what it is.

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.