Grains of Wheat

Date: 07/14/99 at 00:21:41
From: Mostafa Khalafalla
Subject: Problem-solving

This is a question that I have already answered, but with a lot of 
difficulty. 

The person who invented the game of chess was said to have been 
offered any payment he wanted. It is said that he asked for 1 grain of 
wheat for the first square, 2 for the next, 4 for the third, and 8 for 
the fourth, etc. for the 64 squares on the chessboard. How much wheat 
did he receive?

First I tried doing it by hand. Then I searched all my maths books and 
found nothing. Then I asked around the next day at school and found 
that one of my friends had answered the question. I asked him how he 
had done it and he went into a full-scale explanation of how he solved 
it. He had done it on Excel using the formula for multiplication. 
Could you please tell me an easier way to do it?

Date: 07/14/99 at 11:29:37
From: Doctor Rick
Subject: Re: Problem-solving

Hi, Mostafa.

I'm glad you want to know easier ways to do it by hand. Computers 
make it easier to do a lot of arithmetic, but you don't get to know 
numbers very well if you let the computer do all the work. Computers 
can do it the hard way and still do it fast; if you do it by hand you 
need to look for shortcuts, and that means getting to know numbers 
and their patterns.

There is a pattern that can help you.

  Square  Grains  Total so far
  ------  ------  ------------
     1       1      1

     2       2  +---3
                |
     3       4--+   7

     4       8  +--15
                |
     5      16--+  31

Notice that the total so far is always 1 less than the number of 
grains that will be put in the next square. This pattern is true for 
any number of squares. You might want to investigate this to see why 
it is true. If you have learned about binary numbers, you could write 
the numbers in the table in binary, and remember that, for instance, 
1111 (in binary) is 1 less than 10000. If this doesn't make sense to 
you, don't worry about it, but look for other ways to think about the 
pattern.

What this means is that you don't need to add up 64 numbers; you just 
have to find the 65th number (how many grains would be put on the 
65th square, if there were one). Subtract 1 from this number, and you 
have the total number of grains on the first 64 squares.

The number of grains on square 65 is 2 * 2 * 2 ... * 2, with 64 2's. 
(I use "*" for the multiplication sign.) Have you learned about 
powers? We call this number 2 to the 64th power, written

   64
  2

With a keyboard, it's easier to write it as 2^64.

Powers follow patterns or rules, too. You can use one of these rules 
to make it easier to calculate 2^64 - you don't have to do 63 
multiplications. Here is the rule: if you square a power of 2, you 
get another power of 2, with twice the power. For instance,

  (2^4)^2 = 2^(4*2) = 2^8

If you haven't seen this, I'll show you why it works. 

  2^4 = 2*2*2*2     (2^4)^2 = (2*2*2*2) * (2*2*2*2)
        \_____/               \___________________/
          4 2's                       8 2's

(2^4)^2 is a product of 8 2's, so it is 2^8.

Now watch how we can use this rule to calculate 2^64 quickly:

  2^2 = 4
  2^4 = (2^2)^2 = 4^2 = 16
  2^8 = (2^4)^2 = 16^2 = 256
  2^16 = ...
  2^32 = ...
  2^64 = ...

Finish those 3 lines, and you'll have the answer! The multiplications 
get a lot bigger, but if you know how to estimate the size of a 
product, you don't need to do all the work to get a good idea of how 
big the total is.

I've gone over a lot of ideas quickly. I don't know how many of these 
ideas you may already be familiar with. If you want to know more 
about any of them, feel free to write back!

- Doctor Rick, The Math Forum
  http://mathforum.org/dr.math/