December | 2009 | MagiMathics

Archive for December 2009

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:

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.

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.

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 to $x^{2}+y^{2}=z^{2}$ for a given value of $z$ , 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 coconuts $x$ and the number hidden away by each man as $a, b, c, d, e$ respectively, and the number of coconuts each sailor got on the next day as $y$ , 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 left $4\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 case $a=1024$ , $b=-15625$ and $c=8404$ , and we have:

$1024x - 15625y = 8404$

If $a$ and $b$ have a common denominator, then clearly for the equation to have integer solutions $c$ 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 for $x$ must satisfy:

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

If $g$ is the GCD of $a$ and $b$ , then we can divide both $a$ and $b$ on the right hand side by $g$ 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 that $x=-4776$ and $y=-313$ is a solution of $1024x-15625y=1$ . This is all very well but how do we adjust this for the fact that the $c$ 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, namely $x=-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 at $t=2569$ , namely $x= 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 be $5^{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!

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.

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 problem $S_{n}$ , then we can see (modeling the steps above):

– we need $S_{n-1}$ moves for the first step

– plus one move for disc n

– plus $S_{n-1}$ moves for the last step

In other words $S_{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 that $S_{1} = 1$ . So we can write the complete recursive definition of $S_{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 like $S_{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$

where $P_n$ is the number of pieces after the n’th line. I.e. the $n^{th}$ line adds $n$ new pieces. The boundary condition is $P_{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 conditions $a_0 = 1, a_1 = 1$ .

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

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 by $n$ – 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 by $n$ 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: