Brussels Sprouts - Numberphile

Key Takeaways

we're going to play a game called Brussels sprouts so let me show you how to play we're going to start with a couple crosses and here's what we do so on player one's turn they can connect any two of these free ends so player one might go like that and then you need to put a slash through the curve you've just drawn to create two new ends like this so that would be one player's turn then player two would go player two might connect to this end and this end and draw a slash through and then it'll be player one's turn again player one might do this you can't draw through an edge that's already there so another turn might look like this and the game goes on like that alternating player one and player two so the player that wins is going to be the last person that makes a legal move so at some point if there's no more moves that you can make then the other player will win uh you want to play I'll give it a go maybe we'll use some colors yeah I'll play Blue you play okay Brady is red um so why don't you start okay I will play that okay I am going to do this so this isn't really a fair fight because I'm really good at Brussels sprouts are you good at are yeah you've got a good strategy have you I'm going to play copying me I see um I am going to do this I will play through the middle here I'll do this one um I'll do this yeah you lost I'm sorry uh you shouldn't feel too bad about losing because as I said I'm really good at Brussels sprouts and actually it's not really a game it's more of a mathematical trick so no matter how you would have played I claim that this game of Brussels sprouts was always going to have eight moves so because I had you go first you were always going to lose because the number of moves was even so player two would make the last legal move so I want to show you how we know that there always eight moves because it's really cool okay so let's look at this picture that we have our finished game of Brussels sprouts so I'm going to do something I'm just going to make these crosses a little bigger so they're easier to see so I'm just going to fatten them up a little bit and I'm going to call these dots vertices let's see did I get them all I did so this kind of picture that we have here where we have dots that are vertices and edges connecting them where the edges aren't crossing over each other that's what's called a planer graph and planer graphs we have this cool mathematical fact so for any connected planer graph like this one the number of vertices minus the number of edges plus the number of faces is always equal to two so this is like a really not two factorial yeah sorry two excitement sorry that's not a factorial although two factorials too so we'd be okay either way um it's a so I'm enthusiastic about this fact because it's really cool and it's useful in lots of different things it's called the oiler characteristic that guy Oiler yeah so he did a lot of things including this so we have this fact for all planer graphs and I claim that we can use this to study the game of Brussels sprouts so should we do it so let's say that we have a game of Brussels sprouts and it ends after M moves okay so this is just going to be the number of moves until the end of the game and I'm going to try to show that that number has to be eight so if we're going to use the oiler characteristic we need to count some things so we need to count the number of vertices edges and faces so at the end of the game I want to count the number of vertices the number of edges and the number of faces okay so let's figure it out when we started the game we had just these two crosses like this so we had two vertices at the beginning now what happens when we make a move so the first move we connected two of these ends and we put a slash through that creates a new vertex so we started with two of them but every time we do a move we get another one so if we have M moves we have 2 plus M of the vertices does that make sense okay so now I need to count edges so let's look at our moves again so when I make a move I'm drawing an edge but then remember I cut it in half so actually I drew two edges we started with no edges in the beginning when we started the game there were nothing connecting our vertices so we had zero edges at the beginning and on each turn we created two so at the end we have two times the number of turns now faces is the trickiest one so let's look back at our picture here of our completed game of Brussels sprouts so when we count faces I should have mentioned earlier that when you count faces what is a face it's these regions that are bounded by the edges except that we also count all of the outside as one of the faces so over here I need to count these faces so if we look at the picture at the end of the game every face has one free end in it you know if it had two free ends in it the game wouldn't be over because somebody could just connect those two ends so we can only have one free end at the end of the game so each face has one of those ends in it and those things are actually easier to count so instead of counting the number of faces I'll just notice that's the same as the number of free ends Tina how do we know there can't be an end state in which there's a face with no free ends in it yeah you have to think a little bit about how the faces are created so maybe we should look at like this partially um done one how are the faces created well we get faces when we um add an edge and a slash and so every time we're closing off one of those faces we're automatically getting a little free end inside it so there never exists a face that doesn't have one of those ends in it so we just need to know there can't be more than one okay so we count the number of free ends and why is that easier to count well at the beginning of the game how many did we have so we had four on each of our little crosses so we started with eight of them on each turn you use up two of them right we use up these two they're not free anymore but we create two more so after one turn there are still eight and the same thing is true after every other turn we use up two of them but we make two more so we use up two of them but we make two more so there are always if you count we still have eight and in fact we always are going to have eight so the number of free ends is eight which means our faces have to be eight so maybe we should have done this one as an example so in this example for instance if we count vertices there are 1 2 3 4 5 6 7 8 9 10 vertices then I'm supposed to to subtract the number of edges there are 1 2 3 4 5 6 7 8 9 10 15 15 16 edges and I'm supposed to add the number of faces so these faces are their regions so it's 1 2 3 4 five 6 seven but then I also count everything outside the graph as a region so eight and then we get two like we were supposed to okay so let's let's do the oiler characteristic so I'm supposed to do the number of vertices minus the number of edges plus the number of faces 2 plus m is the number of vertices minus the number of edges plus we had eight faces and it has to be equal to two Oiler told us that so what do I have I have 10 minus m is equal to 2 the number of moves is eight we just showed that player two always wins but what if you had insisted that you wanted to go second well I still could have won a because I could what would you have done I would have started with three crosses instead of two so if you start with three then the game ends after 13 moves and the cool thing about brussels sprouts that is that if we start with n crosses the game ends after 5 n minus 2 moves and it's the exact same argument we just did just we add another variable to for the number of crosses um so whenever we start with an even number of crosses player two wins and with an odd number of crosses player one wins so what I recommend is you ask somebody do you want to play brussels sprouts and you put two down and they'll say sure and then you say do you want to go first or second and if they say um you know I want to go second then I just say oh since we already did two crosses let's add a third one and we'll play with three people don't notice because the game seems like it should have strategy to it so uh people mostly are focusing on the strategy and not assuming that I'm starting them with a losing situation