Tanya Khovanova's Math Blog

Here is another lovely problem from a prolific problem writer, Alexander Shapovalov.

Problem. Every cell of a 7 by 7 chessboard has a gnome standing on it. For every pair of gnomes whose cells share an edge, their beards’ lengths differ by no more than 1 inch. Now, we take these gnomes and sit them around a table. Prove that we can do so in a way that any two gnomes sitting next to each other have their beards’ lengths differ by no more than 1 inch.

A standard chessboard is 8 by 8. Why would this problem have a 7 by 7 board? Let’s see.

For even-sized boards, the problem is easy. I will explain why, but first, let me construct a graph related to a board, in this case, any board.

Each cell is a vertex, and two vertices are connected by an edge if the corresponding cells are orthogonal neighbors (share an edge) on the board. A cycle that goes through a graph and visits every vertex exactly once is called a Hamiltonian cycle. A Hamiltonian cycle is a potential way to sit the gnomes around the table and solve the problem. When we sit the gnomes in a circle following a Hamiltonian cycle, two neighbors at the table are also neighbors on the board, and so they have their beards’ lengths differ by no more than 1 inch.

The problem is easy for even-sized boards because it is easy to draw a Hamiltonian cycle on them. An odd-sized chessboard can’t have a Hamiltonian cycle. To prove this, let me color the board in a checkerboard manner. Then, cells that share an edge are different colors. And you can’t make a cycle through the board, where you switch colors at each step, but the total number of steps is odd.

It follows that for odd-sized boards, it is impossible to solve the problem by just connecting neighboring cells on the board. There should be another way. Can you find it?

I want to discuss a problem from a test I gave recently.

Problem. My dog, Fudge, likes books. He brought two books to his corner in the morning and three more books in the evening. How many books will he read tonight?

As I expected, many students didn’t pay attention and just summed up the two numbers in the problem and gave five as the answer. Here are three answers that I especially liked.

Answer 1. Zero, because most dogs can’t read.

This cautious student added most to be on the safe side.

Answer 2. You cannot tell how many books he will read. Just because he brings books to his corner doesn’t mean he will read them.

The second answer demonstrates great logical thinking, were Fudge a human. But the third answer made me laugh.

Answer 3. Three. If he brought three more books to his corner in the evening, it means he finished the two from that morning, so there are three books left for him to read.

Thinking about genders, we used to have only two options: male and female. Now we have more. I have a lot of young acquaintances who are non-binary. So I started to rethink my gender identity.

I was a typical girl: at least, I thought I was. I hated playing with boring dolls. I preferred cars, or even better, construction sets and board games. In second grade, I wanted to be a ballerina but later fell in love with Sherlock Holmes. My dreams switched to becoming a detective or a spy. In fifth grade, I signed up for rifle-shooting training. That same year, my school forced me to compete in an orienteering event, and I won.

Orienteering became my favorite sport, and I did it for many years. I was really good with maps. I would go to a competition, leisurely walk my course and win. Other kids were running around like crazy, but I always knew where to go and was overall faster than them. With time, other kids learned to read maps better, but I myself never learned to run faster. So I stopped winning, but I enjoyed the sport anyway.

It goes without saying: I loved math. Solving math problems was the best entertainment ever.

Later, to my surprise, I discovered that most girls liked shopping and wasted a lot of time on make-up. Not many girls were even interested in math. I actually liked that. I started having crushes on boys since second grade and enjoyed being the only girl in math clubs, having all these nerds to myself.

I grew up in Soviet Russia. While growing up, I wasn’t bombarded with gender stereotypes. My first eye-opening experience was when I was 17 years old. My long-time boyfriend knew that I liked mathematics, and this was okay. But when I told him that I planned to go to college to study mathematics, he didn’t approve. I broke up with him on the spot.

My mom used to tell me that most men do not like brainy women. My reply was that there are more men who like brainy women than brainy women. I got a new boyfriend the day after my breakup.

My gender identity didn’t bother me much in Russia. What bothered me was the Russian tradition for both spouses to work, but the house chores and child-rearing duties fell only on women. I read somewhere that, on average, in Russia, women worked for 4 hours a day more than men. Life was unfair to women but not to their self-esteems.

As I said, I grew up thinking I was a typical girl until I came to the US. This happened 30 years ago, and I was 30 at the time. In the US, I got bombarded with gender stereotypes: they made me feel inadequate and doubt my femininity. Just for reference: by that time, I was in my third marriage breastfeeding my second child. Still, according to those stereotypes, I was not a real woman.

For some time, I wondered what was wrong with me. Then, I was elated to find a book called Brain Sex: The Real Difference Between Men and Women by Anne Moir and David Jessel. (This was many years ago.) Among other things, this book talks about the differences between men and women with respect to the brain. According to the book, men are better on average at abstract thinking and spatial visions, aka math and maps. Women, on the other hand, are better at connecting with people and have higher social intelligence. Boys are less interested in games related to storytelling, aka dolls, preferring more concrete activities. And so on.

The book also describes situations in which girls don’t fit the paradigm. The authors attribute this variation to the mother’s hormones during pregnancy. I found myself described perfectly in the section titled “girls who have been exposed to male hormones in the womb.” I am pretty sure that my mom didn’t take any hormone supplements while pregnant with me back in Soviet Russia. On the other hand, the description in the book was spot-on.

This book classifies me as “a male brain in a female body.”

I was glad to find myself after a period of self-doubt. I was glad that I wasn’t alone and even fit into a special category with a name.

Several years later, I met Sue Katz, a writer who also has a blog Sue Katz: Consenting Adult. She made me realize how ridiculous the whole story was: I was pressured by gender stereotypes to feel bad about myself. Then I was grateful for a book based on those same stereotypes, only because it described women like me and gave me permission to exist. I liked the book because I accepted those stereotypes in the first place. If there were no stereotypes, there wouldn’t be any problems at all.

Why can’t I just be me?

Over the past few years, I have become happier than I have ever been. I do not care what society thinks about my gender. I am no longer ashamed of not feeling 100 percent female.

I like that people in the modern world embrace the idea of individuals being themselves. For example, my daughter-in-law, Robin Dahan, designed a whole line, You-Be-You, for her company, Dash of Pep.

Am I non-binary? I do not know and do not care. I am just me, proudly wearing my You-Be-You socks.

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.

Here is an old goodie.

Puzzle. A criminal is sentenced to death. He is offered the last word. He is allowed to make one statement. If the statement is true, the criminal will be electrocuted. If the statement is false, he will be hanged. Can you find a good piece of advice for this man?

The standard answer to this puzzle is for the criminal to say, “I will be hanged.” This creates a paradox. If he is hanged, the statement is true, and he should be electrocuted. If he is electrocuted, the statement is false, and he should be hanged.

Thinking about it, any paradox works. If the man says, “This statement is false,” then the type of punishment he gets can’t be determined.

Thinking about it some more, asking a question instead of making a statement will confuse his executioners all the same.

One of my students advised the criminal to stay silent. This was not my favorite solution, as staying silent requires some concentration. My favorite solution was the statement, “It will rain exactly a thousand years from now.” This way, the criminal can relax, at least for a thousand years.

Today I discuss ideas for solving the puzzle I posted previously in my blog: A Scooter Riddle.

Riddle. Alice, Bob, and Charlie are at Alice’s house. They are going to Bob’s house, which is 33 miles away. They have a 2-seat scooter that goes 25 miles per hour with 1 rider, or 20 miles per hour with 2 riders. Each of the 3 friends has a walking pace of 5 miles per hour. What is the fastest time that all three of them can end up at Bob’s house?

Let’s start.

• The scooter and the three people should always be on the move. Moreover, whenever the scooter moves towards Bob’s house, it should carry two people, and only the driver should be on the scooter whenever it is going back.
• We do not care about each individual’s path: whenever people meet at the same place at the same time, we can swap them. Therefore, we can assume that the scooter’s driver is the same person at all times.
• Thinking about it, we can ignore the scooter’s driver and assume that the scooter is self-driving, and there are only two people, Alice and Bob, who need to get to Bob’s house.
• If Alice and Bob arrive at Bob’s house at different times, there is room for improvement: the fastest person should have used the scooter less and walked more, allowing the other person more use of the scooter. Hence, we can assume that they arrive at Bob’s house simultaneously.
• Without loss of generality, we can assume that Alice starts on the scooter first.
• So the scooter should carry Alice for some time, drop her off, come back for Bob, then drop him off, come back for Alice, and so on. Without loss of generality, we can combine all scooter trips by the same person into one ride.
• Thus, the plan is the following. The scooter drives Alice for x hours, drops her off, and she finishes on foot. Meanwhile, Bob starts on foot. The scooter goes back after dropping off Alice, picks up Bob, and drives him x hours the rest of the way.

Now this is just algebra. Each person covers 20x miles on the scooter and 33 − 20x miles on foot. The walking takes 33/5 − 4x hours. Thus the total trip for each person takes 33/5 − 3x hours.

Now we calculate what the scooter does. The scooter covers 20x miles with Alice and the same number of miles with Bob. It covers 40x − 33 miles alone. Thus the scooter spends 2x + (40x − 33)/25 hours in transit. The two times must be the same. So we have an equation: 6.6 − 3x = 2x + 1.6x − 1.32. Thus, x = 1.2, and the answer to the puzzle is 3 hours.

If you can figure out my number without the Internet, call me.

• The number of letters in the first name of Anna Karenina’s love.
• The number of times the word nevermore appears in the famous poem, subtracted from the month when the events took place.
• The only number in the title of a Bergman movie.
• The number of vowels in the original and more historically meaningful name for the sorcerer’s stone in Harry Potter books.
• The number of vertices of the other geometric shape in “Girl on a Ball”.
• The cube root of the age mentioned in one of the earliest Beatles songs.
• The number corresponding to the lexicographically first string representing an integer in English.
• The first digit of the age at which Pushkin and Mozart died.
• The smallest of two primes such that their sum and difference are also prime.
• The only triangular number that is also prime.

(Just in case: this is a joke and not my actual phone number.)

This is my second crocheting project to help finance our new program, Yulia’s Dream, in honor of Yulia Zdanovska, a young Ukrainian math talent killed in the war.

I made four Whitehead links in the colors of the Ukrainian flag. You can read about my other crocheting project in my previous post: Hyperbolic Surfaces for Ukraine.

Fun trivia about the Whitehead links.

• Why are these links so famous? They are the simplest non-trivial links with the linking number zero.
• What’s the linking number? The linking number is an invariant of a link. If two loops are not linked (they are called an unlink), their linking number is zero. If they are linked, then their linking number is usually not zero. Here the loops are linked, but the linking number is nevertheless zero. Thus, the linking number can’t differentiate this link from an unlink. To explain how to calculate the linking number, I need to explain another simpler invariant: the crossing number.
• What’s the crossing number? The crossing number is the smallest number of crossings when projecting the link on a plane. The top two pictures have 6 crossings, and the bottom two pictures have 5. The top two pictures emphasize the symmetry of the link, and the bottom two pictures have the smallest possible number of crossings for the Whitehead link. So the crossing number of the Whitehead link is 5.
• Can you now explain how to calculate the linking number? One way to calculate the linking number is to choose directions for the blue and yellow loops and select the crossings where the blue is on top. After that, following the chosen direction of the blue loop, at each crossing with the yellow loop, check the latter’s direction. If the direction is from right to left, count it with a plus and, otherwise, with a minus. The total is the linking number. In the case of the Whitehead link, it is zero.
• Is there a more elegant explanation for why the Whitehead link has the linking number zero? Yes. The linking number only looks at the crossings of two different strands and ignores self-crossings. If you look at the two bottom pictures, there is one self-crossing of the blue loop. Now imagine you change the crossing by moving the top blue strand underneath. After such a transformation, the crossing number doesn’t change, but the loops become unlinked. Thus, the linking number of the Whitehead link must be zero.

As you might know, my team started a project, Yulia’s Dream, in honor of Yulia Zdanovska, a young Ukrainian math talent killed in the war.

In this program, we will do what we are great at — help gifted youngsters pursue advanced math. To help the program, I started crocheting hyperbolic surfaces in the colors of the Ukrainian flag. These crochets are designed as gifts to encourage individual donors.

Fun trivia about these hyperbolic surfaces.

• Why are these surfaces so famous? These surfaces prove that Euclid’s fifth axiom is independent of the other four axioms. The fifth axiom (also known as the parallel postulate) says that if there is a line L and a point P outside of L, then there is exactly one line through P parallel to L. On these hyperbolic surfaces, the first four of Euclid’s axioms hold, while the fifth one doesn’t: if there is a line L and a point P outside of L on such a surface, then there are infinitely many lines through P parallel to L.
• But what is a line on a hyperbolic surface? A line segment connecting two points is defined as the shortest path between these points, known as a geodesic.
• How can such a surface be crocheted? I crocheted a tiny circle and continued in a spiral, making 6 stitches in each new row for every 5 stitches in the previous row. This means that each small piece of the crocheted surface is the same throughout the thingy, making these thingies hyperbolic surfaces of constant curvature.
• What is the constant curvature good for? Constant curvature makes it easy to find lines. You can just fold the thingy, and the resulting crease is a line.
• Is this thingy a hyperbolic plane? No. A cool theorem states that a hyperbolic plane can’t fit into a 3D space, so whatever someone crochets has to be finite. On second thought, anything someone crochets has to be finite anyway. But I digress. This shape can be viewed as a disc with a hole.
• The Ukrainian flag is half blue and half yellow, so why do the colors here seem so unevenly distributed? My goal was to use the same amount of blue and yellow yarn per thingy. I leave it as an exercise for the reader to calculate that regardless of how many rows of one color I crochet, to use the same amount of yarn in the second color, I need more than 3 and less than 4 rows of that color. Since I wanted the thingy to be symmetrical, sometimes I had 3, and other times, I had 4 rows of the second color. I also made 4 surfaces where I switched colors every row.

Overall, I crocheted 10 hyperbolic surfaces. If you are interested in donating to help Ukrainian students receive coaching from our program at MIT, the details will be announced on our website shortly.

What is base 3/2? One of the ways to define such a base is to think of it in terms of exploding dots. What the heck are exploding dots? They are explained and popularized by James Tanton in his YouTube videos.

Essentially, “exploding dots” is a machine made of a row of boxes with rules describing how the dots loaded into the machine explode. As an example, let me describe the 1←2 machine, which corresponds to base 2. We load N dots into the rightmost box. Whenever there are 2 dots in one box, they explode into 1 dot in the box to the left.

For example, to write 5 in base 2, we would first load 5 dots in the rightmost box, as in the figure above. Then each group of 2 dots in the rightmost box would explode, and for each group, 1 dot would appear in the box to the left. Finally, the 2 dots in the second box would explode into 1 dot into the next box to the left. By reading the number of dots from left to right, we get 101, which is 5 in base 2.

The interesting thing here is that there is no reason this model should be exclusive to integer bases. Suppose our rule is that 3 dots explode into 2 dots in the box to the left. Such a rule is called the 2←3 machine, and it corresponds to base 3/2. To represent 5 in this base, we load 5 dots into the rightmost box, then we use the exploding rule shown in the figure below. Using this machine, 5 is represented in base 3/2 as 22.

The figures were made by my junior PRIMES STEP group, in the 2017-2018 academic year, for our paper, Variants of Base 3 Over 2.

But, in this post, I want to discuss a different paper from the same academic year. With my senior PRIMES STEP group, we wrote a paper On Base 3/2 and its Sequences. A shorter version which includes a tribute to John Conway, appeared in The Mathematical Intelligencer.

Speaking of John Conway, he liked inventing new sequences, especially ones with unusual behaviors. One of his hobbies was tweaking the Fibonacci rule to create new sequences, which he called Fibs. For example, the sorted Fibs sequence starts the same as the Fibonacci sequence with 0 and 1. To calculate the next term, we add the two previous terms and sort the digits in non-decreasing order. In base 10, this sequence is A069638: 0, 1, 1, 2, 3, 5, 8, 13, 12, 25, 37, 26, …. It is known that this sequence is periodic with a maximum value of 667.

With my senior PRIMES STEP group, we studied analogs of this sequence in base 3/2. We begin with the sorted Fibs sequence f_n with the same two initial values that start the Fibonacci sequence: f₀ = 0 and f₁ = 1. To calculate f_n+1, we add f_n-1 and f_n in base 3/2 and sort the digits in non-decreasing order. It follows that the numbers in the sequence are written as several ones followed by several twos. Unlike base 10, the sequence is not periodic and grows indefinitely: 0, 1, 1, 2, 2, 12, 12, 112, 112, 1112, 1112, 11112, …. In recognition of the constant growth of this Fibs sequence, we call it the Pinocchio sequence.

Obviously, you can start the sorted Fibs sequence with any two numbers. But we proved an interesting theorem which stated that any sorted Fibs sequence eventually turns into either the tail of the Pinocchio sequence or the 3-cycle 112, 1122, 1122.

However, we didn’t stop there. There are two natural ways to sort the digits of a number, in increasing or decreasing order. Naturally, there is another type of sequences worth considering, in which the digits are sorted in non-increasing order. We called such sequences the reverse sorted Fibs.

We defined the reverse sorted Fibs sequence r_n in base 3/2 as follows. To calculate r_n+1, we add r_n-1 and r_n in base 3/2 and sort the digits in non-increasing order, ignoring zeros. It follows that after the initial terms, the terms of such a sequence are represented with several twos followed by several ones. We call the reverse sorted Fibs that start in a similar way to the Fibonacci sequence with r₀ = 0 and r₁ = 1, the proper reverse sorted Fibs. Here are several terms of the proper reverse sorted Fibs: 0, 1, 1, 2, 2, 21, 21, 221, 2211, 221, 221, 2211, 221, 221, 2211, …. This sequence becomes cyclic, starting from r₇.

We also found one reverse sorted Fibs growing indefinitely: 2211, 2211, 22211, 22211, 222211, 222211, and so on. We proved that any reverse sorted Fibs sequence eventually turns into either this sequence or a 3-cycle sequence: 221, 221, 2211. The similarity between the sorted Fibs and the reverse sorted Fibs surprised us. Up to the initial terms, they both have exactly one sequence which grows indefinitely and one 3-cycle. To emphasize this similarity, we reversed the word Pinocchio and named this growing reverse Fibs sequence the Oihcconip sequence.

Now I need to figure out how to pronounce the name of this new sequence.