TRM intern and University of Oxford student Kai Laddiman speaks to St John’s College Computer Scientist Stefan Kiefer about the infamous million-dollar millennium problem: P versus NP.
You can read more about P vs NP here.
Perfect Numbers and Mersenne Primes
Perfect numbers and Mersenne primes might seem like unrelated branches of math, but work by Euclid and Euler over 2000 years apart showed they are so deeply connected that a one-to-one correspondence exists between the two sets of numbers.
Produced by Tom Rocks Maths intern Kai Laddiman, with assistance from Tom Crawford. Thanks to St John’s College, Oxford for funding the placement.
Countdown Youngest Winner: Kai Laddiman
Kai Laddiman was the youngest ever ‘Octochamp’ on the gameshow Countdown when he was 11 years old, and also happens to be one of my students at the University of Oxford. I spoke to him about his experience 10 years on and put him through his paces with some of the number rounds…
What are the chances that two England teammates share a Birthday?
Cast your mind back to the summer of 2018… we saw the warmest ever weather in the UK, Brexit was not yet a complete and utter disaster, and seemingly against all the odds the England football team reached the semi-finals of the World Cup for the first time since 1990. No doubt the team had a huge celebration together afterwards – but it wouldn’t be the first time that two of them have celebrated an occasion at the same time. As well as playing together at the heart of England’s defence, Manchester City duo Kyle Walker and John Stones also share the same birthday! Stones was born on 28th May 1994, making him 24 years old; Walker was born on the same day in 1990, meaning that he is exactly four years older than his teammate. How strange! Or is it…?
On the face of it, it seems quite surprising that in an England squad of just 23 players, two of them happen to share a birthday. However, as we’re about to see, this isn’t a freakish coincidence – maths says that it’s quite likely! What we’re talking about here is commonly known as the birthday problem: if there are a group of people of a certain size, what is the likelihood that at least two of them have the same birthday?
Let’s start by saying that we have a group of N people, and assume that birthdays are equally likely on every day of the year. (There is some evidence to suggest that this isn’t the case for top athletes; some say that they tend to be born early in the school year, such as around September in England. This is because they are slightly older than the other children in the year, and so they have a slight head-start in their physical development. However, we don’t want to make things too complicated, so we’ll ignore that for now.)
The easiest way to think about the problem is to first try to work out what the probability is that none of the N people share a birthday. Suppose our N people walk into a room, that is empty at first, one at a time. When the first person walks in, it’s obvious that they don’t share a birthday with anyone else in the room, because there isn’t anyone else. Therefore, they have the maximum probability of not sharing a birthday with anyone else in the room, which is 1.
Now think of the second person who walks in. The only way that they could share a birthday with someone in the room is if it happens to be exactly the same day as the first person. That means there is a 1 in 365 chance that they do share a birthday, so there is a 364 in 365 chance that they don’t.
Suppose that the first two birthdays don’t match, and then the third person walks in. They now have 2 days that they can’t share a birthday with, so there are 363 possible choices out of 365. Because we assumed that the first two didn’t match, we multiply the probabilities, so now the chance that none of them share a birthday is (364/365) * (363/365).
We can repeat this process until we get to our final person, number N. For example, the fourth person has 3 birthdays that they cannot share, so we multiply by a chance of 362/365; the fifth person has 4 days to avoid, so we include a probability of 361/365… By the time the Nth person walks in, there are N-1 people already in the room, so there are N-1 days that their birthday cannot fall on. This leaves them with 365-(N-1) possibilities out of 365.
To work out the total probability, we multiply all of these terms together which gives the likelihood that none of the N people share a birthday as
1 * (364/365) * (363/365) * (362/365) * … * ((365-(N-1))/365).
You might be thinking that this still looks like quite a big probability that none of them share a birthday, because all of the terms are very close to 1. But, if we try some values of N in a calculator, then it tells a very different story. (The percentages are calculated by finding the probability from the equation above and multiplying by 100.)
When N = 10, we get an 88% chance that none of them share a birthday. However, this drops down to 59% when there are N = 20 people. When we get to N = 23, the number of players in the England squad, the probability reaches just under 50%. That means that, incredibly, the likelihood that at least two of the 23 people share a birthday is just bigger than 50%!
So, in a random group of 23 people, it’s more likely than not that two of them share a birthday! This seems very strange at first; surely you’d need more than 23 people for a shared birthday to be more likely than not?! This is why the problem is commonly known as the birthday paradox – it might be very hard to get your head around, but the maths doesn’t lie!
Perhaps, in order to convince ourselves, we should look at some real-life examples. This is where the World Cup squads come into play: each team is restricted to bringing 23 players to the tournament. (We’ve seen that number before…) If our calculations above are correct, then if we picked any one of the World Cup squads, there would be roughly a 50:50 chance that at least two of the squad members share a birthday, which means that out of all of the squads that went to Russia, we would expect about half of them to have a birthday match. Well, let’s take a look…
Of the 32 teams, which were divided into 8 groups of 4, the following teams have at least one pair of players who share a birthday:
| Group A | Russia |
| Group B | Iran, Morocco, Portugal, Spain |
| Group C | Australia, France, Peru |
| Group D | Croatia, Nigeria |
| Group E | Brazil, Costa Rica |
| Group F | Germany, South Korea |
| Group G | England |
| Group H | Poland |
So, not only is there at least one team in every group with a birthday match, but if we count the total, there are 16 squads with a shared birthday pair – exactly half of the teams! The experimental results have matched up with the mathematical theory to perfection. Hopefully that’s enough to convince you that our calculations were indeed sound!
A slightly different question that you might ask is as follows: if I am in a group with a certain number of people, what are the chances that at least one of them shares my birthday? Is it the same idea? What we have worked out above is the probability that any two people in the room share a birthday (or rather, we worked out the opposite, but we can find the right answer from our working). Note that the pair doesn’t necessarily include you; it’s a lot more likely that it’s some other pair in the group.
In order to work out the answer to this similar sounding question, we work the other way around again, by calculating the probability that none of the N people share my birthday. For each of the N people, there is only one birthday that they cannot have, and that is mine (14th November, in case you were wondering), which means there are 364 out of 365 possibilities for each person. We no longer care whether their birthdays match up; we only care if they match with mine. So each person has a 364/365 chance of not sharing my birthday; and the overall probability is just 364/365 * 364/365 * … * 364/365, N times, which we write as (364/365)N.
Once again, we can plug some values of N into a calculator: N = 10 gives a 97% chance that no-one else has my birthday. For N = 50 the probability is still very high: there is an 87% chance that none of these 50 people have the same birthday as me. N = 100 gives 76%; N = 200 gives 58%; you have to go all the way to N = 253 before the probability dips below 50%, and it becomes more likely than not that at least one person will celebrate their birthday with me.
Applying this idea to all 736 players (32 squads of 23 players) involved in the World Cup, we should expect around 3 of them to have been born on the same day as me – 14th November. And I am very happy to confirm that France’s Samuel Umtiti, Switzerland’s Roman Burki, and Belgium’s Thomas Vermaelen all have what is undoubtedly the best birthday of the year… Two similar problems with two very different solutions!
You can check which footballers share a birthday with you at www.famousbirthdays.com/date/monthDD-soccerplayer.html, where you enter the month in words and the day in numbers (no preceding zero required).
Kai Laddiman
Complex Numbers – they don’t have to be complex!
The idea of complex numbers stems from a question that bugged mathematicians for thousands of years: what is the square root of -1? That is, which number do you multiply by itself to get -1?
Such a simple question has blossomed into a vast mathematical theory, for the simple reason that the answer isn’t real! It can’t be 1, as 1 * 1 = 1; it can’t be -1, as -1 * -1 = 1; whichever number you multiply by itself, you can’t get a negative number. Up until the 16th century, almost everyone ignored this issue; perhaps they were afraid of the implications it could bring. But then, gradually, people began to realise that there was a whole new world of mathematics waiting to be discovered if they faced up to the question.
In order to explain this apparent gap in maths, the idea of an ‘imaginary’ number was introduced. The prolific Swiss mathematician Leonhard Euler first used the letter i to represent the square root of -1, and as with most of his ideas, it stuck. Now i isn’t something that you’ll see in everyday life in relation to physical quantities, such as money. If you’re lucky enough to have money in your bank account, then you’ll see a positive number on your bank statement. If, as is the case for most students, you currently owe money to the bank (for example, if you have an overdraft), then your statement will display a negative number. However, because i is an ‘imaginary’ unit, it is neither ‘positive’ nor ‘negative’ in this sense, and so it won’t crop up in these situations.
Helpfully, you can add, subtract, multiply and divide using i in the same way as with any other numbers. By doing so, we expand the idea of imaginary numbers to the idea of complex numbers.
Take two real numbers a and b – these are the type that we’re used to dealing with.
They could be positive, negative, whole numbers, fractions, whatever.
A complex number is then formed by taking the number a + b * i. Let’s call this number z.
We say that a is the real part of z, and b is the imaginary part of z.
Any number that you can make in this way is a complex number.
For example, let a = -3 and b = 2; then -3 + 2*i, which we write as -3 + 2i, is a complex number.
As we saw before, complex numbers don’t actually pop up in ‘real-life’ situations. So why do we care about them? The reason is that complex numbers have some very neat properties that allow them to be used in all sorts of mathematical contexts. So even though you may not see the number i in everyday life, it’s very likely that there are complex numbers involved behind the scenes wherever you look. Let’s have a quick glance at some of these properties.
The key observation is that the square of i is -1, that is, i * i = -1.
We can use this fact to multiply complex numbers together.
Let’s look at a concrete example: multiply 2 + 2i by 4 – 3i.
We use the grid method for multiplying out brackets:
| 4 | -3i | |
| 2 | 2 * 4 = 8 | 2 * -3i = -6i |
| +2i | 4 * 2i = 8i | 2i * -3i = -6 * i * i = -6 * -1 = 6 |
Adding the results together, we get (2 + 2i)(4 – 3i) = 8 + 6 – 6i + 8i = 14 + 2i.
Therefore, multiplying two complex numbers has given us another complex number!
This is true in general, and it turns out to be very handy. In fact, Carl Friedrich Gauss proved a very famous result – known as the Fundamental Theorem of Algebra because it’s so important – that effectively tells us that the solutions to all equations can be written as complex numbers. This is extremely useful because we know that we don’t have to go any ‘deeper’ into numbers; once you’ve got your head around complex numbers, you can proudly declare that you’ve mastered them all!
Because of this fundamental theorem, our little friend i pops up all over the place in physics, engineering, computer science, and of course, in all sorts of areas of maths. While it may only be imaginary, its applications can be very real, from air traffic control, to animating characters in films. It plays a really important role in much of theoretical mathematics, which in turn is used in almost every scientific discipline. And to think, all of this stemmed from an innocent-looking question about -1; what were they so scared of?!
Kai Laddiman
Spring into action and get ahead of the competition
Wherever we look in the world, we see competition between different groups or beings. Whether it’s two animals trying to earn the right to a watering hole, people trying to assert their social influence, or simply two sports teams playing against each other, this sort of interaction appears in many different situations. As humans, we have a natural desire to rank things that are in direct competition: which is better? Who would win if they faced each other? How does their rivalry compare to others?
We want to know the answers to these questions because it makes us enjoy the competition more, and we feel that we learn more about it. Imagine being able to correctly predict who would win every football match for the rest of the season, you’d probably feel pretty pleased with yourself… But, apart from the inevitable bragging rights, being able to rank competing entities and predict outcomes is an extremely useful skill in many different areas of research, including sociology, economics and ecology.
Of course, you need a bit of maths if you’re going to rank things reliably; you can’t just trust a hunch! There are many different methods that have been used before for rankings, but a group of scientists at the Santa Fe Institute in the USA have come up with a new way of doing it using springs!
So, the ranking system is… a trampoline?! Not exactly. This ingenious method, called SpringRank, treats each interaction as a physical spring, so the model is a whole system of connected springs. Think of a football league: between each pair of teams there is a spring in each direction, and the force of each spring is determined by how many times they have beaten each other in the past. For example, Manchester United have played Liverpool 200 times, winning 80 matches and losing 65. In our spring system, this means that the spring connecting the two teams is biased towards Manchester United – it requires more force to move closer to Liverpool than it does to move towards Manchester United. With this setup, it turns out that the best ranking of the teams is found when you make the total energy in all of the springs as low as possible.
But why use springs? The bonus is that we’ve been studying springs for hundreds of years and so we know the physics behind how they work, which makes it easy to do the calculations. We can use the positions of the springs to work out the rankings of millions of different teams in just seconds! Not only is the maths simple, but it’s also very effective, especially compared to other methods currently used for ranking. In tests run by the researchers, SpringRank performed much better at ranking competitors, as well as predicting the outcomes of future clashes, than existing methods. The data set covered topics as varied as animal behaviour, faculty hiring and social support networks, demonstrating just how versatile the method can be.
This research is a wonderful example of how different areas of science can be combined to create a tool that can actually be put to use in the real world. When learning the subjects separately at school, it’s hard to imagine that you could take centuries-old ideas from physics, turn them into mathematical models, and stick them into a computer program! But here we are, able to work out who is likely to become friends (and enemies), which animals will make it through the heatwave, and whether it’s worth bragging about your favourite team before the game has even happened. So next time you’re challenged to guess the league winner, reach for SpringRank and jump ahead of the competition!
Kai Laddiman
This robot is a ‘Cheetah’
Robots are developing at an incredible rate, with their ability to perform real-world tasks improving almost by the minute. Such rapid development doesn’t come without downsides, and there are many people who believe that artificial intelligence (AI) could become too powerful, leading to the possibility of robots taking our jobs, or perhaps even taking over the world! Whilst these fears might not be completely unjustified, let’s instead focus on the positives for the time being and marvel at the astonishing accomplishments being made in the field of robotics.
The Cheetah robot, developed by scientists at MIT, is roughly the same shape and size as a small dog, and has been designed to be able to walk across difficult terrains efficiently and effectively. Such a trait is particularly useful when we need to explore dangerous and hazardous environments that may be unsuitable for humans, such as the Fukushima nuclear power plant that collapsed in Japan in 2011. Like all robots, it uses algorithms to help it to navigate, stabilise itself, and ensure that its movements are natural. The latest version, the Cheetah 3, was unveiled in early July, and I think it’s fair to say that it wouldn’t look too far out of place in the animal kingdom!
[Image courtesy of Sangbae Kim, MIT]
Perhaps the most impressive feature of the Cheetah 3 is that the strangely adorable hunk of metal performs the majority of its navigation without any visual input, meaning that it is effectively blind. The researchers at MIT believe that this is a more robust way to design the robot, since visual data can be noisy and unreliable, whereas an input such as touch is always available. Let’s imagine that you are in a pitch-black room; how would you find your way around? Your eyes are pretty much useless, but you can use your sense of touch to feel around the environment, making sure that you don’t bump into walls or obstacles. It’s also important to step carefully, so that you don’t misjudge where the floor is, or tread too strongly and break through something. The Cheetah 3 takes all of this into account as it gracefully glides across even the roughest terrain.
One of the key ideas that was addressed in the new model is contact detection. This means that the robot is able to work out when to commit to putting pressure on a step, or whether it should swing its leg instead, based on the surface that it is stepping onto. This has a massive impact on its ability to balance when it is walking on rough terrain, or one that is full of different obstacles; it also makes each step quicker and more natural. Going back to our dark room, you are likely to step quite tentatively if you can’t see where you are going as this will allow you to react to whatever surface you come into contact with, and adjust your motion as required. With the latest update, the clever ‘canine’ can make these adjustments by itself in a natural manner.
The Cheetah 3 also contains a new and improved prediction model. This can calculate how much pressure will need to be applied to each leg when it experiences a force, by estimating what will happen in half a second’s time. Returning once again to our pitch-black room, imagine how great it would be if you were able to predict what you’re about to step on and adjust your path accordingly – no more treading on sharp objects or stubbing your toe! The scientists tested the power of the new model by kicking the robot when it was walking on a treadmill. Using its prediction algorithm, the Cheetah 3 was able to quickly calculate the forces it needed to exert in order to correctly balance itself again and keep moving. Whilst I can confirm that no animals were harmed in the making of this robot, whether or not the robot itself felt harm is perhaps a question for another day…
The new and improved Cheetah 3 is certainly one of the more remarkable recent accomplishments in the field of robotics. Its natural movements and quick corrections mean that it excellently mimics animal navigation, and it is easy to see how such a robot would be extremely useful for exploring dangerous terrains. Such incredible progress in the study of robotics is as impressive and exciting as it is scary. While it is extraordinary that we are able to replicate animal movements so closely, it has rightly made many people slightly worried; will robots eventually be able to completely replace us? We can only cross our fingers that these critters have no plans for world domination just yet…
Kai Laddiman
