Soylent Red

I learned this puzzle from a friend in work. He posed it one morning before everyone had had their coffee and ended up costing a small handful of engineers a whole morning of productivity as we each solved it. I've been meaning to post about it here for a while. Here's the formulation as best I can describe it:

You have in front of you one of those tables you get in Asian restaurants with the rotating centre—what one of our product managers described as a lazy susan, though I've never heard that phrase from anyone else. Picture the restaurant from the beginning of Indiana Jones and the Temple of Doom if you really want to set the scene.

On the table are four glasses, each of which is either standing upright or turned upside down. They're evenly spaced around the table, in a square. You sit at the table blindfolded. Your aim is to turn the glasses such that they are either all upright or all upside down, subject to the following rules.

You are allowed to inspect two of the glasses, by touch, at a time. You can choose to inspect either the two immediately in front of you (i.e., a side of the square) or one in front of you and the one opposite it (i.e., a diagonal). After inspecting the glasses you are allowed to turn either glass, both glasses or neither glass.

Once you've inspected and possibly turned two glasses the table is rotated a random amount so that you don't know which glass is which. You then have the same choices about inspecting and turning glasses as before. Then the tables is rotated again. It goes on like this for as long as you need to solve the puzzle.

If at any point you get all the glasses upright or all upside down you'll be told that you've won. You don't need to be able to know that you've solved it. You aren't told at the start what configuration the glasses are in, though you can assume they don't start in a solved state.

Find a way to reliably solve this puzzle that will be guaranteed to work in a finite number of moves regardless of the initial conditions or how lucky you are with rotations of the table. In particular this means that you can't just keep spinning the table and turning upright every glass you touch in the hope that you'll get them all eventually.

• Permanent Link
• Toggle Comments [4]

If you watched the video of Randall Munroe at Google you might have heard him mention a site called Project Euler. It's a cool collection of short but interesting mathematical problems that are intended to be solved with a computer. That said, there's nothing stopping you from using good old practical mathematics.

The most solved puzzle on the site is this one:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

Now, this didn't look to me like a computer was required to solve it, so I nibbled the end of my pencil for a second and came up with the following solution:

There will be 333 numbers in that range which are divisible by three (every third number, so a third of the total). There will be 199 numbers in that range that are divisible by five (every fifth number, and a fifth of the total—it's 199 rather than 200 because the top number, 1000, is excluded).

Now I don't know offhand a way to calculate the sum of the first 333 numbers divisible by three. But I do know offhand a way to calculate the sum of the first 333 numbers. It's 333 × 334 ÷ 2. Is that any help? It turns out it is. Consider the first five multiples of three: 3, 6, 9, 12, 15. The sum is 3 + 6 + 9 + 12 + 15 = (3 × 1) + (3 × 2) + (3 × 3) + (3 × 4) + (3 × 5) = 3 × (1 + 2 + 3 + 4 + 5). That is, it's three times the sum of the first five numbers. By the same reasoning, the sum of the first 333 multiples of three is equal to three times the sum of the numbers from one to 333, or 3 × 333 × 334 ÷ 2.

Applying the same reasoning again, the sum of the first 199 multiples of five is five times the sum of the first 199 numbers, or 5 × 199 × 200 ÷ 2.

There's one more piece: in adding up all the multiples of three, and all the multiples of five, I've included some numbers twice. There are some numbers that are divisible by both three and five, i.e., those numbers divisible by fifteen. There are 66 of these, from 15 to 990 (again, by taking 1000 ÷ 15 and rounding down you get 66). So the total has to be reduced by 15 × 66 × 67 ÷ 2.

The final answer is: (3 × 333 × 334 ÷ 2) + (5 × 199 × 200 ÷ 2) - (15 × 66 × 67 ÷ 2) = 233168.

The easy way, of course, is:

$> python

>>> sum([i for i in range(1,1000) if i % 5 == 0 or i % 3 == 0])

233168

• Permanent Link

Did you ever hear the old Chinese story about the rice and the chessboard? The specifics are hazy, and I'm sure there are lots of variations anyway, but I remember the important details. Someone having performed some important task for the king asked that he be paid in rice. The king was to put one grain of rice on the first square of a chessboard, two on the next, four on the next and so on to fill the board with each square containing twice as much rice as the previous one. How much rice do you think this adds up to?

The answer is easy to calculate but difficult to imagine. There are 2^{N - 1} grains on the N^th square. 2⁰ = 1 on the first, 2¹ = 2 on the second, 2² = 4 on the third, and so on. The last square, number 64, has , 2⁶³ = 9x10¹⁸ grains on it. That's a nine followed by 18 zeros or nine billion billion. Let's try to cut that down to something we can imagine.

There are about 2000 grains, give or take, in a reasonable portion of rice. If a person eats one portion every day she will eat 730,000 grains a year. That last square will feed her for about 10¹³ (ten thousand billion) years. I think we need to cut it down further.

There are six billion people alive right now. If they all loved rice as much as the example person in the previous paragraph and consumed it at the same rate of 730000 grains a year it would take about 2000 years to eat it all. The only problem is that none of us will live that long. We could eat it at twice the rate, say two portions a day each, but that will only reduce it to 1000 years. We need more people.

It's estimated that there have been somewhere in the region of 100 billion people ever. Let's assume that they all loved rice and would want to eat two portions a day for their entire lives. So we have 100 billion people each eating 1460000 grains of rice per year. How long would it last?

2⁶³ grains / (10¹¹ people * 1460000 grains per person per year) = 63 years, a lot more than the average lifespan for most of human history. That single square of rice would comfortably feed two portions a day to every person who has ever lived for their entire life.

The rest of the board contains the same amount again (less one grain).

• Permanent Link
• Toggle Comments [4]