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.

---

Share:

I stumbled upon a cute puzzle on Facebook which originally came from a new book, Creative Puzzles to Ignite Your Mind by Shyam Sunder Gupta.

Puzzle. We have four identical boxes. One of the boxes contains three black balls (BBB), another box has two black and one white balls (BBW), the third box has one black and two white balls (BWW), and the last box has three white balls (WWW). Four labels, BBB, BBW, BWW, and WWW, are put on the boxes, one per box. As is often the case in such puzzles, none of the labels match the contents, and this fact is common knowledge. Four sages get one box each. Each sage sees his label but doesn’t know the other’s labels. Without looking in the box, each sage is asked to take out two balls and guess the color of the third ball. All the sages are in the same room and can hear each other and see the colors of the balls that are taken out.

• The first sage takes out two black balls and says, “I know the color of the third ball.”
• The second sage takes out one black and one white ball and says, “I know the color of the third ball.”
• The third sage takes out two white balls and says, “I don’t know the color of the third ball.”
• The fourth sage says, without taking out any balls, “I know the color of all the balls in my box and also the content of all the other boxes.”

Can you figure out what’s in the boxes?

---

Share:

After I crocheted Whitney Umbrellas, I got excited that I figured out how to crochet through an existing layer of fabric. I decided to use my skills to crochet “correct-er” Klein bottles.

A Klein bottle is a cool mathematical surface with only one side, similar to the Möbius strip. Unlike the strip, the Klein bottle has no border making it a non-orientable manifold. The problem in making Klein bottles is that the Klein bottle can’t be embedded into 3D space. Thus, all 3D models of Klein bottles have to self-intersect. But all the models that I saw, including glass models and crocheted hats that you can buy at ACME Klein Bottle, have holes.

I realized that my method of crocheting through might allow me to make more accurate models of Klein bottles, ones without holes.

Now it is time to spill my secret. The idea is easy, the implementation is not. The two pictures show the same yellow cylinder crocheted through a green square, viewed from different angles. I crocheted the green square first, then half of the yellow cylinder. Afterwards, I had to pull the whole ball of yellow yarn through a tiny hole in the middle of the green square. Then, with my hook, I pulled each yellow stitch from one side of the green square to the other side through its own tiny hole and finished the stitch on the new side. In the third picture, you can see my Klein bottle made in two colors. You might be able to see the second color inside instead of a hole.

I invented this method while crocheting Whitney’s umbrellas. I had to pull the whole ball of yarn through a tiny hole once per row. I still remember the tediousness of it with dread.

After the bottles, I decided to try projective planes. In the fourth picture, you can see two projective planes and two projective planes with holes. For the former, I started with the bottom hemispheres, and for the latter with cylinders. I didn’t need to crochet through or pull yarns through tiny holes. I just crocheted one row across the other. I left the easiest crochet task for last!

---

Share:

I do not like odd-one-out puzzles. This old and famous example is one of the reasons why. When given the list: skyscraper, cathedral, temple, and prayer, people usually pick “prayer” as the odd-one-out because it’s not a building. On the other hand, when the order is prayer, temple, cathedral, and skyscraper, people would pick “skyscraper” as it is not related to religion.

I created several pairs of questions that might have a similar issue: the answer depends on how the list is ordered.

Odd-one-out dilemma. Pick the odd-one-out from:

• Pen, book, notebook, tissue.
• Tissue, notebook, book, pen.

Odd-one-out dilemma. Pick the odd-one-out from:

• Banana, apple, orange, grape, lime, nectarine, artichoke.
• Artichoke, nectarine, lime, grape, orange, apple, banana.

Odd-one-out dilemma. Pick the odd-one-out from:

• 6, 3, 15, 9, 5.
• 5, 9, 15, 3, 6.

---

Share:

I buy almost everything on Amazon. Recently, I ordered a back stretcher. It took half an hour to assemble, and after the first use, it changed shape. However, this story is not about quality but about a card that was included with the item.

In the box, I found a gift card that wasn’t a gift card but rather a promise of a $20 Amazon gift card for a 5-star review. Hmm! A bribe for a good review.

I looked at the card more closely, and it had the following text.

WARM TIPS: Please DO NOT upload gift card pictures in the review; it will affect your account.

This is not only a bribe. It contains a threat.

Initially, I assumed it was Amazon, but it makes more sense that the company making this thingy is behind it. I gave Amazon the benefit of the doubt and went to their website to leave a 1-star review. I related the card’s story to warn others that the 5-star reviews can’t be trusted. Amazon rejected my review as it didn’t comply with their guidelines. Is Amazon in on it?

I wrote a different 1-star review, which did comply. It seems I can complain about the product, but I can’t complain about the bribe and threat.

I called Amazon’s customer service, and they promised to investigate. This was three months ago. This crappy product, with a stellar average 4.6 rating, is still out there.

---

Share:

* * *

The teacher asks a student,
“Johnny, how much will your mom pay at the market for three pounds of apples if one pound is three dollars?”
“I do not know,” answers Johnny, “My mom loves bargaining, and she is good at it.”

* * *

The teacher asks a student,
“Johnny, in a 5-story building, you have to go up 30 stairs to get from one floor to the next. If you go from the first to the fifth floor, how many stairs do you have to take?”
“All of them,” answers Johnny.

* * *

The teacher asks a student,
“Johnny, you have 10 dollars in your pocket. You ask your dad for 10 more. How much money will you have?”
“I will have 10 dollars.”
“You do not know your math!”
“You do not know my dad!”

Share:

I am sure I was fooled many times on April Fool’s Days. But I do not remember any stories, except one. It was quite painful and had a lot of potential for humiliation.

I was in high school, and our school didn’t have enough rooms for all the classes. So that particular semester, our classes happened during the second shift: from 2 pm to 8 pm.

One day, I received a call from my friend that school was canceled the following day. My friend told me that I had to notify half of the class. We had about 40 students in our class. She would call everyone whose last name started with the letters A through N, and I would have to call everyone else.

To set the stage, I was really, really shy. Calling people was torture. On the other hand, I was a very responsible person. So, I was walking in circles around our family’s phone with my hands shaking. Then, suddenly, a light bulb went off in my head: the day was April 1st.

It was a great excuse: if I told people not to come to school, they might not believe me. Hooray! I can procrastinate until the next day. Because we wouldn’t start until 2 pm, I would have enough time to notify everyone in the morning.

When I woke up the next day, the other light bulb went off: I didn’t need to call anyone; but I definitely had to have a chat with my “friend.”

---

Share:

I am deeply fascinated with my family’s history, so I took it upon myself to enlighten my children about our family tree. One day my son retorted, “This is not a family tree; this is a family bush.”

He was right. I was married three times and had a child from two of my three husbands. My ex-husbands had other children. So our family “tree” branches out in chaotic and weird ways. My two sons are half-brothers, and each of them has other half-siblings. With mathematics all around them, my sons decided to quantify their family connections: they named a half-sister of a half-brother a quarter-sister.

I didn’t have any children with my first husband, Alexander. But he remarried after our divorce and had two children. I’ve never met Alexander’s offspring, but my children hang out with them. Go figure! This is not just because the world is too small; rather, my exes are mathematicians and work with each other. So, theoretically, if Alexander and I had a common child, Alexander’s children would have been quarter-siblings to my sons. In real life, we didn’t have a child. Still, can my sons call Alexander’s children virtual quarter-siblings?

Share:

My new logic puzzle happens in the usual place: an island with truth-tellers and liars. Truth-tellers always tell the truth, while liars always lie. The liars on this island are dedicated to their lies: they do not want other people to figure out that they are liars and want to confuse people with their responses as much as possible. They also are cooperative: they coordinate their answers. The islanders all know each other and who is who.

Puzzle. A stranger arrives on this island with a plan. Each time the stranger hangs out with a group of people, he will ask each person the same question:

How many truth-tellers are in this group?

The liars on this island discover the stranger’s plan, and, being cooperative and dedicated, they do not want the stranger to figure out the true answer to his question. They also do not want the stranger to know anyone’s identity. What should they say?

For starters, any dedicated liar should always provide a theoretically possible answer. The liar shouldn’t say, “three quarters” or “infinitely many”, as these are obvious lies. In addition, the answer “zero” is too revealing: a truth-teller would never say this. Thus, the liar would answer with a positive integer that doesn’t exceed the total number of people in the group.

Suppose, for example, the stranger meets three people. Then there could be 0, 1, 2, or 3 truth-tellers in the group. As we discussed before, everyone replies 1, 2, or 3.

If there are t truth-tellers in the group, then the answer t is repeated exactly t times. That means the following sets of three answers reveal that all three islanders are liars: {1,1,1}, {1,1,2}, {1,1,3}, {2,2,2}, and {2,3,3}. With the following sets of answers, the stranger can figure out who is the only truth-teller: {1,2,3} and {1,3,3}. The set {2,2,3} allows the stranger to find both truth-tellers. And the following sets of answers do not allow the stranger to figure out who is who: {1,2,2} and {3,3,3}. So those sets of answers are the ones the liars will choose.

To sum up, the best strategy is for all the liars in the group to answer x, where x is the number of liars. Meanwhile, all the truth-tellers would say: 3 − x. That way, the stranger cannot differentiate between the truth-tellers and the liars.

The strategy above works with a group of any size as long as the number of liars is not equal to the number of truth-tellers.

Bonus Puzzle. Is there a way to confuse the stranger when the liars make are half of the group?

---

Share:

Another gem posted by Konstantin Knop on Facebook.

Puzzle. The Vicious Dragon captured two princesses, Evangelina and Oddetta, and placed them in different towers in his castle. Then the Vicious Dragon flipped a fair coin an infinite number of times. He informed Evangelina of all the results of the even tosses and Oddetta of all the results of the odd tosses. Next, the Dragon asks each princess to name the number of any toss whose result is unknown to her. In other words, Evangelina must name an odd number, and Oddetta must name an even number.
If the tosses named by Evangelina and Oddetta are the same (both are tails or both are heads), the Vicious Dragon gives each princess a cake and a pink plush bunny and sets them free. But if the results differ, the Vicious Dragon devours Evangelina and Oddetta with cranberry jam. The Dragon loves princesses and cranberry jam!
The princesses know the Vicious Dragon’s habits and could have agreed on strategies in advance. What are the chances of the princesses escaping if Oddetta names a number first, and Evangelina names her number, knowing which number Oddetta chose?

---

Share: