Polynomial Area

I was doodling the other day when a thought occurred to me: “what is the area of a polynomial?” In particular, consider the following two graphs:

poly1  poly3

In the first graph, the blue line is straight. Algebraically, this is a first degree polynomial.

In the second graph, the blue line is curved. Algebraically, this is a parabola; a second degree polynomial.

The area of the first shape is common knowledge:

\frac{1}{2} * base * height = \frac{1}{2} * 1 * 1 = \frac{1}{2}

The area of the second shape can be calucated using calculus and is:

\frac{2}{3} * base * height = \frac{2}{3} * 1 * 1 = \frac{2}{3}

What if we considered a more complicated polynomial? A third degree polynomial looks like this:

poly3

The new curve bends even more and takes up more area. Using calculus, we find that the area is  \frac{3}{4}

Below are the graphs of 10th, 20th, and 100th degree polynomials:

poly4

poly5

poly6

The larger and larger degree polynomials start to look like a square! This means, that we would expect the area to get closer and closer to 1. This is exactly what I found. The area of a polynomial with degree 100 is 0.99. In general, the area of a polynomial with degree n is:

\frac{n}{n+1}

Taking the limit, we find that:

\lim_{x \to \infty} \frac{n}{n+1} = 1

I found it very interesting that a large degree polynomial becomes so similar to a square. Click the link to view an animation displaying this fact https://www.desmos.com/calculator/afd21wuv0a

Leave a comment

Filed under Uncategorized

Divisibility Problem

Is 59136 divisible by 2?

Of course it is. And you know this because the last digit is a 6.

Is 558162 divisible by 11? Not so easy. If you your schooling was like mine, you never learned a quick trick to check for divisibility for 11. Check this out:

558162

5+8+6 = 19

5+1+2 = 7

197 = 11

Since 11 is divisible by 11, 558162 is divisible by 11. Go ahead, check your calculator!

Here is a challenge problem using the new for 11. What digit could you insert in the number 43160523 to make it divisible by 11? And where would you insert it?

First, we should ensure that the number is not already divisible by 11.

43160523

4+1+0+2 = 7

3+6+5+3 = 17

717 = -10

-10 is not divisible by 11. The nearest multiples of 11 are -11 and 0. We need to insert a digit somewhere to modify the number to get a total of -11 or 0. To get to -11, we could increase the sum of 17 to 18. One way to do this would be to insert a 1 at the beginning of the number. Hence, 143160523 would be our new number. You can verify that it is divisible by 11. If you came up with a different solution, please post it in the comments!

Leave a comment

Filed under Uncategorized

Brothers Meets Physics

I was playing a game called “Brothers” when I noticed a sweet physics problem. Check out the video below:

My question was: is it possible for the little brother to hold on while his big brother makes those crazy swings? Here is what I found.

First, we should make some assumptions about the lengths involved. It looks to me like the rope is about 3 times as long as the big brother. Assuming the big brother is 5 feet tall (they are young boys), this gives us a rope length of 4.5m (see below).

physics problem 2

To determine the force exerted on the little brother, we have the following factors. First, we have the weight of the big brother. Second, we have the centripetal motion of the big brother. As a formula, it would look like this:

F = F_{g} + F_{c}

F = mg + \frac{mv^{2}}{r}

We know the radius of motion is the length of the rope. We won’t specify the mass of the big brother right now. Hence, we need to determine the velocity of the big brother. To do this, we can use energy considerations.

When the big brother is grabbing onto the wall, all of his energy is gravitational potential energy. When he is at the bottom of his swing, all of his energy is kinetic energy.

E_{g} = E_{k}

mgh = \frac{1}{2} mv^{2}

Rearranging the fomula above for v2 gives:

v^{2} = 2gh

Substituting this info our equation for force, we have:

F = mg + \frac{m2gh}{r}

However, h (the height of the drop) and r (the radius of the swing) are the same. Therefore, our formula reduces to:

F = mg + 2mg

F = 3mg

Since we solved the above algebraically, we can be certain that no matter the length of the rope, the force on the little brother will be 3 times the weight of the big brother. Could the little brother hold 3 copies of his big brother dangling from a rope? I don’t know. It seems plausible. Regardless, the physics is quite interesting.

Leave a comment

Filed under Uncategorized

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