Author Archive

## SOS

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.

Share:

## A Quadrilateral in a Rectangle Solution

I recently posted A Quadrilateral in a Rectangle puzzle.

Puzzle. A convex quadrilateral is inscribed in a rectangle with exactly one quadrilateral’s vertex on each side of the rectangle. Prove that the area of the rectangle is twice the area of the quadrilateral if and only if a diagonal of the quadrilateral is parallel to two parallel sides of the rectangle.

Now it is time for a solution where I use the sample rectangle pictured below. We draw lines parallel to the sides of the rectangle from every vertex of the quadrilateral. Now, we can find four pairs of congruent triangles where one triangle is inside the quadrilateral and the other is outside. In the picture below, the pairs are colored the same color. We see that green and red rectangles overlap, creating a brown rectangle. The fact that they overlap means that the quadrilateral’s area is less than half of the rectangle’s area.

It could go the other way, as the next picture shows. Here, the quadrilateral’s area is more than half of the rectangle’s area. In this case, we have an “underlap” as opposed to an overlap.

Therefore, the quadrilateral’s area is exactly half of the rectangle’s if and only if there is no overlap/underlap, implying that the thickness of the overlap/underlap rectangle is zero. This means that one of the diagonals of the quadrilateral has to be parallel to two sides of the rectangle.

Share:

## Polyomino Cutting Solution

I recently posted the following polyomino puzzle, and my readers are asking for a solution.

Puzzle. You are given a 5-by-7 rectangle with two corners cut out: A 1-by-1 tile is cut from the bottom left corner, and a 1-by-2 tile is cut out of the top right corner, as pictured. The task is to cut the resulting shape into two congruent polyominoes.

If a solution exists, there should be a transformation between the two congruent pieces. We can exclude a reflection and a central symmetry, as the union of the two shapes would have to be symmetric. We can exclude a translation: I leave it to the readers to explain why. What is left is a rotation or a glide. Let me remind you that a glide is composed of a reflection with respect to a line and a translation parallel to the line.

People often forget about glides, so this puzzle might be cool precisely because it is about glides. This is where we should start. We can safely assume that the top left corner belongs to piece A and, after the glide transformation, becomes the bottom right corner of piece B. It is also clear that the reflection line is parallel to the grid diagonals.

Then, we can start drawing the shapes. Piece A’s border starts from the top left corner and moves four squares down, then one square to the right, then one square down. Thus, piece B’s border starts at the bottom right corner and continues four squares to the left, then one square up, then one square to the left. In doing so, we reveal how the border of piece A continues. Thus, we can proceed in this manner to get the answer pictured below.

Share:

## A Quadrilateral in a Rectangle

A new geometry problem from my friend, Alexander Karabegov.

Puzzle. A convex quadrilateral is inscribed in a rectangle with exactly one quadrilateral’s vertex on each side of the rectangle. Prove that the area of the rectangle is twice the area of the quadrilateral if and only if a diagonal of the quadrilateral is parallel to two parallel sides of the rectangle.

Share:

## How Many Cows Are Left?

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.

Share:

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 EvenQuads Game and Error-Correcting Codes, we describe error-correcting codes based on a set of EvenQuads cards.
• 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.

My students did a great job.

Share:

## Solomon’s Knot

I deleted my previous post about Solomon’s knot. The reason is simple. I made the mistake of trusting Wikipedia. I was sure that the linking number of Solomon’s knot was 2. Then Wikipedia said it was 0, so I fixed “the error” in my post. One of my readers corrected me. So, I rechecked it, removed my post, and fixed the article in Wikipedia. Now, I have a new post about the knot.

Solomon’s knot is actually not a knot in a mathematical sense. It is a link because it consists of two loops. It is famous for being one of the simplest linked links. The simplest one is the unlink, the link where two loops are not linked. The next simplest is the Hopf link. The Solomon’s knot is the next after that.

Usually, the simplicity of a link corresponds to its crossing number, which is the smallest number of crossings of a projection of the link onto a plane. The unlink has a crossing number of 0, the Hopf link has a crossing number of 2, and the Solomon’s knot has a crossing number of 4. However, the linking number created the confusion, so I will explain it.

The linking number is an invariant of a link, which describes how many times one loop goes around the other. It equals zero for the unlink, one for a Hopf link, and two for Solmon’s knot.

I often have difficulty calculating the linking number by looking at a picture of a link. This is why I started to crochet links: finding their linking numbers by fiddling with them is easy. The first image shows the crocheted standard representation of Solomon’s link. The second image shows the same link, but I slid the red loop so it twists around a small portion of the green loop, which now looks like a segment. Then, I can count the number of times the red loop goes around the green segment. What’s important is to keep the direction in mind. In the second picture, one can see that the red loop winds around the green loop twice but in the same direction, making the linking number two.

Share:

Puzzle. A group of 20 students formed a line to take an oral exam with Professor Chill. They were afraid to enter the classroom, so they decided to do a drawing. They wrote the numbers from 1 to 20 on pieces of paper, placed them in a hat, and each student picked one. The student who drew the number 1 went into the classroom first. Then, the remaining 19 students repeated the process, writing down numbers from 1 to 19, and the one who drew the number 1 took the exam next. They continued this process until all 20 students had taken their exams. Remarkably, each student drew a different number each time. Olga drew number 14 in the first round. How many students took the exam before she entered the classroom?

Share:

## Find the Disappearing Bits

Konstantin Knop posted the following puzzle on Facebook.

Puzzle. An agent sends messages to the command center. The messages have to be encrypted as a stream of 512 characters that can only be zeros and ones. Unfortunately, his transmitter is malfunctioning and gobbles 16 characters of each message. The missing 16 characters are always in the same positions in any message. As a result, the command center receives a sequence of 496 bits. Neither the center nor the agent knows which 16 bits of the sequence are eaten up by the device.
They cannot replace the broken transmitter. However, they can agree ahead of time to send K test messages, the content of which they both know. Find the smallest possible K needed to determine the positions of the disappearing 16 bits.

Share:

## An English Quine

A quine is a computer program which takes no input and produces a copy of its own source code as its only output.

Puzzle. Assuming English is a computer language, write a quine in English.

My students had many solutions on how to solve this puzzle. They were all variations on “Write this sentence.” This is a self-referential sentence which doesn’t quite work. I even tried it on ChatGPT with the following result, “Of course, I’d be happy to help! Please provide the sentence you’d like me to write, and I’ll assist you with it.”

However, the solution I originally had in mind worked. ChatGPT repeated my input. So, ChatGPT provides a simple way for you to check your answer to this puzzle.

My students had more ideas. One of them suggested screaming at a friend, forcing the friend person to scream back. In a similar vein, one might say hello to a person in order to hear hello back. I tried this with ChatGPT, but it didn’t work. The bot replied, “Hello! How can I assist you today?”

Another trivial idea is to write nothing. This certainly works perfectly with ChatGPT.

Share: