Tanya Khovanova's Math Blog

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.

What’s a polyomino? A polyomino is a plane geometric figure formed by joining one or more equal squares edge to edge. Here, we have a puzzle about a polyomino that is almost a rectangle.

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 in the picture. The task is to cut the resulting shape into two congruent polyominoes.

Here’s another brainteaser from my friend, Alexander Karabegov.

Puzzle. Place the numbers from 1 to 8 at the vertices of a cube so that each face is balanced. On a balanced face, the sum of the numbers at the ends of one diagonal equals the sum of the numbers at the ends of the other diagonal.

My friend, Alexander Karabegov, sent me one of his puzzles. I love the mixture of algebra and calculus.

Puzzle. Describe a real quadratic function f such that the graph of its derivative f′ is tangent to the graph of f.

My former student, Xiaoyu He, invented this elegant puzzle and shared it with me.

Puzzle. We’ve got a murder mystery on our hands. There are four suspects, and it’s pretty clear that one of them is the actual murderer. But here’s the twist: there are also four witnesses who know who the killer is. Now, three of these witnesses are the honest type, always telling the truth, but the fourth one always lies.
You get to ask each of these witnesses a single yes-or-no question, and your question must be, “Is the murderer among this group of suspects?” You can choose any group of suspects you want. The challenge is to figure out who the murderer is.
Can you take it up a notch and determine the murderer if you have to list all your questions before getting any of the answers?

The Ural Math Battle in 2016 had several mafia-themed problems of various difficulty with the same initial setup.

Puzzle Setup. Among 100 residents of Saint-San, m are mafiosi, and the rest are civilians. A commissioner arrived to the town after getting this information. In an attempt to expose the mafia, this commissioner asked each of the residents to name s mafia suspects from among the other 99 residents. The commissioner knows that none of the mafiosi would name other mafiosi, but each civilian would name at least k mafia members. What is the maximum number of mafia members the commissioner can definitively identify after his survey?

1. The most difficult case was m = s = 3 and k = 2.
2. In the next case, where m = 3 and s = k = 2, the puzzle had a different task: prove that the commissioner can find at least one mafioso.
3. In the third case, where m = s = 10 and k = 6, the question was whether the commissioner can find at least three mafiosi.
4. In the fourth case, where m = s = 10 and k = 7, the question was whether the commissioner can find all the mafiosi.
5. The last case was for younger students with m = 6, s = 10, and k = 6. The question was whether the commissioner can find all the mafiosi.

When I asked ChatGPT to translate the first and the most difficult case of this puzzle from Russian, ChatGPT decided to solve it too. At the end of its ridiculous solution, it concluded that the commissioner could identify all 21 mafiosi out of the given 3. So, if you comment on this blog that the answer to the first case is 21, I will know that you are a bot.

I recently saw another puzzle on Facebook, a generalization of a problem from the 2002 Belarus Olympiad. In the problem, there are red and white boxes. Given how Russia and Belarus are filled with propaganda, my first question was whether the Belarusian flag was red and white. But in fact, the official flag is red and green; however, the opposition uses a red and white one. It could either be a coincidence or a sneaky way of protesting. Anyway, here is the problem.

Puzzle. There are two boxes filled with candy. The red box has R candies, and the white box has W candies. Alice and Bob are playing a game where Alice starts, and both players have the same options each turn: Either move one candy from the red box to the white box or take two candies from any box and eat them. The player who can’t move loses. For which values of R and W is each of the following true?

• Alice, following her optimal strategy, wins but might lose if she makes a mistake.
• Alice wins no matter what.
• Bob, following his optimal strategy, wins but might lose if he makes a mistake.
• Bob wins no matter what.

The list of options is weird, but I decided to keep it to emphasize …. Oops, I do not want to spoil it. You can decide for yourself what I wanted to emphasize.

I was browsing my analog archives, my high-school notes, and stumbled upon a couple of problems from a math battle we had.

Puzzle. A square is divided into 100 pieces of the same area, in two ways. Prove that you can find 100 points such that each piece in the first division has a point inside, and each piece in the second division also has a point inside.

Puzzle. There is a finite number of points on a plane. All distances between any pairs of points are distinct. Each point is connected to its closest neighboring point. Prove that each point is connected to no more than 5 points.

I used to love math problems about weighing things. But then I got distracted by my own personal scale with its slowly rising numbers. However, having recently lost a few pounds, I want to get back to other scales!

Puzzle. You have a balance scale that is broken in a consistent way: if you put two objects on its two pans, the scale will show you that the left pan is heavier, lighter, or the same weight as the right pan, but it may be wrong. However, it will give the same answer each time you repeat this test with the same two weights. You have a bag of flour and a 1-kilo weight. How can you use this scale to measure out 1 kilo of flour?

Puzzle. This time, your scale is not broken, and, moreover, it is not a balance scale but a digital one that tells you the weight of the objects you put on it. The scale does have a quirk. It can only measure two objects at a time. You have 13 coins of potentially different weights. How can you figure out the total weight of the 13 coins in 8 measurements?

The next puzzle was sent to me by Konstantin Knop, a coin puzzle master. This time there is no physical scale involved; rather, some sort of god answers your questions.

Puzzle. 26 identical-looking coins are arranged in a circle. Two of the coins which are next to each other are fake. You are allowed to pick any set of coins and ask how many fake coins are in the set. What is the smallest number of questions you need to find both fake coins if you only get the answers after you have posed all your questions?

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.