**The Best of Creative Computing Volume 1 (published 1976)**

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