It’s the start of round 2 of the Math-Off, and we’ve already seen some excellent maths. 16 competitors are now 8, and they’re fighting for a place in the semi-final.
The first round 2 match is between Nira Chamberlain and Alison Kiddle.
The rules are still the same: take a look at both pitches, vote for the bit of maths that made you do the loudest “Aha!”, and if you know any more cool facts about either of the topics presented here, please write a comment below!
Nira Chamberlain – Black heroes of mathematics
Dr Nira Chamberlain is an applied mathematician and maths outreach expert, and Vice President, Professional Affairs and Industry at the IMA. You can find him on Twitter at @ch_nira, or at nirachamberlain.com. In round 1 he saw off James Tanton with an application of the Reynolds equation to Formula 1 cars.
Nira has made a video about some of the Black heroes of mathematics.
Alison Kiddle – Ebert’s hat problem
Alison Kiddle works at NRICH, where she makes material to get kids thinking about cool bits of maths. You can find her on Twitter at @ajk_44. In round 1 she pipped Peter Rowlett with Haga’s theorem.
Hat problems are famous in recreational maths. Here is a variant of a well-known hat puzzle:
Alison, Evelyn, Jo and Zoe have been captured by the evil Wizard Lawson-Perfect, and forced to stand one behind another in a line. There is a very tall wall between Alison and the other three, so Alison can’t see them, and they can’t see her. Each mathematician can only see the hats that are closer to the wall than they are. They all know that they are wearing one of four hats; two black and two white. If any of the four intrepid maths communicators can call out the colour of their own hat, they will be free!
Zoe holds the key to solving this problem. As she can see Evelyn and Jo, she knows whether they have two hats the same or one of each colour. If she sees they are both the same, she automatically knows her hat is the other colour, shouts it out, and wins the posse their freedom. Jo, being a rational and logical thinker, knows that if Zoe can see two hats of the same colour, she will shout out. After a short while, if Jo doesn’t hear Zoe speak, she knows Zoe cannot deduce the colour of her hat. This means that Jo can deduce that her own hat is the other colour to Evelyn’s hat, calls out this colour, and frees the posse.
Throughout the process, Alison is stuck behind a wall and is no use to anyone.
Perhaps less well known is Ebert’s Hat Problem, brought to wider attention by Todd Ebert’s PhD thesis in 1998. Let’s start by considering three people participating in a game show. The host chooses at random whether to place a blue or red hat on each participant. Each participant can see the other two hats but no-one can see their own hat. Each contestant has three buttons in front of them; RED, BLUE or PASS. After a short time, they must push their buttons simultaneously to either guess the colour of their own hat, or pass. If all three pass, or anyone guesses wrongly, the team loses. If at least one person guesses correctly, and no-one guesses incorrectly, the team wins a suitably attractive prize. The key to this problem is that the team can decide on a strategy beforehand to maximise their chance of winning. But how can the team maximise the probability that they win? You may wish to think about the strategy you would use, before reading on.
A naive strategy where the team win the prize in 50% of scenarios might look like this: Person A always guesses red. Persons B and C always pass. As A is wearing a red hat 50% of the time, and B and C pass, the team wins 50% of the time. However, you might be surprised to discover that there’s a better strategy that rewards the team in 75% of scenarios. Let’s consider all the possible distributions of hat:
|Person A||Person B||Person C|
In all eight of these scenarios, at least one person can see two people wearing hats of the same colour. The key is that in six of these eight scenarios, the person who can see two hats the same is wearing the opposite colour of hat! It’s only in the situations RRR and BBB that you can see a pair of hats and your hat is the same colour. So the team decide on the following strategy: anyone who sees two hats the same colour presses the button for the opposite colour of hat. Anyone who sees two different colours of hat presses the “PASS” button.
Here’s how that might play out in practice:
Zoe and Jo are both wearing red hats, and Evelyn has a blue hat. As Zoe and Jo can’t see two hats of the same colour, they follow the strategy and pass. Evelyn sees two reds, so she guesses blue. As at least one person got their hat colour correct, and no-one got it incorrect, the team wins! (Before Zoe, Evelyn and Jo come to ask for their prize, I feel I should make them aware that my prize budget is even smaller than my graphics budget…)
Here’s a summary of the possibilities in a table:
|Zoe’s Hat colour||Evelyn’s Hat colour||Jo’s Hat colour||Zoe/Evelyn/Jo votes||Outcome|
|R||R||R||B, B, B||LOSS|
|R||R||B||Pass, Pass, B||WIN|
|R||B||R||Pass, R, Pass||WIN|
|R||B||B||R, Pass, Pass||WIN|
|B||R||R||B, Pass, Pass||WIN|
|B||R||B||Pass, R, Pass||WIN|
|B||B||R||Pass, Pass, R||WIN|
|B||B||B||R, R, R||LOSS|
So for six out of the eight possible distributions of hat, our team wins, giving a 75% success rate!
But what’s the point of hat problems like this, beyond providing entertainment for recreational mathematicians? It turns out that the strategy for hat problems of this type is linked to an important topic from computer science, that of error detection and correction. Hamming Codes are named after Richard Hamming, who invented them in 1950 to correct errors in punch-card computers. The Hamming (7,4) Code takes four ‘bits’ of information (ones and zeroes), and introduces three extra bits to act as a check. You might like to watch the video below to find out how to use the Hamming Code to encode a message, and detect and correct errors. Alternatively, you can read about it on Wikipedia.
At first glance, the link between the Hamming Code and the Hat Problem might not be obvious. However, both are based on the idea of the Hamming Distance; the difference between two different messages. Hamming Codes can detect and correct errors as long as no more than one bit has been flipped; that is, as long as the Hamming Distance between the actual message and the received message is at most 1. By defining a Hamming Space for the hat problem, and finding a minimal covering, it can be shown that our strategy above is the optimal strategy. This can then be extended to more complex hat problems with more colours and more participants. If you would like to read about it, this paper by Guo, Kasala, Rao and Tucker explains in more detail.
Thanks to Beth Romano, DPMMS, University of Cambridge, for introducing me to Ebert’s Hat Problem.
So, which bit of maths has tickled your fancy the most? Vote now!
Round 2 match 1 - Chamberlain v Kiddle
- Nira Chamberlain with black heroes of mathematics (53%, 193 Votes)
- Alison Kiddle with Ebert's hat problem (47%, 173 Votes)
Total Voters: 366
The poll closes at 9am BST on the 13th. Whoever wins the most votes will get the chance to tell us about more fun maths in the semi-final.
Come back tomorrow for our second match in round 2, pitting Paul Taylor against Edmund Harriss, or check out the announcement post for your follow-along wall chart!