Fun with Collatz Conjecture

Collatz Formula

You may have heard of Collatz Conjecture, it’s simple enough to explain to a 2nd grader, yet has stumped mathematicians for the last 80 years. Paul Erdos famously referred to it when he said “Mathematics is not yet ready for such problems.” I like exposing students to unsolved problems in mathematics, because it gives them a real sense for what mathematicians do (also their’s no pressure to solve it).

I have explored it with a variety of ages, last year I had a fruitful experience with my 5th-6th grade class and thought others would enjoy the investigation. Below you will find two ways to introduce the conjecture, and a method for reversing the recursive formula to “grow the Collatz tree.” This investigation also hits a few of the Expressions and Equations standards, such as 6.EE.A.1-2, and 6.EE.B.5.

Collatz Conjecture:

1. Take any natural number n.

2. If its even divide by two, if its odd multiply by three and add one.

Repeat step 2 indefinitely. The conjecture states that you will always reach 1 eventually.

For example, say you start with 5 your sequence would go 5-16-8-4-2-1.

Introduction:

The Game Intro: One way I’ve introduced it in the past is to have the students play a game where they roll a 10 sided die for a starting number. Then the person who gets to one in the most number of steps wins. Students quickly realize they can create a diagram, or tree network, which tells them right away who will win. Sometimes we extend it, by playing the game with 20-sided die and trying to solve that version as well. Here’s what the tree network might look like for the game with a ten sided die.

Collatz Tree for a game with ten sided dice

Collatz Tree for a game with ten-sided dice

The Human Tree Intro: Another way to introduce it that is more kinesthetic, is to give each student a number on a sticky note, name tag, or index card. Then say if your number is even, look for the person that is half your number and if your number is odd find the person with one more than triple your number. Once they find their person they can connect with them by holding their hand or putting their hand on their shoulder. I usually make a stack starting with one, going up the “Collatz Tree” until I have enough numbers for the amount of students and teachers in the group. I also try to make it so there are several branchings. When everyone is “connected,” the group should work to untangle themselves so that the overall structure can be seen. I wish I had a picture of the process, and outcome, but alas I couldn’t find one.

Growing the Collatz Tree (doubling)

IMG_0002

Once students get familiar with the structure of the Collatz tree we talk a bit about what it would mean for the conjecture to be true. Can we prove that a certain set of numbers will always go to one. Quickly students discover that as soon as you hit a power of 2, you are dividing by two all the way down. I like calling this the “tower of powers.”

We use the powers of 2 as the “trunk” of our Collatz tree, and the first example of a way to grow the Collatz Tree. You can reverse the recursive formula and double any number to “grow a branch” of the tree. For example, 5 could have come from 10, which could have come from 20, which could have come from 40, etc.

Branching Rule (n-1)/3

Then I ask the students to notice when there are “branchings” in the tree, in other words when are there two numbers that will lead to the same number such as 5 and 32, both lead to 16. Here students have to think about when (x-1)/3 will have an integer solution. This happens when a number is one more than a multiple of three. So we reviewed the divisibility rule for 3, and tried it out on a few examples.

IMG_0004IMG_0006IMG_0009

Students worked in groups to apply these two methods to grow the Collatz tree. There are lots of opportunities to differentiate the process, as students noticed patterns in branchings and some wrote algebraic expressions to describe the branches. For example, the 3-6-12… branch above can be described as 3*2^n.

Here is an example of what one group made:

IMG_0002

Extensions and Connections

1. If you extend the recursive formula into the complex plane you get the fractal below. For a thorough explanation check out the blog post by Nathaniel Johnston.

collatz fractal

2. Dan Finkel over at mathforlove.com has a variation called “The Dr Squares Puzzle” where they come up with a similar recursive process, with a few loops.

3. Here’s another recursive process involving numbers and their written form (It also has a tree structure):

Step one: choose a natural number N

Step two: write the number in words, count the number of letters in the word and write that number.

Step 3: Repeat Step two.

For example: One-3-Three-5-Five-4-Four… stays at four indefinitely. You can also try other languages. 🙂

For English it has a tree like structure.

For English it has a tree like structure.

Finally, a post on Collatz Conjecture wouldn’t be complete without this from XKCD:

collatz_conjecture xkcd

Advertisements

5 Comments

Filed under 6.EE, Elementary, Graph Theory, Mathematical Investigations, Middle School, Unsolved Problem

Subtraction Reversal Game and Investigation

In this lesson, students start by playing a game with two digit subtraction. Patterns emerge, data is organized, and a “trick” (rule or algebraic equation) is discovered for quickly solving these special kinds of subtraction problems. I love this because it gives an experience of discovering a pattern and then describing it either with words or algebraically. I’ve mostly used this lesson with 2nd-4th graders, but it is highly differentiable. Finding a general solution involved quite a bit of elegant algebra.

Intro: Subtraction Reversal Game Instructions:

•Each player rolls a 10-sided die two times.
•Find the difference between the largest number you can make using both numbers and the smallest number you can make. For example: (3,5): 53-35= 18
•Whoever has the largest difference wins.
•Play several rounds, Recording your results on paper.
Organizing the Data:
Students form groups and share the results of their games. They will notice that certain numbers come up more than once. Some may even notice they are all multiples of 9, or that the digits add up to 9. Others may need to organize the data to see the patterns.
I ask the groups to come up with a way of combining all their data on one piece of paper. You will notice that certain ways of organizing the data better displays the patterns, this can be a point of discussion when groups share their way of organizing the data.
Below is an example of what a groups partially filled out table might look like:

Answer Number Pairs
0 (3,3), (4,4)
9 (4,5), (7,8)
18 (7,9), (2,4)
27
36
45
54 (9,3)
63
72
81
•What patterns do you notice?
•What other numbers would you like to try?
•Is there a way to be more systematic about which numbers you try?
Discovering and Describing “The Trick” 

Students work to describe the pattern either in words or using algebraic expressions.

• Is there a rule you could write to describe the patterns you noticed?
• What’s the trick/rule for finding the difference quickly?
Research Poster Project
After students have enough time exploring the patterns, I have students create posters individually or in partners to share their discoveries. Below are a few examples of posters students have made.
Screen Shot 2015-11-01 at 5.02.06 PM Screen Shot 2015-11-01 at 5.01.51 PM
Differentiation
Some students may only be ready to describe “a trick” using words. Others may be ready to write an algebraic expression to describe the trick. A deeper level would be to try to explain using place value, and/or algebra to explain why this trick always works for 2 digit subtraction when the numbers are reversed.
When students quickly come up with a rule for 2 digits, I let them work on the 3 digit version. For example 632-236. They often immediately make the conjecture that the answers will be multiples of 99, and that for 4 digits it will be 999. The 4-digit version gets a bit harder to predict because the middle two numbers interact, representing the place values algebraically helps with this.

Leave a comment

Filed under Elementary, Mathematical Investigations

Brewster’s Millions Beta

I’m going to try this today, as a sequel to A Billion Nickels. I’m considering it in Beta, and hoping my awesome students can help concretize and enrich the task.

Act 1: $30 million in 30 Days

Possible Questions:

How much does he need to spend per day?

How do you spend money without building Assets?

Does he do it?

Can it be done?

What would 30 million 1985 dollars be be adjusted for inflation?

Act 2: Take the Wimp Clause, or go for the $300 Million?

Students work in groups to figure out how they could spend $30 million in 30 days without accumulating assets. Using the internet and recording their plan on google spreadsheet.

Act 3: What does he do, does he win the $300 million?

“He Mailed It!”

Sequel:

Changemaker Twist

Since our school aims to educate “change makers”, I wanted to put a twist on this plot line and ask students to think about how they could use $30 million to help people.

1 Comment

Filed under 3-Act, Middle School

Multiplication Tic Tac Toe

Analytic presentation of all possible Tic-Tac-Toe games

I adapted this tic-tac-toe game from one I saw in a workshop claiming to be a multiplication tic-tac-toe game. It was similar to this multiplication tic-tac-toe game. It was fun enough, but it had no resemblance to a tic-tac-toe board.

I think my version has what it takes to be considered a “tiny math game.” All you really need to play this is paper, pencil, and two tokens (which could be two pieces of paper).

Embedded in the game is practice with multiplication facts, common multiples, and some good old fashion tic-tac-toe strategy, with a twist.

Instructions:

-Make a big Tic-Tac-Toe board, then make a tic-tac-toe board in each of the 9 squares.

-Now fill in the 9 squares with the multiples of 1-9 (see example below).

-Write the numbers 1-9 underneath your board.

-First player places two tokens (pennies in this case) each on one of the 9 numbers at the bottom. Multiplies these together, and places an “X” anywhere that multiple is found on the tic-tac-toe board. (in the example below player one has chosen 6 and 4, and has placed an X on all four “24s”)

-After the first move, players take turns choosing to move only one of the pennies to select their multiple to “X” or “O.” (For example 2nd player could move the “6” to a “3” and put an “O” over every 12 on the board)

-If you win a small tic-tac-toe game, you win that square on the larger board. The goal is to get Tic-Tac-Toe on the large board, by getting three of these smaller boards in a row.

-Also, I like to say any “Cat’s game” is a wildcard spot once it is completely filled in. This allows for player one and two to win simultaneously, which I like because I’m a sucker for win-win situations. 🙂

Notes For the Classroom:

I usually start by handing out this blank Multiplication Tic-Tac-Toe board. Students then take a few minutes to fill out the multiples of one in the top left corner, then multiples of 2 in the top middle, multiples of 3 in top right corner, etc (See example above).

First player places two tokens (pennies in this case) each on one of the 9 numbers. They multiply those two numbers together, and put an “X” anywhere that multiple is found on the tic-tac-toe board. In the example above, the first player has chosen to place the two tokens on 6 and 4, allowing her to place an “X” on the four places where “24.” I call these “quadruple plays,” and tell students to try to get as many of those as possible. Sometimes I have them color code the quadruple plays, and triple plays (like 36 or 9) so they are aware of them. This introduces and/or reenforces the concept of common multiples and factors. Check out my follow up post for more information on this.

1 Comment

Filed under Elementary, Games

100 Game Theory

This is a great game to introduce game theory at a young age while simultaneously assessing place value and addition concepts.

Race to 100

How to Play:

Two players start from 0 and alternatively add a number from 1 to 10 to the sum. The player who reaches 100 wins.

I usually give students a hundreds chart to help keep track of where they are, as well as a “Race to 100” handout with tables to record what number each person said. Also once they discover that saying “89” guarantees they will be able to say 100, I have them star that number. I ask them to think if there are any other numbers that guarantee a win.

A 3rd grader shows the winning strategy visually on a hundreds chart. He put an X on the numbers he wants to say, and then shaded in the numbers his opponent "him" would be able to say.

A 3rd grader illustrates the winning strategy visually on a hundreds chart. He put an X on the numbers he wants to say, and then shaded in the numbers his opponent “him” would be able to say.

Extensions:

How would the strategy change if it were a race to 99?

How about if we change the numbers that you can add?

This is part of the family of games commonly known as Nim, NRICH has a thorough article and resources for these games called “Meet the Nim Family.”

Leave a comment

Filed under Elementary, Games

Number Bowling

This is a student favorite, simple to start, differentiated, with various levels of success. I’ve done this with grades 2 and up, but my 5th-6th graders have gotten the most out of it.

Most importantly students learn to be very clear in writing their expressions. This activity naturally leads to a discussion about order of operations and mathematical “grammar.” Also, in their pursuit of the strike, students often ask to be introduced to new operations.

Instructions: Begin by rolling a die three times and recording these numbers as your “1st bowl.” You may cross out (knock down) any number that you can write an equation for using those three numbers each only once. For example, if I rolled a 6, 6 and 5, I could knock down the number four by writing: 5=6-6+5, or knock down 1 by writing 1=(6÷6)^5. Notice I used all three numbers, but each only once.

The goal is to knock as many “pins” (numbers) as you can. Knocking all the pins down on your first bowl is called a “Strike.” If you can’t think of any other equations, you may bowl again and try for a “Spare.”

Notes on Implementation:

I’ve created this Number Bowling handout for students to keep track of their games. I’ve also experimented with keeping score, and I think three frames is a good length time for a game. This can get complicated though, since scoring bowling is foreign and not straightforward to many students.

This year, after a few games, I had students write down their “favorite” equations on a notecard. We used these equations during a “strategy session” where we came up with tricks to help knock down more pins. The “tricks” can all be described as using an operation to change a number, or two numbers, into another. For example, 3 can be changed into 6 by using factorial, (3!=6). Some more advanced tricks include using square root, and/or the floor and ceiling function (rounding up or down to nearest integer).

Extensions:

Last year students wondered whether a strike was possible for every combinations. We chose the brute force method of proof :). First students had to figure out how many unique outcomes were possible with 3 dice. For many I assisted them by having them look at this pdf. Obviously rolling 1,6,6 is the same as rolling 6,6,1.  Then whenever a student achieved a strike, we crossed that off the list.

Leave a comment

Filed under Games, Middle School

High Fives in Three Acts

This is my first attempt at publishing a “3-Act Math Lesson.” So it’s not quite polished yet, but it worked really well on the first day of school. Lots of different directions to take it at the end, including paths into rates and design thinking.

Prologue

Act One: High Fives All Around

Students share whatever questions they have about this clip with their neighbor.

Possible Questions

Why is he doing that?

How many people are in the circle?

How long is he doing that for?

How many high fives does he give?

Why would you have a world record for high fives?

(students are really surprised at first)

Act Two: How many high fives did he give?

Students work with their neighbor to come up with an estimate.

Take another look at the video, are there any clues?

Notice that in the clip there is a man keeping time, can you estimate how many times he makes it around the circle in a minute from these clues?

What do we need to know?

-Times around the circle

-Number of people in the circle

I make a table on the board with their estimates for revolutions, people in circle, and total high fives.

Act Three: Watch The Whole Clip

59 people in the circle

4 revolutions

How many high fives is that?

What is the average rate of high fives per second?

Is that more or less than you expected?

Sequel:

Do you think you could beat that record?

How could you better design the attempt to get more high fives?

What’s the upper limit for most high fives in 60 seconds?

Who would be able to high five more people Usain Bolt or LaShawn Merritt (400m World Champion)?

What if we each gave a high five to every student in the class, how many high fives would be given in total?

So many more directions you could go with this!

1 Comment

Filed under 3-Act, Middle School