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.

100 Replies to “NIM, or, always WIN with math

  1. I used to play a strip version of this game. Would make sure to lose occasionally to give them hope and of course, because it's no fun if I end up with all my clothes still on. If I remember correctly the layout I used had one move with which the beginning player could win, but all other starting moves had a perfect way to counter it.

    Never used that ofcourse, made it to easy, and to easy for the other to figure out. Used a couple of general tips, like keeping a piramid shape untill two rows were left and then giving them two rows with the same number.

  2. But, what should player do, if he is already presented with balanced situation – he needs to move, and the one that takes last card loses? For example in game with 3, 9 and 10 cards in each row (or 3, 5 and 6, or with two rows of equal value) – how to win?

  3. Binary, or any translation to decimal is simple if you do it column by column. The formula is (base^column-1)value

  4. Mathologer, what is the winning strategy of a two dimensional NIM game?
    At start, the cards are placed in (m ) by (n) configuration (m rows, n colomns). So we have (m x n) cards. Each player can take as many cards as he/she wants from a single row, or a single column (but not both). The one who play last looses

  5. Ah ! You don't have MONEYBALL in your mathematical movie database ! I don't know if you're interested in general small contained clips of mathematics in the movies but if you search my channel I have uploaded some good compilations.
    SEARCH YOUTUBE "moneyball island of misfit toys" & OR "mathematics in the movies" – also many years ago I did a video on NIM.

  6. Great video as always, but still I will be the devil's advocate. 🙂 I think the proof contains a hole. We have seen that in order to win we need to reach position when all but 1 row contains a single card. We also saw that when we reach balanced stage it is not possible for our opponent to push us out of it. What I miss here is explaining why do we want to be balanced and how it helps to reach that objective (it is quite trivial certainly, but still not explicitly stated).
    Of course I realize the method is working, I just refer to the proof itself. 😉 I also want to say I really enjoyed watching the video!

  7. Nice explanation. To bad you didn't like the movie, it's pretty good IMO, but I like slow paced movies.

  8. It's a very nice game. I wrote a BASIC program on an old Commodore 64 for this many years ago! To play though, I found it easier to just follow patterns. Always try to leave your opponent in a pattern like 1-2-1-2 or 1-2-3 or 4-4 (or 1-4-4-1) etc. It's quite easy once you learn the winning patterns. You can extend the number of lines by adding 9 matchsticks (or whatever) then 11 matchsticks etc. It gets harder, but patterns are the key.

  9. I was hoping that you were going to show that all impartial games (games where each player can make the same move giving the same board) can be turned into nim.  I saw a talk on this once, but it didn't all stick in my mind.

  10. For people familiar with binary logic, it's probably easier to think about it as:
    balanced = XOR on each culumn returns 0 (which translates to: there is an even number of 1's on each collumn)

    Example for card's start position:
    Row1: 0001
    Row2: 0011
    Row3: 0101
    Row4: 0111
    XOR: 0000 => balanced

  11. Sorry, but this time I don't quite understand all of it.
    1 – On the real board, it's not clear to me how to rebalance without thinking 20' for each move… Do I really have to mentally split the cards into the binary positions?
    2 – Why from a balanced position it isn't possible to make a move that leaves the board balanced? It's not that I don't believe you, I just would like to know 🙂
    3 – What happens if both players perfectly know this trick? The mysterious guy says "I always win", even if he has to play first: how can he be sure?

    Keep up the great work, I love your videos!

  12. Hi Mathologer, what's your tool you used in your video to make those fancy visualization of math process? I love your videos so much and want to improve my math lessons with those fancy visualization to help my students learn more. Many thanks!

  13. I see what you did there in the title ;> Nice one. My ability to read upside-down text has finally paid off with some fun 🙂

  14. I think you overcomplicate the puzzle..

    …. isn't it just about if there is 1, 2 or more cards in a row and how many rows are left? Removing any number of cards from a row does not change the balance as long as you leave 3. There is strategically no difference between 3 or more in a row as one turn can change that.

    If you leave 1 in a row you force an out. So two is the setup. 3 or more is the road to two. If I would only take x and my opponent takes the rest except two my opponent forces an out.

    So there are only 4 states a row can have.
    #2 Only 1 card (can only lead to resolved)
    #3 2 cards (you can either take one or all)
    #4 3 or more (you can change it to any other state)

    So basically state 4 almost irrelevant. It can change the balance at every turn. As long as one row with 3 or more cards exists you the state of the game is fluid. Only when you have only rows with no, 1 or 2 cards you force an out.

  15. teenage mutant ninja turtles game in gameboy console had the same game with the extra rule of been able to remove only continuous items of the same row. so if you broke a line in two sets of items you could only remove from a continuous set. does it have the same strategy in balanced;

  16. my teacher game me an assignment to program this game, thank you so much, because i would not have figured out how to do this myself

  17. Another great video, thanks!! (I'm math-addict) The explanation is very nice, but you could have go a bit further and explain the generalized algorithm to turn umbalanced into balanced, it stems directly from your moves at 17:17. Removing the red row would do the work if a human was playing, while a computer would play as you do there (and get the girl).

    As this is your channel, we must respect your taste about cinema. But you didn't just say "I don't like this movie", you just said that Last Year at Marienbad is "pretentious". All I have to say is:
    It would be pretentious, if it wasn't that good.

    … I agree, anyway, that it's not a very amusing movie.

  18. Very interesting. Unfortunately you missed out on the part where you prove why this is correct, so i played alot of 'pearl 3', in order to empirically justify your idea.
    I also came up with a sort of proof: There is only 1 situation, where you forced to give your opponent a winning move, and that is when you get 2,2. In this case you can either give back 2,1 or 2,0, which both will make you lose. There are no other situations where it is forced. Not if you try to delay it. Since 2,2 is balanced, it means that you can never be forced into losing, if you alyways get unbalanced moves from your opponent, and you will always get unbalanced moves from your opponent, if you always give balanced moves to him (as explained in the video).

    So if you just keep giving balanced moves, you will always win, because either he will play a random losing move, and you win, or you will eventually give him 2,2, and you will win. Him playing 1,1,N, counts as a (eventually) losing move, where you can play 1,1,1 (the only good unbalanced move in the game).

    Anyway, love your stuff, keep up the good work.

  19. Thanks for introducing me to this cool game. I watched the video last night and today I played it with my nephew after Thanksgiving dinner. It drove him nuts that he couldn't win. After about 10 games I started putting the cards into binary form like you did and he finally figured it out. Thanks for helping me make a great memory with my nephew!

  20. The version of this game i knew had the same rules as the movie and one more: You have to take successive cards in the same row.
    So for example, if you take the middle card from the 7 row, you are effectively breaking it into two 3 rows.

  21. Another delightful video that fills a longstanding hole in my education. I couldn't figure this out on my own when in high school, nor could I follow the explanation I once found in a book. But with your explanation and a bit of playing around with a deck of cards, it all makes sense now. Thanks 1e6 for putting this video together! Eagerly awaiting another "Aha!" moment courtesy of one of your videos…

  22. Also, NIM is pretty close to the German word 'nimm' which means 'take' as in 'take a card'…. wonder if the game originated from Germany…

  23. I'm surprised and I'm studying class11. Can I use this for my exhibition?

    can u reply as fast as possible

  24. I was introduced to a whole bunch of NIM games from the excellent youtube channel "Scam School". Far less math, but that channel has lot of renditions of Nim.

  25. Took me 10 seconds to realize they were speaking French and that could understand without having to read.

  26. The amazing physics and mathematics from a simple two pan balance:
    2) …
    3) …
    4) …
    5) … #science #physics #math #maths #mathematics #education

  27. It is worth noting that many many many games can be analysed by reducing them to Nim. A very satisfying corner of game theory, and why Nim is so well-known!

  28. the 'Default' game make more sense.  It is important to state that a player, on her turn, is required "to take at least one card from one and only one row."  That way, when you take the last card, your opponent is unable to follow the rules during the her turn.  As she cannot follow the rules, she loses.  It's much clearer this way.

  29. Can anybody claim that he/she can win chess all the time? Is there any study done on a more complex game like chess?
    Or are any fundamental steps taken to try to figure out in simplified conditions

  30. I'm a SW engineer and do get now and then people asking about binary. It would be cool if you did a series of videos explaining different numbering basis, and how to do arithmetic operations with them, including addition and multiplication in binary (e.g.'s_multiplication_algorithm ). I know that, but many people don't.

  31. 18:00 – Do you need to take the smaller ones out, and take one off of the next-largest pile, breaking the larger into smaller pieces? Couldn't you just take the largest unbalanced pile (4), and then check the ones below it (in this case, the rest are balanced)?
    Seems like you are doing extra work.

  32. While your looking into correctness check out the movie "Ready Player One." In said movie there is a corporate army of VR gamers called the "Sixers" presumably after the company name 101, pronounced "eye-o-eye," but the company name in binary equals 5. So why call this army of VR gamers with a quite literal 101 on their forehead Sixers? Oops, movie logic strikes again.

  33. played a bit different version as a kid. just line up some matchsticks, one may only take away 1,2 or 3. then make sure the sum of all matchsticks has to be a multiple of 4. you let the other player begin and whatever he takes, you take so many that it both takeaways sum up to 4. so the other one will always end up with 4 on the board so you take the last one. if you waanna change the winning condition either change starting player or change number of starting sticks to sth else than a multipleo of 4. i think its pretty much the same principle.
    anyway very interesting binary variation here!

  34. It's interesting to notice that in Martin Gardner's "Entertaining Mathematical Puzzles", published in 1986, another version of Nim was given in page 37 that you could read here:

    That version of Nim, according to Martin Gardner, had been analysed in 1901 by professor Charles Leonard Bouton who gave it this name even though the game is believed to be Chinese in origin.

    And that version of Nim is different that the winning strategy is a lot simpler to remember and to use in real life situation.

  35. When I was taught how to win this game I was told the strategy is "pairs and runs". So maybe achieving runs is also advantagous?

  36. Hi there is a little mistake in the explanation. as long as the clueless guy is clueless it is just randomly determined if the state he produces is balanced or not

  37. It's awesome to see how far along Mathologer has come as a presenter of his content. This seemed very paused, slightly confusing at times and it didn't flow as well. Compare to his current videos where now he explains everything perfectly and is much more fluid in his presentation. I think it's great to see this channel grow and become so wonderful!

  38. Hello, everyone!
    Good day!

    Playing Nim was fun, right? And going up against other teams can even be more fun. So, here are your tasks:

    1. Watch the following video on YouTube

    2. Comment "seen" once you (individual) are done. (Comment below this announcement.)

    3. Incorporate the technique with your own. (The one that you came up with last meeting.)

    4. Choose one player to represent your team.

    5. Who will you go up against will be chosen in random and only winners can proceed to the next round. A perfect score will be given to the winning team after the said activity.

    6. We will have the competition on Monday.

    Reminders: A player can bring a pen and paper during the game.

    NIM, or, always WIN with math

  39. Does this math apply to game variations? A friend of mine assembles the game as follows (total of 28 cards):








  40. I was tought about this game by my ancle Rene who was a Belgium captain of merchant marine, yo can play it with toothpics.. lines on a paper or even sand in the beach . when I was 18 I soon figured out myself that the way to win is much more simple than what you explain, by learning a few patterns you leave to the oponent you always win VERY Fast without thinking.. This pattern to leave are off course the simplest: / / / ( in vertical rows) / // ///…. // //… / // / //…… 1 111 1 111… may be 1 1111 1 1111 with this simple patters to LEAVE to you oponent you always win as long as he she do not know the game…. may be if they know the game yo must figure out some more complicated patters have fun!!!

  41. One time i forgot how this worked while playing this with my mom and brother. I didn't know you have to go unbalanced at one of the last turns so I lost every time 😂

  42. I made an app based on this concept. You play against a toy made of simple switches and levers. Check it out.

Leave a Reply

Your email address will not be published. Required fields are marked *