My PRIMES STEP program consists of two groups of ten students each: the senior group and the junior group. The senior group is usually stronger, and they were especially productive last academic year. We wrote four papers, which I described in the post EvenQuads at PRIMES STEP. The junior group wrote one paper related to the game SOS. The game was introduced in the following 1999 USAMO problem.
Problem. The game is played on a 1-by-2000 grid. Two players take turns writing an S or an O in an empty square. The first player who produces three consecutive squares that spell SOS wins. The game is a draw if all squares are filled without producing SOS. Prove that the second player has a winning strategy.
The solution is quite pretty, so I do not want to spoil it. If my readers want it, the solution for this grid, and, more generally, for any grid of size 1-by-n, is posted in many places.
My students studied generalizations of this game, and the results are posted at the arXiv: SOS. We tried different target strings and showed that:
The SOO game is always a draw.
The SSS game is always a draw.
The SOSO game is always a draw.
Then, we tried a version where the winner needed to spell one of two target strings. We showed that:
The SSSS-OOOO game is always a draw.
We tried several more elaborate variations, but I want to keep this post short.
Here is another STEP homework question, which is a famous riddle.
Puzzle. Peter had ten cows. All but nine died. How many cows are left?
The wording is confusing on purpose. So, the students who are in a hurry subtract nine from ten and answer that only one cow is left. This answer is wrong. All but nine means that one cow died. So, the correct answer is nine.
One of my students decided that nine is the name of one of the cows, though it should have been capitalized. This means that all the cows except for Nine died, and only one cow, Nine, is left.
This student managed to find a legitimate explanation for the standard wrong answer.
I love the game of SET, where you have a specialized deck of 81 cards. The image on each card has four features: color, shape, shading, and the number of objects. Each feature can have three possible values. Three cards form a set if, for every feature, the values on the cards are either all the same or all different. One of the best properties of the sets is that, given any two cards, we can calculate the third card that would complete a set.
If we look at the game mathematically, we can assign a number 0, 1, or 2 for every feature value. For example, green could be 0, purple could be 1, and red could be 2. Then, the condition that, given a feature, three cards are either all the same or all different is equivalent to saying that the sum of the values modulo 3 is zero.
A mathematician would wonder, can we make a new game where we take values modulo 4? Each feature value should correspond to 0, 1, 2, or 3. For example, we can add a yellow color corresponding to number 3. The new “set” should be four cards such that the sum of the values modulo 4 is 0. This condition guarantees that any three cards could be uniquely completed into a “set”. But such a game is inelegant. For example, one green, two purple, and one red card will form a set. But one green, one purple, and two red will not. The symmetry between colors is lost.
I decided that there is no good analog for the game of SET that is played modulo 4. I was wrong. Here is a new game called EvenQuads. I heard about it at the 2022 MOVES conference.
The deck consists of 64 cards with three features: color, shape, and the number of objects. There are four values for each feature. Four cards form a quad if, for every feature, the values are all the same, all different, or half-and-half.
For example, the figure above shows a quad where, for each feature, all values are different. To get familiar with quads, here is a puzzle for you. How many quads can you find in the picture below?
The game proceeds in a similar way to the game of SET. You can find out more about EvenQuads at the EvenQuads website.
I picked this game as a research project for my senior STEP group. As many of you know, I have a program where we conduct mathematical research with students in grades 7 through 9. The group started in the fall of 2022 and was extremely productive. We wrote FOUR papers in an academic year, which is obviously our record. The papers can be found at the arXiv.
In Card Games Unveiled: Exploring the Underlying Linear Algebra, we analyze four games related to linear algebra: SET, EvenQuads, Socks, and Spot It!. The games are so connected to each other that sometimes it is even possible to play one game using the cards from another game.
In Quad Squares, we study semimagic, magic, and strongly magic quad squares made out of EvenQuads cards. A semimagic quad square is a 4-by-4 square in which each row and column form a quad. You can guess what a magic quad square is. The idea was inspired by magic SET squares: 3-by-3 squares where each row, column, and diagonal form a set. A magic SET square has an additional property: there are always four more sets in such a square located on broken diagonals. In other words, consider three cards and their coordinates in a square. These cards form a set if and only if the values of each coordinate are either all the same or all different. This property is stronger than the definition of a magic SET square. In the case of the game of SET, these two definitions are the same. However, for EvenQuads, we get two different definitions. This is how we ended up defining strongly magic quad squares. You can find the details in the paper.
In Maximum Number of Quads, we calculate the maximum possible number of quads, given n cards from an EvenQuads deck. For example, the puzzle pictured above is actually an example of the maximum possible number of quads among 7 cards. We generalize this idea to decks of any size. Unfortunately, our formula is based on a conjecture. Though, we strongly believe that our formula is correct.
I was browsing my analog archives, my high-school notes, and stumbled upon a couple of problems from a math battle we had.
Puzzle. A square is divided into 100 pieces of the same area, in two ways. Prove that you can find 100 points such that each piece in the first division has a point inside, and each piece in the second division also has a point inside.
Puzzle. There is a finite number of points on a plane. All distances between any pairs of points are distinct. Each point is connected to its closest neighboring point. Prove that each point is connected to no more than 5 points.
A link is defined as two closed curves in three-dimensional space. The first picture shows an example of a link with one yellow curve and one blue. The linking number is a simple numerical invariant of a link. Intuitively, it represents the number of times that each curve winds around the other. For example, if it is possible to pull the two curves apart, the linking number is zero.
When I studied the linking number, I would look at a picture of a link trying to calculate this number. It was confusing. It only became easy after I started crocheting. For example, the second picture shows the same link as the first but slightly rearranged. I simply slid the yellow loop along the blue one until I could clearly see a piece of the blue loop as a straight segment and the yellow loop circling around it. Now, it is easy to see that the yellow loop winds around the blue one 3 times, making the linking number 3.
The only thing to remember is that while counting the number of windings, I need to consider the direction. It is possible for a loop to wind clockwise and then counterclockwise. In this case, the linking number is the difference between the two.
I crocheted a lot of links, and now my students and I have no problem calculating the linking numbers.
Puzzle. If you can move exactly two matches, what is the largest possible number you can get?
Many people assume that given that 508 has three digits, the answer also has three digits. They get the number 999 and stop there.
Some students realized they can make an extra 1 out of two matches and gave answers with four digits: 1503, 5051, and 5103.
Another great idea is to take out the two horizontal matches from 0, turning the 0 into 11. For example, one might use the two matches to turn 5 into 8 and get 8118. However, we can combine this idea with the previous one and use the two matches to make a new digit 1 to get 51181.
When I first saw this puzzle several years ago, 51181 was the official answer. But my students went further, much, much further.
Another elegant idea is to rotate the picture and get 81151.
Some students decided that having all the digits be the same height is not very important. One vertical match reads as 1, even if it is half the height. The largest number they got this way was 511811. Combining this idea with flipping the number allows us to get 811511.
However, small-font digits are often used in powers. This train of thought led to a brilliant answer, 511811. This number is way larger than everything we saw before: it has 41 digits. If we combine this idea with rotating the number, we can get 811511, a 43-digit number.
I recently decided to check the Internet again and discovered a chain of videos showing solutions to this puzzle by the same author. He started with a simple solution, 51181, then people left comments in the video with better solutions, so he remade the video. This happened several times. I probably should send him a link to this essay for yet another video.
Here is an interesting solution by one of my students that I haven’t seen anywhere else. The idea is to use scientific notation. The student took two matches from the right side of 0. He used one of them to convert the first digit from 5 to 9 and the second digit from 0 into the letter E. He got 9E8 = 900000000. If we combine this idea with using a small 1, we can get 5E81, an 82-digit number.
Another brilliant idea is using two matches to create a caret symbol representing an exponent. This way, we can get 5^118, which is an 83-digit number. If we combine this idea with the rotation idea, we can get 8^115, a 104-digit number.
If we ignore the relative sizes of the digits, we can have the small digits as the base of the exponent and the larger digits as the power. One of the students suggested 115118, a 5330-digit number. And if we rotate the number, the answer we can get is 118115: the number with 8451 digits. This is a humongous number compared to the mere 3-digit one we started with, to the pathetic 5-digit original solution, and to the pitiful 104-digit previous record. But my students didn’t stop there.
One student suggested snapping two matches and creating a double factorial 505!!, with 575 digits. Combining this with other ideas, we can get 8115!!, a 14102-digit number.
One of my students decided to use two matches from the last digit 8 to create a factorial sign. She glued one of the matches perpendicular to the plane to get 505! in the projection. She even made a picture that you can see below. This number has 1148 digits, and combining this with previous ideas, we can get 5118!, which has 16763 digits. Or even 8115!, which has 28202 digits.
For this puzzle, a factorial works better than a double factorial. Here is my own suggestion: use one of the matches to create a small digit one, and split the other match into a factorial. This way, we can get 81151!, a number with a whooping 363154 digits.
This is an excellent example of a thinking-outside-the-box puzzle. I love this puzzle because it has not one, but many boxes one can think outside off.
Sometimes I mess with my students. Recently, I gave them the following problem for homework.
Puzzle. Don’t read this sentence.
This problem is a paradox: students can’t know not to read it unless they read it! I expected my students to explain the paradox, and a couple of them did. But, most of them provided me with an infinite stream of entertainment. Here are some of their answers divided into categories, starting with the apologizing ones, and there were a lot of those:
Oopsie.
Too late?
My apologies.
I wasn’t surprised by the apologies, as this problem is intended to be intimidating. However, other students tried to wiggle out of it:
Next time, I will ask my parents to read my homework to me.
A person named Don’t read, in the past tense, “this sentence”. I read this sentence, too!
I happen to have conveniently forgotten English, and it cannot be proven otherwise.
Yet other students decided to rebel:
Why not?
I didn’t.
You just lost your game.
I will never read anything again, as it says, “Don’t read.”
Karma is a boomerang, and this problem got me into a pickle. One of the most brilliant and funny solutions possible was to leave the answer box blank, implying that the sentence wasn’t read. However, how would I grade this? What if they just skipped the problem? I decided to err on the students’ side and gave full credit for an empty answer box.
A couple of students made a point of pretending they didn’t read the sentence:
Which sentence?
I see an answer box, but there’s no problem.
But I saved the best for last. My favorite answer was the following:
Puzzle. “I guarantee,” said the pet-shop clerk, “that this parrot will repeat every word it hears.” A customer bought the parrot but found it wouldn’t speak a single word. Nevertheless, the clerk told the truth. Explain.
The official answer:
The parrot is deaf.
Indeed, in this case, it is not a lie that the parrot will repeat every word it hears. My students had some other ideas. The following answer differs from the official one by one letter, but the spirit of the solution is the same.
The parrot is dead.
Another idea my students had was to introduce a time component.
The parrot wasn’t guaranteed to say the lines immediately; it would wait 30 years before repeating any words.
The parrot only repeated the words in the customer’s absence.
And a couple of outside-of-the-box answers.
The parrot was a toy and did not have a battery in it.
The customer mistook the pet-shop owner to say the statement about the parrot when in fact, the parrot was saying it.
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.