Tanya Khovanova's Math Blog

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!

I recently posted a cute puzzle about poisoned wine. Today, I would like to discuss this puzzle’s variation with N total glasses, of which two are poisoned.

Puzzle. N glasses of wine are placed in a circle on a round table. S sages are invited to take the following challenge. In the presence of the first sage, N − 2 glasses are filled with good wine and the other two with poisoned wine, indistinguishable from the good wine. After drinking the poisoned wine, the person will die a terrible tormented death. Each sage has to drink one full glass. The first sage is not allowed to give any hints to the other sages, but they can see which glass he chooses before making their own selection. The sages can agree on their strategy beforehand. For which S can you find a strategy to keep them all alive?

What does this have to do with rulers, and what are those? I am grateful to Konstantin Knop for showing me a solution with rulers. But first, let’s define them.

A sparse ruler is a ruler in which some distance marks may be missing. For example, suppose we have a ruler of length 6, with only one mark at a distance 1 from the left. We can still measure distances 1, 5, and 6. Such a ruler is often described as {0,1,6} to emphasize its marks, endpoints, and size.

A complete sparse ruler is a sparse ruler that allows one to measure any integer distance up to its full length. For example, the ruler {0,1,6} is not complete. It can’t measure distances 2, 3, and 4. Thus, if we add the marks at 2, 3, and 4, such a ruler becomes complete.

A complete sparse ruler is called minimal if it uses as few marks as possible. In our previous example, the ruler {0,1,2,3,4,6} is not minimal. The distance between marks 1 and 4 is 3, so if we remove mark 3, we can still measure any distance. We can remove mark 2 too. The ruler {0,1,4,6} with marks 1 and 4 is minimal.

Oops. I forgot that we have a round table. This means we need to look at cyclic rulers: the idea is the same, but the numbers wrap around. For example, consider the cyclic ruler {0,1,4,6} of length 6, where 0 and 6 is the same point. This ruler has three marks at 0, 1, and 4.

Going back to the puzzle, suppose N = 6, aka there are six glasses around the table. The sages need to agree on a complete cyclic ruler, for example, the one described above. As this ruler contains any possible difference between the marks, the first sage can mentally place the ruler on the table so that the marks cover poisoned glasses. He signals the position of the ruler by drinking his glass. The sages can agree that the glass drunk by the first sage corresponds to position −1 on the ruler, and the other sages avoid the first, second, and fifth glass clockwise from the chosen glass.

In this case, three glasses are not covered by the ruler’s marks. This means three sages can be saved.

To summarize, the sages need a complete ruler, as such a ruler can always cover two glasses at any distance from each other with its marks. The number of sages that can be saved by such a ruler is N minus the number of marks. To save more sages, we want to find a minimal ruler.

There are actually more cool rulers. A ruler is called maximal if it is the longest complete ruler with a given number of marks. For example, the non-cyclic ruler {0,1,4,6} is maximal. A ruler is optimal if it is both maximal and minimal. Thus, the ruler {0,1,4,6} is also optimal.

There are other types of rulers called Golomb rulers. They require measured distances to be distinct rather than covering all possibilities. Formally, a Golomb ruler is a ruler with a set of marks at integer positions such that no two pairs of marks are the same distance apart. If, however, a Golomb ruler can measure all the distances, it is called a perfect Golomb ruler. As we can deduce, a perfect Golomb ruler is a complete sparse ruler. I leave it to the reader to show that a perfect Golomb ruler must be a minimal complete sparse ruler.

The rulers rule!

The Conway subprime Fibonacci sequence is defined as follows. Start with the Fibonacci sequence 0, 1, 1, 2, 3, 5, …, but before you write down a composite term, divide it by its least prime factor. Thus, the next term after 5 is not 8, but rather 8/2 = 4. After that, the sum gives us 5 + 4 = 9, which is also composite. Thus, you write 9/3 = 3, then 4 + 3 = 7, which is okay since it is prime, then 3 + 7 = 10, but you write 10/2 = 5, and so on. Here is the sequence: 0, 1, 1, 2, 3, 5, 4, 3, 7, 5, 6, 11, 17, 14, 31, and so on.

My coauthors, Richard Guy and Julian Salazar, and I studied this sequence in our paper Conway’s subprime Fibonacci sequences, in which we allowed any two integers to be the two starting terms. Our computation showed that for small starting terms, the sequence starts cycling. In our first draft, we had a probabilistic argument as to why the sequence should always cycle. Our argument was the following.

Flawed probabilistic argument. Consider the parity of the numbers in a particular subprime Fibonacci sequence. I will leave it to the reader to see that such a sequence can’t have all even numbers. As soon we get to an odd number, the even numbers in the sequence become isolated. Indeed, if two numbers have different parity, the next number must be odd. For subprime Fibonacci sequences, when we add two odd numbers, there is a 50 percent chance that after dividing by 2, the result will be odd. Assuming the result is odd, there a is 25 percent chance the next number will be odd as well. And this pattern continues. Thus, as soon as we get two odd numbers in a row, on average, we expect three odd numbers in a run of odd numbers. Hence, we would expect a typical subprime Fibonacci sequence to have three times as many odd as even numbers.
This means, on average, two consecutive terms sum to an even number half of the time. Therefore, while calculating the next term, we divide by 2 with probability 1/2 and by 3 with probability 1/6. Ignoring larger primes, on average, we expect to have divided by at least 1.698, while the usual Fibonacci growth is only by a factor φ, which is approximately 1.618. We see that the subprime Fibonacci sequence is divided faster than its expected growth rate. Thus, it has to cycle.

However, this argument doesn’t work. When we submitted the paper, an anonymous reviewer pointed out that the argument was flawed. Here I want to explain why. I will start with a counterexample suggested by my sons, Alexey and Sergei.

Counterexample. Start with two real numbers. Suppose the sequence is to add the two previous numbers and divide the sum by 1.8 (which is greater than the golden ratio φ). The resulting sequence grows as a geometric progression with ratio 1.07321.

Here is a variation of the above argument.

Counterexample Variation. Suppose we have a sequence where we add the two previous numbers and then divide the sum by 2. We are dividing by a noticeably larger number than the golden ratio. By our flawed argument earlier, the sequence should decrease. But if we start such a sequence with two identical numbers n and n, the sequence will be constant, disproving the argument.

Here is an additional observation. Obviously, whenever we add two numbers and divide the sum by a number bigger than 2, the sequence has to cycle. Indeed, the maximum of two consecutive terms decreases. Can we add probabilities to this argument? Below is the averaging version of this argument for the subprime Fibonacci numbers. Unfortunately, this argument is also flawed.

Another flawed probabilistic argument. We need to show that, on average, at each step, we divide our sum by a number bigger than 2. We can ignore divisions by 2 as they are fine. Let’s see what happens with sums that we do not divide by 2. With probability 1/3, we divide them by 3. If not, with probability 1/5, we divide them by 5. Otherwise, with probability 1/7, we divide them by 7. Hence, if we do not divide our sum by 2, then with probability 1/3, we divide it by 3, plus with probability 2/15, we divide it by 5, plus with probability 8/105, we divide it by 7. Thus, on average, if we do not divide the sum by 2, then we divide it by at least 3^1/35^2/157^8/105 = 2.07.

Counterexample to the second argument. Why is this wrong? Let us, for example, consider a sequence with the following recursions: a_2k+1 = a_2k + a_2k-1. And a_2k = (a_2k-1 + a_2k-2)/x, where x is a very large number. Then on average, we divide the sum by a very large number. Would this sequence converge to zero? If we look at it more closely, the subsequence of odd-indexed numbers increases. So the answer is no.

We found yet another probabilistic argument that the sequences shouldn’t increase indefinitely. We are sure that one works. Our anonymous reviewer was happy with it too. You can find the argument in our paper: Conway’s subprime Fibonacci sequences.

But I wrote this essay to show how tricky probabilistic arguments can be.

For students applying to PRIMES, we have a question about their research interests. RSI asks a similar question from their applicants.

I am looking at all the submissions, and this essay will help our applicants to get projects that are well-suited for them.

We, at PRIMES and RSI Math, usually have research projects lined up in advance. That means, we are not creating projects to match applicants’ requests. We match existing projects to students’ backgrounds and interests.

If you are applying to one of these programs, here is my advice.

Don’t be too specific about what you want. Suppose you want to study the symmetries of an icosahedron. This request is too narrow: there is a high probability we do not have such a project. How will we match you to a project? Our hope, in this case, is to find clues in your essay. For example, we might discover that you heard a fascinating lecture on icosahedron’s symmetries, which is why you requested the topic. In this case, we assume that another fascinating lecture on a different topic might also excite you, and you will be matched with a random project. But if your description is broader, say, if you write that you like group theory or geometry, your match won’t be as random.

Specify things you do not want. Given our project distribution, you might not get a project in the area that is your first or even your second choice. On the other hand, if you write to us that you hate geometry, it is very easy to find a project without a geometric component. If there is something you definitely do not want, it is advantageous for you to mention it. Be precise about your advanced knowledge. For example, linear algebra is one of the most powerful tools in mathematics. Not surprisingly, we often have projects that require a serious background in linear algebra and specifically look for students who know it. Unfortunately, we often receive inadequate descriptions of students’ backgrounds. Even if you took a linear algebra course, it might be useful to mention which book you used and how many chapters you covered. This also applies to other advanced topics. An applicant might say they are proficient in cohomologies after half-listening to one half-hour lecture on the topic. This is not proficiency; it only indicates interest. If you claim advanced knowledge, specify the scope. The best way to start is by listing the books you have attempted to read. For each book, describe which chapters you only scanned, which chapters you read and understood, and for which chapters you solved all of the exercises.

Add more information if your first choice is number theory. Almost every year, we have several students requesting number theory. This might be explained by the successes of the Ross and PROMYS summer programs. The graduates from these programs love number theory and have a good number theory background. However, modern number theory is very advanced, and we seldom have these types of projects. So, if number theory is your top choice, there are two things you can do. First, mention your second choice. Second, specify what you like about number theory. For example, if you are into the more abstract parts of number theory, another abstract project might be a good fit.

Describe your priorities in broader terms. It is beneficial for every starting mathematician to figure out the area they like by asking themselves broader questions. If you know the answers to the questions below, it is helpful to write them on the application form.

• Do you love or hate abstractions?
• Do you prefer discreet or continuous problems?
• Is the real-life impact or inner beauty of your project more important to you?
• Do you enjoy having a visual component to your project?
• Do you like when problems involve programs and calculations?

If you follow my advice, you might get a project that matches your tastes better. Not only that: figuring out the answers to these questions will help you build the life you love.

Assume that we have n men and n women, all of whom want to get married. They rank each other without ties. After that, we can match them into n pairs for marriage. The matching is called stable if there are no rogue couples. A rogue couple is defined as a man and a woman who prefer each other over their assigned future spouses.

A famous theorem says that, whatever all the rankings are, a stable matching always exists. But how good could a stable matching be? There is a way to assign a quality score to a matching, called the egalitarian cost. The egalitarian cost of any matching is the sum of the rankings that each person gave their assigned partner. The best potential outcome is when all people are matched with their first choices. This corresponds to the minimum egalitarian cost of 2n. But what is the maximum egalitarian cost of a stable matching? I couldn’t find it in the literature, so I proved that it is n(n+1).

Proof. It is easy to see that the egalitarian cost of n(n+1) is achievable. For example, if all men gave an identical ranking to the women, and vice versa, the matching algorithm will end up with couples having mutual rankings (j,j) for different values of j. Another example is a Latin preference profile. Each woman ranks a man n+1−x whenever he ranks her x. In this case, every potential couple’s mutual rankings sum to n+1. Thus, any matching for such rankings ends up with the egalitarian cost of n(n+1).

The next step is to prove that the egalitarian cost can’t be greater. Suppose the cost of a stable matching is C and is greater than n(n+1). Then, for every person, we count the number of people who are better (ranked smaller) than their assigned partner and sum these numbers over all the people. The result must be C−2n, which is the number of pairs of people of opposite genders such that the first person prefers the second one over their assigned partner. Moreover, the result is greater than n(n−1).

The total number of possible couples is n². Thus, the number of unrealized potential couples is n(n−1). We can conclude that we counted one of these unrealized couples twice. In such a couple, two people prefer each other over their assigned partners. Thus, they form a rogue couple, contradicting our assumption that the matching is stable.