George. So I think we have a packed room, completely packed. I'm glad we don't have to use the other little room because it's never quite as nice. So welcome to all of you, to the Matamata Institute to see so, so good Christmas lecture, ending a very successful year of public lecture. And there is no better way to end the year than having Professor Marcus de Soto with us today. Is the, as many of you know, the University of Sydney chair of Public Understanding.
And it's going to be a real Christmas treat for all of us. Thank you, Phillip. Do we need any more people sitting? Is there anybody we need? So I think we could actually forget. Okay, so before we start, actually, we have a word from our sponsor. For the first time, we have a sponsor for a public lecture. We started very small, but as we are expanding, we were very grateful to have a sponsor.
So I'm always wanted to have a radio show so I can say another word from a sponsor or sponsor today is G Research. If you're wondering who G research is, I'll tell you G research is a fast growing, well-established financial research company located in central London. The quantitative researchers develop ideas to predict return in global markets by finding patterns in large, noisy and rapidly changing data set.
They have opportunities for candidates to apply mathematical concept to real world problems in a relaxed yet dynamic environment. So I'm particularly grateful because with the support, we are going to be able to expand further our program of public lecture and really bring the best mathematicians from all around the world to give a public lecture here. So we have an exciting programme coming. We have talks on the mathematics of crime.
Later next term we'll have talks on mathematics of choice would have another lecture, I hope, with the coming book of Marcus later on this year and many more coming next year. So we have an exciting programme of course tonight it's a special night, just not because we have Marcus with us tonight, but for many of you know, it's also the opening night of Star Wars and that makes it, of course, very special.
And I think there's probably a few of you who came here just to be in a warm environment rather than camping outside the movie theatre with. And that's perfectly all right. In the spirit of intergalactic peace, I think we can accommodate you and do a little bit of mathematics in the meantime, but it really made me think and I said, okay, so that's good. Star Wars where would Marcus fit in a Star Wars universe?
So first we have, of course, to decide who is the dark side and who is the non dark side, whatever they call it. To the bright side of the light side where I don't know for you, but for me it's quite clear. That's an easy one. You know, if you look at the dark side, guys, they have they have all the the cool gadgets and of course, they have a great sense of fashion. So for me, clearly the dark side is the applied mathematicians.
Oh, come on. I knew you could imagine a mathematician in a little hurt with the little rope solving equation. But you wouldn't. You wouldn't have them build the Death Star. Probably. Right? Right. Okay, so that's the easy one. No, we have to decide. In that universe, we have the dark side and we call it the pure sides. Make it easy. So what? Who would Marcus be? Of course, Marcus is definitely on the pure side is he's a pure mathematician of great renown.
He's made important contribution in group theory, in the theory of prime number is still very active in this field. He received in 2001. The Berkeley Prize from the London Mathematical Society clearly is very strong. So which one would he be? Where could he be? Obi-Wan Kenobi. Yoda? Well, I think he's way too alive to be Obi-Wan and and to articulate for Yoda to be. I think it would be it would make a great Jar Jar Binks personally because of his ability to entertain people.
But if you think about it, the force is strong in this one. And in recent years I've heard Marcus talk about algorithm, I've heard about all useful mathematics and how it applies to everyday life. I even saw him talk about units kilogram metre, something that pure mathematician would never touch. So I think he's definitely getting corrupted by the dark side. So that leaves only one main character for me.
Marcus is the Luke Skywalker of mathematics, and maybe he's going to be the one to unite both sides. Who knows? So but before I ask you to join me, I have to take my laser sabre and tell you about the emergency exit over here and there and there. We're not going to fight tonight, I hope. But so if you in case of emergency, you can take any of this exit and you'll end up in open space where nobody will hear you scream. Of course. So a final word for Marcus.
Please come, Marcus. Come join me. Marcus. Thank you. Very, very. I actually really enjoy this time of year because there is so much maths hiding everywhere. But there's something really weird because I'm around my. Carol singers just will not come to my door anymore. I've wondered why this was in my mind. Children explain to me it's because that every time they come, you find some mathematical thing in the things that they're singing and they don't come anymore and it's go round it.
So I've got this captive audience now, and so you can sing me carols at the end if you want. But so what I wanted to do is to give you a little bit of the things that I bought my Carol singers with. I'm actually I live in East London and so I actually live in quite a Jewish neighbourhood as well. And we've just finished celebrating. All the Jewish families have had candles in their windows because they just finished celebrating Hanukkah.
Hanukkah is probably the first great sort of mathematical holiday of this time because the candles, if you know the story of Hanukkah is about the miracle of lights and they light candles because the oil should have only lasted for one day, actually ended up lasting for eight days. And so they celebrate Hanukkah by lighting candles over the eight days of Hanukkah. And you get these little boxes with the candles in.
And one of the challenges they set all the kids is can you work out how many candles are in the box? Because the rules are that on the first day you light one candle but with another candle, which is called the shamash. So you actually like two candles on the first day of Hanukkah and then the second day you like three candles, the one that's lighting, and then you like two more. So by the end you you light nine candles in total.
So so that's the challenge you set the kids is, well, how many candles are there in the box? And actually it's it's quite similar. It's amazing how, you know, actually all of these holidays are about the fact that it's really dark out there, the Festival of Lights as well. But Christmas also has a kind of version of this kind of challenge as well, because some of those carols saying is that come round to me, they're all singing on the first day of Christmas, my true love sent to me.
And so one of the challenges again is, well, how many presents on each day do you get? And it's a similar sort of problem that you're adding. You're adding up, well, one partridge in a pear tree, two turtle doves. And so you've got these kind of the same sort of challenge where you've got to add up the number of presents on each day. So I always challenge them. Okay, what if Christmas seems to start earlier and earlier every year? So, you know what if it actually was 100 days of Christmas?
So I always challenge the carols saying I think this is why they never come anymore. So, okay, so you know what, if they were like 100 iPods, 99 copies of Music of the Primes and all the way down to, you know, could you tell me how many presents that you're going to get on the hundredth day of Christmas? And of course, that's a nice way to to view this, because you already saw this kind of triangle building up.
So if you stack all of the presents up, so, for example, you've got one down here and then you've got two turtle. This is a partridge in there and two turtle doves, three French hens and four watts. Yeah, that's what you say. So these are actually examples of things called the triangular numbers. So the triangular numbers apply both to counting the number of candles in Hanukkah and also the number of presents you get on each day of Christmas.
And there's a nice way to actually quickly calculate how many presents there are in here, because what you do is you take two of these sort of sets of presence and you slot them together. So if you do that, you get a rectangle and it's very easy to count things in a rectangle. So if I had 100, the hundred Days of Christmas, I stacked all of those presents up and I took another copy of that.
I put them together. I now have a rectangle which is has 100 boxes down one side, but 101 down the other side. So that's two copies of what I'm trying to count. So if I do 100 times 101, I divide that by two, I'll find out how many there are in that triangular set of boxes. So that gives you a nice sort of formula actually to calculate the number of presents you'll get on each day of Christmas. But kind of she has a little trick to it, of course, because.
So you think. Oh, right. So it's the ninth triangular number is the number of candles that'll be in that box. But of course, a little trick you have to remember is that there's no first day. So you have to take one of that number because you start with two plus three plus four. So it isn't quite the ninth triangular number is the ninth triangular minus the first candle which never gets used. So so that's always a trick to see how clever the kids in a kind of carol.
So it's actually you've got 44 candles in that box, but of course, actually. So that's a kind of nice problem. It's sort of a two dimensional triangle you've got there. But actually I rather like Christmas because there's a little bit more of a challenge inside that problem. Because yeah, on each day of Christmas you've got a triangular number of presents. But what about over the whole of the 12 days of Christmas? How many presents do I get from my true love over the 12 days?
Because then actually you start the problem starts to become a little bit more interesting because it's not just two dimensional. So we've seen the triangular numbers give you the number of presents on each particular day. But what about over the whole of the 12 days of Christmas? Well, the interesting thing is that this is a three dimensional problem. So Hanukkah, the Jewish holiday, is a sort of two dimensional holiday.
Christmas goes one dimension up. We've got a three dimensional holiday for Christmas. So the point is, you know, you get a partridge in a pear tree on the first day, but on the second day, you also get another partridge in a pear tree and the two turtle doves. So already you've got this kind of little stack coming up. And then the Partridge in the Pantry, two title ups and the three French hens. So already you've got some kind of got three partridges down there so you can see what happens.
You actually are building up these triangles until you get some kind of like actually a sort of pyramid effect. So if it's 12 days of Christmas, actually, what you've got to do is to count things in this kind of pyramid. So this is a triangular based pyramid. So we call these the tetrahedral numbers. So how many? So you've got 12 layers of this. Is there some clever way to work out how many? You know, I could count them all up, but I'm rubbish at mental arithmetic and I made some mistake.
And so is there some clever way to find out how many there are? Because I remember what we did. We took with a triangle, so we took two triangles and put them together and we can make a rectangle and then that's easy to count. Well, the wonderful thing is you can do the same thing with these tetrahedron, so this time you need six tetrahedron. So this is what we're trying to add up. Those are the all the triangular numbers.
But you can put six of these kind of pyramids together into a box, which then has 12 one on one side, 13 along the other on 14 up the top. So actually, this gives you another clever way, a three dimensional way to see how many boxes you will need in total. So we take 12 times, 13 times 14 divided by six. The rather remarkable thing is you've got a present for every day of the year except for Christmas. So 364 presents inside there.
So, so actually. So we've got you know, it's quite a nice little trick for that. So a three dimensional holiday. That's great. And here's how far I have to go in promoting science across the universe. So The Daily Telegraph got me to explain this problem, and the editor brought along a Santa outfit, which I had to dress up in the snow. So there's me trying to calculate how many presents there are. But I thought, you know, let's get really geeky and let's have our own sort of a holiday.
So I thought, you know, so you've got a two dimensional Jewish holiday, three dimensional. Why don't we have a sort of four dimensional holiday? So I sort of started to think about a4d festive celebration of science. So if you think about it, actually, the triangles is a kind of single summation. You're adding up a sum of things, but the trunk as a pyramid numbers, it's a sum of sums because we're adding up the triangles which are themselves sums.
So actually to make a four dimensional holiday, what we've got to do, I mean, we can do a sort of song for this. So I was trying to think on so I've called it's science maths. So on the first day of science and I asked my geek friend sent to me what I thought Bose on in the LHC seemed quite good. So that's fine. But now we're going to go to the second day of science, maths, and I have to do a cut of some of his, some of his, some to get this to be a4d holiday.
So so on the second day of science nice my friend sent to me. So I've gone for two twin primes and it goes on in the LHC. But in order to make it for D, I have to add that on again. So we had another repeat of a Bose on in the LHC and this way we do this, we'll build up a thing where the number of scientific things will get well, will be you have to be a foot. We'll have four dimensional boxes that we'll be putting together. So there's a challenge for you I want to work out.
So I decided how many days should Science Match have? Well, it should be a prime number because I'm obsessed with primes, so I've said it's going to have 13 days. So I actually sent out a sort of request across Twitter for people to come up with things for all of the 13 days of science, maths, so, so hey, so we had the Higgs Bose on which there we would think there's one, there might be more than one, of course, actually we're not sure.
Twin Primes three laws of Motions for pairing basis five Platonic Solids six quarks is spinning. Seven base units measuring eight bits are pointing nine making the numbers prime generating ten row shock inkblots, diagnosing 11 dimensions, stringing 12 astronauts moonwalking and 13 Neptune moons and orbiting. So then that's a challenge for you. You now have to work out how many of these things you get over the 13 days of Christmas using four dimensional pyramids.
So there's a time as well you can send me if you think there is a better. Choices for your ones. I'm quite happy to get them through Twitter if you think some of those are a bit rubbish. So you can see, although there are lots of good maths already in some of the songs and the festivities with singing. But of course this is the time of year when it's really party time and party time. There's also some great maths in politics.
So one of the things about parties is that especially at Christmas, everyone seems to get off with each other. And so the challenge is, okay, they're all going to get off with each other. Can we get the pairings to work? So actually there isn't some dreadful breakdown in the office after everyone sort of paired up and people are unhappy because they wanted to go off with somebody else.
So actually maths has come up with a great algorithm in order to you know, if you've got a party and you want to pair people up so everybody will be there, all of the pairings will be stable. So I thought I'd show you how this works. It's just wonderful algorithm. So I'm going to need some volunteers for this. So we're going to have eight people at my party. So I need four boys and four girls, basically.
So can I have four volunteers? And we're going to try and show you how this mathematical algorithm works up. So so everything is kind of safe, so. Yeah. Okay, that's good. You have one here? Yeah, you can come up. Excellent. Yeah. Good, right. Yeah. Back there. So I think that yes. Hand up their great you want to call it excellence. Good. So let's, let's bring you up. And so the boys, you take a king and you go over there and the girls, you take a queen and you come over here.
So if you want to come up, great, we'll see how we're doing. So you're going to take you take the king of diamonds. So we've got this, right? So we go to my boys. Okay, so two, two more girls on each. Yeah, great. Excellent. And they're right. Good. Absolutely. Great. So let's see. So we got them. I'm going to put them in order. I play a lot of poker. So. So king of spades. I'm going to put you here. And king of diamonds. I'm going to put your hair.
Excellent. So what have you in the order. And then queen of spades. Right the end. So that's good. You can swap round. Poker order goes like that. Excellent. Right. So what I got is on each of the sides. So. So they basically ordered such that they give me a little order here about who they fancy. So here we go. So let's see the king of spades. So let's see your first choice. You really fancy. Oh, yeah. Let's make sure we get this the right way around. This the trouble with symmetry.
So, yeah. Make sure your cards are. Yeah, exactly. So the and your ones are down this side, so. Yeah. So you want to turn yours that way. Excellent. Right. So, so you really fancy the queen of diamonds? Okay, that one there. Yeah. Okay. And which one? You really don't want to end up with? The Queen of spades. Yeah. Okay, so. So that's the kind of order we got here. Well, let's see what you, you know, what's what's your kind of wish? So the queen of spades here on course.
Your first choice is the king of spades. Really wants to do well. Ain't going to happen, is it? So then you've got the king of diamonds, king of hearts, and the king of clubs. Right down there is the one you really don't want to end up with. So the challenge here is, can we find a way with all of these preferences to pair everyone up so that nobody will run off with somebody else because they there's a better option for them? You see what would happen if we so let's pair up.
So we're going to do the king of spades and the Queen of spades. So if you'd like to come to the front here, let's suppose we so you're going to pair up there and then we'll have the king of hearts and the Queen of hearts. So king of hearts, if you come down here, let's see if you were going to suppose we paid them up like this, why wouldn't this work?
Well, the trouble is that the you know, we've already seen the king of space really doesn't want to be with the queen of spades, but he wants to run off. He'd be quite happy. He'd be quite happy. The second choice on his is the queen of Hearts. But what about the queen of hearts? I mean, queen of hearts may not like the king of spades, actually. You know, you've been paired with the king of hearts as your bottom choice.
King of Spain. So king of hearts, queen of spades is the next one up. So actually you'd be quite happy to run off. So both of you, if we try pair this off, we'd have a disaster. They'd run away with each other. So that would just just wouldn't work. Okay, so you want to get back to your places. So here's the challenge is, is there a way to pair these up such that nobody will run off with somebody else in these things? Maybe there isn't the way to do this. Maybe it's always some instability.
If you think about rock, paper, scissors, you know, always there's something which beats something else and you can never make it work. So something is sort of stable when there is a way to do this. And so the way to do this is to get so let's put those back. So the algorithm that was that was come up with is that the queens all propose to your first choice. KING So look at all the ones on the top of your list. What I want you to do is go and stand in front of the one that you would really like.
Okay? So if you go, let's see how many, but who's who's the. Dorsey of this kind of outfit, I think. Oh, yeah, they all want to. Yeah. Most of them want to be. Yeah. Look at him. Isn't he cute? Wow. Yeah, it's the hat. I think we started it, so. Look at them. They're buzzing around. These two go. Poor guys are like, No, nobody wants us, but. Oh, well, at least you. So you got somebody proposed to use. That's one. Okay, but what do we do about this lot? Okay, well, basically, you get to choose.
So. So who's your top choice? Queen of diamonds. Yeah. Okay. So I'm afraid the other two get rejected. So if you come home, I'd say yeah. So you could get the queen at times for the moment. So the other two. Come here. You got to find something else to do. So. Right. Okay, so. So that's the first round of this. So we seen the first round, but the two of them got rejected. So these are provisional pairings. But now, okay, so first choice you're not going to get.
So let's go for your second choice. Okay. So if you want to go and propose to your second choice, so let's see where they go. I think we get now. So. So it may work. Great. Oh, poor king of hearts is kind of like, shucks, I'm not got anybody. But now you got a choice now. That's right. So. So you got queen of hearts and queen of plump. So which one do you like? Oh, that one. Well, I'm sorry. You got to come away then. So how is that? That didn't last it.
Gosh. Well, okay, so you come over here, so you've just got rejected, so let's reject you. Okay, so now so you king of clubs is your top choice. So you got the king of diamonds so you could go and propose to the king of diamonds. Okay, let's see what the king of the why now, King of Dimes is gonna go and see the king of diamonds. Yeah, he's. There he is. Okay, so now let's see. Which one do you prefer? So your top choice is queen of Queen of hearts.
You got your top choice. So, yeah, you're going to reject this one here. Okay. Oh, death. It's terrible, isn't it? Yeah. So. So we got this one now, so. All right, so you just got rejected again. Christ, God, that's two rejection. So we're right down here. Okay, King of hearts. Okay, so now you propose a way to the King of hearts. Finally, the king of hearts gets lucks out. So.
And now everyone is paired up with a single person. And this algorithm, if you carry this algorithm on, it means that you can prove that this will lead to a stable pairing such that now if anybody looks and sees, well, I actually would prefer somebody else, but they have got somebody who's better than the one who's proposing.
So so we find now that nobody is going to run off with anyone else, even though they might not have got their top choice, they can't offer somebody else who would say, well, I'm already with somebody I prefer than you. So. So this algorithm works. Now, the intriguing thing is we could have done this the other way round. We could have started with the Kings proposing all to the Queens. Does anyone think do you think that would give a different answer to the way these were paired?
If you put your hand up, if you think it would lead to the same answer. Yeah. Proximity could do things that actually might lead to a different answer. It's kind of an even split that actually does lead to a different answer. Not always, but very often. So it matters which order is it the women proposing to the men or the men proposing to the women? I think in this way the men lock out. They get the best that they could possibly get and the women get the worse that they could possibly get it.
But we did it the other way around. It was swap over so the women would get the best that they could possibly get out of this and the men would not do so well. Okay. Let's give them a round of applause. Thank you very much. Put your cards on the table. So this is actually an algorithm that was come up with for for trying to solve this problem. It's called the stable marriage problem. And it's one of the only algorithms ever to win a Nobel Prize.
So Galen Shapely came up with this girl who'd already died, but Shapely won the 2012 Nobel Prize in Economics for coming up with this algorithm. And it's a very powerful algorithm that can be used in a lot of different circumstances. One of the first was sort of pairing up not a lot at a party like this, but students applying to placements at university. And interestingly, the way they applied the algorithm, of course, the universities knew what they were doing.
They made the students propose to the university. So the universities got the best that they could and the students got the worse that they could do. The students suddenly work this out after a while, and so they say This isn't fair. So now they flipped it over. So the students, the universities now propose to the students. So the students get the best possible result out of this some. So but another interesting place is used in the NHS by and America as well kidney transplants.
Very often you might have a partner who is quite happy to give their kidney, but they don't match. And then the problem is you've got to find somebody who does match, but why would they give you the kidney? And so if you've got just to it's very simple. If you could find two and they'd be quite happy to swap over and donate a kidney to somebody else if their partner will donate a kidney, which will save their partner. So that's is quite simple.
But this matching algorithm, if you look at the number of people who are prepared to give kidneys across the country or in America, for example, it can get quite complicated trying to match these up. And this a similar sort of algorithm has being used and I think the longest one was this particular train of people here who managed to be matched up.
So this algorithm was actually saving lives in order to be able to find the right match for somebody, which I think is quite amazing what algorithms of course all over the place and algorithms are at the heart of how I find my Christmas presents to get people actually, because, you know, basically I don't know what to do. So I, I type into a search engine and say, what's the best Christmas present you could give to somebody?
And this is the amazing thing. I mean, Google is, I think, one of the most extraordinary algorithms and it's like almost like magic. I mean, yeah, but of course, it's not match, it's not elves. They're sort of saying, Oh, it's just a really amazing piece of mathematics that is at the heart of finding out what the best website is for for the present that you want to give. So I thought I'd do a little demonstration to explain how this algorithm works.
So let's suppose we got, say, three websites that's they're offering presents for Christmas and we're going to try and order and see which one is the most popular, which one is the most likely one that I should go to for this. So you might know that this Google algorithm works on the basis of the fact that it's the links between websites which actually rank the order of the websites. But how does this work? So suppose that I had this particular way of linking.
So suppose that website A or also recommends both B and website C. So that link from website A to website B and website C, website B only links to website website B only links to website C and website C only links to website A. Now with this particular set up, which do you think Google is going to put right at the top as the most popular? We're going to do a little vote. Okay. So you can you can put your hand up in a second.
So who thinks that website is going to end up at the top of the pile with the Google ranking with this particular way that network is connected? So put your hand up if you think website A should be the one which will be at the top of the list. So we've got some votes for a few votes, right? Okay. Who thinks the website B is the one that's going to go top of the pile? Very much for you in there. Okay. Losing weight. I see.
It's a loss. Are you going to see? That's interesting. Okay, so how does Google work this out? Well, basically the idea is that, yeah, Google is very clever because it's quite hard to kind of boost your own website's ranking in this. There's not much you can do. You've got to wait for other people to link to you. And that's the importance of how the Google algorithm works. So I need three volunteers are going to come up and be my websites for me and we're going to do a little.
It's a great you can come up. And who else? It's it's very mechanical. You don't have to do much maths. You just have to. Great. Excellent. We have one there. One more. Yes, one. You come. Great. So. So let me show you how this algorithm works. Okay. So I'm going to give we're going to give each website a kind of equal amount of value right at the beginning. Okay. So do you want to be website a? Oh, you've got a ruby red for.
Excellent. All right. Yeah. And I'm ready. Have you read the recent Ruby Red? I do the codes for Lauren Child's Ruby Red for books. And I'm really proud of my code for this one. So each book is about a different sense. And so we did one about twice this time. So I did this amazing four dimensional code for my one, and it was like, Yeah, sorry, I'm getting it right. So you, me, which I be and we, we get sizes, so we're going to put website B over here.
Okay. So I'm giving them equal value at the moment. So how does the Google algorithm work to see which one is the best? So I'm going to put these pots down here. So you a so essentially what you do is you share your value. If you link to a website, several websites, you have to share your value between those websites. So for example, you've got each of you got eight balls inside here.
So you link to both of these websites. So you're going to share your balls between four balls, two website B and four balls website C. Okay. But you, you only link to one website, so you will link to website C, so you're going to give all your value to website C. Okay. And the same for you. You link to website, are you giving all your balls to website? So what basically what we're trying to do is to run this and see how the value gets distributed among the websites.
So let's offer you go you. That's the pots there. So you're going to go to the pot and fill up the other person's pot with the value. So let's open these up. So all of them so you're giving four balls each, but all of your balls are going into that one and all of yours are going into them half off. So in the first round we distributed the ball so, so half ago on the here from the website, but they swapped all of those over.
So now the way the value is being distributed and you can see that's a website but not know many of you went to website B and that's kind of right because it's not getting much value on this round at the moment. Website. See, you've got ten balls inside there, so you're being highly valued at the moment, but that's not good. Not one round isn't good enough, so we need to run it again. So let's do exactly the same thing again.
So take the balls. So put the empty ones down. Take the ones that you got filled up and you do the same thing again. So you're equally distributing your balls and you're distributing them. It's all to one website. So if you go, let's open these up. So what happens now is website C, you still going to stay ahead?
Well, after we it on this one website B it's got a little bit is still pretty low but what's my CS going down now and the website is going up so now it's not clear whether you know which one is it website B you website C so a website. So it's a website. See your website. So let's do it one more time. Let's distribute. So, so, so basically this algorithm first of all, is just keeps on distributing. So if you go again, let's redistribute them. Where do they go?
Okay. So now, yes, you put half there and make sites. And so again, it's after that round website B is gone up a bit actually. So so is this thing ever going to stabilise or is it just sort of pinpointing all around? And this is the kind of challenge of this. So I think, am I doing one more round? Yeah, let's do one more round, see what happens. So this is the kind of what the algorithm is doing. So if you go share them around. But what we want to do is does it stabilise after a while.
If we kept on doing this, would one website would the websites kind of stabilised one of the moments that's we seem to get equal value for website and website C and that's the interesting thing is how can you work out mathematically without going through this thing over and over again until you see some sort of stability?
Well, this is actually a really powerful piece of mathematics, because essentially each time I'm doing this, I've got a little so this is the hardest part of maths I'm going to do, but there's a little matrix. So the number of balls that are at a website, A, B and C, when we do this round and we redistribute, basically it's the way this matrix acts on this little column vector gives us the new distribution of balls.
So I want to know, is there a. Play at distributing the ball such that the thing is actually stable. So it doesn't keep on changing each time. And this is actually a really powerful piece of maths called it's finding the eigenvalue of a matrix. So actually and this is at the heart of many things like quantum physics, it's about eigenvalues. So we want to know, is there a way of distributing those balls such that when we redistribute, they don't change ever.
And in this case, actually, we distributed them with 2/5 to website, a 2/5 to website C and a fifth to website B, then this distribution would actually stabilise. And so this is actually how Google works. It looks for the way that the websites are linked together and then what's the waiting to give to each website? So should when I do this redistributing, I don't actually get any change. So this is amazing thing. Eigenvalues of matrices basically are the heart of how Google works.
So if we change that and I put a 0.4, 0.4, so let's change that. So yeah, so we've got a distribution of 2/5 to face and one fifth, if we ran the websites again and did the little algorithm we did here, we'd see that the thing would stabilise. And those are the values, the ranks that are given to each particular website. Okay, just give our websites a round of applause. So. Thank you.
Oh, you can leave that. So the interesting thing is it's your intuition that to see was actually the most powerful because it seems to be being linked to by both the other websites. But actually both C and A are equally valued with this particular ranking. And it's quite I get asked actually quite a lot by advertisers now in advertising companies used to be overrun by people doing English literature because they wanted good copy and sort of.
But now advertising firms are full of mathematicians who are trying to reverse engineer the Google algorithm because they basically want to put their product right at the top of the ranking. And so, you know, this is pretty public, but actually the real mechanics of Google, there's a lot of hidden things because they don't want people kind of reverse engineering it and finding a way to get their website at the top one way. The other thing I get a lot of approaches is will you link your website?
Here are the Maths Institute to my website because actually some of the places with the highest page rank across the world are universities. So Oxford University has one of the highest PageRank because a lot of you know, we have a lot of value, a lot of people are linking to us and it boosts our page rank. So if I then link to somebody else, I'm giving them a lot of these boards and a lot of value.
So so it's interesting that, you know, of course, the more I do that, the more I'll I'll sort of water down the particular value. But it's interesting that people are coming to me because I have powerful page rank because of my place at this university, and that will actually boost their page rank as well. So this, of course, was discovered by these two geeky mathematicians, Page and Brin, in their in their garage in the West Coast of America.
And just using this simple tool of eigenvalues, of matrices, they've been able to make their their billions, basically. So I think it's a wonderful example of pure maths. Eigenvalues were considered rather pure. And I think the the idea of the dark side and light side, you know, this is really disappearing. The amount of pure mathematics that are now popping up in sort of an applied area kind of area like this really shows there's really no difference between us.
So the hope is, of course, that when you put in, you know, best birthday present of what will pop up is maybe Amazon recommending a copy of my book. In fact, this is this is what happened to me. So sometimes these algorithms don't really work because I got this letter a couple of days ago saying, Dr. de Sautoy, maybe you'd like these books. Yeah, yeah, yeah, I do like those books. And so they recommended three copies of my books.
And one of the trouble is, some of the times these algorithms really just because they're not, they, you know, you could have done this to make sure I didn't get a copy. I don't mind being recommended copies of my books, but, um, but sometimes on some kinds of these algorithms can do some weird things.
So it's an interesting example of a book that wasn't very popular book, but when this person put it in, he was interested in this book for his PhD. He put this book in The Making of a Fly, The Genetics of Animal Design. So, you know, they're second hand books on Amazon and basically, you know, this prize. So some of these second hand bookshops, they use algorithms to generate the price of these books.
Now, when he looks at this book, he got a big surprise because the book was on one website for $1,000,000, 730,000, and on another website over $2 million, he said, This is really weird. He wrote to Peter Lorre and said, you know, you know, your book is selling, you know, why is it selling for so much? You didn't know either. So this guy came back a few days later to say, you know, maybe it'd sort itself out.
But two days later, the thing had gone up. So one one bookseller was offering it for 18 million. Wow. This is amazing book. This must be that. And the other one, 23 me. I wish somebody buy my book for $23 million. So, so what was happening here? What was going wrong that somehow, weirdly, you know, why were they competing with each other to to sell this book?
Well, actually, the guys started to analyse what was happening over each of the days, and he saw basically there was a multiplier going on. So so each website was looking at each other and they were using the price of the other website in order to determine the price that they put their book on. So Prof. Nath, for example, is always trying to undercut the other one. They're basically, well, if you want to buy there, but we got it a little cheaper.
And we the beauty books was slightly over pricing their book. And of course, the way they'd weighted it meant that the cumulative effect. Was that actually the book was being pushed up and up and nobody was wanting to buy this book. I was reading it so nobody had noticed. And this thing was just over time. I mean, it's an exponential growth. Doesn't take too long to blow this book up to the price here.
Now, here's a question for you. You can understand why pro-Nazi were wanting to undercut, you know, so. Okay, well, we'll make it a little cheaper than the other bookshops, so you can understand that. But what's going on with the other books? Why are they actually got their algorithm? Making the book a little bit more expensive than the other website. Anyone got any ideas? Why? Yeah. Exactly. That could be one reason you think, oh, go with a really cheap one.
And maybe the other one's got a higher quality, you know, it's got everyone's ranking it. So maybe you'll go, Oh no, I'd rather trust the person and pay a little bit more. It was only a little bit of a factor, so that's one idea. But actually it turned out that probably wasn't the reason you got an idea that already broke, listed it fast and the other cost. Yeah. But then why bawdy books? It's actually got their algorithm always looking at the other website and multiplying it a little bit more.
So it's over time. That's right. So yeah. Yeah. Maybe they just wanted to mess with everyone. Yeah. Yeah, well, they certainly succeeded. Exactly. Yeah, yeah. But, you know, they're not I'm nobody's going to say pay 23 million for that book. I my thought was that 40 books didn't have a copy of Making the Fly. They didn't have a copy. So they just kept on looking. And the other one said, okay, if anyone orders from us, we buy their book.
But if we buy their book, we need to pay a little bit more so we can pay for it to be delivered and then we send it on. So we need to crank it up a little bit. And so I think that's what was happening. They didn't have that book at all and they needed to have a little multiplying factor. But it ended up, you know, with it costing 23 million, that is. And that's the trouble with these algorithms. Sometimes they just aren't sensitive to kind of with these sort of anomalies happening.
And this happens in the stock market. So there was this amazing thing which happened. And so there were a lot of algorithms at work in the stock market which essentially, you know, you want something which acting much faster than a human brain can react to.
And so when things change, it automatically does something. These algorithms that are in the stock market, we think that they were probably responsible for a rather remarkable flash crash that happened on the 6th of May 2010, when in about an a couple of minutes, the value of the stock market just absolutely crashed because these algorithms are working faster than anybody could react to. And they just sort of basically the same thing happened.
But instead of escalating the price of that Amazon book, it basically just crash the whole thing. And, you know, people were just going crazy. You know, this is one person's reaction to seeing what the [INAUDIBLE] is happening. But we then very quickly, the whole thing, it picked up again. And it seems now that there was somebody sitting in West London in with his parents, actually with Alison, and he created these algorithms to basically just sort of manipulate the market a little bit.
But these algorithms eventually led to this flash crash. And he's, I think, still waiting trial for actually manipulating the markets in this way with these algorithms, although it's not clear whether he knew the effect that they would have. So very interesting questions coming up now with these algorithms whether actually, you know, whose if you write an algorithm, are you responsible for the effects of the algorithm, which of course. I mean, you still are. I think so, just to warn you.
Yeah. Okay. So the the challenge I actually set in my my the title of my talk was this travelling centre problem. So this is, I think one of my favourites is, you know, a centre has this great challenge on Christmas Eve of having to find his way across the whole of the planet, delivering all of these presents down chimneys. And and so, you know, how how does he manage to do this? He has to find the most efficient path to deliver all of these presents.
This is one of his things. Now, have you gone on Google on Christmas Eve? And you can see where where Santa is on any particular moment. So here he is. He caught him on the top of Mount Everest delivering. So, you know, the challenge is, you know, you're going across the planet. Is there an efficient way to find the shortest path so he can get round all of the chimneys?
So I tell you, a little challenge. When you came in, you got the Santa's grotto there and various cities that they have to visit. So I don't know, will you be having a go at this, but the idea is you start at Santa Grotto and you go to visit each of the chimneys in turn and then come back to Santa's grotto here. And the challenge is, can you find the shortest path around this?
Now, I've been telling you about these wonderful algorithms to match people up, wonderful algorithms to find you presents on Google. But this presents a real challenge to mathematicians because we cannot find an efficient algorithm other than TRON an error. I mean, basically, I've got a lot of you here. Have you all tried trying to find a path around here? We probably would find one, which was minimal, but basically there's no kind of efficient way to see how to find the shortest route here.
I mean, you can have a go at this, as it were, to see whether you can find the shortest path. We'll see whether anybody comes up with it. The trouble is, that's the only thing we really know how to do, is to try one path after another and just see, try all the different paths and see which one comes out the smallest. But that is a very inefficient way to do it. And the more and more cities you have to visit, the more different possibilities there are around this network.
And so Point Sans has got a lot more than this to to visit. So this is an example of a problem. In fact, it's one of these millennial problems, so called the NP versus P problem. And these problems have the particular quality that once you kind of find a solution. So suppose you want to find a path around there. Which has a sort of which is less than, say, 240 miles or something once you've found one. You know, you've you've you've found a path.
But trying to find a path, which is to say less than 240 miles, requires just searching for the needle in the haystack. So there are a lot of these problems out there which have this quality that to in order to find the most efficient solution, you just got to try sort of one after another after another. But when you find it, you can prove very quickly that it is the fastest solution. So, in fact, we don't know whether there's a very efficient algorithm to find this path.
And this is one of the challenges. So we have these seven millennial problems. So now businessmen in America, Land and Clay offered $1,000,000 to anybody who could solve one of these seven problems. So one has already been solved. It's called the Poincaré conjecture. This is the my third book was about some of these problems. So the other one is the Riemann hypothesis about primes.
But this problem many regard as perhaps the most important because it has so many applications to the real world around us. So the NP versus P problem is basically can you find an efficient algorithm to find the shortest path around centres network or can you prove that there isn't one other than by trying all of them out and seeing which is the smallest? The intriguing thing is that there are many problems which have this quality to them. So one of my favourite is the the premiership problem.
So you might detect here that I'm an Arsenal supporter because I took this little freeze frame before Leicester beat Chelsea and went back on the top of the premiership. So this is a small moment a couple of days ago when we were still top. But the challenge here is, well, can you put pressure on Aston Villa, who we beat at the weekend? A Right down there at the bottom. But is it still technically possible for Aston Villa to win the premiership?
So what is the challenge there? It means, okay, well, Aston Villa are basically going to win all their games. Okay. But it's not enough because there are other teams who will be winning games or drawing and maybe it's a bit like the stable marriage problem. Is there a way to distribute the wins and losses and draws such as Aston Villa will stay top with all of their wins and we can make sure that no other team beats them weirdly.
So many years ago, when I was young, you used to get two points for a win and one point each when you drew. This means that actually the end of the season, you know, the total number of points in the division because it didn't really matter whether it was a win or a draw or a loss. It was basically, you know, everyone would be those two points would be distributed around. But then something changed. The premiership decided, okay, now we want to incentivise people to win and they changed it.
So you get three points for a win and only one each if you draw. So now at the end of the season, we don't know how many of the total points will be. If everyone drew all their games, it would be as small as possible. If there were no draws, it would be much bigger. The weird thing is that before we did this change, there was an efficient algorithm to work out whether Aston Villa would actually have a possibility to win the Premiership.
But with the change from two points for a win to three points through in suddenly this change and we no longer have an efficient algorithm, in fact, this has the same quality as a travelling centre problem that's essentially you've just got to try all the different possibilities of results and see whether there's one which will make sure that Aston Villa will stay top. And so all of these problems, their various different versions of them say this one about Minesweeper,
there's another one sort of another coming back to the party problem. If you're staging several parties across the Christmas season and you know, there are people who really don't like each other and you go to invite them to different parties. So, for example, suppose you cannot invite somebody to the same party if they are linked to the other person to that party. So Fran and Ian, we can't invite to the same party because they hate each other.
So the challenge is, you know, can we find a way to have as many, you know, as few parties as possible such that nobody is coming to a party with somebody that they hate? So this is another version, it seems to be you can only just try different ways, give it your day in doing the invites. There's another version of this which is kind of interesting, which is so you probably know this thing called the full colour map problem.
Robin Wilson is here. He's written a wonderful book about the full colour problem. It's this challenge of, you know, if you have any map, you can always get away with four colours to colour that map such that no countries that have the same border will have the same colour. But here's the challenge actually. Could you get away with three? Is three colours enough? So with any particular map, the challenge is well. Okay. I know thanks to this proof that for will suffice.
But in this particular case can I get away with three? So in this. So you might. So I think in this case you can't because Luxembourg has three countries around, it is no way to colour those. But sometimes you can re divide the map such that there are three. So the challenge of trying to work out whether there are three colours that will suffice is actually absolutely equivalent to the challenge of trying to work out whether you can do get away with inviting everyone to three parties.
Because if you think about suppose I tried to see whether there were three parties that I could stage such that nobody here would be invited to a party with somebody they hated. Well, that's exactly the same sort of problem if I change these now from people to countries. Actually, it's the same problem as if I was trying to colour the map with three colours as opposed to four and make sure that no countries with the same border would have the same colour.
And this is the amazing thing about all of these problems, actually, if you can solve one of them. So if you can solve the travelling side to problem, you end up actually finding an algorithm which will solve all of them. So we've managed to prove that all of these problems are actually equivalent so that any solution to one of them, if you do the Minesweeper one or the Premiership one, you can use that algorithm to solve all of the others.
So it's extraordinary. So you only have to analyse one problem in order to be able to work this out. Now Centre is actually faced not only with the problem of finding an efficient path around the earth, but there's another version of this which we are going to end with. So I need to volunteers from this side of the lecture theatre who can great if you can come up and one more volunteer from this line. Excellent point.
So you're going to come down here and two volunteers from this site who are going to compete against them and a little problem, which is a problem. So any volunteers from this side? Great. Yeah. I just need one more. You can bring him. You will. Okay. So the problem here is I've got basically Santa has to find the most efficient way to pack his sleigh when he's setting off. And he has to try and get as many people up and presence inside as he can.
So the challenge here is I've got different sorts of sizes of packages now. The length of each lorry is 150 metres long and you have to find is there a way to choose these presents so you can fill the hole of the lorry? Okay, so we've got a little time here, so I'm going to give you 30 seconds and see who can find the most efficient way of filling this. And you mustn't overfill it. You can under fill it, of course, but the sleigh won't move.
So we're going to go with 30 seconds starting now. And you can also kind of have a go there, see whether you can find is there a way to find those boxes such that you add them up and you can get up to exactly 150? What's the closest you can get? You mustn't go over 150. Okay. So that's you don't. 15 seconds left. So basically you've got to find at so many different ways I can stack these up. So we got seven, five, four, three, two, one and stop there.
Okay, so let's see, let's see what we got. So right now, you know what? You've got to you've got you you've got to stick them on. Yeah, yeah. You can't start changing now. Okay, let's see what is always interestingly so. So this one is a draw here because they got 52, 59 and 27, which fits, but it isn't maximising the thing. So 30 seconds. Well, because you could have got the whole length, so you got a little bit left here. Okay. So and this side here, you also went for 52, 59 and 27.
So did anyone manage to get a different way, which got a little bit more efficient? Yes. 65, 47, 60. Okay. Let's and that adds up exactly to 150. So well done. But this is a real cut. But this is the interesting thing, because here I just asked to two people to do it and they had to try all the different possibilities they didn't get. You know, interestingly, obviously, you're using the same sort of algorithm.
I mean, one of these algorithms is, you know, well, just put the biggest one in first and then you find, well, that's not really good. And so you go for the next biggest one down maybe. But if I ask all of you, basically you're working a bit like everyone trying something different and it was not unexpected. The maybe with the whole of you here, we would find one person would find the most efficient one. But again, we don't have an efficient algorithm to find.
It seems such a simple problem. You know, just what's the most efficient way to pack the back of your van or the the sleigh? And this is another version of this. No problem. So let's give all our volunteers a very grounded ball. Thank you very much. So I think this season is just jam packed with amazing mass. I mean, it was all I could do, snowflakes as well and tell you all about that. But time has run out. So we come to the end of the lecture, they say.
So if you can find a solution to this an efficient way, an algorithm will prove that there isn't an algorithm. There is $1,000,000 prize. And so the travelling sales centre problem, travelling salesman problem, as it's known. Did anyone get anything below 240? Yes. What did you get from the 231 231? That's amazing. Today, anyway. What are you going to at 2 to 8? Right. Okay. Yeah. So 2 to 8. Wow. You see, even I got it wrong, you see. So I thought 2 to 8 is even less than I said.
That's. No, I did that one time. Yeah. Oh, okay. He's the true mathematician in the room. So I thought it was 238. But that's the interesting thing. You see, I might well have missed a path around here that that would give you a more efficient way. So anyway, if you want to find out more about some of these problems, I'm selling copies of my book, The Number Mysteries, which is about some of these monolingual problems. There were five problems. One has been solved. There's still £4 million.
You can win if you buy a copy of the book. Anyway, thank you very much for coming along and.