Earlier today I set up these two puzzles, which were given to me by a computer scientist at Microsoft. This is an analogy for how companies protect data centers from the random failures of hard drives. Here they are again with solutions and works.
The disappearing boxes
You have 100 boxes. Each box contains a single number in it, and no two boxes have the same number.
1. It is told to you one of the boxes at random will be removed. But before it is removed, you are given an extra box, and allowed to put a single number in it. What number do you put in the extra box that ensures that you will be able to get the number back from whichever box is removed?
[A clarification, as I think some readers of the puzzle were unclear: your own boxes are not laid out at random. You know which box is which. Just as in a data centre, the hard drives are all positioned in order and do not move around. What is random is the the box that is removed.]
Solution The sum of all the numbers in the 100 squares.
Here is an explanation with a little more work. Let the number in box be 1 a1be the number in 2 a2, and so on. So, we sit a1 + a2 + … a100 in the extra box. Now let’s say that box r removed, so the information that is lost is the number ar. To recover ar we add up all the numbers in the 99 boxes that remain and subtract them from the number in the extra box. That number is ar.
2. It is told to you two of the boxes at random will be removed. But before it is removed, you are given two extra boxes, and allowed to put one number in each of them. What (different) numbers do you put in these two boxes that will ensure that you will be able to recover the numbers from both removed boxes?
Solution In one block we do what we did in the previous example, which is the sum of all the numbers in the 100 blocks. Let’s call this number A. In the other box we need another sum that combines all the numbers in the 100 boxes, like:
a1 + 2a2 + 3a3 + … 100a100
Let’s call this number B.
So let’s say the two boxes being removed are boxes r and s. If we add up all the 98 numbers that are left and subtract them from A, we have a value for ar + as.
Similarly, we add up the values a1 + 2a2 + 3a3 + … 100a100 but without rnr and sns we are left with the value of rnr + sns.
This gives us two equations in two unknowns (ar and as ) which can be solved to find both ar and as. (As you hopefully remember from learning basic ‘simultaneous equations’ at school.)
Tah dah! We managed to find an extremely efficient method to recover our data. And as a bonus, you learned the basic idea of how “error-correcting codes” work, which is the technology that makes sure the digital world can handle random noise and failures.
I hope you enjoyed today’s puzzle. I’ll be back in two weeks.
Thanks to Sivakanth Gopi, a principal researcher at Microsoft, for today’s puzzle.
I’ve been doing a puzzle here on alternate Mondays since 2015. I’m always on the lookout for great puzzles. If you want to suggest one, email me.
