Stuffing Sacks

I came across an interesting problem posted by a fellow teacher. Think about all those plastic bags you get from the grocery store. Say you shove them into in a single bag, and throw that bag under the sink. How many different ways can you store those bags?

For 1 bag, there is only 1 way.
For 2 bags, there is still only 1 way.
For 3 bags, there are 2 ways.

Here is a picture to illustrate:

stuffing sacks 1

How many ways for 4 bags? 5? How about 20 bags?

Give the problem a try for 4 bags. Once you think you have an answer, click here to confirm.

If you want, I encourage you to try to find the number of ways for 5 and 6 bags.

As I started to try to find all the combinations for 5 bags, I found that drawing the individual bags became cumbersome. I wanted a better method of diagramming. Ready and waiting was my trusty friend, graph theory.

I represented the bags as nodes and connected 2 nodes if one bag contained the other. Here is what the graph would look like for the 1, 2 and 3 bag cases:

Stuffing sacks 3

Here is the drawing for 4 bags, again showing that there are only 4 ways of stuffing the 4 sacks:

Stuffing sacks 4

Before we make the jump to 5 bags, we need to explore the graph theory representation a bit more. Consider these 2 different drawings, do they represent the same situation?

Stuffing sacks 5

On one hand, the drawings are clearly different. One has a branch going to the right and one has a branch going to the left. On the other hand, if we draw out the stuffing situation that they represent, the two situations seem identical:

Stuffing sacks 5

Indeed, the reason these 2 stuffing arrangements are the same, is because it doesn’t matter what order the 2 smallest bags are in. The only thing that matters is which bag they are contained in.

To visualize this with our graph, we are going to add a rule. You can transform the graph by dragging around the nodes, as long as you do not disconnect the lines. As you can see, I can easily transform the left graph into the right graph; showing they represent the same situation.

output_lBakYF

Using this rule, and trial and error, I was able to produce all 9 different arrangements for 5 bags:

Stuffing sacks 7

I challenge you to try to find all of the combinations for 6 bags. Hint: the answer is larger than 14 and less than 25.

 

 

Leave a comment

Filed under Uncategorized

Flip and Multiply

What is \frac{2}{3} \div \frac{7}{5} ?

Some of you may remember the simple rule for dealing with fraction division. If you encounter a question about the division of fractions, simply flip the second fraction and change the division to multiplication. Flip and multiply.

\frac{2}{3}\div\frac{7}{5}=\frac{2}{3}\times\frac{5}{7}=\frac{10}{21}

Why does this work? To justify this technique, we need to remember a crucial rule in math. If we see a division, we can change the question into a fraction, or vise-versa. For example:

4\div3=\frac{4}{3} and \frac{11}{5}=11\div 5

Here is the argument:

\frac{2}{3}\div\frac{7}{5}=\cfrac{\frac{2}{3}}{\frac{7}{5}}    because division can be converted to a fraction

\cfrac{\frac{2}{3}}{\frac{7}{5}}=\cfrac{\frac{2}{3}\times\frac{5}{7}}{\frac{7}{5}\times\frac{5}{7}}    because we can multiply the numerator and the denominator of a fraction by the same quantity

\cfrac{\frac{2}{3}\times\frac{5}{7}}{\frac{7}{5}\times\frac{5}{7}}=\cfrac{\frac{2}{3}\times\frac{5}{7}}{\frac{35}{35}}    by multiplying out the denominator

\cfrac{\frac{2}{3}\times\frac{5}{7}}{\frac{35}{35}}=\cfrac{\frac{2}{3}\times\frac{5}{7}}{1}     by simplifying the denominator

\cfrac{\frac{2}{3}\times\frac{5}{7}}{1}=\frac{2}{3}\times\frac{5}{7}\div 1    because a fraction can be converted to division

\frac{2}{3}\times\frac{5}{7}\div 1=\frac{2}{3}\times\frac{5}{7}    because anything divided by 1 remains the same]

Thus \frac{2}{3}\div\frac{7}{5}=\frac{2}{3}\times\frac{5}{7}

The above technique works with any fraction division question. Hence, the flip and multiply shortcut will work for any fraction division question. QED

Leave a comment

Filed under Uncategorized

Nim Part 6

Just when I thought Nim was done, I remembered that I had only generalized to 3 players! What about 4 or 5 or more players? The details of my analysis get very technical. Therefore, instead of boring you with a wall of text about the intricacies of programming an algorithm to optimize a strategy for playing Nim with p players, I will opt instead to show you some interesting pictures.

Below is the strategy graph for 4 players. Once there are 10 stones (yellow), the pattern becomes evident and contains 6 nodes. The yellow, pink, green, light purple, teal, and lavender groups all have 6 nodes in them. Further, each group has the same structure.

nim4

Below is the strategy graph for 5 players. Here the pattern starts at 13 stones and contains 8 nodes. The yellow, lavender, teal, and light green groups all have 8 nodes in them.

nim5

Finally, here is the graph for 6 players. The pattern does not start until 23 stones and contains 9 nodes. Again, we ignore the purple, red, and green nodes. Starting with the deep blue nodes, and continuing with the pink and brown nodes, we can see a similar pattern with 9 nodes in each.

nim6

The strategies for more players follow very similar graphs. One important characteristic of each picture is the number of nodes in the repetition (9 in the picture above). Below is a table of these results for many more players:

Number of Players Number of nodes in repetition
2 3
3 5
4 6
5 8
6 9
7 11
8 12
9 14
10 15
11 16

The number of nodes is increases by 1 or 2 each time. This pattern is easy to generalize:

n = \lfloor \frac{3p}{2} \rfloor

Where p is the number of players, n is the number of nodes, and the fancy brackets (called the floor function) tell you to round down if you get a decimal. Thus, if there were 45 people playing Nim, the pattern would repeat every:

\lfloor \frac{3 \times 45}{2} \rfloor = \lfloor 67.5 \rfloor = 67 nodes

So where does this leave us? After mining the depths of Nim we have found that the simple sequence:

3, 5, 6, 8, 9, 11, 12, 14, 15, 16, …

created by adding 1, then adding 2, is intimately related to determining the optimal strategy for any number of players in the game of Nim. This connectedness between ideas lies at the heart of mathematics. The connections between these ideas are beautiful.

Leave a comment

Filed under Uncategorized

Nim Part 5

Recently I was chatting with a friend about how I had generalized the game of Nim. I was very proud of the fact that I had solved the game no matter how large the pile was and no matter how many stones each player could remove. I thought I had generalized all I could. Then he asked me “what if you had more players?”

The thought had never occurred to me, but instantly I knew it would be interesting. Here is why:

Suppose you 3 players, Alice, Bob, and Charlie. Each player can remove 1 or 2 stones. Now consider what happens when Alice is facing a pile of 4 stones:

Capture4

As you can see, no matter what happens, Alice cannot win. However, the choice that Alice makes will determine whether Bob or Charlie wins. The above diagram proves that no matter how you change around the game, once you have more than 2 players, there is no guaranteed winning strategy. There might be a strategy that increases your chance of winning, but you cannot find a foolproof plan, like we could with 2 players.

As I began to explore the game with 3 players, I realized that I needed to add in some additional rules. My analysis would not make sense if one player just decided to be silly and only took 1 stone every turn. Further, if one player intentionally lost every game, it would make analysis impossible. I decided that none of the players would work together. Any partnership would be useless in the end because only one player can take the last stone. In a future post I may consider what would happen if the players collaborated on a slightly different version of Nim.

Here is what I found in picture form:

nim3

 

The picture is a diagram of the optimal strategy when playing with 3 people. The number represents the number of stones you are currently facing. The arrows indicate which move you should make. For example, if you are facing a pile of 35, you should take 2 stones and leave your opponent with 33 stones. Some numbers have an option. For example, if you are facing 6 stones, you can remove either 1 or 2 stones. Either choice gives you the same chance of winning.

The colours represent the pattern I found. Every time you reduce the pile by 5 stones the recommend strategy repeats. You can see how both 33 and 28 can remove 1 or 2 stones. Hence, if you were facing 528 stones, you should remove either 1 or 2 stones. I found this very beautiful.

Here are some interesting things to note.

  • If you are facing 5 stones you should remove 1 stone and leave the next person with 4. This makes sense because now they (like Alice above) are guaranteed to lose
  • If you have 7 stones you should remove 2 stones. However, there is no move that leads to 7 stones. Thus, unless the game starts with 7 stones, no player will ever face a pile with 7 stones
  • The pattern is initially chaotic and does not begin to repeat consistently until the red section with 13 stones

While the above picture details what move each player should make, it does not describe his or her chances of winning. Below is a table that gives the percent chance of winning, depending on the size of the pile:

Capture5

As you can see, the chance of winning repeats every 5 stones, just like the strategy repeats every 5 moves.

In conclusion, Nim gets complicated and beautiful with 3 players.

Math notes

For those of you curious as to how I created the above graphic, here is a rundown of my method. First, I assumed that each player was completely rational and would make the best decision possible. I defined the best decision as the move that would maximize the number of paths to victory. Second, if either move had an equal percentage of paths that would lead to victory, either move could be chosen.

The algorithm started with the base graph 3 → 2. It then considered the case with 4 stones and determined that the moves 4 → 3 and 4 → 2 were valid moves. The algorithm continued to build up the graph, adding the next number of possible stones at each step.

I realized that by the time I had 48 stones, there were already 26,244 possible paths. A quick graph revealed that the number of possible paths increased exponentially.

Capture6

If we wanted to determine the optimal strategy for 1,000 stones, we would need to search:

y = 0.5851 e^{0.2158 \times 1000} = 0.5851 e^{215.8} = 3.0 \times 10^{93} paths

This is more than the atoms in the known universe! Thankfully, I noticed a pattern in the strategy and so I could determine the chance of winning and the recommended strategy without brute forcing the solution on my computer and waiting for eternity.

1 Comment

Filed under Uncategorized

Nim Part 4

In the previous post, we generalized the problem to any number of stones. How else could we generalize the problem? One option is to change the rules and take more stones! What would happen if you could remove 1, 2, or 3 stones? Suppose the pile only has 4 stones in it.

Capture3

Bob has his revenge! Alice (who goes first) is facing a pile of 4 stones and has no hope. She loses no matter what he does. This new game appears to centre on multiples of 4. If you are facing a multiple of 4 (4, 8, 12, 16) then you have no hope. On the other hand, if you are facing another number (3, 7, 13) you can take the correct amount of stones to leave your opponent with a multiple of 4 and secure your victory!

The reason that multiples of 4 are important is because 4 is one more than 3 (the maximum number of stones you can take). What if we changed the rules again and you could take 1, 2, 3, 4, 5, or 6 stones?

You would find that multiples of 7 are the key to victory.

In general, say you have a pile of “n” stones and you can remove at most “k” stones, what numbers will be the winning numbers and which player will win? We know that the multiples of “k + 1” will be important. In words, we would say that:

If n is a multiple of k+1                   then Alice will lose

If n is not a multiple of k+1           then Alice will win

In modular arithmetic, it would look like this:

If n ≡ 0 (mod k + 1)          then Alice will lose

If n ≢ 0 (mod k + 1)         then Alice will win and the strategy will be to remove “m” number of stones such that nm ≡ 0 (mod k + 1)

For example, what if you had 49 (n) stones and you could remove up to 9 (k) stones? Since 49 is not a multiple of 10 (k + 1), Alice will win! She should remove 9 stones to leave Bob facing 40 (a bad pile because it is a multiple of 10). Then she should remove however many stones she needs to keep him on a multiple of 10.

In conclusion, if you are in Alice’s position (Player 1) you need to calculate the multiples. If you are starting on a multiple, you will lose. If you are starting on any other number, you will win. So, next time your friends ask you to play a game of Nim, do a little modular arithmetic in your head first to see if it is really in your best interests to play.

1 Comment

Filed under Uncategorized

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.

1 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