The game of NIM is won by the player who takes the last counter, and the winning strategy is based on the NIM sum (bitwise XOR) of all pile sizes: if the NIM sum is non-zero, the current player can always make a move to change it to zero, guaranteeing a win; if the NIM sum is zero, any move will result in a non-zero NIM sum, giving the opponent the winning strategy. To find the winning move, calculate the NIM sum, identify the highest power of 2 in that sum, find a pile containing that power of 2, and adjust that pile so its new size equals the NIM sum of the original pile size XOR the total NIM sum.
Winning Strategy in the Game of NIM: NIM Sum Lemma & Theorems
Added:welcome in a previous video we've discussed the game of NIMH where there is a pile of for a pile of three and pile of two now you can also play the game own em in a more general way you can have any amount of piles or rows that you like and you can put however many counters in those piles of rows that you want and in general the rules of the game are similar the player that takes the last counter wins the game and they alternate removing counters provided that they're all in the same row okay so let's give a formal definition for the game of NIM in general so in general if you want to talk about a game of NIM you can just list a bunch of numbers and one number for each row just like this example from above if you have different numbers it represents different amounts in each row so if you calculate the NIM sum of these numbers so if we talk about the NIM sum of four and three and three and two and we calculate what that is well we're gonna give a formal name to that we're going to call that the NIM some of the game so the four three to itself represents a position in the game where the four three two when in sum together gives you the NIM some of the game and that's exactly what we put in the definition below so the NIM some of the game is the name some of those numbers now there's a couple of lemmas that are going to be really helpful for figuring out a winning strategy to the game of NIM we're not going to go through the proofs of these lemmas if you'd like to on your own you can read closely what those proofs are the real important thing that we're going to highlight in this video is what the lemma is say so the first lemma that we're going to dig into here says that every move in the game of NIM will change the NIM son so whatever number this is if you make a valid move in the game if it's like seven to begin with and you make some valid move then it has to change it'll be something other than what it was before so let's put that into practice let's collect these definitions and try this lemma out so in the next example we're considering a game of NIM and it first asks us to use the definition above to represent the state or position if you like of this game of NIM and in terms of the starting position so this is just a list of numbers so we have a row of five a row of four and a row of three and we're going again keep with the standard of larger numbers on the left hand side just so we don't you'll have any confusion about repeating symmetric positions so then there's the NIM some of the game as we defined above so that is calculating 5m summed with 4m summed with three so five is four plus one name summed with four and NIM summed with two plus one so we look for any pairs to cancel though we see two ones and two fours there's just a two left over so that is the NIM some of our game okay so finally to finish this example off we're gonna make any move and notice that the NIM some of the game will change so right now the NIM some of the game is - we're gonna make a move and it's gonna change I'm gonna challenge you to do that on your own I want you to you'll play this game make a move whatever you want to this game board taking whatever you want from one particular row and then calculate the NIM some again and I can guarantee you ahead of time that you are not going to get to I don't know what you're gonna get but I do know that it won't be too so pause now and give that a try I'll do it on my own as well okay so I've decided to take four from the last row and the 4:31 position so there's now a row four in a row three in a row of one so I'll take the NIM some of this and see what we get so for min sums with three which changes to 2 plus one and one is already a power of 2 2 to the power 0 so we'll leave that as one we cross out anything that we see twice and we add up what's left and we get 6 and we notice indeed that number did change also notice that there's not really an association with with bigger or smaller when you're dim summing as there is with regular summing if you're just adding numbers you're having positive numbers things get bigger when you're nim summing different combinations together you know things could get bigger or smaller there's no real rule in that direction so it's kind of nice to let go of what's big and what's small when you're just looking at a expression with NIMS ohms okay so the next lemma that we want to discuss so we just discussed that when we make a move the NIM some changes this next lemma says that there's always a move that changes the NIM some with a nonzero sum to a zero sum so if you have something like two in your NIM sum you can change that to zero there is a move that does that for you if you have seven something other than zero you can change it to zero and so on so we're not going to go through the proof but if you are interested in the you know details below you can pause the video now and check that out we're going to work with the statement that the lemma gives us so in the example below let's try to think about that so in this game the NIM sum is not zero we actually calculated the NIM some of that came earlier on and found that it was too so our job is to take this game that we're looking at now which has an M sum of two and change that by making a valid move in the game to zero we want to change that to to a zero and the lemma that we just read told us that there should be a way to do this there should be a way to change any nonzero NIM sum to zero so we're going to try to find such a move now because these numbers are relatively small it's not too tricky to find this in other cases when these numbers get bigger and more complicated we're gonna go through a step by step process later on that will tell us how to deal with those situations for now we're just going to do a little bit of guessing and testing to see if we can figure it out so can you think of a move to make here that would create a new position in the game of NIM that would make the game have an in sum of zero see if you can do that pause now give it a try okay so maybe you notice that in this calculation if that two wasn't there we would cancel everything out and we'd end up getting a zero so if we take this two away that would correspond to the move that takes two from the very first row that's the move that we want to make so now we would calculate the NIM sum of five four and one and we would get four plus one NIM summed with four NIM summed with one and everything kindly cancels out for us and we get zero leftover so the old NIM sum was to and the new NIM some as desired is zero all right so now we get to put the two lemmas together and build a theorem if you've never heard the sequence of lemma and then theorem the idea is that lemmas are a more basic result or something that comes before a theorem and then the theorem is something that mathematicians are jumping up and down about we're all excited this is the the big result that we've been waiting for so here it comes the game of NIM is in a hot position if and only if the NIM sum is something other than zero so if the NIM sum is five it's a hot position if the NIM sum is 20 it's a hot position if the NIM sum is zero the statement says if and only if so if it's zero then it's not a hot position it's a cold position okay so how can we prove this statement this proof we will go through this is an important one so suppose that the game starts with a non zero NIM 'some what can the first player do well we just learned that the first player can always change the NIM sum to zero so the first player moves so the new NIM sum is zero that's their their job and that was described in lemma three saying that we'd always be allowed to do that and then the second player will have to move of course and they're gonna move when the game has an M sum of zero and let's remember back to a lemma two lemma two said the game has to change its NIM sum as you play it so player two is forced to move so that the NIM sum is no longer zero it was zero to begin with and now it's no longer zero then rinse and repeat the first player changes it back to zero the next player second player changes it away from zero and so on and so on so this process continues eventually the game will end right this is a finite game and there's only so many counters and eventually we run out of the counters that are on the table in front of us which player is going to move so that there's no counters left in front of you well eventually the first player will move so that there's no counters left and it's the first player this whole time that has moving so that the NIM sum is zero so it's the first player that is gonna be the one that makes sure that you know the game ends with no counters and the first player will win because the game is described as the player that picks up the last counter or last bunch of counters all at once wins the game so this doesn't mean that the first player always wins the style of games the second player of course can steal this strategy if the game starts with a dim sum of zero then it would be the first player that would be forced to move away from zero and the second player can take over the winning strategy so that's where the if and only if is coming from so how do we put this into practice let's go back to the very first game that we played and we analyzed it with a state diagram there's a 4 3 2 game and let's try to see how this theorem fits in with that state diagram ok so here's a state diagram of the four three two game what I'd like you to do is go through all the positions that are in this diagram and assign them their nim sum so right next to the position just write whatever the name sum is so this NIM sum here is 0 so go ahead and pause the video do that as an activity before the answer it comes up on the screen ok so all of our NIM sums are assigned and if we think back to the theorem that we're just talking about the game starts with a non zero NIM sum so that would make sense that this is a hot position there's a way to change it all to zero so our new NIM sum is zero that's a cold position every way of playing from there gives us hot positions and those are all nonzero NIM sums we changed those positions into zero and from there you must play into hot positions and then from there you must play into cult positions which are zero and then finally you must finish off at the cult position which is a 0 so it backs up what the theorem was saying in terms of these unum sums and also if you think back to this diagram to begin with I suppose this is just a partial state diagram there's many other ways of playing from here you know how could someone know that you know this move was a good move well if you know about the nihms I'm ahead of time you can make a diagram like this and make the correct first move so I knew ahead of time that you know that was a good first move to make and I didn't think about all of the other options okay so next we're gonna discuss how to come up with the correct move to make other than just a guess and test method ok so now we're gonna discuss something that comes after a theorem often call that a corollary it's kind of something that trickles out of a theorem another result that we get almost for free by just maybe looking at the proof or looking at the result so lemons become before theorems and choral theories come after theorems so there's a three step program here to dealing with how to find the correct move to make in a game of NIM so how do we change a nonzero NIM sum to zero so the first thing that you do is calculate the NIM some so this is some number we're going to call it s and every time you have a number you can break it into powers of two and then we know the largest power of two that appears in that list so we've maybe order at these powers of 2 where K is the biggest one and then the the T's that come after that are smaller let's do that step below ok so our first step is to find the NIM son so I want to know what number this s is to find the house I need to calculate that and to calculate that NIM sum that's sitting there we need to follow the rules and break this up into different powers of two eight and sixteen are already powers of two five changes into four plus 1 and then we cancel out anything to be cancelled this time there's nothing to cancel at this point there's no pairs often there is this this time there isn't that's ok so we add up what's left to get 29 so now that we've found this number s right here we're interested in what is it equal in terms of a bunch of different powers of 2 let's write that on the next line so this means that my number S which we found is equal to 29 which equals 16 plus 8 plus 4 plus 1 what we want to know is what is the highest power of 2 in the number 29 that's why we wrote out all these so that highest power that we're looking for is 16 so something to kind of watch out for here is in this calculation there wasn't any cancelling out but even if there was like if there was like a 32 Nym summed with a 32 in the calculation you know you still got 29 left over as the result of the NIMH Sun because the you know the the 32 s would cancel out you know the point of my display here is that 32 is not the largest power of 2 it may have occurred in the calculation to arrive at what that nim sum is but if you crossed out bigger powers of 2 then you know they're not the power of 2 that you notice here you take the number you write it out as a bunch of powers of 2 and then you find the largest one so the 2 to the K the K that we're interested in is 2 to the power 4 or 16 okay let's move on to step two so in step two it says find a row that two to the power K appears in so when we say find a row with a sub I and it equals a bunch of powers of two and one of them is the power of two that we found above each of these a sub i's are the rows so Row one is a sub one and there's you know five in that row so that number happens to be a sub two is referring to the second row and that number happens to be 8 and a sub 3 is referring to the last row and that number happens to be 16 so we get to look at all of these numbers 5 8 and 16 and think about where our highest power is appearing in those numbers it could appear in more than one number it could appear in you know all three of these numbers and then you have a choice from here on in this case for this example 16 is only in the number 16 appearing as a power of 2 so you have to pick 3 as your choice so find a row for our purposes for this example below it would be Row 3 I would equal 3 and a sub I would equal 16 so in step 2 we pick Row 3 so our final step is going to be to leave a certain number of counters in that row so in step 2 we decided okay now we're going to play the game by operating on Row 3 so Row 3 has 16 counters that's our a sub I and we're going to NIM sum that with the NIM some itself so we need to calculate this number so a sub because 16 and Wien in some that with the NIMH some we NIMH some it with s let's remember what has is we calculated s to be 29 so 16 NIM summed with 29 need to write out our powers of 2 16 as a power of 2 and then 29 is 16 plus 8 plus 4 plus 1 so our 16 cancels out and we're left with 8 plus 4 plus 1 so our number is 13 now let's remember this is how many you leave in the last row not how many you take it says leave 13 counters in Row three that's what we need to write down maybe we'll write it down in terms of the move that we make there's 16 to begin with we take 3 so once again in review because we found that the NIM son was nonzero right away we knew that the first player can always win and the move that they make is stated below so the first player can always win by taking 3 from Row 3 let's do one more example okay so in this example we've got a bunch of rows and some counters once again the very first thing that we want to do is find the NIM some okay so we've written down the amounts in each row so now we'll calculate our NIM sum by breaking up into different powers of 2 so 2 & 3 because 2 plus 1 & 5 is 4 plus 1 copy 8 it's a power of 2 and then 13 would be 8 plus 4 plus 1 okay now we get to cancel out pairs so 2 ones cancel out two twos cancel out two 4s cancel out two ones cancel out and two eights cancel out so there's nothing left over we have a zero in this case we don't need to analyze a first move of the game the first move is kind of trivial the first player would just play and change the name to dim sum to something other than zero and the second player can always win okay so that summarizes how to always win the game of NIM and what correct move that you can make in a systematic way to change the game from hot to cold or in other words from non zero to zero in the next video we're gonna discuss a variation of NIM called classic NIM so in regular NIM you take the last counter to win the game there's going to be one switch up of the rules for classic NIM when you take the last counter in classic NIM you lose the game but the rest of the rules will be the same so maybe before you start watching the next video you might want to think about that variation thanks so much for listening we'll see you on the next one
Up Next

Sprague-Grundy Theorem and Winning Strategies in Impartial Games
@gkcs
21.7K views•2017-03-20

JEE Maths | Circles: Pole & Polar Explained with Equations
@TargetPublications
14.4K views•2019-02-23

Fourier Series Introduction: The Big Idea Explained
@DrTrefor
387K views•2021-05-03

The Mathematical Impossibility of Accurate World Maps
@Vox
23.3M views•2016-12-02
Related Study Plans & Knowledge Roadmaps
Structured learning paths in Mathematics











