Oh, hi. Good to see you back. Give me a second, I'll be right with you. Hey, so here we are. Let's cut the deck a few times. See what we have. One here once more. Okay. Here's your card. My card, your card. My card, your card. Ooh, what's that? Ooh, another king, you're doing good. My card, your card, and my card. Ooh, I got an ace. What else did I get? I got all aces. No chance. Okay, here we are in week 6. So what was the change of that? As advertised, week six is all about Nim, how to win it, all about impartial games, reversible moves, examples, minimal excluded function and the big theorem [unknown] but all impartial games are equivalent to Nim. So let's start off with nim and how to win. Okay. Star n is our game. It's a new heap of size n. If you go back and look at the introduction video. You know it's like 2 or 3 years ago. We look at the Nim heap of size one, two and three applied together, plus star one plus star two plus star three. First players loses so that's zero and we say that in terms of game theory, star one plus star two plus star three is zero. All is okay, let's look at a, one nim heap all by itself. This is not very interesting. So here I have a nim heap of f, four dice. Now whoever comes along just picks them up and they're all gone. So a nim heap all by itself is a loss. If there's to the first player, if there's nothing there, there's a win to the first player if there's something there. Okay? So that takes care of one nim heap all by itself. So it turns out that, the sum of a bunch of nim heaps is equivalent to another nim heap and d, the size of the heap that's computable, which is called the nim sum a, b, c, d, a, b, and c etc is, is computable from that and it's called the nim sum. And what we just proved or in the introduction video, we, we kind of used the fact that star one plus star two plus star three is zero star zero is the same as zero. And so what this says in terms of nim sums, is the nim sum of 1, 2 and 3 is 0. Another example which you can work out after we say how to compute nim sums is the star two plus star three plus star 7 and star 6. I hope that's right. But I'm not very good at arithmetic. There are 3 kinds of mathematicians in the world, those that can count and those that can't. All right. So let's compute this. So here's how to compute. Let's, let's look at an example. I want to compute the nim sum of 14, 11, and 2. So, how many kinds of mathematicians are there in the world? There are this many and that's two, because this is binary. Binary is just like base 10 except instead of 10 fingers You have just two factors one, two, three, four I can't do that 1, 2, 3, 4 et cetera., et cetera. So 1, 2, 3, 4, 5 et cetera, et cetera so you can like that that's binary You all can look it up. It's not something it's new. It's been around for a while. And some time, and ultimately inside computers, it's binary. So computer scientists know all about that. There are 2 kinds, there are 10 kinds of computer scientists. And this actually means there are just 2. All right. So, so 14 is 1, 1, 1, 0 in binary. Because 8 plus 4 plus 2, 8 plus 4, yeah it's 14, I did that right. 11 is 8 plus 2 plus 1 and 2 is just 2 all by itself. And here's how you can be at the nim's sum. You add these up, column wise, but. Just mod 2. So 0 plus 1 plus 0 is 1. 1 plus 1 plus 1 is 1 mod 2. 1 plus 0 plus 0 is 1 mod 2. And 1 plus 0, 1 plus 0 is 0 mod 2. So the nim sum of 14, 11, and 2 because 0, 1, 1, 1, which is 4 plus 2 plus 1 which is 7. Okay, here's how to win the nim game. If you have a heap size 14, hepa size 11, hepa size 2, you're Nim sum is not 0. So therefore, there's a winning move if you start. And let me show you how to do the winning move. You take the answer here, go and find the, the right most oh, that's not right most, that's left most. Find the left most 1, go up here and find 1 of the numbers. It has a 1 there and circle it. Now take what's to the right of that zero one over here, take this down here one, one, now do the same to here one plus zero is one and one plus one is zero again mod two. So we're going We, we take one because that's already there, take this one and make it a zero, make this a zero and make this a one. So that comes from the zero one over here. So that's 1, 0, 0, 1 which is what? That, seems to me that's 8 plus 1 that's 9. So take the 14 heap and remove how many, 5 coins. So it's now 9 heap, and that's your winning move. Okay. Here's something for you to try. Try with an n heap of size 11, and then heap of size 13, and then heap of size 10. If this is a win for the first player, find the winning move. If it's a loss for the first player, then give up. Or at least offer the other player. Say, why don't you go first? That, the end of the first module.
