The Best of Creative Computing Volume 1 (published 1976)

Page 181 << PREVIOUS >> NEXT Jump to page:
Go to contents Go to thumbnails

Doubling Up (folding a piece of paper in half 7 times, growth of doubling sequence)

graphic of page

Doubling Up

by Frank Tapson

Take a piece of paper - you may use any size you please - and fold it in half.
Then fold it in half again, and yet again, and again... How many times do you
think you can do this? If you have never met this problem before then try it
before you read any further - you will very probably receive a surprise. Have a
guess first before actually trying to do the folding and then see how far you
get.

Many people on meeting this little problem for the first time are prepared to
say that, provided the paper is large enough then it may be folded in half any
number of times. Well, as you might have discovered by now, after 7 such
foldings the task becomes extremely difficult, and if not impossible then it
will almost certainly be after the next fold. It is interesting to look at what
in fact happens.

After our first fold, the piece of paper we have to work on next is double the
thickness of the original. Another fold of this piece doubles the thickness so
that we now have 4x the thickness of the original. Folding again will once more
double-up on the thickness so that we have (2 x 2 x 2) 8 thicknesses of paper.
This is followed by 16 thicknesses after the next fold, then 32, then 64, and
128 after the 7th fold. Assuming that the paper we are using is one-thousandth
of an inch thick (not the thinnest possible but still a flimsy paper) then after
folding it 7 times we have a piece which is one-eighth of an inch thick, or
about the thickness of a piece of stout card. Now such a card could certainly be
folded in half generally, but there is an added difficulty. Just as the
thickness has been doubled with each fold so the area has been halved, and after
only 6 foldings we are usually trying to bend something which is not much bigger
than an extra-large postage stamp, which is why that piece of 'stout card' is so
difficult to fold.

It is interesting to wonder how far the process might be taken if a piece of
super-large paper were used. Let us assume it is still one-thousandth of an inch
thick, but that we can start with a piece the size of a football-pitch. Go on -
have a guess, how many times would you manage to fold it in half?

Some might wish to argue about the precise stage at which the task becomes
impossible, but if the 13th folding can be made, it produces something which is
about four feet square and eight inches thick. Now think about bending that!

Once we start folding by speculation (and not by actually trying to do it) it
becomes fascinating to go on with the process. For instance, just suppose we
were able to get an extremely large piece of paper and fold in in half exactly
100 times and, having done that we wished to stand on top of it - how long a
ladder would we need to get to the top? By now you have no doubt some idea of
what to expect - or have you? After the 26th fold we have a "piece of paper"
which is just over a mile thick so you might think we are going to need a fairly
tall ladder for 100 folds. Keep going - the 53rd fold gets us just past the sun,
and if you think that we are at least over half way then you have failed to see
what doubling is all about. The 83rd fold gets us somewhere near the centre of
our galaxy, from which it follows that the 84th fold puts us out on the other
side and still going. And there we will let the matter rest, if anyone can work
out 'precisely' where the top of our work will be after the 100th fold do let us
know. We might be able to use it as a navigational aid for inter-stellar
travel!

This simple concept of the growth of the doubling sequence has had a fascination
for those concerned with the lighter side of mathematics for many years. Perhaps
the most famous is the story told around the invention of the chess-board, how
the king was so pleased that he offered the inventor any reward that the
inventor cared to name. This was expressed as 'one grain of corn on the first
square of the board, two grains on the second square, four grains on the third
square and so on...' The king thought this is a very light price to pay for such
a great game and readily agreed. However, he was not at all pleased to learn
that the total quantity of grain required could not be supplied by the entire
world output of grain for several years to come. Some accounts of the story
claim that he had the inventor beheaded for imposing such a mathematical joke
upon royalty! Re-telling this story in his mammoth work A History of Chess, H.
J. R. Murray says that the quantity of grain needed is such as to cover England
to a uniform depth of 38.4 feet. The actual number of grains needed to fulfil
the stated conditions is 2^64-1, a figure which also occurs in connection with
the story woven around the Tower of Hanoi.

Another form of the story involves either the sale of a horse, or the shoeing of
one. In either case the price is fixed at a farthing (over a hundred years ago)
or a penny for the first nail in its shoes, doubled-up for the second nail,
doubled again for the third nail and so on. The only serious disagreement
appears to be concerning the total number of nails (I have stories giving 6, 7,
and 8 nails per shoe).

A story can also be woven around the telling of a secret to two friends, each of
whom tells it to two other (different) friends, each of whom... Assuming that
the actual telling occupies just one minute, and that another minute is lost in
scurrying off to find someone else to tell the secret to - how many people will
know after one hour has elapsed from the initial telling? By now of course you
will have some idea of what is happening and won't be too surprised to learn
that by the end of the hour 2,147,483,647 people would know the secret. Since
this is just over one-half of the present total world population, it hardly
could be called a secret any more! The same story has been presented differently
by asking, under the above conditions, in a village of a given number of
inhabitants, how soon would it be before everyone knew the secret?

There is a surprising growth rate in the simple matter of doubling at every
stage of the sequence. Just think of it next time you fold a piece of paper in
half, and don't go on for too long lest you should fall off the top!

For the curious, the exact value of 2^100 is -
1,267,650,600,228,229,401,496,703,205,376.

Reprinted from Games & Puzzles, December 1974. Copyright 1974 Games & Puzzles,
11 Tottenham Court Road, London W1A 4XF, England.

118

Page 181 << PREVIOUS >> NEXT Jump to page:
Go to contents Go to thumbnails