NIM, or, always WIN with math
So last couple of weeks we’ve been doing a couple of videos based on movie clips – used movie clips as hooks to talk about Mathematics and Well, I had a look at my collection And we’ve got a pretty big collection of mathematical movie clips if you look on the web. We’re actually Looking after the mathematical movie database me and a friend of mine Marty Ross Anyway in this collection is another clip that well I kind of sorted out the maths behind it Like two years ago, but I not forgot about it again, and I thought well Let’s just lets us put in a video and then it’s done. It’s there next time I’ll actually want to revive this stuff It’s going to be there. Alright, so this is from a movie called Last year at Marienbad. It’s quite a famous movie It’s a pretty pretentious movie, pretty much. I hate it anyway, but apart from the maths the maths is really good So there’s a there’s a nice game in there Let’s have a look at the clip and then you know I’ll start talking about. Okay, well, there’s the mysterious guy here And there’s the clueless guy and they’re actually having a couple of games throughout the movie and the coolest guy always loses Well, yeah, always um now What the game that they’re playing here is called Well, it’s a special version of a game called Nim It’s a very mathematical game, so it’s a very nice winning strategy And it’s actually the winning strategy that enables this guy here to to win all the time So I want to talk a little bit about this so it’s nim. It’s called Nim One nice thing about nim is that when you turn it upside down. It turns to win, so we’ll call this video here Nim to it okay. So what’s the setup? What’s the setup? We’ve got cards one three five and seven I’ve actually colored them in to make things even easier to refer to um now the winning strategy is based on binary Representation of numbers okay, so at the moment. We’re kind of writing things down in decimals We want to write things down in binaries and that involves expressing numbers as sums of powers of two so in decimals we express them basically as sums of powers of Ten binary of two okay, so in with these numbers here What powers are we talking about just one? two and four okay, so now to turn seven for example into Binary what we do is. We will first look well What’s the largest of those numbers that goes in seven to four so there’s a four and then there’s three left over What’s the largest power of two it goes in there, too? And then it’s just the one left over and that makes this number Then into one one one so seven in binary is one one one what about five well largest of our numbers or powers of two that goes in there’s four and Then what’s left always one is already one of those numbers again So that means that the binary of the five in binary is one zero one What about three? well 3 is 1 1 and 1 1 is 1 Okay, so I mean I could talk about binary numbers here But I’m not going to I’m just going to kind of draw these diagrams, and it’s clear what I’m saying here it’s basically a special way of Nicely representing binary numbers okay, so let’s just save this somewhere up there alright, so that’s how the game starts and Well, maybe that was a bit quick. So you know let’s just follow through what actually happens here in the game alright so this guy says You start clueless guy you start, so clueless guys faced with this You know setup, and now what did he do? Well, he doesn’t know what to do. So he just takes a card all right now Mysterious guy, what does he do well? He also takes a card at this point in time We actually don’t know whether he knows what he’s doing or not, right? So who knows right clueless guy? Well? He just wants to know what’s happening now, right? So what does he do well? He just takes away a lot of the cards right and Maybe just to reiterate the rules right on every move you can either take away Just one card or two cards or three card or all the cards, but they have to all be from one row, right? It’s very important right you can’t take away cards from from different rows, okay? That’s what the people are doing at the moment, alright? So he’s just taking away all the cards here You just wants to see what happens. Yeah now. What does the mysterious guy do? He takes away two cards all right. Well, it seems like he knows what he’s doing. Actually he could start analyzing what’s happening here. Let’s just not do this let’s just kind of keep going Well, it’s the clueless guy do this one here mysterious guy two cards Okay, then then it’s all predetermined right once you down to one card each and every one of the rows you basically just take turns taking off cards and then You know just one card left over for the clueless guy to take so mysterious guy wins Okay, now what I’m going to do is I’m going to turn every one of those diagrams into one of my binary diagrams Okay, nope just do this in one go And see okay so and Now we’ll have a look at You know the different? diagrams here Now this diagram is what I want to call balanced. Why is it balanced because if you look at the ones in here There’s an even number of ones there’s an even number of tools and There’s an even number force now when you Look at what clueless leaves left With when he’s finished, this diagram is actually unbalanced because you’ve got an odd number of ones Well that’s balanced the tweezer balance the force balance doesn’t matter as long as one of the numbers that That you see here is not balanced the whole thing is not balanced okay. It’s not balanced that’s balanced again It’s a two here even even even then down here Not balanced right. There’s just one here is a odd number, one here is an odd number – not balanced. What about here? Balanced what about here? Unbalanced. Ahh now something strange happens, the mysterious guy does not go for balanced he goes for Unbalanced all right, so so some some some break in this strategy seems to happen at this point in time and then once you’re in the you know one card per row everything kind of predetermined right it does take turns and So you know he wins? Okay, so why is there a break in strategy? Well, there’s actually or what was happen what would happen actually if you just followed our strategy always go for the Balanced position always go for a balanced position if we just continue or if the guy just continued like this well lets us have a look, so We’re here the clueless guy just has taken his card and now if you go for balanced What do we do well? We just take away those we take away those three cards right and then we’re balanced we’re balanced now the coolest has to take away one card, forced and Well, we are left with one card, and we take the last card which makes us lose but There’s another version of the game Which says well if you have the last card if you take the last card then you win. So they’re playing the version where whoever takes the last card loses but there’s the other version which actually the kind of default version which says if you have to if you take the last card you win, okay? and to win the default version you actually always go for the Balanced position and you can always go for the balanced position right so once you imbalanced the other person automatically unbalances Whatever, they do Then you can balance again the other person unbalances and so on all the way to the end and the end is Balanced obviously because there’s nothing left over right. There’s all even numbers zero zero zero zero so it’s it’s going to work if What I just said is true right that you can always Achieve a balanced position when you are unbalanced, and that once you’re unbalanced and you do anything you actually get to something unbalanced All right, so lets us have a look at strategy Okay so We’re not really dealing with the game as its played in the movie, okay? So what’s special about this position where he kind of changes strategy? Well what’s special about it? Is that this is the first position? where there’s In every row just either one card, or just one of the rows has more than one card Okay, in all the other positions that we’ve seen previously there’s at least two rows that have more than one card So here is the first position where? It is just one row that has more than one card Okay, then. What do you do? What do you do? Well it depends on how much is left over so I’ve just indicated like this, okay So we can actually think our way through this now let’s say there’s a let’s say there’s Like three Rows left over and one has three cards like just like what we’ve got here Okay, then you can think what can you do next. There’s not that many things that you can do. You could take away, Take away one of those cards like the red card well, if I as the mysterious guy, take away the red card, okay? What does the other guy do? Well, he takes away all of those then I’m stuck with the green card so taking away the red card or the green card It’s not a good idea so what else can I do? Well, I can take away some of these Purple cards if I take away all of them well then the other guy takes a bit of green I’m stuck with this, so what I do is I just take away – all right, so let’s take away two of those cards and then clueless guy, me, clueless guy has to take the last card okay, so you’re basically just aiming for clueless guy having an odd number of Single cards in front of him when he starts what about here well similar sort of analysis in this [case] We’re [just] taking away all three cards down there, and that leaves us in the same situation okay, so pretty obvious that that would work Alright So okay, so in this I mean finally he kind of figured out. Well. Maybe it’s got [something] to do… the clueless guy figured out that maybe it’s got something to do that, I always have to start right and of course, it’s absolutely right So now he says what if you start? What if you mysterious guy start right well? Let’s see okay. So here. I’ve got the complete game that they’re about to play So the mysterious guy has to make the first move right, and when he’s finished he’s necessarily in an unbalanced position Okay, you can see it right, so this is after he takes like a card he is an unbalanced position because we’ve got three ones here Unbalanced then what does the clueless guy do well? It seems like he’s not so clueless because when he’s finished with his move. He’s actually in a balanced position So maybe he’s he’s figured it out, right? So then the mysterious guys has to make him move and obviously you know he’s to be in an unbalanced position He is an unbalanced position as this one here, then what does the clueless guy do? Oh, he messed up. Have a look There’s two here, one here, two here, unbalanced right which means that this guy can now get into a balanced position You see he’s in the balance and now Everything’s won or lost depend on whose perspective you assume? okay, so well You know what the strategy is I should tell you a little bit about why it works Well, why does it work? Well, it’s really it’s really about two things, right? I said it before I claim that if you’re in a balanced position And you make any of those moves that are possible you automatically end up with something unbalanced, okay? and that’s actually fairly simply to see so if you’re balanced and Say you’re faced with this row, and you take away anything there, alright? then you’re not going to see when you’re finished and kind of redistribute things. You’re not going to see the same thing again which means that one of these is missing, right? one of the ones that you see here to either the one or the two? four is missing. When one of them is missing the whole thing but unbalanced, you can forget about it right, okay? So that’s easy to see. Balanced: you take anything you end up with unbalanced. The other way around is a bit more tricky So to see that if you’ve got something unbalanced you can always balance it That’s a little bit more tricky to see and I just want to show you how that works But to really be able to show you a really good example, to let you in on another secret, Which which you can actually play this game with any number whatsoever, doesn’t have to be one three five seven [you] could have chosen 666 653 Twenty right so you could have left like four piles four piles And you don’t draw the diagrams you can play exactly the same game if you want to be the one who has the last card you just play always for balanced position, if you want the other person have the last card then you break your strategy as soon as you faced with a finishing position where there’s just one row which has more than one card okay, so straight away Okay, let’s have a look at one of those Bigger games, so there’s a bigger game. At the moment, we are Unbalanced okay, so we don’t only have one to four, we also have eight next power of two up, okay So here we’ve got four of those that’s balanced. That’s unbalanced that’s unbalanced so the largest power of two that’s unbalanced is actually two eight and We could use any of the rows that have an eight in it, to balanced this position, So let’s just choose one Let’s just go for This one, okay, all right So focus on this guy first, we’ll throw away everything else. So we’re definitely going to take that card away, okay, and what we’re also going to do is we’re going to take one of the cards from the eight and then now seven left over and When you actually distribute the 7, 7 is just one plus two plus four so we can distribute them over here And then well this one was unbalanced because we just moved our cards. This is balanced now. It’s two and Since we’ve got like one and two and four in those positions. We can our checked. Which is balanced. This is balanced This is unbalanced. We just move the – this is balanced. This is balanced. We finished okay, just one more example Here’s another set up, so it’s also somehow unbalanced this is balanced, balanced unbalanced, balanced Okay, so this time the largest unbalanced Corresponds to the four okay, so we leave the eight and everything else that might be there on the left You know we leave that in peace. It really depends on the lot and the largest one that’s that’s not balanced so in this case it’s the four and We could use any of the parts that have afforded to now achieve a balance so let’s just use this one here, okay? So as I said, we’re going to leave this in peace for a moment. We’re going to leave this in peace We’re going to get rid of everything to the right so get rid [of] it Now we’re also going to get rid of one of the cards here What’s left is 3 3 is 2 plus 1 so we kind of shifted over here? All right now because we just shifted Stuff from here to there that column is balanced now and now since you have a 2 in here, and I one in here We just have to check well 1 and 1 balanced and to balance that we actually don’t have to do anything else, right? so if there was say this this one wasn’t there we could just get rid of this one here and then what things would be balanced or if that one was missing we could get rid of this one here if Neither this one, now or that one was there we could get rid of both of them would couldn’t balance again, and that’s basically it Except what the movie is really about is of course to get the woman and well even the woman gets into Playing the game. So there she is pondering the game… wait, coming up – there she is! So it’s actually clueless guy was really interested in her Alright, so let’s just play a game with her what you know know how to play the game So let’s just play the game with her Here we go. She has the first move okay so she has the first move she’s thinking and she takes away 2 cards Ok now we’re going to turn this whole thing into one of our binary diagrams So there she’s waiting for us to move, so what is it now? We’ve got 4 here. We’ve got unbalanced here. We’ve got Two fours, they’re obviously it. We just take away these two here and we’re balanced Huh, okay, so back take away two red cards, and we’re balanced Okay now she has to make a move, thinking, she takes away one two three four And actually well we are in one of those situations where the strategy breaks all right? So we have to figure out well at this point the time hmm here We have to figure out whether we want to win, or whether we want to lose, right? well I hate losing so I’m going to go for a win right so what I’m going to do is I’m going to take away like everybody here in this row and that leaves us with a winning situation odd number of single cards So let’s have a look Now she doesn’t have a choice just to take this I take that and She’s left his last card and now depends What is she impressed by my strategy or she does she hate me because I just won We’ll see, you have to watch the movie to find out what happened.