## Friday, 14 May 2010

### Rice and the Chessboard

In the story, an Emperor asks his mathematician to solve a difficult problem.

In payment, the mathematician asks for a chessboard with one grain of rice on the first square, two on the next, four on the one after that, eight on the next, and so on. The emperor agrees. Then the smart-alec mathematician points out that by the time we get to the sixty-fourth square, the number of grains of rice is astronomical. It's about 10^19, or 10,000,000,000,000,000,000. In binary, that's 1111,1111,1111,1111,1111,1111,1111,1111,1111,1111,1111,1111,1111,1111,1111,1111 , which is probably the largest number that you can express as a standard integer on a modern 64-bit processor running a specialist 64-bit version of Windows. One more grain of rice and you probably get an overflow error.

If each grain of rice weighs about 25 mg, then, when we double the last-square figure to get the total number of grains on the chessboard, I think we end up with something like 460 billion metric tonnes (minus one grain).

According to the story, the Emperor's response was to point out that this created a new problem that required the mathematician's involvement. As Emperor, he couldn't go back on his word, even if the mathematician allowed him to. An Imperial Decree couldn't be rescinded. On the other hand, that much rice didn't physically exist. The solution was to point out that if the mathematician didn't exist, the debt would cease to exist, too. So the Emperor signed the mathematicians' death warrant on the grounds that pulling this sort of trick on the Emperor counted as treason, and had him executed.

Here's how to work out the result in your head, without using a calculator (or even pen and paper) :

Square 1 has one grain of rice. The next ten have 2, 4, 8, 16, 32, 64, 128, 256, 512 and 1024.

Every time that you advance another ten squares, you multiply the number on the square by 1024 (2^10), which is only slightly more than a thousand (1000, 10^3). As a first approximation, every ten-square move pretty much shifts the "decimal" version of the number three places to the left.

This means that when we move sixty squares, we're adding those three zeroes six times, giving us eighteen zeroes. That leaves just three more squares, so we go 2, 4, 8 … and write down a "guesstimate" figure of 8 ×10^18 for the number of grains on the last square.

This is an underestimate, but by how much? We treated 1024 as if it was 1000, so we have a missing factor of 1.024 that needs to be multiplied in six times to get to the proper answer. What's 1.024 raised to the sixth power? Eww. :(

Well, when we square "one-point-something", we get one, plus two times the "something", plus "the something-squared" ( (1+x)^2 = 1 + 2x + x^2 ).
If the something is very small, then something-squared is going to be extremely small, and hopefully so small that we can forget about it, and get away with just doubling the original small something.

So "1.024 times 1.024" gives 1.048, plus a little bit. Call it 1.049 .
Now we need "1.049 times 1.049 times 1.049", to get us up to that power of six.
A similar principle applies: cube something very close to one, and the tiny difference kinda triples (plus a little bit).
So we take 1.049, look at the part after the decimal point, 0.049, nudge it up to a nicer 0.05 , then triple that to give ~0.15 as the ratio that has to be multiplied into our original result to find the amount of undershoot correction.

"Eight" times the 0.1 is 0.8
"Eight" times the 0.05 should be half that, so 0.4 .
Adding them together, 0.8 + 0.4 is 1.2 (× 10^18).
That's our error .
Add that to the original guess of 8 (× 10^18), and we get our improved estimate, of ~9.2 ×10^18 .

… and if we check that against our calculator, which says that 2^63 = ~9.22 × 10^18, we were correct to two significant figures. Not bad for calculating something to the sixty-third power. Yayy Us!