This puzzle was in a homework assignment I gave to my students.
Puzzle. In the given configuration of matches, move two matches to form three squares.
I assume that the intended solution is the one below. Its appeal is that it has three squares of the same size and no dangling matches.
As usual, my students were inventive and suggested many alternative solutions.
The first picture shows a solution with three squares of different sizes: two small ones and one twice as big.
The next solution has two big squares and one smaller one.
The following picture shows three squares of different sizes.
Since the problem doesn’t forbid forming more than three squares, there are, of course, many solutions with more than three squares. The last picture has six squares.
The Wythoff array is an array of integers that can be defined through Wythoff’s game. For my purposes, I will skip over Wythoff’s game and define his array using Fibonacci numbers.
You probably heard about binary, ternary, decanary, and other bases. I am sure you know the decanary base: it is our standard decimal system. But, have you ever heard about the Fibonacci base?
Let me define it. Any positive integer can be represented uniquely as a sum of distinct Fibonacci numbers that are not neighbors. For example, 16 is 13 + 3. Now, we just write ones for Fibonacci numbers that we used and zeros for unused Fibonacci numbers, so that the digit corresponding to Fibonacci number 1 is last. (The digit corresponding to Fibonacci number 2 is second to last). Thus, 16 in the Fibonacci base is 100100. The result looks like binary, but it will never have two consecutive ones. Such a representation is called the Zeckendorf representation.
What happens if we add 0 at the end of a number in its Zeckendorf representation? This is like multiplying by 2 in binary. But, in the Fibonacci base, it corresponds to replacing every Fibonacci number in the sum with the next Fibonacci number. The result is called the Fibonacci successor. For example, the Fibonacci successor of 16 has the Zeckendorf representation 1001000 and is equal to 21 + 5 = 26.
Now back to the Wythoff array. The first row consists of the Fibonacci numbers in order. Their Zeckendorf representations look like powers of two in binary. The first column consists of numbers ending in 1 in the Zeckendorf representation, in increasing order. In other words, the Zeckendorf representations of numbers in the first column resemble odd numbers in binary. To finish the definition of the array, each number in the nth column is the Fibonacci successor of a number to its left.
As an example, let’s calculate the first three numbers of the second row. The smallest number that is not a Fibonacci number and looks odd in its Zeckendorf representation is 4, represented as 101 (remember, we are not allowed to have two consecutive ones). We place 4 in the first column of the second row. The next number in the second row has to be the Fibonacci successor of 4, so its Zeckendorf representation has to be 1010. This number equals 5+2 = 7. The Fibonacci successor of 7 is 11, with Zeckendorf representation 10100.
John Conway and Alex Ryba wrote a paper where they studied the Wythoff array. They continued the array to the left and drew walls according to a few rules. Here is a picture of their result. The picture is too small to make out the numbers, but you can see the shape, which looks like the Empire State Building. Oops, I forgot to mention, the paper is called The Extra Fibonacci Series and the Empire State Building.
My last year’s PRIMES STEP senior group (Eric Chen, Adam Ge, Andrew Kalashnikov, Ella Kim, Evin Liang, Mira Lubashev, Matthew Qian, Rohith Raghavan, Benjamin Taycher, and Samuel Wang) studied the Conway-Ryba paper and decided to generalize it to Tribonacci numbers.
Just a reminder. The Tribonacci sequence starts as 0, 0, 1, 1, 2, 4, 7, 13, 24, 44, and continues so that any next term is the sum of the three previous terms. For example, the next term after 44 is 81.
Now we need an analog of the Wythoff array for Tribonacci numbers. My readers might by now guess why I chose the above definition of the Wythoff array. Yes, this definition is perfect for generalizing to Tribonacci numbers.
We start by defining the Tribonacci base. We can represent every integer uniquely as a sum of distinct Tribonacci numbers on the condition that there are no three consecutive Tribonacci numbers in the sum. This is called a Tribonacci representation. We can express it with zeros and ones, and there will never be three ones in a row. For example, 16 can be expressed as a sum of Tribonacci numbers in the following way: 16 = 13 + 2 + 1. Thus, its Tribonacci representation is 10011.
We can define a Tribonacci successor, similarly to the Fibonacci successor, by adding a zero in the Tribonacci representation. For example, the Tribonacci successor of 16 has to have the Tribonacci representation 100110 and is equal to 24 + 4 + 2 = 30.
Now, we define the Tribonacci array similarly to the Wythoff array. The first row of the Tribonacci array consists of distinct Tribonacci numbers in order. The first column consists of integers whose Tribonacci representations end in 1. The number in the nth column is a Tribonacci successor of the number to its left.
Consider any integer sequence such that the next term is a sum of the three previous terms. We call such sequences Tribonacci-like. One of the cool properties is that, in some sense, the Tribonacci array contains all positive Tribonacci-like sequences. More formally, if a Tribonacci-like sequence has three consecutive positive terms, then the tail of such a sequence has to appear in the Tribonacci array as one of the rows.
It follows that multiples of any row in the Tribonacci array have to appear in the array. An awesome fact is that they appear in order.
Moreover, when all the numbers of a row are divisible by n, the row number minus 1 is also divisible by n.
It is easy to extend the Tribonacci array to the left, but this extension doesn’t have the same nice properties as the extension of the Wythoff array. So finding an Empire State Building, or any other building, in the Tribonacci array is futile.
As my readers know, I run a PRIMES STEP program, where we conduct mathematical research with students in grades 6 through 9. Last year, our junior group wrote the paper, The Struggles of Chessland, which is now posted on the arXiv.
This is the funniest paper ever written at PRIMES STEP. In the paper, the King, with his self-centered Queen and their minions, try to protect their lands in the Bermuda triangle, called the Chessland, which consists of square islands of different sizes.
In the first part of their fairy tale, the King, his lazy Queen, and other chess pieces are trying to survey their islands. The first volunteer for this surveying job is the Knight. The Knight starts somewhere on an island and walks around it by using the knight’s moves in chess. The goal is to see every cell, and a Knight can see all cells that are a knight’s move away from where he is standing. In other words, every cell is either visited by the Knight or is one knight’s move away from a visited cell. In mathematical terms, the Knight walks a path that is a domination set on a knight’s graph.
The students found a lot of such paths. The picture shows a surveying path for the Knight for the island of size 7. The students called this pattern a shoelace pattern. They used similar shoelaces to survey any island of size 7 or larger. However, when I look at the picture, I see a cat.
Other chess pieces survey the land too. Funnily, the King surveys better when he is drunk. Do you know why? Take a look at the paper.
After all the islands had been surveyed, enemy spies started to appear in Chessland, and our band of chess pieces tried to trap them. My students invented the rules for trapping enemies. An example of the black Queen being trapped is in the picture below, and the rules are the following. Wherever the black Queen might move, should be under attack by a white queen. Also, white queens can’t directly attack the black Queen, or each other.
Oh! I forgot to mention: the trapping should use as few white queens as possible. Also, if the enemy is not a queen but another kind of chess piece, it can only be trapped by its own kind.
The trapping can be described in terms of graph theory. The black Queen is located at a vertex of the queen’s graph. The white queens should be positioned at vertices in such a way that they are not neighbors of the black Queen or each other. In addition, any vertex that is a neighbor of the black Queen, has to be a neighbor of at least one white queen.
This year’s PRIMES STEP project was a real chess adventure!
I often receive letters from parents of math geniuses — “My twelve-year-old is reading an algebraic geometry book: accept him to PRIMES,” or “My ten-year-old finished her calculus course: here is her picture to post on your blog,” or “My two-year-old knows the multiplication table, can you write a research paper with him?” The last letter was a sarcastic extrapolation.
I am happy to hear that there are a lot of math geniuses out there. They are potentially our future PRIMES and PRIMES STEP students. But, it is difficult to impress me. The fact that children know things early doesn’t tell me much. I’ve seen a student who didn’t know arithmetic and managed to pass calculus. I’ve also met a student claiming the full knowledge of fusion categories, which later appeared to be from half-watching a five-minute YouTube video.
There are a lot of products catering to parents who want to bring up geniuses. My grandson received a calculus book for his first birthday: Introductory Calculus For Infants. Ten years later, he still is not ready for calculus.
Back to gifted children. Once a mom brought us her kid, who I can’t forget. The child bragged that he solved 30 thousand math problems. What do you think my first thought was? Actually, I had two first thoughts: 1) Why on Earth would anyone count all the problems they solved? 2) And, what is the difficulty of the problems he solved 30 thousand of?
From time to time, I receive an email from a parent whose child is a true math genius. My answer to this parent is the same as to any other parent: “Let your child apply to our programs. We do a great job at working with math geniuses.”
Our programs’ admissions are done by entrance tests. Surprisingly, or not surprisingly, the heavily advertised kids often do poorly on these tests. It could be that the parents overestimate their children’s abilities. But sometimes, the situation is more interesting and sad: I have seen children who sabotage the entrance tests so as not to be accepted into our programs. We also had students give us hints on their application forms that they were forced to apply.
In the first version of this essay, I wrote funny stories of what these students did. Then, I erased the stories. I do not want the parents to know how their children are trying to free themselves.
Dear parents, do not push your children into our programs. If they do not want to be mathematicians, you are decreasing their chances of getting into a good college. Imagine an admission officer who reads an essay from a student who wants to be a doctor but wastes ten hours a week on a prestigious math research program. Such a student doesn’t qualify as a potential math genius, as their passion lies elsewhere. Nor does this student qualify as a future doctor, as they didn’t do anything to pursue their claimed passion. In the end, the student is written off as a person with weak character.
On the other hand, the students who do want to be in our programs, thrive. They often start breathing mathematics and are extremely successful. Encourage your children to apply to our programs if they have BOTH: the gift for mathematics and the heart for it.
Puzzle. How can an egg fly three meters and not break?
The expected answer:
The egg flew more than 3 meters and broke afterward.
Some students tried to protect the egg:
The egg was bubble-wrapped.
The egg was dropped on a cushion.
The egg was thrown up, then caught.
The egg was thrown into water.
My favorite: The egg used a parachute.
Other students specified qualities of an egg making it more resistant:
The egg was hard-boiled.
The egg was made of plastic.
The egg was a frog egg.
An educated answer: It could be an ostrich egg, which is extremely strong. (I checked that online, and, indeed, a human can stand on an ostrich egg without breaking it.)
My favorite: The egg was fried.
Here are some more elaborate explanations:
The egg flew on a plane.
The egg was thrown on another planet with low gravity.
The egg was thrown in space and will orbit the Earth forever.
My favorite: The egg was not birthed yet: it flew inside a chicken.
To conclude this essay, here is a punny answer:
The egg was confident, not easy to break by throwing around.
Puzzle. A goat was on a 10-meter leash. Yet it managed to go 300 meters away from the post. How come?
The standard answer. The leash wasn’t attached to the post.
My students scrutinized the puzzle and found some other possible ambiguities. For example, there might be two posts: the goat was leashed to one and was far away from the other. In another example, the timing is not given. It is possible that the goat was on the leash at one time and unleashed and far away from the post at another time. Here is my favorite answer.
Here is the current picture of my coauthor, Joel Lewis. I remember him from many years ago when he was a graduate student at MIT. I am glad he kept his big smile.
Back to the subject matter. Joel Lewis made a comment on my recent post, thinking-outside-the-box ideas. He mentioned his two theorems:
The Big Point Theorem.Any three lines intersect at a point, provided that the point is big enough.
The Thick Line Theorem.Any three points lie on the same line, provided that the line is thick enough.
I recently wrote an essay, Thinking Inside and Outside the Box, which starts with a famous nine-dots puzzle that kicked off the expression: thinking outside the box. Here is another puzzle with the same nine-dots setup.
Puzzle. What is the smallest number of squares needed to ensure that each dot is in its own region?
Usually, people who try to solve this puzzle come up with the following four-squares solution.
As with the classic nine-dots puzzle, they imagine that the dots are on a grid and try to build squares with sides parallel to the grid lines. What would be the outside-the-box idea? The sides of the squares would not need to be parallel to the grid. This way, we can solve the puzzle with three squares.
One of my MathRoots students offered a different and awesome solution also using three squares.
The most famous thinking-outside-the-box puzzle is the Nine-Dots puzzle. This puzzle probably started the expression, “To think outside the box”. Here is the puzzle.
Puzzle. Without lifting the pencil off the paper, connect the nine dots by drawing four straight continuous lines that pass through all the dots.
Most people attempt something similar to the picture below and fail to connect all the dots.
They try to connect the dots with line segments that fit inside the square box around the dots, mentally restricting themselves to solutions that are literally inside the box.
To get to the correct solution, the line segments should be drawn outside this imaginary box.
Do you think that four line segments is the best you can do? Jason Rosenhouse showed me a solution for this puzzle that requires only three lines. Here, the outside-the-box idea is to use the thickness of the dots.
This and many other examples of thinking outside the box are included in my paper aptly titled Thinking Inside and Outside the Box and published in the G4G12 Exchange book.
A section of this paper is devoted to my students, who sometimes give unexpected and inventive solutions to famous puzzles. Here is an example of such a puzzle and such solutions that aren’t in the paper because I collected them after the paper was published.
Puzzle. Three men were in a boat. It capsized, but only two got their hair wet. Why?
The standard answer is the following: One man was bald.
Lucky for me, my creative students suggested tons of other solutions. For example,
One man was wearing a waterproof helmet.
The boat capsized on land, and two men had their hair already wet.
