Tanya Khovanova's Math Blog

The puzzle In the Details by Derek Kisman is one of my favorite MIT Mystery Hunt puzzles of all times. I even wrote a blog post advertising it and another post with comments on the solution. This puzzle type became known as fractal word search.

In the standard word search, you have a grid of letters and a list of words. You need to find the words written in the grid in all eight directions. The unused letters provide the answer, or a clue to the answer, of the word search puzzle.

In the fractal word search, you have a grid of letters and a list of words. It looks like a regular word search, but you will not find all the words inside the given grid. The given grid is only a snapshot of the whole grid on some particular level k. To go to level k+1, you have to use replacement rules: each letter is replaced by a 2-by-2 block of letters. This creates a much bigger grid where you might find more words from the given list.

An interesting question is, where do you find the replacement rules? In Derek’s puzzle, the rules were not given, but the initial grid was level 2. So you could notice that this grid can be decomposed into 2-by-2 squares, and there are only 26 different squares, implying that each square corresponds to a letter. Assuming that replacing the 2-by-2 squares with correct letters will allow you to find more words from the list, you can decipher the replacement rules. This will allow you to get to level 1 as well as any other level. Small levels are easy to search, but on large levels, the grid gets so huge that it might not fit in the memory of a computer, or a million computers. That is why this puzzle was presented at the MIT mystery hunt, but not at any other puzzle hunt. It is quite difficult: one of the given words is hiding on level 86.

I liked the puzzle so much, I included it in one of my lectures. After I gave my talk at Brown University, a student, Klára Churá, approached me. She got as fascinated with the puzzle as I was. We ended up collaborating on the paper Fractal Word Search: How Deep to Delve. As the title suggests, we focused on finding the upper bound of the level where we could find a word of a given length. We had two parameters: the size of the alphabet n and the block size b used in the replacement rules.

For different reasons, the most interesting case is words of length 3. I will leave it to the reader to figure out why this is the most interesting case, or the reader can check our paper. We showed that any word of length 3 appears no later than level n³ + n² + 1.

When we posted the paper, I sent the link to Derek. He immediately wrote a program and showed that our bound is fairly tight. His code is available at GitHub. He created a configuration that puts a 3-letter word at depth LCM(a,b,c)+1, where a,b,c ≤ n-3. If n is even, this gives us a lower bound of (n-3)(n-4)(n-5) + 1. If n is odd, this gives us a lower bound of (n-4)(n-5)(n-6) + 1. In any case, asymptotically, it is very close to our upper bound.

Foams are a recent craze in homology theory. I want to explain what a foam is using a tesseract as an example. Specifically, the 2D skeleton of a tesseract is a foam.

We can view a tesseract as a convex hull of 16 points in 4D space with coordinates that are either 0 or 1. The edges connect two vertices with the same three out of four coordinates. Faces are squares with corners being four vertices that all share two out of four coordinates.

Foam definition. A foam is a finite 2-dimensional CW-complex. Each point’s neighborhood must be homeomorphic to one of the three objects below.

1. An open disc. Such points are called regular points.
2. The product of a tripod and an open interval. Such points are called seam points.
3. The cone over the 1D-skeleton of a tetrahedron. Such points are called singular vertices.

My favorite example of a foam is a tesseract. Or, more precisely, the set of tesseract’s vertices, edges, and faces form a foam.

1. The regular points are the insides of the tesseract’s faces. Their neighborhoods are obviously open discs.
2. The seam points are the insides of the tesseract’s edges. Each edge is incident to three faces, and the projection of its neighborhood to a plane perpendicular to the edge is a tripod.
3. The singular vertices are the tesseract’s vertices. Each vertex is incident to four edges and six faces. We can view this neighborhood as a cone cover of a tetrahedron formed by this vertex’s neighbors.

Some of the coolest foams are tricolorable. A foam is called tricolorable if we can color it using three colors in such a way that each face has its own color, and any three faces that meet at a seam are three distinct colors.

Not surprisingly, I chose a tricolorable foam for our example. Let me prove that the tesseract’s 2D skeleton is tricolorable. We start by coloring the edges in four colors depending on the direction: red, green, blue, or gray, as in the first picture (source: Wikipedia). Each face has two pairs of edges of two different colors. We can color the faces in the following manner: if none of the edges are gray, then the face color is the complementary non-gray color (For example, if the edges are red and blue, the face is green). If the edges are gray and one other color, then the face color matches the non-gray color (For example, if the edges are red and gray, the face is red). I leave it to the reader to prove that this coloring means that each edge is the meeting point of three different face colors.

Here is an interesting property of tricolorable foams. It is Proposition 2.2 in the paper Foam Evaluation and Kronheimer-Mrowka Theories, by Mikhail Khovanov and Louis-Hardien Robert.

Proposition. If we remove the regular points of one particular color from a tricolored foam, we will get a closed compact surface containing all the seam points and singular vertices.

In our example, the result is a torus, which you can recognize in the second picture. Here, I use the Schlegel diagram as a model for a tesseract, shown on the right (source: Wikipedia). The exercise for the reader is to explain where the eight green faces of the torus were before they were removed.

The following lemma from the aforementioned paper describes another cool property of a tricolorable foam.

Lemma. If a foam is tricolorable, its 1D skeleton (the graph formed by seams and singular points) is bipartite.

And, surely, I am leaving it up to the reader to check that the tesseract’s 1D skeleton forms a bipartite graph.

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.

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.

In December 2022, I wrote a blog post Uncrossed Knight’s Tours about Derek Kisman’s amazing achievement of calculating the largest uncrossed knight’s tours on rectangular chessboards on sizes M-by-N, where M is small, and N can be very very large.

The data showed some asymptotic periodicity, and I wondered how to prove it mathematically. I didn’t realize that Derek already proved it. In my ignorance of programming, I assumed that programs just spewed out the data and didn’t think they could prove anything. I was wrong. It appears that no other proof is needed. Derek tried to explain the details to me using the terminology of dynamic programming, but I am not sure I can reproduce it here.

Let’s recall the problem. Consider an M-by-N chessboard and a knight that moves according to standard chess rules: jumping one square in one direction and two squares in an orthogonal direction. The knight must visit as many squares as possible, without repeats, and then return to its starting square. In addition, the knight may never cross its own path. If you imagine the knight’s path consisting of straight line segments connecting the centers of the squares it visits, these segments must form a simple polygon. To summarize, given M and N, we want to calculate the longest uncrossed knight’s tour length.

To be clear: the programs, their output data, proven answers, and images are by Derek Kisman. I am just a humble messenger showing my new appreciation of the power of a computational proof.

The image shows Derek’s solution for a 3-by-13 chessboard. There is a repeating 3-by-4 pattern marked by dashed lines. The same tour works for boards of lengths 10, 11, and 12. Thus, for chessboards of width 3 and length from 10 to 13 inclusive, the longest uncrossed knight’s tour is length 10. We can write the answers for 3-by-N chessboards as a sequence with index N, where -1 means the tour is impossible. The sequence starts with N = 1: -1, -1, -1, 4, 6, 6, 6, 6, 10, 10, 10, 10, 14, 14, ….

We can prove that this sequence is correct without programming. Suppose the tour starts in the leftmost column. If we start in the middle of the column, the whole tour ends as a rhombus and a tour of length 4, which, by the way, is the longest tour for N = 5. Thus, for a larger N, we have to start in a corner. From there, there are only two possible moves. We can see that the continuation is unique and that, asymptotically, we gain one step per extra column. That is, asymptotically, the length of the longest tour divided by N is 1.

Derek uses an additional notation in the following sequence: each cycle is in brackets. Any two consecutive cycles differ by the same constant. So to continue the sequence indefinitely, it is enough to know the first two cycles.

Closed tours: 3xN (asymptote 1):  -1, -1, -1, -1, 4, [6, 6, 6, 6], [10, 10, 10, 10], …

I continue with other examples Derek calculated:

Closed tours: 4xN (asymptote 2): -1, -1, -1, [4], [6], …

Closed tours: 5xN (asymptote 2 3/5):  -1, -1, 4, 6, [8, 12, 14, 18, 20, 22, 24, 28, 30, 34], [34, 38, 40, 44, 46, 48, 50, 54, 56, 60], …

Closed tours: 6xN (asymptote 4): -1, -1, 6, 8, 12, 12, 18, 22, 24, 28, 32, 36, [38], [42], …

Closed tours: 7xN (asymptote 4 10/33):  -1, -1, 6, 10, 14, 18, 24, 26, 32, 36, 42, 44, 48, 54, 58, 62, 66, 72, 74, 80, 84, 88, 94, 98, 100, 106, 112, 114, 118, 124, 128, 130, [136, 140, 144, 148, 154, 158, 162, 166, 170, 176, 180, 184, 188, 192, 196, 200, 204, 210, 214, 218, 222, 226, 232, 236, 240, 244, 248, 254, 256, 260, 266, 270, 274], [278, 282, 286, 290, 296, 300, 304, 308, 312, 318, 322, 326, 330, 334, 338, 342, 346, 352, 356, 360, 364, 368, 374, 378, 382, 386, 390, 396, 398, 402, 408, 412, 416], …

Closed tours: 8xN (asymptote 6): -1, -1, 6, 12, 18, 22, 26, 32, 36, 42, 46, 52, 58, [64, 70, 76, 80, 88, 92], [100, 106, 112, 116, 124, 128], …

Closed tours: 9xN (asymptote 6 6/29): -1, -1, 6, 14, 20, 24, 32, 36, 42, 50, 56, 60, 68, 74, 80, 86, 94, 98, 106, 114, 118, 126, 132, 136, [144, 150, 156, 162, 168, 174, 180, 186, 192, 200, 206, 212, 218, 224, 230, 236, 242, 250, 254, 262, 268, 274, 280, 286, 292, 300, 304, 312, 318, 324, 330, 336, 342, 348, 354, 360, 366, 372, 378, 386, 392, 398, 404, 410, 416, 422, 428, 436, 440, 448, 454, 460, 466, 474, 478, 486, 492, 498], [504, 510, 516, 522, 528, 534, 540, 546, 552, 560, 566, 572, 578, 584, 590, 596, 602, 610, 614, 622, 628, 634, 640, 646, 652, 660, 664, 672, 678, 684, 690, 696, 702, 708, 714, 720, 726, 732, 738, 746, 752, 758, 764, 770, 776, 782, 788, 796, 800, 808, 814, 820, 826, 834, 838, 846, 852, 858], …

Closed tours: 10xN (asymptote 8): -1, -1, 10, 16, 22, 28, 36, 42, 50, 54, 64, 70, 78, 84, 92, 100, [106], [114], … I do not have an image for this case.

As you might have noticed, for an even M, the asymptote equals M-2. The asymptote for an odd M is slightly greater than the asymptote for M-1.

Derek also calculated the longest open knight’s tours: the tours where the knight doesn’t have to return to its starting position.

Open tours: 2xN (asymptote 1/2): -1, -1, [2, 2], [3, 3], …

Open tours: 3xN (asymptote 1): -1, 2, 3, 5, 6, 7, [9], [10], …

Open tours: 4xN (asymptote 2): -1, 2, 5, [6], [8], …

Open tours: 5xN (asymptote 3): -1, 3, 6, 8, 11, 15, 17, 20, 23, 26, 29, [32, 35, 38, 41, 44, 46], [50, 53, 56, 59, 62, 64], …

Open tours: 6xN (asymptote 4): -1, 3, 7, 10, 15, 18, 22, 26, 30, 33, [36], [40], …

Open tours: 7xN (asymptote 5): -1, 4, 9, 12, 17, 22, 25, 31, 36, [40], [45], …

Open tours: 8xN (asymptote 6): -1, 4, 10, 14, 20, 26, 31, 36, 43, 48, 54, 60, [64], [70], …

Open tours: 9xN open (asymptote 7): -1, 5, 11, 16, 23, 30, 36, 43, 48, 56, 62, 68, 75, [82, 88, 94], [103, 109, 115], … I do not have an image for this case.

There are a lot of interesting new sequences in this essay that were very nontrivial to calculate. I hope someone adds them to the OEIS database.

My PRIMES project last year, done with Rich Wang, was about violinists living in a hotel and being annoyed with each other. The project was suggested by Darij Grinberg and based on the following puzzle.

Puzzle. Consider a hotel with an infinite number of rooms arranged sequentially on the ground floor. The rooms are labeled from left to right with consecutive integers. A finite number of violinists are staying in the hotel with no more than one violinist in a room. Each night, two violinists staying in adjacent rooms get fed up with each other’s playing, and both request different rooms from the manager. The manager moves one of them to the nearest unoccupied room on the left and the other to the nearest unoccupied room on the right. This keeps happening every night as long as there are two violinists in adjacent rooms. Prove that this relocation will stop after a finite number of nights.

The project was not to solve the puzzle, and I won’t describe the solution, leaving it to my readers to ponder on their own. The project was to take this puzzle and see what we could discover. The relocation process in the puzzle is reminiscent of chip-firing, with a few differences.

Let me explain chip-firing in terms of violinists. The starting position would allow any number of violinists per room. Each night, two violinists in the same room will get annoyed with each other and request new rooms. There might be more violinists in that same room, but only two at a time are really annoyed. The manager will put one of them into the room on the left and the other into the room on the right, regardless of how crowded the rooms are.

In the chip-firing example, violinists always move to the next room. In our puzzle, they might need to go miles to a new room. And carry their luggage with them!

The original puzzle above implies that after several nights the relocations will stop, and violinists will enjoy the hotel in peace. This peaceful configuration is called a final state. Interestingly, depending on the order in which violinists are getting annoyed with each other, a starting configuration can result in different final states.

For example, consider the smallest interesting case, where only 3 violinists are staying in a hotel. We use 1 to describe a noisy room with a violinist and 0 to describe an empty room. Suppose the starting configuration is 0011100, where we ignore rooms far away from the noise. Depending on which two rooms have the complaining violinists on the first night, we can end up with a final state 0101001 or 1001010.

Initially, in the project, we looked at final states where we start with N violinists in consecutive rooms. We call such a configuration an N-clusteron. The example above describe the final states of a 3-clusteron. Here is an exercise for the reader: prove that in the final state, the gaps between occupied rooms have to be 1 or 2.

A final state can be described by the index of the leftmost occupied room and the sequence of gaps between occupied rooms. In the exercise above, it is easy to prove that the gaps must be size 1 or 2. In our paper, we proved a more refined statement: any final state has exactly one gap of size 2. Thus, a final state has two parameters: the index of the leftmost room and the location of the size 2 gap. For example, this means that in a final state, the span between the leftmost and the rightmost rooms, inclusive, is 2N.

As we continued exploring final states, we discovered something else. But first, I need to define the shadow of a final state. Let’s denote an occupied room with a one and an empty room with a zero. Then a final state corresponds to an infinite sequence of zeros and ones. But the interesting part of the final state is not infinite: it is a subsequence between the leftmost and rightmost ones, inclusive. We call this subsequence the shadow of the final state. In other words, the shadow describes the final state up to a translation and is completely defined by one parameter: the location of the 2-gap. In our example of a 3-clusteron, there are 2 final states with 2 distinct shadows. For larger clusterons, the situation is more interesting. There are 5 different possible final states for a 4-clusteron but only three distinct shadows. We discovered the following conjecture.

Conjecture. If we start from an N-clusteron and at each state uniformly select a move to perform from all possible moves, then the shadows of the final states are equiprobable.

You can find more details in our paper Ending States of a Special Variant of the Chip-Firing Algorithm. This conjecture is beautiful as it shows that there are hidden symmetries in this process of appeasing the fussy violinists. We didn’t prove this conjecture. Can you do it?

A Whitney umbrella is a cool surface I wanted to crochet. The umbrella continues to infinity, and there is no way I want to crochet the whole thing. I wanted to make a finite portion of a Whitney umbrella surrounding the most exciting point.

The result is seen in the picture. Technically, I crocheted not Whitney umbrellas but topologically equivalent surfaces. I am most proud of my secret — and painful — method of crocheting the self-intersecting segment. One day I will spill it.

As Wikipedia defines it: the Whitney umbrella is the union of all straight lines that pass through points of a fixed parabola and are perpendicular to a fixed straight line parallel to the parabola’s axis and lies on its perpendicular bisecting plane. If you look at the picture, the fixed straight line is the self-intersection line, which is a continuation of the line segment where the colors are woven through each other. You can find the parabola as the curve formed by the two-colored edge on either side of the umbrella. Oops, I forgot that only three of these umbrellas are made of two colors.

The Whitney umbrella is a ruled surface, meaning that for every point, there is a straight line on the surface that passes through the point. A ruled surface can be visually described as the set of points swept by a moving straight line.

Oh, look, the stitched rows can pretend to be these straight lines. Actually, if I fold these thingies, the stitched rows ARE straight lines. But, when I make the edges into parabolas, the rows stop being straight. In the real Whitney umbrella, if you look along the intersection line, the straight lines are closer to each other than they are along the parabola. But in crochets, the distances between rows have to be fixed. If my crochets are folded, they become rectangles and ruled surfaces. The real Whitney umbrella does not fold into a plane.

The Whitney umbrella is famous for being the only stable singularity of mappings from R² to R³. I am grateful to Paul Seidel for emailing me the proof. This singularity is so famous it even has two names: pinch point and cuspidal point. Though my crochets are not exactly Whitney umbrellas, they show this singularity. Hooray! I found a secret way to crochet the most famous stable singularity!

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.

We found many cool properties of the Tribonacci array. They are in our paper, Generalizing the Wythoff Array and other Fibonacci Facts to Tribonacci Numbers, posted on the arXiv. Let me give you three examples of these awesome properties.

1. 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.
2. 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.
3. 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!

The 2018 International Collegiate Programming Contest (ICPC) had a very hard problem which is of interest to mathematicians. The problem was proposed by super-coder Derek Kisman. Here is the problem as it was presented at the contest.

Problem J. Uncrossed Knight’s Tour. A well-known puzzle is to “tour” all the squares of an 8 × 8 chessboard using a knight, which is a piece that can move only by jumping one square in one direction and two squares in an orthogonal direction. The knight must visit every square of the chessboard, without repeats, and then return to its starting square. There are many ways to do this, and the chessboard size is manageable, so it is a reasonable puzzle for a human to solve.

However, you have access to a computer, and some coding skills! So, we will give you a harder version of this problem on a rectangular m × n chessboard with an additional constraint: the knight may never cross its own path. If you imagine its path consisting of straight line segments connecting the centers of squares it jumps between, these segments must form a simple polygon; that is, no two segments intersect or touch, except that consecutive segments touch at their common end point. This constraint makes it impossible to visit every square, so instead you must maximize the number of squares the knight visits. We keep the constraint that the knight must return to its starting square. Figure J.1 shows an optimal solution for the first sample input, a 6 × 6 board.

The input consists of a single line containing two integers m (1 ≤ m ≤ 8) and n (1 ≤ n ≤ 10¹⁵), giving the dimensions of the rectangular chessboard.

Mathematicians know many things about knight tours on a standard 8 × 8 chessboard. But one of the limits in this puzzle is so huge, that the answer to this computational puzzle constitutes a new mathematical discovery. Unsurprisingly, no one solved this puzzle during the contest. A well-written solution summary is available on the ICPC website. The solution requires dynamic programming and a realization that tours have to have repeating patterns.

Since no one solved this problem during the competition, it is useful that, in addition to the solution summary, Derek posted his innovative code online. The two figures below (courtesy of Derek Kisman) show his answer for the longest closed tour on a 6 × 24 board and the longest open tour on a 6 × 26 board.

Derek got interested in uncrossed knight’s tours after reading my blog post, 2014 Math Festival in Moscow, where I presented the following problem given at that festival to 7th graders.

Problem. Inside a 5 × 8 rectangle, Bart draws closed paths that follow diagonals of 1 × 2 rectangles. Find the longest possible path.

The 2014 Math Festival organizers offered an extra point for every diagonal on top of 16. It is funny that the organizers obfuscated that it is useless to try and find 17 diagonals, as the number of diagonals has to be even. The official solution, shown below, had 24 diagonals.

In the solution booklet, the organizers mentioned that they did not know the best answer to their own question. They hoped that the longest possible path matched their official solution.

In Derek’s notation, the above problem is equivalent to finding the largest uncrossed knight’s closed tour on a 6 × 9 grid. And Derek proved that, indeed, 24 is the largest tour. While proving this, he also calculated the answer for gazillions of other boards.

We can go further: beyond gazillions. Let’s consider what happens on m × n boards, where m is fixed, and n is astronomically large. Suppose f_m(n) is the largest size of an uncrossed knight’s closed tour on the m × n board and g_m(n) is the largest size of an uncrossed open tour.

The answer has repeating patterns everywhere except around the ends of the board. We would expect that the number of possible repeating patterns is finite. Moreover, for large boards, only the densest patterns would appear. This means that asymptotically, both functions f and g are linear functions of n. On top of that, as each pattern is periodic, the behavior at the ends of the long boards should become periodic as well. Hence, the difference functions of f and g for fixed m would eventually become periodic. (Here, the f’s difference function, which I denote D(f_m) is defined as follows: D(f_m)(n) = f_m(n+1) – f_m(n).)

That means we can solve a more difficult problem. We do not need the limits for n. It should be possible to calculate these functions for a given m and any n (even if n is way more than a gazillion). I am being over-optimistic here. First, we need some mathematical theory to find the bounds for where the periodic behavior has to start and estimate the size of the period. Suppose we can prove that for D(f₆)(n), the eventual period has to start before n reaches A, and the length of the eventual period is not more than B. Then, we need to calculate the A + 2B values of the function f₆(n) to know the function for any n.

Derek actually calculated the functions f_m(n) and g_m(n) for m up to 9 and n up to infinity. More precisely, he found the cycles I am describing above. What a mindblowing achievement!