Nim Part 3

Mathematicians love to generalize ideas. In the previous posts (part 1 and 2) we considered the game of Nim with only 10 stones. What would happen if we had a different amount of stones to start?

What if we changed the setup and there were 9 stones in the pile? Alice would want to remove enough stones so that she could land on a 3, 6, or 9. However, this is impossible. Suddenly it seems as if the tables are turned. Whatever number of stones Alice removes, Bob will be able to counter it and land on the 6. Then after another round, Bob will land on the 3. Finally, Bob will win!

Clearly, Alice was doomed from the start. What is it about 9 that was so different from 10? 9 is a multiple of 3, so it already is a bad pile. Alice is starting on a multiple of 3, and since she still has to play her turn and remove some stones, she must leave the multiple of 3. Bob is then able to expertly land on the 6. Bob then navigates to the 3 and finally to the 0 for a win.

nim2

If we changed the number of stones to 11, it would be clear that Alice would win again (by removing 2 stones and leaving Bob with 9). Thus, if there are 9 stones Alice will lose (always assuming that Alice goes first), 10 stones Alice wins, 11 stones Alice wins.

The explanation is that Alice wants to finish her turn and leave a pile of stones that is a multiple of 3. In the case where the pile has 10 or 11 stones Alice can take 1 or 2 stones, respectively, and leave a pile of 9 stones. In the case where the pile has 9 stones there is no way for her to take enough stones to get to 6 and Bob will win.

What if there were 30 stones? Is 30 a multiple of 3? Yes. Alice will lose.

What if there were 406 stones? Is 406 a multiple of 3? No. Alice will win.

There could be any number of stones in the pile. All we have to do is ask the question, is it a multiple of 3? If it is, Alice will lose. If it is not, Alice will win. In modular arithmetic it would look like this (where n is the number of stones in the pile):

If n ≡ 0 (mod 3)                 then Alice will lose

If n ≢ 0 (mod 3)                then Alice will win

Modular arithmetic handy.

Leave a comment

Filed under Uncategorized

Nim Part 2

In the previous post, we discussed the game of Nim. Before we investigate the Mathematics of the game further, we need to introduce an important concept called modular arithmetic. According to Wikipedia, “In Mathematics, modular arithmetic (sometimes called clock arithmetic) is a system of arithmetic for integers, where numbers ‘wrap around’ after they reach a certain value—the modulus.”[1]

Analog clocks use this type of math all the time. If it is 10am and 4 hours pass, what time is it? After some quick mental math, the answer is 2 pm.

clock

Wait a minute, isn’t 10 + 4 = 14?

The key to understanding the enigma is that a clock only has 12 numbers on it. After the little hand passes the 12, it “wraps around” and starts at 0 again. Therefore, we say that a clock has a modulus of 12 or we can say it has “mod 12.”

10 + 4 = 10 + 2 + 2 = 12 + 2

and we know that on a clock the 12 and the 0 are the same thing. So replacing the 12 with a zero, we get

12 + 2 = 0 + 2 = 2

It is like magic the first time you see it, 14 ≡ 2 (mod 12). The triple equals sign signifies that 14 and 2 share some commonality but are not the same number. The “mod 12″ signifies that we are working with a system that has 12 steps before wrapping around (12 numbers on a clock).

This same math is all around us. When we go from week to week, we add 7 days but do not change the day of the week. When we go month to month, we reuse the days of the month. Using real world examples can be helpful to get an intuitive grasp of the underlying math but it is not very useful for actual calculations. For example, what number would the little hand on the clock read after 2043 hours? If you were to spin the little hand around and around you would be here forever. The mathematical solution is much more elegant.

Each time the little hand performs 1 revolution it goes through 12 numbers. Thus, 0 ≡ 12 (mod 12), 12 ≡ 24 (mod 12), 0 ≡ 240 (mod 12) and so on. This means that every multiple of 12 will leave the clock unaffected since it will return the hand back to where it started. Therefore, what we really are looking for is the remainder in the math problem of 2043 ÷ 12.

When we take our 2043 and divide by 12 (using our old friend, long division), we get 170 and remainder 3.

long division

Thus 2043 ≡ 3 (mod 12).

I hope the above is clear, if not it would be best to try your hand at a couple of examples. Convince yourself that with modulus 12,

25 ≡ 1 (mod 12), 38 ≡ 2 (mod 12), 100 ≡ 4 (mod 12).

If we mix it up a bit and use 3 as the modulus, then

3 ≡ 0 (mod 3), 10 ≡ 1 (mod 3), 14 ≡ 2 (mod 3), and 502 ≡ 1 (mod 3).

long division 2

Returning to the game of Nim with our new-found powers of modular arithmetic, we can be more precise about the game. We found that the bad piles were 3, 6, and 9. These are all multiples of 3. Using the language of modular arithmetic, we can see that:

3 ≡ 6 ≡ 9 (mod 3)

The piles with 3, 6, and 9 are all the same mod 3. Whenever 3 stones are removed from the game, poor Bob is back where he started, in a losing position.

1 Comment

Filed under Uncategorized

Nim Part 1

According to Wikipedia, “Nim is a mathematical game of strategy in which two players take turns removing objects from distinct heaps.”[1] We are going to simplify the game slightly and only have one heap of objects with players removing up to a maximum number per turn. The winner of Nim is the person who removes the last object from the pile. The two players are Alice and Bob. Alice always starts. So let us get started with a simple example. Say you have a pile of 10 stones and each player can remove up to 2 stones, what could a game look like? Here we go:

Alice removes 1 stone, 9 stones remaining.

Bob removes 2 stones, 7 stones remaining.

Alice removes 1 stone, 6 stones remaining.

Bob removes 1 stone, 5 stones remaining.

Alice removes 2 stone, 3 stones remaining.

Bob removes 2 stones, 1 stone remaining.

Alice removes 1 stone, 0 stones remaining. Alice wins!

Nim

There you have it: a simple game of Nim with Alice as the winner. However, a perceptive individual might wonder, “Is there a pattern to this game? Is there a winning strategy?”

Rewinding a bit, what if Alice were to take the 4th last stone, leaving 3 stones in the pile? Then Bob could either take 1 or 2 stones. Using a diagram, we can see what happens.

Capture1

From the above flow chart, it is clear that no matter what action Bob makes, Alice can counter it and come out victorious. Therefore, as long as Alice is able to leave a pile of 3 stones for Bob, Alice will always win. Facing down a pile of 3 stones is bad news for Bob.

Rewinding another step, what if Bob was facing a pile of 6 stones?

Capture2

Again we see that from 6 stones, no matter what move Bob makes, Alice will be able to counter him and leave him with a pile of 3 stones. Further, we already know that leaving Bob with 3 stones assures her a victory. Poor Bob loses when he is facing down a pile of 6 stones as well. The same logic can be applied if Bob is staring at a pile of 9 stones.

Since the original pile starts with 10 stones, if Alice takes 1 stone to start the game off, leaving a pile of 9 stones, she will win 100% of the time. What do 3, 6 and 9 all have in common? They are all multiples of 3!

So there you have it: if you can leave your opponent with a pile of stones that is a multiple of 3 then you will win. Another way of thinking about this is that 3, 6 and 9 all have remainder 0 when divided by 3. The strategy employed by Alice is to remove enough stones each round so that she leaves Bob on a multiple of 3. As seen in the flow charts above, if Bob removes 1 stone, Alice should remove 2 stones. Similarly, if Bob removes 2 stones, Alice should remove 1 stone. And her victory is certain.

2 Comments

Filed under Uncategorized

Fraction Multiplication

Addition is easy to explain. 3 + 5 = 8. You can see addition with a picture:

Capture1

However, I have been thinking about how to explain multiplication. For example, I know that 4 x 5 = 20. But how can I show that? One method is to think about repeated addition. 4 x 5 means that we take the number 4 and add it up 5 times.

4 + 4 + 4 + 4 + 4 = 20

Capture2

Now this extends very nicely when thinking about fractions. What is \frac{2}{3} \times 5 ?

We can use the method of repeated addition:

\frac{2}{3} + \frac{2}{3} + \frac{2}{3} + \frac{2}{3} + \frac{2}{3}

If you recall, when the bottom of the fraction (denominator) is the same, we can just add up all the tops (numerators).

\frac{2}{3} + \frac{2}{3} + \frac{2}{3} + \frac{2}{3} + \frac{2}{3} = \frac{10}{3}

Many of you could simply calculate:

\frac{2}{3} \times 5 = \frac{10}{3}

because you know that you can multiply the 2 and the 5. The above method shows why this trick is valid. See if you can figure out \frac{8}{3} \times 7 =

Leave a comment

Filed under Uncategorized

Minus Minus makes a Plus

“Minus minus makes a plus.” You have all heard a version of this at some point in your life. Your teacher was trying to explain integers to you and this phrase was supposed to help you understand. The phrase stems from this problem:

4 – (-3) =

This question is often difficult for students. If the question was simply 4 – 3, then the answer would be 1. However, the extra negative sign confounds many students. A quick teacher response is to rattle off the phrase minus minus makes a plus. Then the student can transform the problem and solve it with ease:

4 – (-3)

4 + 3 = 7

Yesterday, I was trying to teach this concept to my wife and she kept asking why. She understood how to do the questions but she wanted a deeper explanation as to why the two minuses made a plus. Unfortunately, even though I have thought long and hard about integers, I have been unable to explain why the trick works. That is, until yesterday.

After going back and forth with her for a while, I suddenly had an idea! I will illustrate it in picture form. 4 can be represented as 4 individual +1s.

Picture 1

How can we subtract -3 from the above picture? There are no -1s to take away. Here was my epiphany. We need to create an environment in which this subtraction can take place. Consider the new picture below:

picture 2

The picture still has the original 4 in the middle. However, there are now a bunch of +1 -1 pairs all around the 4. Since +1 – 1 = 0, these pairs do not change the answer and the picture still represents 4. Now the beauty of this approach.

We need to calculate 4 – (-3). That means we need to subtract -3. Hence, we need to subtract 3 -1s. Like so:

Picture 3

We have subtracted (or removed) 3 -1s. Count the total. The answer is clearly +7. This technique and be used with positive or negative numbers using addition or subtraction.

Here is another example:

-5 – (-7)

First the initial setup:

Picture 4

Then the subtraction:

Picture 5

The result is +2. I hope the above explanation gives you a deeper understanding of why subtracting a negative is equivalent to adding a positive. I know it did for me.

Leave a comment

Filed under Uncategorized

Percentage Activity

I was at teacher’s conference (WestCAST 2015) the other week and I heard an interesting idea for how to teach percentages. After tweaking the idea for a little while, I think I am ready to share it.

A percent is a part of a hundred. The word comes from the Latin adverbial phrase per centum meaning by the hundred.1 Suppose we have 100 people in a room. If 40 are men and 60 are women we say 40 percent are men and 60 percent are women. We often use the symbol “%” instead of the word “percent.”

Consider the following picture of Mario:

Mario

Let’s investigate different sections of Mario and determine the percentage of each colour. To do this, we will use a sheet of paper with a 10 by 10 hole cut in it. Thus, we will only ever see 100 squares at a time. Suppose I place the paper and this is what I see.

Mario covered

Let’s count the number of times each colour appears:

Tan: 7

Red: 15

Blue: 39

White: 39

First, we notice that 7 + 15 + 39 + 39 = 100 which is good because there are supposed to be 100 squares! Second, it is as easy as adding a percent symbol to turn these numbers into percentages.

Tan: 7%

Red: 15%

Blue: 39%

White: 39%

I really like this activity for a number of reasons. First, it clearly communicates that percentages are proportions of a hundred. Second, each student can place the 10 by 10 hole on a different part of Mario and get a different answer. Third, if the students are interested in the concept, they can design their own pictures in Excel to create percentage activities.

As a follow up activity, we could ask the question, what is the percentage of white squares in the entire picture of Mario? How can we calculate percent when we have more than 100 squares?

1 http://dictionary.reference.com/browse/percent

1 Comment

Filed under Uncategorized

Complex Roots Part 2

In the last post, we had poor Carlos trying to catch the bus. To understand the third situation we need a bit of knowledge of square roots. You see, when we take square roots, we usually only allow positive numbers. For example:

\sqrt{9} =3

But \sqrt{-9} is not usually defined. Now, if you had to try to define \sqrt{-9} , you would want it to be something like 3, since it looks kind of like it should be 3. However, you also want to differentiate it from the regular 3. So why not just add a symbol and call it:

i3

Before you declare this approach crazy, consider this. What is 10-3 ?

10-3 = 7 of course.

What if we reverse the order. What is 3-10 ?

-7 of course.

Normally in subtraction you have a bigger number and you take away a smaller number. When the situation changes we simply introduce a new symbol and invent a new word, “negative”.

I hope that justifies my methods. If not, just humour me for now.

Returning to Carlos, when I use the formula for the first situation I get the values 2 and 5. As you can see from the graph, these are points of when the blue line (Carlos) red line (the bus) intersect.

2014-11-04 10.59.25

When I use the formula for the second situation, I get the value 3.16. Again, this is the point where Carlos catches up with the bus (where the two lines intersect).

2014-11-04 11.04.22

When I use the formula for the third situation I get an interesting answer. I get:

2.5 + i1.9

What does this solution mean? It can’t mean that Carlos catches the bus, because the lines do not intersect. However, Carlos does get close to the bus. The proper interpretation is as follows.

The first number, 2.5, means that after 2.5 seconds Carlos will be as close as possible to the bus. Before 2.5 seconds, he was gaining on the bus and after 2.5 seconds the bus gets further and further away. The second number, 1.9, means that at 2.5 seconds, Carlos is 1.9 meters away from the bus. This is the closest that Carlos will get to the bus. If Carlos had a friend on the bus with a really long pole, maybe he could grab on to the bus. But otherwise, he will miss it.

2014-11-04 11.06.01

Even though Carlos does not make his bus, the math can still tell us interesting information about the situation. This is preferable to the usual “no solution” we are taught in school.

What I have used are the numbers more formally know as the complex numbers. While some people might say they are imaginary numbers, I say, that real or not, they are incredibly useful.

Leave a comment

Filed under Uncategorized