The Big Internet MathOff is now taking place. Sixteen mathematicians are competing in a knock-out tournament to present the most interesting piece of mathematics. With the final two matches of the first round now taking place, there has already been a wealth of fascinating mathematics presented. Christian Lawson-Perfect deserves huge thanks for creating this wonderful showcase of exciting maths.

But not only are the contestants' pitches fascinating. There is also interesting maths involved in the background.

First, Each match runs for 48 hours. As a contestant, my most pressing question today is whether I will win my first round match against Jo Morgan, in which case I will need to work urgently on my pitch for round 2. So the question is, how soon can I extrapolate from the early votes to be reasonably sure of the outcome?

I am sure that this has been studied in the context of political elections. But this is harder because the electorate is everybody with access to the internet - several hundred million people (though not all will actually vote).

Now, when I first looked at the score ten minutes after the match started, I was leading by 2 votes to 1, but I think that was a bit too early to be confident of the result. As I write this, four hours into the match, Jo is leading by 58 votes to 29, and my share of the vote has consistently been around 30% for some time. Although time differences may mean that America has yet to vote, my intuition is that I can safely abandon my pitch for round 2 and turn to other things like writing blog posts.

I've already had to find my answer to my second problem. Each contestant has to provide a different piece of fun mathematics for each round so we all had to submit four topics before the tournament started. It's unlikely that each set of four topics were all equally good. So what order do you choose for your topics? Do you save your best one for the final? In that case, you might not get to the final and your best idea is wasted. Or do you use your best ideas in the early rounds, to improve your chances of progress, but risk putting your weakest idea forward in the final?

There may be a similarity with World Cup penalty shoot-outs. With five penalties to take, it's clear that a team should select their best five penalty takers. But in which order should they take the penalties? One suggestion is that you should save your best penalty-takers for the end, when the pressure will be greatest. But that could mean that your team has lost 5-3 and your best taker hasn't taken one of the penalties. The great Ally McCoist, commenting on last night's shoot-out between Russia and Croatia, argued for putting your best takers first, guaranteeing that at least they will take penalties. I'm not convinced that's a sound argument, though if you score your early penalties then the pressure on your opponents will increase.

So what did I do for the MathOff? Did I save my best idea for the final, or bring it out for the first round? Well, there is a further complication. I have no idea how to judge which of my topics would win most votes in an internet poll. Ranking them in order would have been pure guesswork. So, shamefully, I didn't use any game theory or simulation to decide the order of my pitches - I just entered them in the order in which I thought of them. Which may be as good a strategy as any!

## Sunday, 8 July 2018

## Sunday, 20 May 2018

### Mathematical discoveries

I was lucky enough to attend a meeting organised by the British Society for the History of Mathematics on "The History of Cryptography and Coding". It was a quite exceptional meeting - six excellent talks. As one of the other audience members said, I learned something from every talk, and a lot from several talks. (Anyone who goes to these events will know that this isn't always the case.)

The final talk, by Clifford Cocks on the discoveries of the public key cryptography, was fascinating in many respects. (Cocks was one of the people at GCHQ who discovered both the Diffie-Hellman key exchange method and the Rivest-Shamir-Adleman (RSA) algorithm before those after whom the ideas are named, but this wasn't known until GCHQ made it public over 25 years after the event.) Cocks told us about the (different) reasons why the British and American discoverers were looking for these methods. I was particularly struck by his insights into the creative processes that led to the discoveries.

In 1970 James Ellis at GCHQ had the idea of public-key cryptography. Many people at GCHQ tried to find a way to implement it, without success. Cocks suggested that this was because of "tunnel vision" - because Ellis's paper suggested using look-up tables, everyone was focused on that idea. Cocks had just arrived at GCHQ from university, and his mentor mentioned Ellis's problem to him, but described it in general terms without mentioning look-up tables. Without having been led in a wrong direction, Cocks quickly came up with the idea of using factorisation, and the problem was solved. (When Cocks told his colleague and housemate Malcolm Williamson about his paper, Williamson overnight worked up the idea of using the discrete logarithm problem, anticipating Diffie and Hellman.)

Cocks also told us about how Diffie was working on these discoveries having left his academic job, supporting himself on his savings - something which I don't recall knowing.

Then Cocks told us about Rivest, Shamir and Adleman's discovery of RSA. They had tried about 30 ideas, none of which worked. Then after a Passover meal at which alcohol flowed freely, Rivest had the big idea, wrote it down, and checked the next morning to see if it still worked.

I think these stories shed some light on mathematical creativity. It needs hard work, of course, but it also needs flexibility. Cocks (by his modest account) had the advantage over his colleagues that his mind wasn't conditioned by an unproductive idea. Rivest's solution came after a break from thinking about it. Of course, there are many other examples - PoincarĂ©'s inspiration as he was getting on a bus is the standard one - but it is always interesting to hear how great mathematical discoveries came about, and to hear this story from Cocks himself was a wonderful privilege.

The final talk, by Clifford Cocks on the discoveries of the public key cryptography, was fascinating in many respects. (Cocks was one of the people at GCHQ who discovered both the Diffie-Hellman key exchange method and the Rivest-Shamir-Adleman (RSA) algorithm before those after whom the ideas are named, but this wasn't known until GCHQ made it public over 25 years after the event.) Cocks told us about the (different) reasons why the British and American discoverers were looking for these methods. I was particularly struck by his insights into the creative processes that led to the discoveries.

In 1970 James Ellis at GCHQ had the idea of public-key cryptography. Many people at GCHQ tried to find a way to implement it, without success. Cocks suggested that this was because of "tunnel vision" - because Ellis's paper suggested using look-up tables, everyone was focused on that idea. Cocks had just arrived at GCHQ from university, and his mentor mentioned Ellis's problem to him, but described it in general terms without mentioning look-up tables. Without having been led in a wrong direction, Cocks quickly came up with the idea of using factorisation, and the problem was solved. (When Cocks told his colleague and housemate Malcolm Williamson about his paper, Williamson overnight worked up the idea of using the discrete logarithm problem, anticipating Diffie and Hellman.)

Cocks also told us about how Diffie was working on these discoveries having left his academic job, supporting himself on his savings - something which I don't recall knowing.

Then Cocks told us about Rivest, Shamir and Adleman's discovery of RSA. They had tried about 30 ideas, none of which worked. Then after a Passover meal at which alcohol flowed freely, Rivest had the big idea, wrote it down, and checked the next morning to see if it still worked.

I think these stories shed some light on mathematical creativity. It needs hard work, of course, but it also needs flexibility. Cocks (by his modest account) had the advantage over his colleagues that his mind wasn't conditioned by an unproductive idea. Rivest's solution came after a break from thinking about it. Of course, there are many other examples - PoincarĂ©'s inspiration as he was getting on a bus is the standard one - but it is always interesting to hear how great mathematical discoveries came about, and to hear this story from Cocks himself was a wonderful privilege.

## Sunday, 28 January 2018

### London buses, and the use of the mean as an estimate

A couple of weeks ago, I got onto my morning bus, climbed the stairs, holding on as the bus lurched forward, and sat down, to hear for the first time the new announcement "Please hold on: the bus is about to move", introduced by TfL (Transport for London). Over the next few days this announcement was widely ridiculed. It was broadcast after every stop, but often - in my experience almost always - AFTER the bus had started moving, and sometimes when it was slowing down for the next stop, making the announcement appear ridiculous. Occasionally, at busy stops like the railway station, it was broadcast while large numbers of people were still waiting to board, presumably causing consternation to prospective passengers who took it seriously. And on one occasion, while the bus was stationary, I heard "The bus is about to move" followed immediately by the announcement "The driver has been instructed to wait here for a few minutes", flatly contradicting the previous words.

What was happening? TfL explained that they were piloting the announcement for four weeks, to try to reduce the number of injuries sustained by passengers on moving buses - apparently of the order of 5000 each year. The timing of the announcement was based on the average time buses spent at each stop - I suspect by "average" they meant the mean.

The intention is laudable. But the problem with using a mean in situations like this is that it doesn't really tell you how long a particular bus will wait at a given stop. My bus home probably spends longer stopped at the railway station than at all the other stops put together. Just as most people earn less than the mean national salary, which is heavily influenced by the very small number of people earning millions each year, so I imagine most of the time a bus spends less time at a stop than the mean. So a system based on the mean time spent at a stop will result in the announcement usually being played after the us has left the stop, leading to ridicule.

Now, TfL are pretty good at maths - their planning of the transport around London during the 2012 Olympics was a very successful example of operational research in action. So did they really get this wrong? After all, one would think that a few tests would have shown the problem.

Certainly one result of the announcements was a great deal of publicity, which perhaps has made people more aware of the need for care when standing and moving on a bus. The announcements themselves may have a short-term effect, but in fact one very quickly ceases to notice them (or at least I have found that they very rarely impinged on my attention, after the first few instances on the first day). But perhaps the press coverage, and people talking about the announcements, had more impact than the announcements themselves.

But if the announcements are to continue, how can TfL avoid the absurdity of an announcement that the bus is about to move being broadcast after it has moved? The solution TfL have adopted (as well as apparently changing the timing) is simple. The wording of the announcement is now "Please hold on while the bus is moving". The timing no longer offers the possibility of absurdity. The solution to this problem was not mathematical modelling, but thoughtful use of language.

## Sunday, 19 November 2017

### MathsJam

Here is my overdue post on last weekend's MathsJam gathering. MathsJam is always a wonderfully exciting and enjoyable weekend, and this one was particularly good. I can honestly say that I enjoyed every talk, and was entertained, surprised and educated in roughly equal measures.

I'm nervous about selecting highlights, because almost everything was a highlight, and my list inevitably leaves out many excellent talks. There is a list of all the talks on the MathsJam website but here are some I particularly remember (in the order in which they were presented):

And of course the "extra-curricular" puzzles, games and magic, Tiago showing me how to tie a knot with one hand, and the spectacular mathematical cakes.

So once more a memorable MathsJam, with an excellent range of speakers and talks, friendly atmosphere and fascinating and surprising mathematics. The organisers once again did an amazing job!

I'm nervous about selecting highlights, because almost everything was a highlight, and my list inevitably leaves out many excellent talks. There is a list of all the talks on the MathsJam website but here are some I particularly remember (in the order in which they were presented):

- Simon's 3D-printed robot which solves Rubik's cube (time-lapse video shown here with Simon's permission);
- Matt on logical deduction games, which brought back memories of playing Eleusis when I was a student and introduced others I need to find out about;
- Noel-Ann on data and how to it can be represented (and misrepresented);
- Zoe's poem about
*e*, which (understandably) seems to be on everybody's highlight list; - Matthew's amazing recreation of a problem from
*Captain Scarlet*about the bongs of Big Ben; - Andrew's paradoxical balloon monkey, which although made from a single balloon, has an underlying graph which is not semi-Eulerian;
- Angela's poem;
- Rachel on spinning yarn;
- Alison on illogical units, and Dave on illogical scales;
- Will on non-binary cellular automata;
- Miles finding striking similarities between mountaineering and mathematics;
- Glen showing how many holes a constructed object (equivalent to a T-shirt) possessed (most of MathsJam seem to have got it wrong, going for four rather than three!);
- Sue on Ada Lovelace;
- Paolo using a pack of cards to find two numbers from their sum and difference;

And of course the "extra-curricular" puzzles, games and magic, Tiago showing me how to tie a knot with one hand, and the spectacular mathematical cakes.

So once more a memorable MathsJam, with an excellent range of speakers and talks, friendly atmosphere and fascinating and surprising mathematics. The organisers once again did an amazing job!

## Wednesday, 8 November 2017

### Looking forward to MathsJam

With only three days to go till the MathsJam Gathering - the best weekend of the year, I've been thinking of some of my favourite MathsJam discoveries. Sticking to pure mathematics, here are my memories of three gems. I could have chosen many others, but perhaps because these happen to relate to my current teaching, and I showed two of them to my graph theory students immediately upon my return from the gathering, they are the first that come to mind. Since I believe all MathsJam presentations are available online, further details should be readily available.

I could have chosen many more examples: I'm certainly not ranking these presentations or any others. On another day I might have chosen a completely different set! But I'm certainly looking forward to coming across more wonderful mathematics this weekend!

- Colin Wright's amazing talk on graph colouring, which started by asking us to complete a partially-completed 3-colouring of a small graph, and turned into a more-or-less complete proof, within a 5-minute talk, that there is no polynomial-time algorithm for 3-colouring a graph.
- Ross Atkins's talk about Braess's Paradox - a simple situation in which adding an extra road to a network, with no increase in traffic, results in longer average journey times. I should have known about this counter-intuitive result so I'm very glad to have found out about it, and especially with the wonderful demonstration with a network of springs that showed a mechanical realisation of the paradox.
- David Bedford's "What's my polynomial?" I love this because it is arguably what the late Raymond Smullyan called a "monkey trick". David asked you to think of a polynomial
*p*(*x*) with non-negative integer coefficients, and, for a single value of*x*of your choice, greater than any of the coefficients, tell him both*x*and*p*(*x*). He would then tell you your polynomial. Knowing that one needs*n*values to determine a polynomial of degree*n*, I was taken in by this!

I could have chosen many more examples: I'm certainly not ranking these presentations or any others. On another day I might have chosen a completely different set! But I'm certainly looking forward to coming across more wonderful mathematics this weekend!

## Wednesday, 1 November 2017

### Black Mathematician Month

One of the best things to have happened for mathematics in the UK recently is the arrival of Chalkdust magazine - an exciting, witty magazine with a unique style. (It's very different in feel from the equally admirable, and much missed,

And the best thing that Chalkdust has done is the Black Mathematician Month which has just finished - a month of interviews, conversations and activities "promoting black mathematicians, and talking about building a more representative mathematical community". The stories that were told were sometimes shocking, sometimes horrifying, often inspiring, and very important. I was lucky enough to be one of the large audience for the final event, an excellent talk about the Black Heroes of Mathematics by Nira Chamberlain (and I was particularly pleased that several undergraduates from the University of Greenwich were also there). Nira told us about a number of great black mathematicians: despite his own negative experiences as a young black man wishing to become a mathematician, and the obstacles in his way, his presentation was overwhelmingly positive in tone and his passion communicated strongly with the audience.

I myself was a very privileged mathematics student. I had an adequate grant and did not need to work while I was studying. I had a supportive family. Both my parents went to university (probably quite unusual for the time although I didn't realise that), as did my father's sister (I believe the first woman from her school to do so) and all my siblings. I was supported not only by their academic expectations but by their understanding of university education. I was well prepared by excellent schoolteachers. Careers advisers encouraged me to study maths, not to forget that ambition and aim to be a boxer (as Nira was advised) or a singer (as Nira's son, alarmingly recently, was told).

I understood some of that privilege at the time. But of course, I was also white and male. It is only now, when I look at the achievement of people like Nira, and many of our students at Greenwich who have overcome enormous obstacles, that I am beginning to understand just how that contributed to my privilege. My mathematics cohort as an undergraduate was almost all white (possibly even entirely white: I don't remember any exceptions) and largely male. When I look at my classes (and colleagues) at Greenwich, I feel very glad to have the opportunity to work with such diverse people.

Chalkdust's reflections on Black Mathematician Month deserve wide circulation. This feels like an important initiative, which hopefully will help all potential mathematicians, whatever their race or gender, have the opportunity to follow their dreams, inspired by people like Nira and the other mathematicians featured.

*iSquared*, which is happily preserved online*.*)And the best thing that Chalkdust has done is the Black Mathematician Month which has just finished - a month of interviews, conversations and activities "promoting black mathematicians, and talking about building a more representative mathematical community". The stories that were told were sometimes shocking, sometimes horrifying, often inspiring, and very important. I was lucky enough to be one of the large audience for the final event, an excellent talk about the Black Heroes of Mathematics by Nira Chamberlain (and I was particularly pleased that several undergraduates from the University of Greenwich were also there). Nira told us about a number of great black mathematicians: despite his own negative experiences as a young black man wishing to become a mathematician, and the obstacles in his way, his presentation was overwhelmingly positive in tone and his passion communicated strongly with the audience.

I myself was a very privileged mathematics student. I had an adequate grant and did not need to work while I was studying. I had a supportive family. Both my parents went to university (probably quite unusual for the time although I didn't realise that), as did my father's sister (I believe the first woman from her school to do so) and all my siblings. I was supported not only by their academic expectations but by their understanding of university education. I was well prepared by excellent schoolteachers. Careers advisers encouraged me to study maths, not to forget that ambition and aim to be a boxer (as Nira was advised) or a singer (as Nira's son, alarmingly recently, was told).

I understood some of that privilege at the time. But of course, I was also white and male. It is only now, when I look at the achievement of people like Nira, and many of our students at Greenwich who have overcome enormous obstacles, that I am beginning to understand just how that contributed to my privilege. My mathematics cohort as an undergraduate was almost all white (possibly even entirely white: I don't remember any exceptions) and largely male. When I look at my classes (and colleagues) at Greenwich, I feel very glad to have the opportunity to work with such diverse people.

Chalkdust's reflections on Black Mathematician Month deserve wide circulation. This feels like an important initiative, which hopefully will help all potential mathematicians, whatever their race or gender, have the opportunity to follow their dreams, inspired by people like Nira and the other mathematicians featured.

## Saturday, 14 October 2017

### Monty Hall

Two weeks ago, on Saturday 30 September, two big names in mathematics died. Vladimir Voevodsky, who was only 51, made huge contributions to mathematics. I became aware of his importance to contemporary mathematics when reading Michael Harris's wonderfully stimulating book

The other, Monty Hall, was not a mathematician but a game show host, who has given his name to one of the most famous recreational mathematical puzzles. A lot has been written about the Monty Hall Problem: I recommend Jason Rosenhouse's book (called, surprisingly enough,

In Monty Hall's game show, a contestant had to choose one of three boxes. One contained a car: the other two each contained a goat. After the contestant had made their choice, Monty (who knew which box contained the car) would sometimes open the door of an unchosen box to reveal a goat, and then offer the contestant the chance to change their choice. Should the contestant switch?

I remember, as a schoolboy, discussing with my friends a problem in one of Martin Gardner's books. Three prisoners, A, B and C, are told that on the next day two of the three will be executed: which two has already been decided randomly. (As I get older I increasingly find the rather bloodthirsty settings of puzzles like this in very poor taste: why do so many mathematical puzzles involve the abuse and execution of prisoners?) A knows that his chance of survival is 1/3. The guard won't answer any question which would give him information about whether or not he has been chosen for execution. But A points out to the guard that at least one of the other two is going to die, so if the guard identifies to A one of the others who will die, then that cannot give any information about A's fate: whichever two have been selected, the guard can answer this question without revealing whether A has also been chosen.

So the guard tells A that C is going to die. A is now happy: his survival chance was 1/3 but has now gone up to 1/2 since it is either him or B who will survive.

Of course (on certain assumptions) A is wrong: it is B whose survival chance has gone up to 2/3. A's chance is unchanged at 1/3. If A and B were selected to die, the guard would tell A that B was ill-fated. If it was A and C to die, then the guard would answer "B". Bit if B and C are both going to die, then the guard could answer either "B" or "C", and if one assumes the guard chooses randomly which to name, then enumerating the cases shows that when the guard answers "C", two times out of three it was A rather than B who is also selected for death.

This led me to get the Monty Hall Problem wrong when I first read about it in a newspaper article (the

In fact, the problems are very closely related. What Monty Hall is doing is essentially saying to A, "C is going to die - would you like to change places with B?" And since B has a 2/3 chance of survival, A should certainly accept that offer. (On certain assumptions.)

But the assumptions are critical (and most recent presentations of the Monty Hall Problem do make this clear.) The 2/3 probability of winning if the contestant switches assumes that the host will always carry out the procedure, and that, when the contestant has initially chosen the box with the car, that the host will choose one of the other boxes to open with equal probability. (If the host simply always opens the nearer box with the goat, then on the occasions when the host opens the further away box, the contestant will know that a switch guarantees success.) And the host might not go through this procedure every time. If the host wants to save his employers money, then he might only offer the switch option on those occasions when the contestant has initially chosen the winning box. If the host likes the contestant, he might only offer the switch option when the initial choice is losing.

In fact (according to, for example, the Wikipedia entry for Month Hall, in the real game show Monty did not always offer the choice. He was playing a psychological game with the viewer, and, when "The Monty Hall Problem" became famous, he was well aware that the conditions necessary for the mathematical puzzle did not in fact apply to his game show. I find it very pleasing that the game show host had a better understanding of the mathematics problem than many of the mathematicians whose instinctive answer, like mine, was wrong.

*Mathematics without Apologies*and regret that I do not know much about him and his work.The other, Monty Hall, was not a mathematician but a game show host, who has given his name to one of the most famous recreational mathematical puzzles. A lot has been written about the Monty Hall Problem: I recommend Jason Rosenhouse's book (called, surprisingly enough,

*The Monty Hall Problem*, which gives an excellent account of the embarrassing (for male mathematicians)*l'affaire Parade*which brought the puzzle to public notice - see http://marilynvossavant.com/game-show-problem/ for the correspondence.In Monty Hall's game show, a contestant had to choose one of three boxes. One contained a car: the other two each contained a goat. After the contestant had made their choice, Monty (who knew which box contained the car) would sometimes open the door of an unchosen box to reveal a goat, and then offer the contestant the chance to change their choice. Should the contestant switch?

I remember, as a schoolboy, discussing with my friends a problem in one of Martin Gardner's books. Three prisoners, A, B and C, are told that on the next day two of the three will be executed: which two has already been decided randomly. (As I get older I increasingly find the rather bloodthirsty settings of puzzles like this in very poor taste: why do so many mathematical puzzles involve the abuse and execution of prisoners?) A knows that his chance of survival is 1/3. The guard won't answer any question which would give him information about whether or not he has been chosen for execution. But A points out to the guard that at least one of the other two is going to die, so if the guard identifies to A one of the others who will die, then that cannot give any information about A's fate: whichever two have been selected, the guard can answer this question without revealing whether A has also been chosen.

So the guard tells A that C is going to die. A is now happy: his survival chance was 1/3 but has now gone up to 1/2 since it is either him or B who will survive.

Of course (on certain assumptions) A is wrong: it is B whose survival chance has gone up to 2/3. A's chance is unchanged at 1/3. If A and B were selected to die, the guard would tell A that B was ill-fated. If it was A and C to die, then the guard would answer "B". Bit if B and C are both going to die, then the guard could answer either "B" or "C", and if one assumes the guard chooses randomly which to name, then enumerating the cases shows that when the guard answers "C", two times out of three it was A rather than B who is also selected for death.

This led me to get the Monty Hall Problem wrong when I first read about it in a newspaper article (the

*Independent*, perhaps around Christmas 1990?) Knowing that in the Gardner problem A's chances haven't changed, I assumed that the quiz show contestant can't improve their chance of winning by switching. This is plain wrong, but I wonder if memories of Gardner's puzzle led astray many of the mathematicians who on first seeing it got the Monty Hall Problem wrong? Although my initial answer was wrong, on careful reading of the analysis I did quickly come to agree that the contestant should switch, and verified this by computer simulation.In fact, the problems are very closely related. What Monty Hall is doing is essentially saying to A, "C is going to die - would you like to change places with B?" And since B has a 2/3 chance of survival, A should certainly accept that offer. (On certain assumptions.)

But the assumptions are critical (and most recent presentations of the Monty Hall Problem do make this clear.) The 2/3 probability of winning if the contestant switches assumes that the host will always carry out the procedure, and that, when the contestant has initially chosen the box with the car, that the host will choose one of the other boxes to open with equal probability. (If the host simply always opens the nearer box with the goat, then on the occasions when the host opens the further away box, the contestant will know that a switch guarantees success.) And the host might not go through this procedure every time. If the host wants to save his employers money, then he might only offer the switch option on those occasions when the contestant has initially chosen the winning box. If the host likes the contestant, he might only offer the switch option when the initial choice is losing.

In fact (according to, for example, the Wikipedia entry for Month Hall, in the real game show Monty did not always offer the choice. He was playing a psychological game with the viewer, and, when "The Monty Hall Problem" became famous, he was well aware that the conditions necessary for the mathematical puzzle did not in fact apply to his game show. I find it very pleasing that the game show host had a better understanding of the mathematics problem than many of the mathematicians whose instinctive answer, like mine, was wrong.

Subscribe to:
Posts (Atom)