by Today’s puzzle is tricky! I mean trickle-y. It’s all about currents.
The source of the puzzle is a “streaming algorithm,” a type of computer science technique that analyzes data as it arrives in a stream, rather than waiting for the data to be stored in memory.
The first streaming algorithms were developed in the 1980s. The idea behind this was to get a full readout of the incoming data as quickly as possible while 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 — so is this type of algorithm.
You are about to learn about one of the most important early streaming algorithms. Well, you are if you solve today’s puzzle. Buffer now!
The Big Voting Brain Teaser
An election is held between candidates A, B, C and D. You are given a set of 100 completed ballot papers and your task is to find out if any of the candidates have the overall majority, ie received 51 or more votes. If a candidate has done this, you must say who it is.
But there’s a catch. You are not allowed to count the ballots. That means you are not allowed to use numbers in any way. You must not write anything down, nor must you keep the count in your memory. Instead, you must develop a clever strategy that involves making instant decisions about each ballot as you see it.
All you are allowed to do is move the papers between three piles on a table. In the initial position, as shown below, all the papers in a stack are on the first stack. The ballots are exposed so you can always see which candidate got a vote on the ballot at the top of the stack. There are two more positions for stacks, but they are still empty.
It is only two options to start. You move the top ballot from Stack 1 to either Stack 2 or Stack 3. For your next turn, you can do the same thing again, or you can move the ballot that is in Stack 2 or Stack 3 to a different stack. Etc. At each stage, you can only move the ballot that is on top of a pile to another pile.
Your task is to find a strategy that will tell you whether a candidate has an overall majority (i.e. 51 or more votes) simply by moving the ballots between the piles. Can you do it?
As is often the case, it’s helpful to simplify the problem to see if it gives us any insight. Let’s consider the case where there are only 2 candidates, A and B.
A simple strategy is as follows: if we see A on the first pile, we put it on the second pile, and if we see B on the first pile, we put it on the third pile. After 100 moves, the first pile will be empty, the second pile will contain all the As, and the third pile will have all the Bs. We can now find out which pile has the most ballots by placing them alternately back onto the first pile. At the end of the day, if there are ballots left on the second pile, then A has at least 51 votes, and if there are still ballots left on the third pile, then B. Call this the “two-group strategy.”
Now try to scale down to four candidates, A, B, C, and D. One option would be to use the two-group strategy, splitting the candidates into two coalitions, say A&B vs. C&D. If one of the coalitions has more than 51 votes, we apply the two-group strategy twice more – once for each member of the winning coalition. This strategy works, but it’s not very efficient: it relies on moving papers between decks at least 500 times and tracking coalitions. There is a much faster way. can you find it
I’ll be back in the UK at 5pm with a solution and discussion. NO SPOILERS PLEASE, just discuss your favorite streaming services.
If you’re wondering what moving ballots has to do with streaming, here’s the analogy. Each ballot is a piece of incoming data. You are not allowed to count, which is analogous to not being able to use memory to store information. Instead, you have to make an instant decision about what to do as each piece of data arrives, hoping that you can very quickly learn something about the overall property of the entire stream: whether or not there is a majority value, and if so it is what is it.
Today’s puzzle was developed by Pierre Chardaire, a retired computer scientist.
I post a riddle here every two weeks on a Monday. I’m always looking for great puzzles. If you want to suggest one, email me.
I give school lectures on math and puzzles (online and in person). If you are interested in your school, please contact us.
