Try this fun puzzle and learn about the Collatz conjecture.
Zara Zeld, a math Professor at the University of Sikinia, was trying to understand why it seemed like you could pick any positive integer, do some simple math and always end at the number 1. The simple math was this:
- If the number is odd, multiply it by 3 and add 1.
- If it’s even, divide it by 2.
- Now you have a new number. Apply the same rules to the new number.
Zara was curious if it always worked– if every starting number would always eventually go to 1. She asked another professor if there was a proof showing that this was always true for every starting number.
Her friend laughed and said, “Yes! There is a proof, Haven’t you heard of Terrance Tao?” Zara hadn’t, so her friend told her all about Professor Tao.
“Terence Tao is one of the most famous living mathematicians.” the friend explained. “He’s published over 300 research papers and is a professor at UCLA. Tao loved math from a very early age and started taking college math classes when he was nine. When he was fifteen, he published his first paper. He finished college and a master’s degree by sixteen.”
“Wow.” Zara was impressed, but she wanted to know more about her question: if any number she started with, applying these math rules, would always end with 1, or rather, if only some numbers would. Her friend explained more:
“One of the most interesting math problems Tao has worked on is known as the Collatz conjecture, which is this exact problem! Before Tao, people called this the ‘the simplest unsolved problem in mathematics’. It all started in the 1930’s in Germany,” her friend said, “when a mathematician named Lothar Collatz asked this same question! ‘Pick a number, any number. If it’s odd, multiply it by 3 and add 1. If it’s even, divide it by 2. Now you have a new number. Apply the same rules to the new number.’ And then Collatz asked, what happens if you keep repeating the process? Will you always get back to 1?”
Zara looked the Collatz conjecture up online to learn more. She found out that mathematicians have tested quintillions of examples without finding a single exception to Collatz’s prediction, but before Terrance Tao, no one had been able to show that it would be true for every number.
While Tao’s result is not a full proof of the conjecture, he was able to show that the Collatz conjecture is “almost” true for “almost” all numbers, and his work is a major advance on a problem that has mystified mathematicians for almost one hundred years.
Zara was so intrigued. She read Terrance Tao’s proof online, but had more questions for the famous Professor. She decided to send him a letter; she went to the local Island of Sikinia post office to buy stamps and send her correspondence off to Los Angeles. Once she arrived at the post office, Zara recalled that Sikinia’s postal system had been designed to help Sikinians improve their math skills. In fact, Zara would have to solve a math problem in order to get this letter to Terrance Tao! She looked at the sign over the clerk’s head:
Postage for an item can be anything from 1 to 15 Kulotniks, and exact postage is required. Sikinian envelopes only have space to attach a maximum of three stamps. We only have three different denominations of stamps, and every possible price of postage, from 1-Kulotnik all the way through 15-Kulotniks can be made using one, two, or three of these stamps. Please tell the clerk which three denominations we sell, and which postage stamps you would like to buy. Letters to the United States are 10-Kulotniks. (A Kulotnik is the basic unit of currency in Sikinia. If you are curious about Sikinia, it’s an island that IMACS has used in math enrichment lessons since the 1970’s! Learn more about Sikinia here, and more about IMACS’ history here.)
Zara could only send her letter if she could tell the clerk:
(a) What are the three denominations of stamps in Sikinia?
(b) As Zara’s letter requires 10-Kulotniks of postage, what must she buy to provide the correct postage? (Hint: there are 2 ways)
Try to solve it, then click to see the answer!
Answer (a): The denominations that are sold are the following: 1-Kulotnik stamp, 4-Kulotnik stamp, and 5-Kulotnik stamp.
Answer (b): She can use 1 of each stamp which equals 10, or two 5-Kulotnik stamps which is also 10.
Since we need to be able to create all numbers from 1 up to 15 using only three unique numbers, it’s clear that we need a 1-value stamp to make 1. With a 1-stamp, it’s easy to see we can make the numbers 1 through 3.
With the 1-stamp we couldn’t make the number 4, it’s clear we need an additional stamp in the range of 2 through 4 to make 4. We also need a third stamp in the range 5 to 15 in order to make 15.
Let’s consider each of the following possibilities where the question mark must be a stamp in the range of 2 through 4:
Stamps 1, ?, 15 – it’s impossible to make 14.
Stamps 1, ?, 14 – it’s impossible to make 13.
Stamps 1, ?, 13 – it’s impossible to make 11.
Stamps 1, ?, 12 – it’s impossible to make 11.
Stamps 1, ?, 11 – it’s impossible to make 10.
Stamps 1, ?, 10 – to make 15, a 4-stamp would be needed, but then it’s impossible to make 13.
Stamps 1, ?, 9 – to make 15, a 3-stamp would be needed, but then it’s impossible to make 14.
Stamps 1, ?, 8 – it’s impossible to make 15.
Stamps 1, ?, 7 – to make 13, a 3-stamp would be needed, but then it’s impossible to make 12.
Stamps 1, ?, 6 – to make 15, a 3-stamp would be needed, but then it’s impossible to make 14.
Now let’s consider the following two possibilities:
Stamps 1, 2, 5 – it’s impossible to make 14.
Stamps 1, 3, 5 – it’s impossible to make 14.
The only possibility left is to include a 4-value stamp. Using 1, 4, and 5 value stamps, we can create each of the possibilities from 1 through 15 as follows:
1 = 1
2 = 1 + 1
3 = 1 + 1 + 1
4 = 4
5 = 5
6 = 5 + 1
7 = 5 + 1 + 1
8 = 4 + 4
9 = 5 + 4
10 = 5 + 5
11 = 5 + 5 + 1
12 = 4 + 4 + 4
13 = 5 + 4 + 4
14 = 5 + 5 + 4
15 = 5 + 5 + 5