MagiMathics

Just another WordPress.com weblog

A Christmas Carroll

with one comment

On Christmas day, 1877, Lewis Carroll, author of the Alice books, entertained two bored young girls by inventing a new game that he called Word Links: given two words, change one word to the other by changing a single letter at a time with the intermediate steps all being valid words themselves. For example, to change “cold” to “warm”, one can use the steps “cord”, “card”, “ward”. Carroll later popularised this form of puzzle in a series of articles in Vanity Fair magazine, changing the name to Doublets – from the “double, double, toil and trouble” witches’ incantation in Shakespeare’s Macbeth.

These puzzles are still popular today (usually called Word Ladders). The noted Stanford computer sciencist Don Knuth dedicated several pages of his work on graph algorithms (The Stanford Graphbase) to the topic. Knuth investigated five-letter words and found that of a set of 5,757 common English words, there were 14,135 links between words (where a link is a single ladder step). Only 671 words had no links – Knuth called these words ‘aloof’ – ‘aloof’ itself being aloof, along with words such as ‘earth’, ‘ocean’, ‘sugar’ and ‘laugh’. 103 pairs such as ‘opium’ and ‘odium’ exist. The two biggest connected sets have 25 words each. By relaxing the rules – for example by allowing the letters to be rearranged at each step – the words become considerably more connected.

Ted Johnson conducted an analysis of four letter words, with the additional rule of allowing the word to be reversed at any step. Starting with an online dictionary of 4776 words, he found that there was one huge linked component of 4436 words. This is not surprising; in 1960 Paul Erdős and Alfred Rényi proved that if the average number of links is sufficiently high then the set of words will form one large connected component with a few outliers.
Word ladders are interesting because of their similarity to genetic mutation in DNA. Carroll himself came up with the evolutionary chain ‘ape’, ‘are’, ‘ere’, ‘err’, ‘ear’, ‘mar’, ‘man’, although he was a sceptic of Darwin’s theories.

Consider the subsequence from ‘err’ to ‘man’ – can you prove that to change one word with a single vowel to another word with a single vowel but in a different position, that it is necessary to go through an intermediate step of a word with two vowels? For the purpose of this problem, consider ‘y’ to be a vowel.

Advertisements

Written by Graham Wheeler

March 29, 2011 at 10:11 pm

Posted in Uncategorized

The Gym Locker Paradox

leave a comment »

It happens so often – you go to your section of the gym change room, and there is just one other person there, and they are using the locker next to yours and blocking the way. I noticed this a long time ago, and noticed that others noticed it too, referring to Murphy’s law, or “just my luck”, or some such explanation. Why does it happen so often?

I call this the Gym Locker Paradox. It is related to a much more well known paradox, the Birthday Paradox, which is commonly formulated as a puzzle: how many people do you need to have in a room together before the odds are better than even that two share the same birthday?

Obviously in a non-leap year, if there are 366 people you are guaranteed a matching pair (in the worst case there will be one person for every day of the year plus one duplicate). This worst case is generalized as the Pigeonhole Principle – if you have n items shared between m containers, then if n > m at least one container will have more than one item.

 

The answer to the Birthday Paradox is 23. This is because we care only about any pair matching, not a particular match. There are a large number of possible pairs in this case.

We can calculate the probability more easily by thinking about the probability of no match. For one person this is 1. Add a second person and they for them not to match they must have a birthday on one of the other 364 days, i.e. the probability of them not matching is 364/365. Similarly, for the third person not to match they must be on one of the 363 days left, with probability 363/365. The total probability for n people is then:

P(n) = \frac{365}{365} \times \frac{364}{365} \times \frac{363}{365} \times \ldots \times \frac{(365-n+1)}{365} = \frac{365!}{365^{n} (365-n)!}

which falls below 50% at 23 people.

This result – which many people find surprising – is the basis of what are known as Birthday Attacks on cryptographic hash functions used in computer security. Cryptographic hash functions compute some value that is treated as a secure “fingerprint” of a much larger input. For example a digital contract may be “signed” using such a function. An attacker could use the birthday paradox to try to create two versions of a contract with the same fingerprint, one of which is legitimate, then get the legitimate contract approved based on the fingerprint, and finally substitute the fraudulent one. If just the fingerprint is used for verification the fraudulent contract will be accepted. To avoid this kind of attack the number of possible fingerprints needs to be extremely large before the attack becomes impractical.

The math behind the gym locker paradox is much more complex. However, clearly if a locker has multiple neighbors the chance of two people having adjacent lockers is that much higher (consider a version of the birthday problem where we consider a collision to be not just a match but a match within a day or two of each other). Add to that the fact that gym locker selection is not entirely random (people like lockers at eye level rather than lower down, for example), and it is no wonder just a few people can clog up a change room.

Written by Graham Wheeler

January 20, 2011 at 6:02 am

Posted in Uncategorized

The Calculus of Democracy

leave a comment »

Earlier this year I went to a “guys movie night” at a friends house. Before the movie we sat around drinking Croatian Schnapps and eating Chinese food, and the conversation turned to politics. There was general agreement that our various political systems were highly suspect and not very democratic, but Ray, the Texan lawyer with the Croatian wife who had provided the schnapps, explained the Australian system of instant runoffs and asserted that this was at last a fair system.

For those not familiar with this system, let me explain: voters get to rank the candidates in order of preference. The votes for everyone’s first preference are counted, and the candidate who gets the least votes is eliminated. That candidate is also struck from the voters choices and the process is repeated until there is a candidate that has more than 50% of the vote.

This Marquis de Condorcetseems fair on the surface – if someone obviously gets too few votes they should be out of the running, and everyone gets their preferences for the remaining candidates counted. But back in 1785, the Marquis de Condorcet pointed out paradoxes in this system. For example, if there are three candidates A, B, C and three voters who rank them A-B-C, B-C-A, and C-A-B, the system is a tie. In general, this is known as Condorcet’s paradox.

Still, this system is more fair then the plurality voting systems used in Canada, India, the UK and the USA, where in each district the winner takes all. In systems with multiple parties the winner may get way less than half the vote and still get to represent the entire district. Often two dominant parties with similar policies will split the vote allowing a less popular party to win a majority.

Sometimes a hybrid system with a second run-off election between the top two candidates is used – but due to the vagaries of plurality systems, the “top two” candidates may not really be the top two at all.

In two party systems like the USA parties mostly compete for the center, causing the difference between them to become all but irrelevant (in economics this is known as Hotelling’s law). Over time these systems tend to lose the interest of the voters, occasionally being re-energized when someone breaks the mold and retargets the extreme instead, as George W. Bush did.

The Gerry-ManderAnother problem with plurality systems is the way in which voting district boundaries are drawn up. A candidate may even win the election while losing the popular vote overall, as George Bush did in 2000. Economic and other factors often cause areas to have a preference for one party over another, and ruling parties often exploit this by redrawing boundaries while they are in power to favor their chances, a process known as gerrymandering after the 19th century governor of Massachusetts, Elbridge Gerry, who drew up a district map so convoluted it was compared to a salamander (see photo).

Yet another common system is proportional representation, where each district has representatives allocated to each party in proportion to the percentage of votes that party obtained. Once again this is subject to issues with how districts are divided up. It may seem to make sense to have just one district, the entire country – the system used in Israel – but the disadvantage is that voters end up with little control over which individuals represent them, even if they do have some control over which parties do. Furthermore, such systems often end up with weak coalition governments that are hamstrung and ineffective, or in which minority parties can wield excessive power as “king-makers” for their bigger rivals.

So what makes a fair system? In 1963 the economist Kenneth Arrow came up with four attributes that he felt described a fair voting system – and then went on to prove Arrow’s impossibility theorem – no voting system could satisfy all four conditions. Democracy, it seems, isn’t.

Written by Graham Wheeler

July 20, 2010 at 5:03 am

Posted in Uncategorized

Fibonacci ties it all together

with 2 comments

In the past few posts I have discussed a diverse set of topics, from number representation to recurrence relations, Pythagorean triples.

All of these topics are related, and this is particularly illustrated when we consider the work of Leonardo of Pisa, better known as Fibonacci (from the Latin “de filiis Bonacci”, or “of the family of Bonacci”). Fibonacci was born in 1175, in Pisa, Italy, shortly after the start of the construction of the famous leaning tower. The city of Pisa was a maritime republic which had its own colonies, including Bugia (in modern day Algeria), where Leonardo’s father moved in 1192 to be a clerk in the customs house. It was here that Fibonacci became acquainted with the Hindu numerals and zero, and where his Muslim teacher introduced him to the the great book Al-Jabr wal-Muqabalah. Fibonacci subsequently travelled broadly, where he learnt from mathematicians of different cultures. Around 1200 he returned to Pisa and began work on his masterpiece Liber Abaci, which was published in 1202, and begins with these words:

“The nine Indian figures are 9 8 7 6 5 4 3 2 1.

With these nine figures, and with the sign 0, which the Arabs call zephyr, any number whatsoever is written”.

This is the earliest known formal mention of the decadic Hindu-Arabic number system in the Western world.

A page of the Liber Abaci The Liber Abaci contains a large collection of problems, some aimed at merchants, but most related to algebra and what would now days be considered number theory. One of these problems concerned the rate of reproduction of rabbits, and how the number of pairs of rabbits grows over successive generations assuming each pair spawns another at each generation. If each pair takes one generation to mature, then the number of adult pairs is given by the sequence:

1, 1, 2, 3, 5, 8, 13, 21, …

which are the now-famous Fibonacci numbers, defined by the recurrence relation:

F_n = F_{n-1} + F_{n-2}

These numbers are a source of endless fascination, as they appear in various guises throughout nature, art, architecture, and mathematics. For example, the number of spirals of bracts on pineapples and pinecones are Fibonacci numbers, as are the number of branches on some species of trees, the number of ancestors at each generation of male bees, and more. Furthermore, the ratio between consecutive Fibonacci numbers approaches phi, the golden ratio, which again appears throughout art and science. Many of these relationships only began to be noticed in the 1800’s, and it was in the mid-1800’s that the name “Fibonacci numbers” was given them by Edouard Lucas – the inventor of the Tower of Hanoi puzzle. Today they still command attention, so much so that there is a quarterly journal dedicated to their exploration!

Many of these interesting properties of the Fibonacci numbers will be discussed in future posts; for now, I wish to focus on the relationship of the Fibonacci numbers to the Pythagorean triples. Before doing so I need to point out one of the many interesting properties of the Fibonacci numbers; the proof will be left for another day although you may want to try obtain it yourself:

F_{2n-1} = F_n^2 + F_{n-1}^2

Can you prove the following?

  • If we have a succession of four consecutive Fibonacci numbers a, b, c, d, then (2bc, ad, b^2c^2) form a Pythagorean triple
  • Is it possible to have a triangle whose sides are all distinct Fibonacci numbers? It should be obvious that this is not possible with consecutive Fibonacci numbers, but what if we can choose any Fibonacci numbers?

The first problem is quite easy to prove if we just note that c = a + b and d = c + b = a + 2b, and then expand the three operations in the triple in terms of just a and b:

A = 2bc = 2b ( a + b) = 2ab + 2b^2

B = ad = a (b + a + b) = a^2 + 2ab

C = b^2 + c^2 = b^2 + (a + b)^2 = a^2 + 2ab + 2b^2

If we then square these results it is trivial to see that A^2 + B^2 = C^2 holds.

Interestingly, if we use two consecutive Fibonacci numbers as the coefficients in the Babylonian formulae for Pythagorean triples (i.e. the formulae given by Diophantus), then one of the numbers in the triple is a Fibonacci number. This should be clear from the property mentioned above, which stated that the sum of the squares of two consecutive Fibonacci numbers is a Fibonacci number

For the second problem, assume we have three distinct Fibonacci numbers, F_a, F_b and F_c, ordered by size, so that:

F_a \leq F_{b-1}

F_{b+1} \leq F_c

Then:

F_a + F_b \leq F_{b+1}

So:

F_a + F_b \leq F_c

which contradicts the triangle inequality – namely that the sum of any two sides of a triangle must be greater than the third side.

Written by Graham Wheeler

January 20, 2010 at 5:37 am

Posted in Uncategorized

The Horn of Gabriel

leave a comment »

And the seventh angel sounded [his horn]; and there were great voices in heaven, saying, The kingdoms of this world are become the kingdoms of our Lord, and of his Christ; and he shall reign for ever and ever.” (Revelations 11.15, King James Edition)

In Christian and Islamic folklore, it is the angel Gabriel who is considered to be the seventh angel, who announced the coming of judgement day. An angel with such a huge responsibility clearly needs an instrument worthy of the task, and indeed there is one: Gabriel’s horn, also known as Torricelli’s trumpet, after its discoverer, Evangelista Torricelli, a student of Galileo. Gabriel’s horn has infinite surface area but finite volume, and is described the rotating the curvey=\frac{1}{x} forx>=1 around thex axis.

image

It is easy to see that this shape, which extends to infinity along the positivex axis but gets thinner and thinner, must have infinite surface area. It is less obvious that it has finite volume, although this can be shown with elementary calculus (if you’re unfamiliar with the calculus needed for surface area of revolution and  solid volume of revolution, just bear with me).

The volume is given by:

V = \pi \int_{1}^{a} \frac{1}{x^2} dx = \pi (1 - \frac{1}{a})

While the surface area is given by:

A = 2 \pi \int_{1}^{a} \frac{\sqrt{1 + \frac{1}{x^4}}}{x} dx > 2 \pi \int_{1}^{a} \frac{\sqrt{1}}{x} dx = 2 \pi ln(a)

Clearly in the limita \rightarrow \infty, we have:

V = \pi

A = \infty

At the time that Torricelli discovered this (1641), calculus had not yet been invented, and he obtained the results by a technique developed by his friend Cavalieri, called the summation of plane slices – essentially a technique similar to the calculus of limits using successively smaller slices. This itself required a leap of faith at the time and only became solidified later, as the idea of limits took hold, and the concept of infinitely many infinitely thin slices was given a rigorous mathematical foundation.

Torricelli’s trumpet caused some consternation and disbelief – in 1672, for example, Thomas Hobbes, the English philosopher, claimed that to believe Torricelli would be madness. It appears to result in a paradox, the painter’s paradox: if the volume is finite, the horn can be filled with a finite amount of paint, and yet to cover its interior surface would require an infinite amount of paint! Before reading on, can you resolve this paradox?

The paradox comes from confusing our mental model of real paint with “mathematical” paint. Real paint has a finite thickness – say the thickness of a paint molecule. At some point the trumpet becomes thinner than this, and so with real paint we could neither fill the trumpet nor cover its surface. The only paint that could do this would be “mathematical” paint that has infinitely small thickness. A finite amount of infinitely thin paint could cover an infinite surface.image

While he made a number of contributions to mathematics, Torricelli is more well known for his contributions to physics. He was the first scientist to create a sustained vacuum and suggested the experiments that led to the invention of the barometer; later he went on to use the much more effective mercury in place of water. In his honour the vacuum in a barometer is known as a Torricelli vacuum, and the Torr is a measure of vacuum. He gave the first scientific explanation for wind, which he recognized as being caused by variations in air density caused by temperature differences. He was a skilled lens maker and his telescopes and microscopes provided much of his income. Sadly, he contracted typhoid and died at the age of 39  in 1647;  not all his writing and research was preserved, and had he lived longer he may well have been credited with being the inventor of integral calculus; he was well on the way to understanding its principles.

"We live submerged at the bottom of an ocean of air." – Evangelista Torricelli, 1644.

Written by Graham Wheeler

January 18, 2010 at 6:48 am

Posted in Uncategorized

More on Pythagoras

leave a comment »

Pythagoras is known for two great contributions to mathematics – he established the need for formal proofs instead of just conjecture and rules of thumb, and he established the existence of the irrationals. In popular culture of course, Pythagoras is more well known for the Pythagorean theorem – that the square of the hypotenuse of a right angled triangle is the sum of the squares of the other two sides – but this was one of the oldest known results in mathematics and in fact predates Pythagoras by as much as a thousand years. Nonetheless, Pythagoras provided a formal proof, and the result led him to ask whether there were rational numbers that worked in the case where the hypotenuse had the length two. That is, what was the fractional representation of the square root of two? Pythagoras managed to show there was none, leading to the discovery of the irrational numbers.

His proof was quite simple. Assume that\sqrt{2} can be expressed as a fraction\frac{a}{b} of two whole numbersa andb. Assume these are the two smallest such whole numbers – that is, they have no common divisor allowing the fraction to be further reduced. Then:

\frac{a^2}{b^2} = 2

so:

a^2 = 2 b^2

The right hand side is even, which meansa^2 is even, and thusa must be even, ora=2m for somem. But then:

{(2m)}^2 = 2b^2

so:

2m^2 = b^2

So the left hand side is even, and thusb must be even. But if botha andb are even, then they have a common factor 2, which contradicts the assumption that they were the smallest such numbers.

There are, of course, infinitely many cases where the Pythagorean triangles have sides with rational length, and for that matter, integer length. In a recent post I mentioned the method described by Diophantus that inspired Fermat’s last theorem. It is easy to derive this method. Assumea andb are relatively prime, and thatb is odd. Then:

{(a+b)}^2 = a^2 + b^2 + 2ab > a^2 + b^2 = c^2

Thusc < a+b. So we can writec = a+b-d for some positived. Then:

a^2 + b^2 = {(a+b-d)}^2 = a^2 + b^2 + d^2 + 2ab -2ad -2bd

So:

d^2 = 2ad + 2bd - 2ab

From this we can seed must be even. Letd=2m; then:

4m^2 = 4am+4bm-2ab

So:

ab=2am+2bm-2m^2

Thusab is even, and as we assumedb is odd,a must be even. Since the sum of an even and an odd is an odd,c^2 must be odd and soc must be odd.

Soa is even, andb andc are odd. We can writeb=s-t andc=s+t for some integerss andt. Then:

a^2 + {(s-t)}^2 = {(s+t)}^2

or:

a^2 + (s^2 - 2st + t^2) = (s^2 + 2st + t^2)

Simplifying:

a^2 = 4st

Sost must be a perfect square. We can writes=u^2 andt=v^2. Thus:

a^2 = 4u^2v^2

So:

a=2uv

So we have shown that a Pythagorean triple takes the form:

( 2uv, u^2-v^2, u^2 + v^2 )

Written by Graham Wheeler

January 17, 2010 at 3:12 am

Posted in Uncategorized

Much Ado about Nothing

with one comment

Many people have heard that the number zero was introduced later than the other digits. Upon hearing this it seems fantastical – how could people have managed even elementary arithmetic without zero? However, it is not the concept of “nothing” that was missing, but rather the use of a zero in other places when representing or recording numbers. For example, in the number 101, zero is used as a separator, and it is this concept that was lacking in early number systems.

Medieval tallies

We are used to our modern decimal representation where each digit represents units, tens, hundreds, thousands, etc. Not all systems worked that way – the Roman system is a well-known example of a different approach. Throughout history there have been many alternative ways of recording numbers. In ancient China and the South Sea islands knots in string were used. Creating notches in sticks is another (the word score has its roots in this method, as do the Roman numerals I, II, III). Contracts were often formalized by scoring a piece of wood with an appropriate count then splitting it in two with each party taking half; the halves would be matched up later to ensure no alteration. The burning of the Parliament, painted by Turner In Britain such Exchequer tallies were used from the 12th century and were legally binding until 1826; in 1834 the burning of the no-longer required tallies started a fire that destroyed the old Parliament buildings.

The use of simple score marks developed with writing into more sophisticated forms. Different symbols were used for values of different magnitudes, and they were repeated as necessary (e.g. III for 3, and CCC for 300 in Rome). The use of subtractive methods (IV instead of IIII) was a later innovation.

This simple grouping approach evolved into a multiplicative approach, where instead of repeating a symbol it was preceded with a count. For example, if that were applied to Roman numbers we might write 3C3V for 315. A real example is the Chinese-Japanese number system.

A different approach is a ciphered approach, where there are separate symbols for the ten symbols 0 through 9, then the nine symbols 10 , 20, 30 through 90, then 100, 200, 300 through 900, and so on. Examples of this are the Hindu Brahmi and the Egyptian hieratic and demotic systems. Variations on this, where alphabetic characters were repurposed for numbers, are the Greek numerals, Hebrew, Syrian and Gothic systems.

Unfortunately, many of these systems are ill-suited for calculations, as anyone who has attempted math on Roman numerals will know. Performing arithmetic was thus considered an advanced art and required the assistance of tools such as the abacus.  It was only with the spread of the Hindu-Arabic decadic positional system around 800AD that arithmetic operations became easy to perform without assistance. It was positional systems that necessitated the introduction of a symbol to represent no value at a particular position, to distinguish, for example, 31 from 301. The lack of a zero made the earlier positional systems such as the Babylonian sexagesimal system highly ambiguous, although the Mayans developed an early positional representation system that included a zero, which may account for why their mathematical calculations were considerably more advanced and accurate than other cultures.

A page of Al-Jabr wal-Muqabalah The spread of the Hindu-Arabic system was largely facilitated by the translation into Latin of the text Al-Jabr wal-Muqabalah (hence: algebra) by the great Arab mathematician Mohammed ibn Musa al-Khowarizmi.  The use of this system became known as algorism (leading to the modern word algorithm) , but its adoption took time; the abacists who adhered to the Roman system resisted the algorismic system and it took until the 16th century for it to become predominant in Europe.

Written by Graham Wheeler

January 13, 2010 at 5:53 am

Posted in Uncategorized