MagiMathics

Just another WordPress.com weblog

Archive for December 2009

The Mathematics of Toilet Rolls

leave a comment »

In the late 1980s I was contracted to write some software for a company that produced video-based educational systems. They had video cassette machines that had been modified to interface with a PC, which could send instructions to the VCRs such as play, stop, fast forward, and rewind. The educational programs consisted of short recorded segments which typically ended with a question, and based on the answer the user provided they wanted to continue play at different portions of the tape. The software they wanted me to write was meant to be able to be given a current position (i.e. play time) and advance to a new position. For example I might be told that they are at minute 8 currently and want to resume play at minute 12.

Picture by Dvortygirl, licensed under GNU Free Documentation License

Without going into all the detail, I can tell you this was a Very Hard Problem. There was no way to tell where you were on the tape without actually playing, and if you are familiar with VCRs (which are rapidly going the way of the dinosaur) you may be aware that engaging the play head takes a few seconds. There were variations in motor speed, tape stretching, and all sorts of other variables to take into account. The approach I used was to try to calculate the “optimal” fast forward time, shorten that a bit, and then narrow down to the exact position with a modified binary search (or, to put it more crudely, “trial and error”).

We got the system to work although it was a pretty crude affair but before anything shipped new VCRs came out that recorded “time code” on the tape and had much more precise electronics essentially supporting just this functionality we had duct-taped together, and so it was all for naught (and not long after CD-ROMs came and made it all redundant anyway).

I don’t remember all the math that I worked out for this system, but it is easy enough to recall the basic parameters. There was the diameter of the empty plastic spools, the diameter of a full spool, and the playing time of the tape (typically 120 minutes), which was a linear function of the length (assuming an unstretched tape :-))

While playback happened at a constant speed, as the tape ran through an independent roller mechanism unaffected by the spool state, fast-forwarding and rewinding happened at a variable rate, as it was controlled by the motors driving the spool, and the spool diameters changed.

Picture by Barndon Blinkenberg, licensed under Creative Commons

All in all, a nasty business, and we are better off without tape! But there is still a common household item with some similar characteristics, namely the toilet roll. So, here are some problems surrounding toilet rolls to think about. To save you having to measure your toilet rolls here are some typical measurements from mine (Charmin 2 ply from Costco) – spool diameter 45mm, roll diameter 120mm, 250 x 101mm sheets = 25250mm length.

 

 

  • how thick is each sheet of paper? (and thus, how many times does it go around the spool?)
  • what would the diameter of a roll be that went all the way around the earth (assuming the earth’s diameter is 12,756.32km)?
  • what if it went around the earth but 1m higher than in the example before? How long would the roll be? (you may recognize this as a familiar puzzle involving rope but I thought I’d sneak it in here!)

(BTW no less a figure than Donald Knuth has considered toilet paper worthy of investigation, as evidenced here).

If we call the paper thicknesst, the radius of the spoolr_s and the radius of the roll (spool plus paper)r_r, then it should be obvious that the number of windsn is:

n = \frac{r_r - r_s}{t}

If we approximate the roll as a number of concentric circles rather than a spiral, then the innermost roll has length2\pi r_s, and the next roll has length2\pi (r_s+t), and so on; each successive roll is2\pi t longer than the prior one, and the final roll has length2\pi r_r.

Because each successive roll is longer by a constant amount, we have an arithmetic sequence. Recall that the sum of an arithmetic sequence is given by\frac{n}{2}(a_1 + a_n), wheren is the number of terms,a_1 is the first term, anda_n is the last term. So the length of the entire roll is given by:

l = \frac{n}{2} ( 2\pi r_s + 2 \pi r_r) = \pi \frac{r_r^2 - r_s^2}{t}

Thus my toilet paper is about 0.38 mm thick – quite luxurious!

For the second problem it is reasonable to assumer_s = 0, to give us the simpler formula:

l \approx \pi \frac{r_r^2}{t}

or:

r_r \approx \sqrt{\frac{l t}{\pi}}

or:

r_r \approx \sqrt{d t}

whered is the earth’s diameter. So for my paper this would be about 70 meters. If I had a cheaper brand of one ply paper this might be considerably less.

I’ll leave the last question as an exercise but it should be fairly clear that the difference inl in this case is quite small and so the extra radius needed for the toilet roll is very small.

Advertisements

Written by Graham Wheeler

December 27, 2009 at 6:36 am

Posted in Uncategorized

Babylonian numbers in 60 seconds

with 2 comments

My 5 year old daughter wanted to heat something up in the microwave. I suggested she use a minute, and she asked me how to enter that. I said enter 1, 0, 0, Start. “But when mom tells me to do a minute she says 6, 0, Start”, she responded. I wasn’t sure how to explain to her that 1:00 minute is the same as 60 seconds; microwaves are confusing enough to her as is.

So why are there are 60 seconds in a minute? Why not 100? The answer lies about 4000 years ago, in some of the earliest known mathematics, of Sumeria and Babylon. The Sumerians and later the Babylonians used a sexagesimal (base 60) number system for their astronomy (although they used decimals for day-to-day applications). They had no way to represent non-whole numbers other than as fractions, and 60 was a convenient base as it has a large number of factors; in particular it can represent 1/2, 1/3, 1/4, 1/5, and 1/6 all with whole numerators. In fact sexagesimal notation can be used to exactly represent any fraction in which the denominator has prime factors of 2, 3, and/or 5 (as these are the prime factors of 60), with a finite number of symbols.

Interestingly, both cultures did not have 60 distinct symbols but still used base 10 representation for numbers in the range 0..59, with narrow vertical wedges for 0..9 and thicker horizontal “corner” signs for 0..5 tens:

image

However, numbers were encoded as base 60 using place notation. For example, decimal 63.3 would be written as 1, 3 . 18.

As there was no symbol for zero interpreting these numbers sometimes had to be done in context; often a space was used although various other symbols were introduced later, like slanting wedges. As far as we know these symbols didn’t represent “zero” as we understand it – that came later – but just represented a “void” position.

Sumeria was invaded by the Akkadians around 2350BC, who adopted the Sumerian system but introduced new symbols for hundreds and thousands.

This system was an improvement over the earlier Egyptian notation, which was base 10 but, apart from a few special cases, was limited to fractions with one as the numerator (i.e. reciprocals only).

Written by Graham Wheeler

December 27, 2009 at 6:09 am

Posted in Uncategorized

Monkeying Around

with 4 comments

After a huge storm blew up, the ship foundered. Dawn’s light found just six survivors washed up on a desert island – five men and one monkey. The men spent the day gathering all the food they could find – which was just a pile of coconuts. After a dinner of coconut milk and flesh, the exhausted men decided to they would divide the remaining coconuts up the following day, before splitting up and exploring the remainder of the island.

During the night one man woke up and started worrying about whether there would be a disagreement in the morning over the coconuts. He decided to take his share, and divided the coconuts equally into five. There was one left over which he gave to the monkey, then he took his share and hid them away, before going back to sleep.image

A little later the next man woke up, and had the same fear. He too divided the coconuts into five, and had one left over that he gave to the monkey, before hiding his share and going back to sleep. And so the night went on, with each man waking up, dividing the remaining coconuts in five, hiding one share and giving the one extra to the monkey.

In the morning, the men awoke and divided the remaining coconuts, which came out to five equal shares. No-one said anything about the missing coconuts as each thought he had been the first to hide a share and was thus the best off.

How many coconuts were there in the beginning?

It is not difficult to express this problem as a set of equations; what makes the equations hard to solve is that the solutions must be integers. Such equations are called Diophantine equations, after the 3rd century AD’s Diophantus of Alexandria, who was the first known algebraist to examine equations limited to rational number solutions. We know little of Diophantus himself other than the following puzzle left after his death:

  • his childhood lasted 1/6 of his life
  • he grew a beard after another 1/12
  • after 1/7 more he married
  • 5 years later he had a son
  • the son lived to half Diophantus’ age
  • and Diophantus died 4 years later

From this we can determine how long Diophantus lived, how long his boyhood lasted, what age he grew a beard, what age he got married, when he had a son, and how long his son lived.image

Diophantus’ great work, The Arithmetica, is a text on computational arithmetic rather than theoretical mathematics, closer to the mathematics of Egypt, Babylon and India than to Greece. Diophantus promised 13 books in his introduction but only ten are known, with four only being discovered recently in an Arabic manuscript found in Iran. The earliest commentaries on The Arithmetica were written by Hypatia, the first known Western female mathematician, who was brutally murdered by a mob of Christian fanatics in 415 AD as they burned Alexandria’s great library to the ground and destroyed much of the world’s repository of classical knowledge.

Many people are familiar with Fermat’s famous “Last Theorem”; it was in the margins of a copy of Diophantus’ Arithmetica (Book 2, problem 8 ), in which Diophantus describes how to find solutions tox^{2}+y^{2}=z^{2} for a given value ofz, that Fermat wrote his famous note asserting that there are no solutions to equations of this form for any powers higher than two, and that “For this I have discovered a truly wonderful proof, but the margin is too small to contain it.”

Going back to the coconuts, if we call the initial number of coconutsx and the number hidden away by each man asa, b, c, d, e respectively, and the number of coconuts each sailor got on the next day asy, we get this set of equations:

x = 5a + 1
4a = 5b + 1
4b = 5c + 1
4c = 5d + 1
4d = 5e + 1
4e = 5y

We can use successive substitutions to reduce this to a single equation in two unknowns. The first sailor took\frac{1}{5}(x-1) coconuts, and left4\frac{1}{5}(x-1) = \frac{4}{5}(x-1) coconuts. The second sailor then took\frac{1}{5}(\frac{4}{5}(x-1)-1) = \frac{4x-9}{25} coconuts and left\frac{4x-9}{25} = \frac{16x-36}{25} coconuts. Continuing in this way we can find that the number of coconuts left by the third, fourth and fifth sailors were\frac{64x-244}{125},\frac{256x-1476}{625}, and\frac{1024x-8404}{3125} respectively. Therefore:

\frac{1024x-8404}{3125} = 5y

or:

1024x = 15625y + 8404

Normally, for real numbers, we would need two equations in two unknowns, but because we know the solutions must be integers the possible answers are more constrained. Equations of the form:

ax + by = c

are known as linear Diophantine equations; in our casea=1024,b=-15625 andc=8404, and we have:

1024x - 15625y = 8404

Ifa andb have a common denominator, then clearly for the equation to have integer solutionsc must also be a multiple of this common denominator.; if it is not, then there are no integer solutions. So we can simplify a linear Diophantine equation by dividing the coefficients of x and y, and the constant, by their greatest common denominator (GCD). The coefficients are then relatively prime, the gcd is 1 and no further simplification can be done.

Assuming we can simplify to the point where we have co-prime coefficients and still have an integer constant, we will have solutions – in fact, an infinity of them. This is quite easy to show. Assume we do have two solutions,(x_{1},y_{1}) and(x_{2},y_{2}). Then:

a x_{1} + b y_{1} = c = a x_{2} + b y_{2}

and so:

a(x_{1}-x_{2}) = b(y_{2}-y_{1})

So the difference between two solutions forx must satisfy:

x_{1}-x_{2} = \frac{b}{a}(y_{2}-y_{1})

Ifg is the GCD ofa andb, then we can divide botha andb on the right hand side byg to get a coprime numerator and denominator:

x_{1} - x_{2} = \frac{\frac{b}{g}}{\frac{a}{g}} (y_{2} - y_{1})

Because\frac{b}{g} and\frac{a}{g} are coprime, the smallest(y_{2}-y_{1}) that can expand the right hand side out to an integer value is:

y_{2}-y_{1} = \frac{a}{g}

And similarly:

x_{1}-x_{2} = \frac{b}{g}

So we have an infinite number of solutions of the form:

x = x_{1} - \frac{b t}{g}

y = y_{1} + \frac{a t}{g}

The problem usually comes down to finding the smallest pair of positive integers that satisfy the equation.

To solve a linear Diophantine equation such as the one above, we can apply Euclid’s method for finding the GCD of the coefficients (which will be 1, as our coefficients are coprime, but we are interested in the steps anyway):

15625 = 15 \times 1024 + 265\\ 1024 = 3 \times 265 + 229 \\ 265 = 1 \times 229 + 36 \\ 229 = 6 \times 36 + 13 \\ 36 = 2 \times 13 + 10 \\ 13 = 1 \times 10 + 3 \\ 10 = 3 \times 3 + 1

Note how the coefficients on the left of the right hand side match those in the continued fraction:

\frac{15625}{1024} = 15 + \frac{265}{1024}\\ = 15 + \frac{1}{\frac{1024}{265}}\\ = 15 + \frac{1}{3 + \frac{229}{265}}\\ = 15 + \frac{1}{3 + \frac{1}{\frac{265}{229}}}\\ = 15 + \frac{1}{3 + \frac{1}{1 + \frac{36}{229}}}\\ = 15 + \frac{1}{3 + \frac{1}{1 + \frac{1}{\frac{229}{36}}}} \\ = 15 + \frac{1}{3 + \frac{1}{1 + \frac{1}{6 + \frac{13}{36}}}} \\ \ldots\\ = 15 + \frac{1}{3 + \frac{1}{1 + \frac{1}{6 + \frac{1}{2 + \frac{1}{1 + \frac{1}{3 + \frac{1}{3}}}}}}} \\ = \langle 15; 3, 1, 6, 2, 1, 3, 3 \rangle

We can invert the steps to get a solution. Starting at the bottom:

10 = 3 \times 3 + 1 \Rightarrow 1 = 10 - 3 \times 3

We keep expanding this, working backwards, and substituting the equations we have derived above for the remainders:

1=10-3\times 3=10-3\times(13-1\times 10)=4\times 10-3\times 13

1=4\times 10-3\times 13=4\times(36-2\times 13)-3\times 13=4\times 36-11\times 13

1 = 4 \times 36-11 \times 13 = 4 \times 36-11 \times ( 229-6 \times 36 ) = 70 \times 36-11 \times 229

1 = 70 \times 36-11 \times 229 = 70 \times ( 265-1 \times 229 )-11 \times 229 = 70 \times 265-81 \times 229

1 = 70 \times 265-81 \times 229 = 70 \times 265-81 \times ( 1024-3 \times 265 ) = 313 \times 265-81 \times 1024

1 = 313 \times 265-81 \times 1024 = 313 \times ( 15625-15 \times 1024 )-81 \times 1024 = 313 \times 15625-4776 \times 1024

So we have determined thatx=-4776 and y=-313 is a solution of1024x-15625y=1. This is all very well but how do we adjust this for the fact that thec value we actually care about is 8404, not 1? Simple! We just have to multiply each side by 8404 to get a solution to our original equation, namelyx=-4776 \times 8404 = -40137504 and y=-313 \times 8404 = -2630452.

We know from earlier that the general solution of our equation has the form:

x = -40137504 + 15625 t

y = -2630452 + 1024 t

It’s easy to see we have our first positive solution att=2569, namelyx= 3121 and y=204. So there were 3121 coconuts originally, and on the last division each sailor got 204 coconuts.

A variant of this problem has there being a single coconut left on the final day as well. In this case there is a very clever trick that can be used, which uses the fact that if we add four coconuts to the original pile it is evenly divisible by 5. If we allow the use of negative coconuts it is easy to see that –4 is a solution. In this case, the first sailor divides the pile into 5 negative coconuts, gives one positive coconut to the monkey, and returns four negative coconuts to the pile, so there are once again –4 coconuts! Each sailor repeats the same process, always leaving –4 coconuts. To get to the first positive solution we just need to observe that since we divide the pile into 5 six times, each successive solution must be5^{6} = 15625 larger than the last, so the first solution is 15621.

This variant appeared in a short story by Ben Ames Williams that ran in the Saturday Evening Post in October 1926. Williams did not include the answer, and the Post’s offices were flooded with letters, to the point where the editor sent Williams a wire: “For the love of Mike, how many coconuts? Hell popping around here”. Williams continued to receive letters requesting the answer for the next twenty years!

Further reading:

I first heard this problem, and learnt the method of continuous fractions, as a high school student when doing an extra-curricular math class at the University of the Witwatersrand’s Schmerenbeck Center (so long ago Diophantus may still have been alive).  Martin Gardner’s Colossal Book of Mathematics discusses this problem in the first chapter, along with some unorthodox and general solutions. Steven Hawking’s book God created the Integers includes annotated excerpts from The Arithmetica, and some biographical material. Clifford Pickover’s The Math Book includes a chapter on Hypatia.

Written by Graham Wheeler

December 13, 2009 at 7:03 pm

Posted in Uncategorized

The End of the Universe

with 2 comments

In the Indian city of Benares, beneath a dome that marks the center of the world, is a brass plate in which are set three diamond needles, each as thick as a bee and a cubit high. At the time of creation Brahma placed on one of these needles 64 disks of pure gold, each a different size, each resting only on plates of a larger size (so the largest disk was at the bottom and the smallest at the top).

In the temple are priests whose task is to transfer all the disks to a different needle, moving only one disk at a time between needles but never placing a larger disk on top of a smaller one. When the task is done, tower, temple and Brahmins all will vanish with a thunderclap and the world will vanish.

So how much time do we have left?

The romantic fable above was popularized (and possibly invented) by one Edouard Lucas to accompany a popular game he invented and sold in 1883, called the Towers of Hanoi. The game itself has only 8 disks (which is fortunate, as we shall see), and is still available today.

2007-03_Hanoi_1st_lab_375 An original Edouard Lucas puzzle. Photo courtesy of the Puzzle Museum.
(C)2009 Hordern-Dalgety Collection http://puzzlemuseum.org

When trying to solve the problem, it helps to start small. Obviously if there were no discs, no moves would be needed, and with one disc, just one move is needed. What about two discs? That would require three moves: moving the smallest disc from the “initial” to the “spare” needle, then moving the largest disc to the “target” needles, and finally moving the small disc to the target needle.

Going beyond two discs things are a little less obvious. If we think about the largest disc though, we can note that in order to move the largest disc from the initial to the target pin, we must first move all the other discs to the spare pin. So, if we have n discs, we can state a solution to the n-disc problem thus:

– move n-1 discs from the initial to the spare needle, using the target needle as a spare

– move disc n (the largest disc) from the initial needle to the target needle

– move n-1 discs from the spare needle to the target needle, using the initial needle as a spare

So we have effectively reduced the n disc problem to an n-1 disc problem. If we repeatedly apply this approach, eventually we get to a 1 disc problem which is trivial.

Even though we have “solved” the problem, it is not obvious what the sequence of moves should be for a large number of discs. Nonetheless, the method above works, and describes a formal recipe, commonly known as an algorithm, to solve the problem. Keeping track of the sequence of moves that have been done and still need to be done can be somewhat tedious for a human, but not for a computer, and the method above is often used in computer programs to solve the Towers problem. The algorithm could be written as:

SolveTowers(from, to, using, n)
{
    if (n > 0)
    {
        SolveTowers(from, using, to, n-1);
        print “Move disc “ + n + “ from needle “+from+” to needle “+to;
        SolveTowers(using, to, from, n-1);
    }
}

If we called the needles A, B and C, and ran the algorithm above with “SolveTowers(A, B, C, 64)” we would get the sequence of moves needed by the monks. Algorithms like the one above, where we break the problem down using a smaller version of itself, are called recursive algorithms.

We still haven’t answered the question of how long it would take, but we’re getting closer. If we call the number of moves needed to solve the n-disc Tower problemS_{n}, then we can see (modeling the steps above):

– we needS_{n-1} moves for the first step

– plus one move for disc n

– plusS_{n-1} moves for the last step

In other wordsS_{n} = 2 S_{n-1} + 1.

This  equation needs to stop somewhere to be useful; we know that one disc takes one move so we know thatS_{1} = 1. So we can write the complete recursive definition ofS_{n} as:

S_{n} = \left\{ \begin{array}{ll} 2 S_{n-1} + 1 & \mbox{if } n>1 \\ 1 & \mbox{if } n=1 \end{array} \right.

Equations like this, where we define sequence terms in terms of earlier sequence terms, are called recurrence relations or difference equations, while known values likeS_{1} = 1 that terminate the process are called boundary conditions.

Towers of Hanoi is just one of many recurrence relations. We’ll look at a few more and then look at some general techniques for dealing with these.

For a first example, consider how many pieces you can slice the plane into with a number of lines, where no two lines are parallel and no three intersect at a single point (lines that satisfy these conditions are said to be in general position). The first line will divide the plane in two; the second line will divide it in four, the third in seven, and in general:

P_n = P_{n-1} + n

whereP_n is the number of pieces after the n’th line. I.e. then^{th} line addsn new pieces. The boundary condition isP_{0}=1.

As another example, consider a population of organisms that takes 2 years to mature after which each pair produces another pair, and continues to do so each year thereafter.

Each newborn pair plus offspring then has an annual population count of 1, 1, 3, 5, 8, 13…, which may be recognized as the Fibonacci sequence:

a_n = a_{n-1} + a_{n-2}

with boundary conditionsa_0 = 1, a_1 = 1.

The problem with these is that in order to compute the value for somen, we have to calculate all values all the way from the boundary condition up to then^{th}. We’d prefer to just have some function in terms ofn.

There are a number of approaches we can use. We can try to find the function by inspection, using some number of terms, and then prove the postulated solution by induction. A related approach is to look at modified versions of the sequence – for example dividing each term byn – to see if a pattern emerges. Adding a constant to each term before the division may make the pattern more obvious.

If we look at Towers of Hanoi, we can see that the first few terms are 1, 3, 7, 15, 31, 63. So a reasonable postulate is:

S_n = 2^n - 1

It is easy to prove this by induction:

S_{n+1} = 2 S_n + 1 = 2 (2^n - 1) + 1 = 2^{n+1} - 1

For the regions of the plane, we can use the second approach. Simple division byn doesn’t offer a clear pattern, but if we first subtract 1 from each term, i.e. look at the sequence\frac{P_n-1}{n}, we get the sequence 1, 1.5, 2, 2.5, 3, 3.5, …, and a clear pattern emerges. It appears that:

\frac{P_n-1}{n} = \frac{n+1}{2}

or:

P_n = \frac{n (n+1)}{2} + 1

Once again by induction:

P_{n+1} = P_n + n + 1 = (\frac{n (n+1)}{2}+1) + n + 1 = \frac{n^2 + 2 + 2n}{2} + 1 = \frac{(n+1)(n+2)}{2}+1

As for the Fibonacci sequence, that is a topic for another day!

Written by Graham Wheeler

December 13, 2009 at 6:00 am

Posted in Uncategorized