Saturday, 1 April 2017

How to use number theory to help bus travellers

Living in London, I use buses a lot.  Each day I catch a 180 or 199, ignoring the 188, 286 and others whcih don't take me home.  I have a good memory for all the different buses in the parts of central London that I frequent, but wouldn't it be easier if the bus number told me where it was going?  If, rather than 180 arbitrarily designating a route between Lewisham and Belvedere, the number itself indicated where the bus goes?

So today I am going to unveil my scheme for taking advantage of the properties of numbers to do exactly that.  I will start off with my first idea, and then show enhancements.

The Fundamental Theorem of Arithmetic tells us that any number can be expresssed as the product of prime numbers in an essentially unique way.  So my first scheme allocates to every destination a different prime number.  For example, we might assign 2 to Waterloo, 3 to Euston and 5 to London Bridge.  Then the bus route serving these three places would be number 30.  All you need to do, as a passenger, is know the number assigned to your destination.  If you want to go to Waterloo, you know that any even-numbered bus will take you there: if you are heading for London Bridge then any bus whose number ends with 0 or 5 will do,

You might object that it is easy to tell when a number is divisible by 2 or 5, but less easy if your destination's number is, say, 17.  But there are tricks: to test whether a number is divisible by 17, one simply tests the number obtained by subtracting five times the last digit from the rest (so for 374, we subtract 20 from 37, getting 17: that tells us 17 divides 374).

But this method has a glaring weakness.  It doesn't tell us the order of the stops.  I want to be able to distinguish the route Euston - Waterloo - London Bridge from Euston - London Bridge - Waterloo since I want to travel direct from Euston to Waterloo, and going via London Bridge would take much longer.  So my improved proposal uses Godel numbering.  If a bus visits destinations a, b, c, ... in that order, its number is 2^a times 3^b times 5^c times ...  And this can be dynamically adjusted during the journey: when the bus has left Euston, the number changes to reflect that the next stop is Londo Bridge.  Now, I can find out not only whether the bus takes me to Waterloo, but how many stops there are first.  In my example, if I am at Euston, bus number 288 (2^5x3^2) will take me to London Bridge and then Waterloo, while 1944 (2^3*3^5) will go to London Bridge via Waterloo.

But my final scheme is even better.  In this one, The bus number is the product of the primes representing the places it visits, each raised to the power of the number of minutes it is expected to take to get there.  If a bus doesn't call at destination p, then the number is not a product of p.  So if I want to get to Waterloo, and bus number n arrives, I check to see what is the largest power of 2 which divides n: that is how many minutes it will take to get there.  Of course, this is adjusted dynamically, in the same way as London's bus stops now tell us how long it will be before the next bus arrives.

You might object that this system assumes bus passengers can carry out mental arithmetic.  But of course, there will be apps to do this for those who are not confident.  I will just point my smartphone at the front of a bus, and the app will read the number (say 7200) and tell me that it will be at Waterloo (destination 2) in 5 minutes (since the highest power of 2 dividing 7200 is 2^5 = 32).

Yet another way in which mathematics can make our lives easier!

Sunday, 12 March 2017

Puzzles from my grandmother

I have been reading the autobiography of one of my heroes - the great popular mathematics writer, Martin Gardner, who along with my school maths teachers Jimmy Cowan and Ivan Wells, inspired me with the excitement of mathematics.  I have come late to Gardner's autobiography, Undiluted Hocus-Pocus, which was published a few years ago, partly because of luke-warm reviews, and while I enjoyed many of the anecdotes, I wouldn't regard it as essential reading even for those who, like me, admire Gardner enormously.  But I'm glad to have read it.

One of Gardner's stories reminded me of my own childhood.  Gardner recounts his uncle telling him a riddle.  "There was one duck with two ducks behind it; one duck with two ducks in front of it; and one duck between two ducks.  How many ducks were there?"

SPOILER ALERT: Gardner notes that his uncle began by saying, "There were three ducks", which gave away the answer.

This reminded me of my paternal grandmother giving me two puzzles when I must have been perhaps in the upper levels of primary school.  I had to make sense of the following:

First riddle:

11 was a race-horse.
22 was 12.
1111 race.

Second riddle:

If the B MT put : .
If the B . putting : .

(I have just googled the first of these, and curiously it is described on one website as a tongue-twister, which it isn't!)


The first riddle reads as "One-one was a race-horse.  Two-two was one too.  One-one won one race. Two-two won one too."

The second is "If the grate be empty, put coal on.  If the grate be full, stop putting coal on."

Monday, 2 January 2017

Why (some) mistakes are interesting

Image of Hull Paragon crash from

Having recently put up here a couple of posts about mistakes, I feel I should perhaps say why I find (some) mistakes fascinating.

As you would expect, there are a number of reasons.

Perhaps a mistake casts interesting light on someone's thought processes, revealing the way a mathematician was approaching a problem or what was in their had as they tackled it.

Perhaps it is simply a cautionary example: seeing how someone else has erred helps one avoid making the same mistake.

Yet another reason is not exactly schadenfreude (though that may be part of it) but that seeing better people than me make errors is encouraging: I make lots of mistakes and it's helpful to realise that most other people do too!

Now, I worked for many years as a software engineer, working on safety-critical systems, and I have taught software engineering.

Errors occur too often in software, and the better we understand how we make errors, the more likely we are to be able to reduce their frequency.

When I was writing software, I felt that there were lessons to be learnt from railway accidents, particularly those where a remarkable combination of circumstances defeated what had seemed to be an infallible system.

You might have had considerable faith in the Tyer electric tablet system, which for many years after its introduction prevented the dreadful collisions on single-track lines which had occurred when two trains travelling in opposite directions entered the same section: but at Abermule in 1921 the combination of many tiny lapses by several individuals subverted what had appeared to be an infallible system.

Equally unlucky was the Hull Paragon accident in 1927, when two apparently independent slips by signalmen interacted in an extremely unlikely way to subvert the signalling system which protected the trains (the photo above comes from

As a software engineer,I felt there was a lot to be learnt from thinking about such system failures: could I be confident that my own system could not fail in some unlikely combination of circumstances, when the accidents at Abermule and Hull Paragon show how even apparently the most secure systems can fail?

Rhese are some reasons I think (some) mistakes are worth our study.

Thursday, 29 December 2016

A curious cat and another curious error

The first mathematics book written in English was the snappily-titled, anonymous An introduction for to lerne to recken with the pen, or with the counters accordyng to the trewe cast of Algorisme, in hole numbers or in broken, newly corrected..., first published in the 1530s.  A few years ago the British Library paid £95,000 for a copy of the first edition.  Happily, a facsimile (of the second edition) is now cheaply available in the wonderful series produced by TGR Renascent Books.

The book concludes by presenting lots of interesting problems and their solutions.  One is a version of the Josephus problem, in which fifteen out of thirty merchants are to be cast overboard to save an overloaded galley in a storm: the reader is given a mnemonic for arranging the merchants so that the right fifteen (the Christians rather than the Saracens, as one would expect for the time) are saved.  The mnemonic is a Latin verse, which seems a little odd for a book whose selling point was that it was in English!  Presumably the author was padding his book out with whatever came to hand, not very carefully, as we shall see.

Another example asks about travellers going in opposite directions between London and Paris and when they will meet, or at least I think that is the intention: but since in the book one traveller is going between Paris and London, and the other between Paris and Lyon, they are unlikely to meet unless one of them gets badly lost.  It seems that our author was trying to make the problem more relevant to an English readership but didn't carry his intention through.

The most curious of the problems, to my mind, is "The rule and questyon of a Catte". The problem presented (transcribed from a 1546 edition) is,

"There is a catte at the fote of a tre the lēght of 300 fote / this catte goeth upwarde eche day 17 fote, and descendeth the nyghte 12 fote.  I demaunde in howe ōge tyme that she be at ŷ toppe."

Or in today's spelling, "There is a cat at the foot of a tree of height 300 feet.  This cat goes upward each day 17 feet, and descends each night 12 feet.  I ask, how long a time will she take to reach the top?"  It's good to see that even as far back as the sixteenth century, authors of maths textbooks were presenting realistic real-life problems to their students.

Luckily our author provides the solution:

"Answere.  Take by and abate the nyghte of the day, that is 12 of 17 and there remayneth 5, there fore the catte mounteth eche daye 5 fote / deuyde now 300 by 5 and thereof cometh 60 dayes then she shall be at the toppe.  And thus ye maye do of all other semblable."

That is, "Subtract the night from the day, that is 12 from 17: this gives 5, therefore the cat mounts each day 5 feet. Divide now 300 by 5 and you get 60 days: then she shall be at the top.  And thus you may do all other similar problems."

Which is very neat and useful.  But unfortunately the answer is wrong.  After sliding down 12 feet on the 57th night, the cat will be at a height of 285 feet and will reach the top of the tree after 58 days, not 60.

What is curious about this is that the author seems to have missed the point of the puzzle.  It is interesting, surely, only because it is a trick question, but the author has fallen for the trick. What has happened?

A historian friend with whom I discussed this had a plausible idea.  The author was probably taking his problems from a continental book.  This book may have presented the problem of the cat, and first derived the incorrect solution as above, but then went on to say something like, "But in fact this is not the correct answer, because ..." and explained the trick.  However the unwary writer of An introduction ... didn't read any further, and reproduced the problem with the incorrect solution.  Who knows how many generations of English students were bemused by their cats gaining the top of the tree two days earlier than they had calculated as a result of this carelessness?

Friday, 2 December 2016

Learning from the audience at my Prisoners' Dilemma talk

Today I had the privilege of taking part in an excellent "Mathematics in Action" day at which around 700 school students heard a series of talks about maths.  I was talking about one of my favourite subjects, the Prisoners' Dilemma (PD) (I gave a rather different talk about the same material at Gresham College a few years ago.)  I was in amazing company: the other speakers were David Acheson, James Grime and Hannah Fry, and we were wonderfully compered by Sarah Wiseman.  It was a delight to talk to such an enthusiastic audience.

This was my second such event, and this time I had enough confidence to ask the audience (by show of hands) how they would play the games I was discussing.  I had hoped to win more than my fair share of the "Rock, Paper and Scissors" games, but the audience out-thought me (it probably didn't help my cause that, thanks to a clicker malfunction, my choice was revealed to the audience earlier than I had intended).

But the really interesting thing was when I asked whether the audience would co-operate or defect in the Prisoners' Dilemma.  To my surprise, the vast majority of the audience chose to co-operate: to my even greater surprise, those who defected were loudly hissed by many in the audience!  This made a point that I was coming to (very briefly) at the end of my talk: games like the PD give us insights not just into games but into issues like trust and reputation.  If defecting in a PD results in this kind of opprobrium, then the benefit of a shorter prison sentence may be negated by the damage to one's reputation, and this kind of peer pressure makes co-operation a more profitable choice than defection.

But then when I asked the audience about the "Cold War arms race" PD - should a superpower invest its resources in more and bigger nuclear weapons rather than in health research and education? - the response was different.  People who would co-operate in the standard PD, rather than betray their friend, chose to build up their nuclear arsenals.  Furthermore, there was no hissing.  (To be fair, the way I asked the questions may have had a lot to do with the answers, so I am not claiming that the audience behaviour proves anything at all, only that it is suggestive.)

So basically it appears that we frown upon people who are selfish in their dealings with individuals, but when it is selfishness at national level, our response is quite different.  If this reading is correct, then there ia a real challenge to achieving co-operation between nations because we perceive that kind of co-operation as fundamentally different from people interacting as individuals, and we don't feel the same social behaviour to be nice to other nations as we do when we interact with people.

As Martin Nowak says in his fascinating book Super Co-operators, "… Our analysis of how to solve the [Prisoners'] Dilemma will never be completed.  This Dilemma has no end."

Tuesday, 29 November 2016

A curious error

One of the happy outcomes from the recent MathsJam conference (See my previous post) was that I was able to get my copies of two recent maths books signed by their authors.  (It would have been three had my copy of Matemagia not already been signed.)  One was Problems for Metagrobologists by the mathematical puzzles expert David Singmaster.  This is a collection of mathematical puzzles, with a lot of fascinating insights and historical comments.  (I'm not convinced David's title will maximise sales of this excellent book: using a word which many of your target audience may not understand is probably not the most effective marketing technique.)

I was interested in Singmaster's discussion of his puzzle 196 ("Not so likely").  He quotes a 1977 magic book which indicates a good bet - you ask your dupe to cut a pack of cards into three and bet even money that there is an Ace, a Two or a Jack at the bottom of one of the piles.  Apparently the original author indicates that there is about a two-thirds probability that you will win - Singmaster not only asks you whether this is right (it isn't!) but also invites you to speculate on how the author went wrong.

I was interested because I had recently acquired a 1964 book on mathematical magic, and had opened it at exactly the same problem (well, in this case the winning cards are an Ace, a Four and a Jack). But this author (whose blushes I will spare by not naming him) gives a different answer, albeit also wrong.  This book indicates that the chance of winning is 36 in 52,   There are twelve ways the bottom card of the first pile can win, twelve winning cards for the bottom card of the second pile, and twelve for the third pile: a total of 36.  I will leave the reader to identify the fallacy in this argument.

The author goes on to say that, of one cut the deck into four piles, one would have an overwhelming 48 in 52 chance of winning.  (Did he try it?  It wouldn't take too many attempts to cast doubt on that claim.)

I find it astonishing that the author didn't go one step further, and comment that if one divided the deck into five piles, one would have 60 chances of winning out of 52.  At that point it becomes clear that something is very wrong with the argument.

So why didn't the author take that step, and see that he had made an error?  Did he do so, realise there was a problem, and give up, hoping his readers wouldn't notice?   Did the author really believe his answers?  Is the whole thing some sort of joke?  Probability is a difficult subject and it is easy to go wrong.  But this author is not only well-read but also well-connected (he thanks Martin Gardner for advice in his introduction).  Could he really be unaware that he had got this example so badly wrong? Whereas Singmaster in his book gives a plausible guess as to how his author arrived at his erroneous two-thirds figure, I find it puzzling that my author didn't carry his argument that one step further and see that he had gone wrong.

I'm not quite sure what moral to draw from this!

Tuesday, 15 November 2016

The impossibility of blogging about MathsJam

I thought I would do a blog post on the MathsJam weekend conference which I have just attended. This was two days of short (five-minute maximum)  talks about interesting maths, delivered by a wide variety of speakers.  Although by definition anything presented at MathsJam is recreational, topics varied from very pure mathematics to very applied, with statistics, operational research, computing and communication all included (and also art and poetry).  I think I say this every year, but 2016 was the best MathsJam yet.

My plan for this blog post was to describe three or four highlights and ideas I had taken away.  But after a quick look at my notes I find that that would be impossible,  There were too many highlights to mention: no small selection could be fair.  So all I'm going to do is refer readers to the website which, we are promised, will in due course make the presentations available, and thank the organisers and participants for providing such an amazing, inspiring, friendly weekend.