This blog has a modern version at http://blog.tanyakhovanova.com/, where you can leave comments. This page contains the copies of 79 blog entries for 2022. The latest essays are at http://www.tanyakhovanova.com/MathBlog.html
I stumbled on this puzzle on Facebook the day of the World Cup finals. How timely!
Puzzle. Sixteen teams play a single-elimination tournament, where the losing team is immediately out. The teams have different rankings, and a higher-ranking team always wins against a lower-ranking team. The initial seeding is random.
In the semifinals, A won against B, and C won against D. Given that B is stronger than D, what is the probability that A will become the champion?
Consider a group of people in which some are friends. We assume that friendship is symmetric: if Alice is Bob's friend, then Bob is Alice's friend. That means we can build a friendship graph where vertices are people and edges correspond to friendships. Let's assume that every person has at least one friend, so the friendship graph doesn't have isolated vertices.
Darla needs to conduct research by surveying random pairs of friends. But first, she has to find those pairs. To ensure that the pairs are randomly selected, she must pick two random people from the group, contact them, and ask them whether or not they are friends. If they are, she gives them her questionnaire. If not, Darla wasted tons of time and had to keep looking.
The group she is surveying is enormous. So, when she picks two random people, they typically have never even heard of each other. Bother!
Darla decides to speed up the process. She would pick a random person, ask them for a list of friends, and then randomly pick one person from the list. Since every person has at least one friend, Darla always ends up with a filled questionnaire.
Puzzle question. Why is Darla's method wrong? Can you describe the pairs of friends her method favors?
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 ≤ 1015), 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 even further: beyond gazillions. Let's consider what happens on m × n boards, where m is fixed, and n is astronomically large. Suppose fm(n) is the largest size of an uncrossed knight's closed tour on the m × n board and gm(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(fm) is defined as follows: D(fm)(n) = fm(n+1) - fm(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(f6)(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 f6(n) to know the function for any n.
Derek actually calculated the functions fm(n) and gm(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!
My former IMO coach, Gregory Galperin, converted a famous joke into a logic puzzle, adding a variation.
Puzzle. Ten logicians walked into a cafe. Each knew whether they wanted tea or coffee, but no one knew each other's preferences. When they sat at a table, the waiter asked loudly, "Will everyone be having coffee?" Then the waiter went around the table, writing down each person's answer.
There were three possible answers: "I don't know", "Yes", and "No". All answers were truthful and spoken loudly so that all group members heard them.
- Suppose the first nine people said, "I don't know", and the tenth person said, "Yes". How many of them wanted coffee?
- Suppose the sixth and the seventh answers were not the same. How many people said, "I don't know", how many said, "No", and how many said, "Yes". Find the smallest number of people who for sure would have ordered coffee and the smallest number who for sure would have wanted tea?
Here are some problems that I liked from the YuMSh (Youths Math School in St. Petersburg) Olympiad.
Problem for 6th grade. Twenty people from an island of knights and knaves have a party. Knights always tell the truth, and knaves always lie. Each party-goer got a card with a different number from 1 to 20. When they were asked about their numbers, each answered with a number from 1 to 20. The sum of all the answers is 156. What is the minimum possible number of liars that have to be at the party?
Problem for 7th grade. Alice and Bob bought a deck of playing cards (52 cards total) and took turns gluing the cards on the wall one at a time. Alice was first. The game is lost if, after a move, the wall has 4 cards of the same suit or 4 cards of consecutive values (for example, 8-9-10-jack). Can Alice or Bob guarantee themselves a win, regardless of their opponent's moves?
Problem for 7th grade. Buddhist monks gather in an infinite cave where a finite number of prime numbers are written on the wall. The numbers might not be distinct. Every second, one of the monks performs one of the following operations.
Every time they do it, they erase the old number and write the new one. The rule is that the new number has to be greater than the old one. If a composite number gets written on the wall of this cave, then the world collapses into nothingness. Can the monks save the world for eternity?
Problem for 8th grade. The incenter of a triangle is equidistant from the midpoints of the sides of the triangle. Prove that the triangle is equilateral.
Problem for 9th grade. Bob was given 30 distinct natural numbers. He wrote down all the 435 pairwise sums. It appears that among those sums, 230 are divisible by 3. How many of the original 30 numbers are divisible by 3?
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!
I wrote a lot about the inventiveness of my students. Here is more proof.
Puzzle. A police officer saw a truck driver going the wrong way down a one-way street but didn't try to stop him. Why?
Many of my students came up with the expected answer:
The truck driver was walking.
They also found some legit ways for a truck driver to not be stopped.
Some more ideas, rather far-fetched.
Some funny ones.
I often receive letters from parents of math geniuses — "My twelve-year-old is reading an algebraic geometry book: accept him to PRIMES," or "My ten-year-old finished her calculus course: here is her picture to post on your blog," or "My two-year-old knows the multiplication table, can you write a research paper with him?" The last letter was a sarcastic extrapolation.
I am happy to hear that there are a lot of math geniuses out there. They are potentially our future PRIMES and PRIMES STEP students. But, it is difficult to impress me. The fact that children know things early doesn't tell me much. I've seen a student who didn't know arithmetic and managed to pass calculus. I've also met a student claiming the full knowledge of fusion categories, which later appeared to be from half-watching a five-minute YouTube video.
There are a lot of products catering to parents who want to bring up geniuses. My grandson received a calculus book for his first birthday: Introductory Calculus For Infants. Ten years later, he still is not ready for calculus.
Back to gifted children. Once a mom brought us her kid, who I can't forget. The child bragged that he solved 30 thousand math problems. What do you think my first thought was? Actually, I had two first thoughts: 1) Why on Earth would anyone count all the problems they solved? 2) And, what is the difficulty of the problems he solved 30 thousand of?
From time to time, I receive an email from a parent whose child is a true math genius. My answer to this parent is the same as to any other parent: "Let your child apply to our programs. We do a great job at working with math geniuses."
Our programs' admissions are done by entrance tests. Surprisingly, or not surprisingly, the heavily advertised kids often do poorly on these tests. It could be that the parents overestimate their children's abilities. But sometimes, the situation is more interesting and sad: I have seen children who sabotage the entrance tests so as not to be accepted into our programs. We also had students give us hints on their application forms that they were forced to apply.
In the first version of this essay, I wrote funny stories of what these students did. Then, I erased the stories. I do not want the parents to know how their children are trying to free themselves.
Dear parents, do not push your children into our programs. If they do not want to be mathematicians, you are decreasing their chances of getting into a good college. Imagine an admission officer who reads an essay from a student who wants to be a doctor but wastes ten hours a week on a prestigious math research program. Such a student doesn't qualify as a potential math genius, as their passion lies elsewhere. Nor does this student qualify as a future doctor, as they didn't do anything to pursue their claimed passion. In the end, the student is written off as a person with weak character.
On the other hand, the students who do want to be in our programs, thrive. They often start breathing mathematics and are extremely successful. Encourage your children to apply to our programs if they have BOTH: the gift for mathematics and the heart for it.
This puzzle was in last week's homework.
Puzzle. How can an egg fly three meters and not break?
The expected answer:
Some students tried to protect the egg:
Other students specified qualities of an egg making it more resistant:
Here are some more elaborate explanations:
To conclude this essay, here is a punny answer:
I am so tired of spam emails. I keep thinking about how we can fight spam, and here is an idea.
Gmail should change its system: every email you send to me would cost 1 dollar, payable to me. We can add an exception for people on my contact list. Everyone else, pay up!
I do not often contact strangers. But if I do, it is always important. So paying 1 dollar seems more than fair. On the other hand, this system will immediately discourage mass emails to strangers. Spam would go down, and I would stop receiving emails inviting me to buy a pill to increase the size of a body part I do not have.
This idea of getting paid for reading an email is not new. It was implemented by Jim Sanborn, the creator of the famous Kryptos sculpture. Kryptos is located at the CIA headquarters and has four encrypted messages. People tried to decrypt them and would send Jim their wrong solutions. Jim got tired of all the emails and administered Kryptos fees. Anyone who wants Jim to check their solution, can do so by paying him 50 dollars. I wonder if Jim would still charge the fee if someone sent him the correct solution.
Thinking about it, I would like the payable email system to be customizable, so I can charge whatever I want. After all, I do value my time.
Gmail could get a small percentage. Either Gmail, together with me, gets rich, or spam goes away. Both outcomes would make my life easier.
Puzzle. A goat was on a 10-meter leash. Yet it managed to go 300 meters away from the post. How come?
The standard answer. The leash wasn't attached to the post.
My students scrutinized the puzzle and found some other possible ambiguities. For example, there might be two posts: the goat was leashed to one and was far away from the other. In another example, the timing is not given. It is possible that the goat was on the leash at one time and unleashed and far away from the post at another time. Here is my favorite answer.
My favorite answer. The goat ate the leash.
Puzzle. Find the largest and the smallest 4-digit numbers n such that when you erase the first two digits of n, you get the sum of the digits of n.
I recently posted a gnome puzzle by Alexander Gribalko.
Puzzle. Nine gnomes repeat the following procedure three times. They arrange themselves on a 3 by 3 chessboard with one gnome per cell and greet all of their orthogonal neighbors with handshakes. Prove that not all pairs of gnomes greet each other.
As often happens with my blog puzzles, I used this puzzle as homework for my students. They calculated that the total number of handshakes needed for all nine gnomes to greet each other is 36. On the other hand, each arrangement of gnomes creates 12 handshakes. This means that the numbers are tight: no greeting can be wasted, and every pair of gnomes need to greet each other exactly once. The students then studied different cases to prove this was impossible.
In each arrangement, a gnome can have either 2, 3, or 4 handshakes. Hence, we can distribute handshakes over three placements as 2+2+4 or 2+3+3. It follows that if a gnome is ever in the center of the grid, he has to be in a corner for the other two arrangements. Therefore, the three gnomes who end up in the center for one of the arrangements never greet each other.
However, I always love solutions that involve coloring the board in a checkerboard manner. Here is my solution.
Solution. Let's color the board in a checkerboard manner. We assign each gnome a binary string, of length 3, describing the colors of the cells where the gnome was in each placement. There are 8 different possible strings. It follows that at least two gnomes are assigned the same string. But they can't greet each other if they are standing on the same colors in each arrangement!
* * *
I hate getting into debates about Möbius strips. They're always one-sided.
* * *
North Korea's ballistic missile test failed due to a bug in Windows. The next missile containing a bug report has been automatically sent to Microsoft.
* * *
4 out of 3 people have trouble with fractions.
* * *
Do you know what seems odd to me?
Numbers that aren't divisible by two.
* * *
Why was algebra so easy for the Romans?
X was always 10.
My readers know that I love hat puzzles. This is why I decided to turn a number trick by Konstantin Knop (in Russian) into a hat trick.
Hat Trick. The audience has a bottomless supply of hats in ten different colors. They arrange ten people in a line and put one of the hats on each person. Then the magician's assistant comes in and removes a hat from one of the ten people. After that, the magician appears and, abracadabra, guesses the color of the removed hat. The magician and the assistant agreed on a strategy beforehand. What is it?
Keep in mind that this trick won't work with fewer than ten colors. As a bonus, can you explain why?
As my readers know, I am devoted to my students. When I need something I can't buy, I try to make it. That is why I crocheted a lot of mathematical objects. One day, I resolved to have in my possession a Seifert surface bounded by Borromean rings (a two-sided surface that has Borromean rings as its border).
However, my crocheting skills were not advanced enough, so I signed up for a wet and needle felting workshop. When I showed up, Linda, our teacher, revealed her lesson plan: a felted soap with a nice pink heart on top. It looked cool to have soap inside a sponge, not to mention that wool is anti-bacterial. But I had bigger plans than soap and eagerly waited for no one else to show up.
When my dream materialized, and, as I had hoped, no one else was interested in felt, I asked Linda if we could drop the hearty soap and make my dream thingy. She agreed, but my plan didn't survive for long. As soon as Linda saw a picture of what I wanted, she got scared. Seifert surfaces were not in the cards, so soap it was. I told her that there was no way I was going to needle-felt a pink heart onto my felted soap. I ended up with a blue Sierpiński gasket.
We had a great time. Linda was teaching me felting, and I was teaching her math. I am a good teacher, so even felters working on a farm enjoy my lessons.
After the workshop, I went online and found my dream surface on Shapeways. In the end, I was happy to just buy it and not have to make it.
But my felting workshop wasn't a waste of time: tomorrow I will wash myself with a gasket.
A combinatorial games section? At a math competition? I have never heard of it before. But here it is, at the Lomonosov Tournament. The first problem is from the 2012 Tournament (the link is to a Russian version). The problem is by Alexander Shapovalov. I picked it for its elegance and simplicity.
A rectangular band. You have a paper rectangle of size m by n with grid lines, where both m and n are greater than 1. Two players play the following game. The first player cuts the rectangle along any grid line into two rectangles. The next player picks one of the rectangles and cuts it again along a grid line, and so on. The winner is the player who, after their move, can arrange all the rectangles into a band of width 1. Which player is guaranteed a win regardless of the moves of their partner? Consider two cases.
- One of the numbers, m or n, is even;
- Both m and n are odd.
The next problem, by I. Raskin, is from the 2015 Tournament (in Russian). The problem is about fruits, and I know a lot of great puzzles with bananas and oranges, so I immediately got attracted to this one.
The original version had three types of fruit starting with the letters a, b, and c in Russian. They were oranges, bananas, and plums. I reused bananas and replaced oranges with apples, but I got stuck on the letter c. The players in this game eat their fruits, so using cantaloupes seemed like overkill. Plus, I am on a diet, so I decided on cherries.
Fruits. There are a apples, b bananas, and c cherries on the table. Two players play a game where one move consists of eating two different fruits. The person who can't move loses. Assuming the players use their best strategies, would the first or the second player win in the following cases?
- a = 1 (the answer might depend on the values of b and c);
- a = 6, b = 8, c = 10;
- a = 7, b = 9, c = 15;
- a = 19, b = 20, c = 21.
The last problem is from the 2012 Tournament (in Russian). It has great sentimental value for me, as it was created by John Conway. It also reminds me of the famous Frobenius (chicken McNugget) problem.
Coin mintage. Once upon a time, in a faraway kingdom, two treasurers were minting coins. They decided to make it into a game, taking turns minting coins. Each turn, the player chooses a particular integral denomination and mints an infinite supply of coins of this denomination. The rules of the game forbid choosing a new denomination that can be paid with the existing coins. The treasurer who is forced to mint a coin of denomination 1 loses.
- Prove that if the first treasurer starts with denomination 2 or 3, s/he loses.
- Is it profitable for the first treasurer to start with denomination 4?
- Is it profitable for the first treasurer to start with denomination 6?
- Suppose the first treasurer minted coins of denomination 5, and the second treasurer of denomination 6. What is the winning strategy for the first treasurer after that?
- Suppose the first treasurer minted coins of denomination 5, and the second treasurer of denomination k. Prove that the largest denomination available for minting is 4k − 5.
- Prove that the first treasurer can win by starting with denomination 5. (Hint: Suppose the second treasurer replied with denomination k, and the first treasurer minted 4k − 5 after that. If this strategy wins, the problem is solved. However, if after that, the second treasurer wins by minting denomination m, then minting denomination 4k − 5 was the wrong move. What was the right move?)
Here is another exciting puzzle posted on Facebook by Konstantin Knop.
Puzzle. Eight glasses of wine are placed in a circle on a round table. Three sages are invited to take the following challenge. In the presence of the first sage, five glasses are filled with good wine and the other three 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 three sages can agree on their strategy beforehand. What is the strategy to keep them all alive?
An extra question. Does a strategy exist if fewer than eight glasses are placed around the table?
Let's start with two trivial variations. If there is only one sage, s/he knows which glass to drink. Now, suppose there is only one poisoned glass and any number of sages. If the total number of good glasses is not less than the number of sages, the solution is obvious. The first sage drinks the glass clockwise from the poisoned one, and the other sages continue clockwise.
The next slightly less trivial case involves two sages and two poisoned glasses. If the total number of glasses is at least five, the sages are safe. The reason: there are at least two good glasses in a row. So the sages can agree that the first one drinks a good glass followed clockwise by another good glass. If the total number of glasses is less than 5, there is no reliable strategy, as the reader can check.
The above idea works if the number of sages is S, the number of poisoned glasses is P, and the total number of glasses is T, where T is greater than SP. Then, the strategy is the same since there is a guaranteed continuous stretch of S good glasses.
On the other hand, one can argue that for S and P more than 1, and T = S + P, it is impossible to find a strategy.
Our original problem corresponds to the case S = P = 3, and T = 8. Presumably, the strategy doesn't exist if S = P = 3, and T < 8. If the 8-glasses problem is difficult, here is a much easier version, corresponding to the case S = 2, P = 3, and T = 6.
An Easier Puzzle. Six glasses of wine are placed in a circle on a round table. Two sages are invited to take the following challenge. In the presence of the first sage, three glasses are filled with good wine and the other three 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 three sages can agree on their strategy beforehand. What is the strategy to keep them all alive?
I am trying to make a point that, mathematically, the Sleeping Beauty problem is resolved, and the Wikipedia article about it should stop assuming that there is an ongoing debate.
The Sleeping Beauty problem. Sleeping Beauty participates in the following experiment. On Sunday, she is put to sleep, and a fair coin is flipped. Regardless of the result of the coin flip, she is awakened on Monday and asked whether she thinks the coin was heads or tails. Regardless of her answer, if the coin was heads, the experiment ends. However, if the coin was tails, she is put back to sleep with her memory erased and awakened again on Tuesday and asked the same question. In this case, the experiment stops on Tuesday. She knows the protocol. She is awakened one morning. From her point of view, what is the probability that the coin was heads?
Here is the solution. If it is Monday, then the probability that the coin is heads is one half. So the probability of Monday/heads is the same as Monday/tails. If the coin is tails, Sleeping Beauty can't distinguish between Monday and Tuesday. So the probability of Monday/tails is the same as Tuesday/tails. Thus, the three cases Monday/heads, Monday/tails, and Tuesday/tails are equally probable. It follows that when she is awakened, the probability of heads is one third.
However, there are still people — called halfers — who think that the probability of heads is one half.
But suppose we ask a different question.
Different question. She is awakened one morning. From her point of view, what is the probability that the day is Tuesday?
As I explained before, when she is awakened, the probability of it being Tuesday is one third. Let us calculate what the halfers think. Suppose they think that the probability of the day being Tuesday is x, then the probability of Monday is 1 − x. Let's calculate the probability of the coin being heads from here. The probability of heads, if today is Tuesday, is zero. The probability of heads, if today is Monday, is 1/2. Therefore, the probability of heads equals 0 · x + (1 − x)/2 = (1 − x)/2. In halfers' view, the resulting calculation equals 1/2. In other words, (1 − x)/2 = 1/2. It follows that x is zero. Doesn't make much sense that the probability of the day being Tuesday is zero, does it?
Halfers are wrong. Wikipedia should update the article.
The Sleeping Beauty problem. Sleeping Beauty participates in the following experiment. On Sunday, she is put to sleep, and a fair coin is flipped. Regardless of the result of the coin flip, she is awakened on Monday and asked whether she thinks the coin was heads or tails. Regardless of her answer, if the coin was heads, the experiment ends. However, if the coin was tails, she is put back to sleep with her memory erased and awakened again on Tuesday and asked the same question. In this case, the experiment stops on Tuesday. She knows the protocol. She is awakened one morning. From her point of view, what is the probability that the coin was heads?
This problem is considered controversial. Some people, called halfers, think that when she is awakened, the probability that the coin was heads is one half. Other people, called thirders, think that when she is awakened, the probability that the coin was heads is one third.
I am a thirder, so let me explain my thinking. If it is Monday, then the probability that the coin is heads is one half. So the probability of Monday/heads is the same as Monday/tails. If the coin is tails, Sleeping Beauty can't distinguish between Monday and Tuesday. So the probability of Monday/tails is the same as Tuesday/tails. Thus, the three cases Monday/heads, Monday/tails, and Tuesday/tails are equally probable, and the answer follows.
This problem is similar to the Monty Hall problem in some ways. The main difference is that The Monty Hall problem stopped being controversial, while Sleeping Beauty problem continues to be. The best argument that helped intuition and led to the resolution of the Monty Hall problem was increasing the number of doors. Similarly, for the Sleeping Beauty problem, we can increase the number of days she is put back to sleep when the coin is tails. Forgive me for the cruelty of this theoretical experiment.
The Sleeping Beauty Variation. Sleeping Beauty participates in the following experiment. On Sunday, she is put to sleep, and a fair coin is flipped. Regardless of the result of the coin flip, she is awakened on Monday and asked whether she thinks the coin was heads or tails. Regardless of her answer, if the coin was heads, the experiment ends. However, if the coin was tails, the experiment continues for 99 more days. Each day, she is put back to sleep with her memory erased and awakened the next day and asked the same question. She knows the protocol. She is awakened one morning. From her point of view, what is the probability that the coin was heads?
In this variation, when she is awakened, she should be almost sure that the coin was tails. I hope it will help halfers feel that, in this case, the probability of heads can't be one half. For me, the argument is the same as before, making the probability that the coin was heads is 1 over 101.
After I wrote this essay, I discovered that Nick Bostrom made the same argument. Though, for tails, he put Sleeping Beauty to sleep one million and one times, which is about 2,740 years. He increased my one hundred days by several orders of magnitude, amplifying our point. Surely, when Sleeping Beauty awakens, she should be almost certain that the coin was tails. After Sleeping Beauty agrees to so much torture, why is the problem still controversial?
We already blogged about the Sleeping beauty problem three times: The Sleeping Beauty Problem, Sleeping Beauty Meets Monty Hall, and Sleeping Beauty and Mondays. The posts were more than ten years ago, but the mathematical community seems to continue being stuck on this problem. So we come back to it.
Problem. Sleeping Beauty participates in the following experiment. On Sunday, she is put to sleep, and a fair coin is flipped. Regardless of the result of the coin flip, she is awakened on Monday and asked whether she thinks the coin was heads or not. If the coin was tails, however, she is put back to sleep with her memory erased, awakened on Tuesday and asked the same question again. She knows the protocol. She is awakened one morning: What is her probability that the coin was heads?
Let's raise the stakes a little bit. Suppose a prize of $1K is set aside for her correct guess of a flip. What should be her strategy?
The problem is ambiguous. We didn't tell you how the prizes are awarded. We see several reasonable scenarios:
Because of selective amnesia, she can't distinguish between her awakenings, thus her strategy has to be the same at every awakening. That is, she should say heads with probability p. The exact number depends on the scenario:
We see that though she is asked to guess the outcome of the coin flip and is rewarded for guessing correctly, her strategy is not to try to maximize the probability of guessing correctly each time. The strategy depends on the reward protocol.
We see that in the first and the sixth scenario, she gets one guess per coin flip. Not surprisingly, it doesn't matter what she chooses to do. The classic Sleeping Beauty problem corresponds to the third scenario. If she wants to improve her chances per guess, she should favor tails.
Let's look at the following variation.
Problem. Suppose Sleeping Beauty's goal is to guess right once, but if she guesses right on Monday, she wins and is not put back to sleep. If she guesses wrong on Monday and the coin was tails, she is put back to sleep with he memory erased. That is, she is given a second chance. What's the right strategy in this case?
As her memory is erased, the only strategy is to do the same thing each time she is awakened. That is to guess heads with probability p. Thus, she guesses correctly at least once with probability p/2 + (1–p)/2 + p(1–p)/2. We see that whatever strategy she chooses, she guesses with probability one half on Monday. She gets an additional chance of p(1–p)/2 to get a correct guess on Tuesday. Her worst strategy is to always guess tails or heads. Her best strategy is to flip a fair coin each time. This way, she has an additional probability of 1/8 to win on Tuesday.
Here is a question to our readers, for the best strategy above, what is her probability on waking that the coin is actually heads? Here is the problem more formally.
Problem. Sleeping Beauty participates in the following experiment. On Sunday, she is put to sleep, and a fair coin is flipped. Regardless of the result of the coin flip, she is awakened on Monday and asked whether she thought the coin was heads or not. Sleeping Beauty answers by flipping a fair coin. If she guesses correctly, or if the Sunday coin was heads, the experiment ends. If the Sunday coin was tails and different from her guess, she is put back to sleep with her memory erased, awakened on Tuesday, and asked the same question again. She knows the protocol. She is awakened one morning: What is her probability that the Sunday coin was heads?
I love Toblerone, but I never paid attention to its logo.
This Swiss chocolate was created in Bern (Berne) more than a hundred years ago. A legend says that Berne's founder loved hunting and vowed to name the city after the first animal he met on his hunt. The animal happened to be a bear, and so the town was named Berne. The bear became a big deal for the town; you even can find the bear on the town's flag and coat of arms.
Theodor Tobler, the creator of Toblerone, put the famous local mountain, Matterhorn, in the logo of Toblerone and hid a bear in the image. He obviously loved his country and town.
Tobler was clearly a wordsmith and invented a fascinating name for his chocolate. As Wikipedia explains, the name Toblerone is a portmanteau combining Tobler's name with the Italian word torrone, which is a type of nougat used in his chocolate. However, Wikipedia doesn't explain that the word Toblerone also contains a secret: the word BERNE (bear).
After writing this, I couldn't resist and bought some dark Toblerone chocolate. Now it brings me pleasure in more ways than one.
There are many cute math problems that use the trivial fact announced in the title. For example, I recently posted the following problem from the 43rd Tournament of Towns.
Problem. Find the largest number n such that for any prime number p greater than 2 and less than n, the difference n − p is also a prime number.
Solution. Prime numbers 3, 5, and 7 have different remainders modulo 3. Thus, for any n, one of the numbers n − 3, n − 5, or n − 7 is divisible by 3. If n > 10, that number that is divisible by 3 is also greater than 3, thus, making it composite. Therefore, the answer to this problem is not greater than 10. Number 10 works, thus, the answer is 10.
Here is another problem using the fact that 3, 5, and 7 have different remainders when divided by 3.
Problem. Find the maximum integer n, such that for any prime p, where p < n, the number n + 2p is prime.
Here is the current picture of my coauthor, Joel Lewis. I remember him from many years ago when he was a graduate student at MIT. I am glad he kept his big smile.
Back to the subject matter. Joel Lewis made a comment on my recent post, thinking-outside-the-box ideas. He mentioned his two theorems:
The Big Point Theorem. Any three lines intersect at a point, provided that the point is big enough.
The Thick Line Theorem. Any three points lie on the same line, provided that the line is thick enough.
I grew up a purist. Mathematics was about mathematics, not about gender. I personally would never have competed in a math competition exclusively for girls. I would have felt diminished somehow. Furthermore, suppose there were separate math competitions for boys, where girls were not allowed. I would have felt outraged. By symmetry, I should have been outraged by math competitions exclusively for girls.
When I first heard about math competitions for girls, I was uncomfortable. I also noticed that my Eastern European friends shared my feelings, while my other friends did not.
There was a stage in my life when I lived in Princeton for seven years and became friends with Ingrid Daubechies, who is NOT Eastern European. She didn't share my extreme views, and we argued a lot. Every spring, there was a big conference for Women-in-Mathematics at the Institute for Advanced Study in Princeton. But I was stubborn and completely ignored it. With one exception: when Ingrid gave a lecture there, I went just to hear her talk.
In 2008, I was living in Boston, worrying about money, as I had just resigned from my industry work to return to mathematics. Out of the blue, Ingrid called to offer me a job at that very same Women-in-Mathematics conference. I admire Ingrid and got excited about working with her. More importantly, I needed the money. So I decided to put aside my prejudice and take the job.
Being part of the conference was a revelation. Although most of the two-week conference was spent on mathematics, there were some women-and-math seminars. There, women discussed bullying by advisers and colleagues, impostor syndrome, workplace bias, the two-body problem, and other issues. And guess what? I went through all of that too. I just never realized it and never talked about it.
My biggest regret was that I hadn't attended the conference earlier. Plus, the conference didn't feel unfair towards men: all lectures and math seminars were open to the public, and some courageous guys sat in.
What about my symmetry test? What happens if we swap genders? Should there be separate math conferences for men, open to the public? The idea makes me laugh. Women are in the minority in math, and many conferences already feel like conferences for men open to the public. My symmetry test doesn't quite work.
But, while I saw how helpful the support was for female mathematicians and for me, something still bugs me. Where is the fine line between minority support and unfairness? Let's look at math clubs for girls. On the surface, there are so many math clubs, so why not have the occasional math club for girls? I can imagine a girl, not me, who would prefer to attend such a club. However, girls' clubs often have sponsors and are much cheaper to attend than regular clubs. This is unfair to boys whose parents can't afford a regular club. It also becomes counterproductive for girls. What if some girls go to such a club, not because they need a special environment but because it is a cheaper club? They are missing out on the fun of learning math together with boys. (Trust me, I know!) So, I am not sure where that line is.
I am older and wiser now. I do not run away from events organized for women in math. I think lunches and dinners for women in math are great. They help female mathematicians find mentors, build networks, and stay in mathematics.
What about my original question: Should there be separate math competitions for girls? In a truly equal society, math competitions should be for everyone. And, though I do not actively oppose girls' competitions anymore, I hope the need for them will die out in my lifetime.
Recently, I stumbled upon three lovely logic puzzles, while scrolling Facebook for news from the Russia-Ukraine war. I will start with an easy puzzle.
Puzzle. A traveler got to an island, where each resident either always tells the truth or always lies. A hundred islanders stood in a circle facing the center, and each told the traveler whether their neighbor to the right was a truth-teller. Based on these statements, the traveler was able to clearly determine how many times he had been lied to. Can you do the same?
In the next puzzle, there is another island where people are either truth-tellers or normal. There are three questions that increase in difficulty.
Puzzle. You are on an island with 65 inhabitants. You know that 63 inhabitants are truth-tellers who always tell the truth, and the other 2 are normal, who can either lie or tell the truth. You are allowed one type of question, "Are all the people on this list truth-tellers?" This question requires a list, which you can create yourself. Moreover, you can have as many different lists as you want. You can pose this question to any islander any number of times. Your goal is to find the two normal people. The easy task is to do it in 30 questions. The medium task is to do it in 14 questions. The hard task is to figure out whether it is possible to do it in fewer than 14 questions.
Here is the last puzzle.
Puzzle. You got to an island with 999 inhabitants. The island's governor tells you, "Each of us is either a truth-teller who always tells the truth, or a liar who always lies. " You go around the island asking each person the same question, "How many liars are on the island?" You get the following replies.
First person, the governor: "There is at least one liar on the island."
The second person: "There are at least two liars on the island."
This continues progressively until the 999th person says: "There are at least 999 liars on the island."
What can you tell about the number of liars and truth-tellers on this island?
I recently wrote an essay, Thinking Inside and Outside the Box, which starts with a famous nine-dots puzzle that kicked off the expression: thinking outside the box. Here is another puzzle with the same nine-dots setup.
Puzzle. What is the smallest number of squares needed to ensure that each dot is in its own region?
Usually, people who try to solve this puzzle come up with the following four-squares solution.
As with the classic nine-dots puzzle, they imagine that the dots are on a grid and try to build squares with sides parallel to the grid lines. What would be the outside-the-box idea? The sides of the squares would not need to be parallel to the grid. This way, we can solve the puzzle with three squares.
One of my MathRoots students offered a different and awesome solution also using three squares.
Problem. Find the largest number n such that for any prime number p greater than 2 and less than n, the difference n − p is also a prime number.
The most famous thinking-outside-the-box puzzle is the Nine-Dots puzzle. This puzzle probably started the expression, "To think outside the box". Here is the puzzle.
Puzzle. Without lifting the pencil off the paper, connect the nine dots by drawing four straight continuous lines that pass through all the dots.
Most people attempt something similar to the picture below and fail to connect all the dots.
They try to connect the dots with line segments that fit inside the square box around the dots, mentally restricting themselves to solutions that are literally inside the box.
To get to the correct solution, the line segments should be drawn outside this imaginary box.
Do you think that four line segments is the best you can do? Jason Rosenhouse showed me a solution for this puzzle that requires only three lines. Here, the outside-the-box idea is to use the thickness of the dots.
This and many other examples of thinking outside the box are included in my paper aptly titled Thinking Inside and Outside the Box and published in the G4G12 Exchange book.
A section of this paper is devoted to my students, who sometimes give unexpected and inventive solutions to famous puzzles. Here is an example of such a puzzle and such solutions that aren't in the paper because I collected them after the paper was published.
Puzzle. Three men were in a boat. It capsized, but only two got their hair wet. Why?
The standard answer is the following: One man was bald.
Lucky for me, my creative students suggested tons of other solutions. For example,
My favorite example, however, is the following.
I still get comments that my place is in the kitchen, and women shouldn't do math. Luckily, occurrences of such events are getting rarer. So the world is progressing in the right direction. But gender bias still exists. Multiple studies show that among people of the same level of intelligence, men are perceived as smarter. In layman's terms, people think women are stupider than they are. I will give my own examples at another time. But now, I want to discuss my model for gender bias.
Let's denote the mathematical strength of a researcher by S. In real life, if the researcher is female, people perceive her strength as smaller than S. Let us assume that there exists a bias coefficient B, a number between 0 and 1 so that a female researcher of strength S is perceived on average as having strength BS. When B is 1, then there is no bias. But the world is not there yet.
In recent years, there has been a push to hire female mathematicians. Suppose a math department has a cutoff C for hiring a math professor. Being eager to hire a female professor, the department slightly reduces the cutoff by the bias reduction coefficient R, where R is a number between 0 and 1. Thus, the cutoff to hire a female professor becomes RC, which is less than C.
Now consider Alice, who has mathematical strength S, such that S ≥ C ≥ BS ≥ RC. She is perfectly qualified to be hired by the department independent of her gender. However, the department members, on average, perceive her strength as not good enough for a male hire but good enough for a female one. Alice is hired. What happens as a result?
Many male colleagues are angry. They think that because of Alice, they couldn't hire a male candidate they believe to be stronger. They also expect Alice to be grateful for the opportunity. How will Alice react? It depends on whether Alice herself is biased. I will give two potential scenarios.
Scenario 1. Alice is biased and realizes she is only hired because she is female. Alice thinks that her strength is below the cutoff C. Alice develops impostor syndrome and doesn't contribute to the department and mathematics as much as she could have, reinforcing everyone's belief that she is weaker than she actually is.
Scenario 2. Alice is not biased but realizes that she was hired for her gender and not for her mathematics. She gets angry too because she knows she is perfectly qualified. She also realizes that the department expects her to be grateful, while another male hire is thanked for taking a similar position. In this scenario, everyone is angry.
In both scenarios, the intent is to fight the bias. But as a result, no one is truly happy. A supportive environment is not created. And the idea that male and female mathematicians differ in strength is reinforced.
Recently, I talked to a male colleague about gender bias. He was adamant that he isn't biased and, as proof, described his contribution to hiring females in his department. This is not proof of being unbiased. This is proof of trying to resolve the bias, either sincerely or due to outside pressure. However, the real proof would be to change one's attitude towards female colleagues. As a female colleague myself, I would notice this change in attitude. But while nothing changes, I can't accept the fact of female hires as proof of no bias.
To truly resolve the bias, we need B to be equal to 1. To improve the situation, people should collectively work on increasing the bias coefficient B. This is more about changing the attitude.
I am for hiring more female mathematicians as professors. But sometimes, I feel like hiring more female mathematicians without addressing the attitude is treating the symptoms while making the disease worse.
I love knights-and-knaves puzzles: where knights always tell the truth, and knaves always lie. The following puzzle has a new type of person: a sophist. A sophist only makes statements that, standing in their place, neither a truth-teller nor a liar could make. For example, standing next to a liar, a sophist might say, "We are both liars." Think about it. If the sophist was a truth-teller, then the statement would have been a lie, thus creating a contradiction. If the sophist was a liar, the statement would be true, again creating a contradiction.
Here is the puzzle with sophists. And by the way, this one is intended for sixth graders.
Puzzle. You are on an island inhabited by knights, knaves, and sophists. Once upon a time, a sophist made the following statements about the island's inhabitants:
1. There are exactly 25 liars on this island.
2. There are exactly 26 truth-tellers on this island.
3. The number of sophists on this island is no less than the number of truth-tellers.
How many inhabitants were on the island once upon that time?
I love this new sophist character in logic puzzles, but I have no clue why they are called sophists. Can anyone explain this to me?
As my readers know, I collect Russian license plates. They are actually American plates, but the letters form words readable in Russian. This is possible because the shapes of English and Russian letters overlap. Here is my new favorite plate. It is actually not the best plate, but rather makes the best picture ever.
The plate says Moscow, the Russian capital. And the car is parked next to the Ukrainian flag. I am from Moscow too, and I too support Ukraine in its war against evil Putin, who wants to restore the Russian Empire. Did you know that now he wants Alaska?
After reading my post, Shapovalov's Gnomes, Grant, one of my readers, directed me to the Brick puzzle from Section 2.3 of Xinfeng Zhou's A Practical Guide to Quantitative Finance Interviews.
Puzzle. Can you pack 53 bricks with dimensions 1-by-1-by-4 into a 6-by-6-by-6 box?
The solution in Zhou's book has some flaws. So I am posting my own solution here.
Solution. We start with a sanity check. The box contains 216 unit cube cells, and 53 bricks would take up 212 cells. So there is no contradiction with the volume. We need to look at something else.
Let's divide the box into 27 smaller 2-by-2-by-2 boxes and color the smaller boxes in a checkerboard manner. We get 13 boxes of one color, say white, and 14 boxes of another color, say black. Whichever way we place a brick inside the original box, it has to cover 2 white cells and 2 black cells. But we have a total of 104 white cells, which is only enough for 52 bricks.
Alexander Gribalko designed a new coin problem, two versions of which appeared at the 43rd Tournament of the Towns. I will start with the easier version.
Problem. Alice and Bob found eleven identical-looking coins; four of them are fake. All real coins weigh the same. All fake coins weigh the same but are lighter than the real ones. Alice offered Bob four specific coins. Before agreeing to take them, Bob wants to ensure they are all real. Can he do so by only using the balance scale twice? He can use any of the eleven coins for weighing purposes.
Surprisingly, the more difficult version has fewer coins.
Problem. Alice and Bob found eight identical-looking coins; three of them are fake. All real coins weigh the same. All fake coins weigh the same but are lighter than the real ones. Alice offered Bob three specific coins. Before agreeing to take them, Bob wants to ensure they are all real. Can he do so by only using the balance scale twice? He can use any of the eight coins for weighing purposes.
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 31/352/1578/105 = 2.07.
Counterexample to the second argument. Why is this wrong? Let us, for example, consider a sequence with the following recursions: a2k+1 = a2k + a2k-1. And a2k = (a2k-1 + a2k-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.
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.
I recently posted a cute Shapovalov's puzzle about gnomes. Here is another easier gnome puzzle, also by Alexander Shapovalov.
Puzzle. All gnomes are knights or knaves: knights always tell the truth, and knaves always lie. There is a gnome on every cell of a 4 by 4 chessboard. It is known that both knights and knaves are present in this group. Every gnome states, "Among my neighbors, the number of knaves is the same as the number of knights". How many knaves are there, if by neighbors they mean orthogonally adjacent gnomes?
The next gnome puzzle has a different author, Alexander Gribalko. Gnomes in this puzzle are not knights or knaves but rather friendly and polite beings.
Puzzle. Nine gnomes repeated the following procedure three times. They arranged themselves on a 3 by 3 chessboard with one gnome per cell and greeted all their orthogonal neighbors. Prove that not all pairs of gnomes greeted each other.
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 n2. 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.
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.
(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.
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.
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 fn with the same two initial values that start the Fibonacci sequence: f0 = 0 and f1 = 1. To calculate fn+1, we add fn-1 and fn 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 rn in base 3/2 as follows. To calculate rn+1, we add rn-1 and rn 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 r0 = 0 and r1 = 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 r7.
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.
I run Number Gossip, where you can input a number and get some of its cute properties. For example, the number 63 is composite, deficient, evil, lucky, and odd. In addition, it has a unique property: 63 is the smallest number out of two (the other being 69), such that the common alphabetical value of its Roman representation is equal to itself. Indeed, the Roman representation of 63 is LXIII, where L is the 12th digit, X is the 24th, and I is the 9th. Summing them up, we get 12 + 24 + 9 + 9 + 9 = 63 — the number itself.
I have a list of about 50 properties of numbers that my program checks. Each number greater than one gets at least four properties. This is because I have four groups of properties that cover all the numbers. Every number is either odd or even. Every number is either deficient, perfect, or abundant. Every number greater than one is either prime or composite. Every number is either evil or odious.
In addition, I collect unique number properties. During the website's conception, I decided not to list all possible unique properties that I could imagine but to limit the list to interesting and unusual properties. My least favorite properties of numbers are the ones that contain many parameters. For example, 138 is the smallest number whose base 4 representation (2022) contains 1 zero and 3 twos. If you are submitting a number property to me, keep this in mind.
Some parameters are more forgiving than others. For example, 361 is the smallest number which is not a multiple of 9, whose digital sum coincides with the digital sum of its largest proper divisor. In more detail, the digital sum of 361 is 3 + 6 + 1 = 10, while 19, the largest divisor of 361, has the same digital sum of 10. In this case, the parameter 9 is special: for a multiple of 9, it is too easy to find examples that work, such as 18, 27, and so on. Sequence A345309 lists numbers whose digital sum coincides with the digital sum of their largest proper divisor. The first 15 terms of the sequence are divisible by 9, and 361 is the smallest term that is not divisible by 9.
By the way, another number that is buried deep in a sequence is 945, which is the smallest odd abundant number. There are 231 abundant numbers smaller than 945; all of them are even.
A more recent addition to my collection is related to the sequence of distended numbers (A051772). Distended numbers are positive integers n for which each divisor of n is greater than the sum of all smaller divisors. It is easy to see that for distended numbers, all sums of subsets of divisors are distinct. The opposite is not true: 175 is the smallest number, where all sums of subsets of its divisors are distinct, but the number itself is not distended.
It is difficult to find special properties for larger numbers, so I am less picky with them. For example, 3841 is the number of intersections of diagonals inside a regular icosagon. The word icosagon hides a parameter, but I still like the property.
I invite people to submit number properties to me. And I received many interesting submissions. For example, the following oxymoronic property was submitted by Alexey Radul: 1 is the only square-free square.
The numbers below 200 that still lack unique properties are 116, 147, 155, 162, 166, 182, and 194. The earliest century that doesn't have unique number properties ranges between 7000 and 7100. The next ones are 8000–8100 and 9100–9200. By the way, my site goes up to ten thousand.
I also have a lot of properties in my internal database that I haven't checked yet. I am most interested in the proof of the following property: 26 is the only number to be sandwiched between any two non-trivial powers.
One of my posts about John Conway has a picture I took of him in 2015, leafing through a book about himself, Genius at Play. I allowed Wikipedia to use this image, and they did. They also retouched it for their article on John Conway in Dutch. I like the result.
Every year, after the MIT Mystery Hunt was over, I would go through all the puzzles and pick out the ones related to mathematics. This year, I didn't feel like doing it. Besides, I think it is more important to collect quality puzzles rather than all the puzzles by topic. So my new collection is the puzzles recommended to me, which I might like.
I start with math and logic puzzles.
I continue with computer science.
I carry on with some non-math fun.
I conclude with the plot device round. All the puzzles in this round are relatively easy. But our team got stuck on them until we realized that we already had the answer, which was not a single word. Here are some of the puzzles that were specifically recommended.
Putin became the 21st century Hitler. I call him Putler.
I am an American. However, I was born in Moscow and lived my youth in the Soviet Union. I speak Russian, and I have friends in both Russia and Ukraine. The war in Ukraine is the biggest tragedy of my life.
When Putler invaded Ukraine, I didn't know what to do. I wanted to pick up a rifle and go to Ukraine to fight, but then I remembered my CPAP machine and the distilled water it needs, and I didn't go. Instead, I ended up watching the news non-stop. Then I started sending money to different organizations supporting Ukraine.
However, I am a mathematician, so I tried to figure out whether I could help Ukraine by doing math. At first, I posted math problems from Ukraine Olympiads. Then I started discussing what we could do with my PRIMES colleges. The result was a new program, Yulia's Dream, in honor of Yulia Zdanovska, a 21-year-old brilliant young Ukrainian mathematician killed by a Russian-fired missile. Yulia's Dream is a free enrichment program for high-school students from Ukraine who love math.
All these activities didn't help me with the pain. So I started crocheting. I bought yarn in the colors of the Ukrainian flag and crocheted a hyperbolic surface of constant curvature. The first picture shows the thingy from above. The second one is there for you to estimate its size: this is the biggest crocheting project I have ever finished.
For a free Ukraine! Let democracies win over dictatorships!
I wrote a lot about how during entrance tests for Moscow State University, the examiners were giving Jewish and other undesirable students special (e.g. more difficult) questions during the oral exams. (See, for example, our paper Jewish Problems with Alexey Radul.) Not all examiners agreed to do this. So the administration made sure that there were different exam rooms: brutal rooms with compliant examiners torturing students with difficult questions, and normal rooms with normal examiners testing preapproved students. The administration also had other methods. One of them is the topic of this essay.
The math department of Moscow State University had four entrance exams. The first was a written math test consisting of three trivial problems, a very difficult one, and a brutally challenging one. At the end, I will show you a sample: a trivial problem and a very difficult one from 1976, my entrance year.
What was the point of such vast variation in difficulty, you may ask? There were two reasons.
But first, let me explain some entrance rules. The exam was scored according to the number of solved problems. A score of two or less was a failing score. People with such scores would be disqualified from the next exam. Any applicant with a smidge of mathematical intelligence would be able to solve all three trivial problems. Almost all applicants who qualified for the next test would have the same score of three on the first test, as they wouldn't be able to solve the last two problems. Thus, mathematical geniuses and people who barely made the cut got the same score.
There was another rule. Officially, people with a gold medal from their high school (roughly equivalent to a valedictorian) could be accepted immediately if they scored 5 on the first exam. So one of the administrative goals was to prevent anyone getting a 5, thus, blocking Jewish applicants from sneaking in after the first exam.
Another goal was to have all vaguely qualified people get the same score. The same goal applied to other exams. After the four admission exams, the passing score, say X, was announced. A few people with a score higher than X were immediately accepted. Then there were hundreds of applicants with a score of X, way more than the quota of people the department was planning to accept. An official rule allowed the math department to pick and choose whoever they wanted from everyone who scored X.
I heard a speech by the famous Russian mathematician, Vladimir Arnold, directed at decent examiners who tested "approved" students at the oral math exam, which was the second admissions exam. His suggestion was brilliant and simple. If the students are good and belong in the department, give them an excellent grade of 5. If not, give them a failing grade of 2. Arnold's plan boosted the chances of good students doing better than the cutoff passing score X and removed mediocre students from the competition. His idea was not only brilliant and simple but also courageous: he was risking his career by trying to fight the system.
I never experienced the entrance exams firsthand. By ministry order, as a member of the USSR IMO team, I was accepted without taking any exams. I already wrote an essay, A Hole for Jews, about how getting on the IMO team was the only way for Jewish students to get into the Moscow State University, and how the University tried to block them.
But I still looked at the entrance exam problems I would have had to solve to get in. The last two problems scared me. Now I found them again online (in Russian) at: the 1976 entrance test. The trivial problem below is standard and mechanical, while the other problem still looks scary.
Trivial problem. Solve for x:
Solution. We were drilled in school to solve these types of problems, so this one was trivial. First, make a substitution: y = 3x. This leads to an equation: (2y - 1)(y - 3)/(y2 - 2)(y - 1) ≤ 0. From this we get ranges for y: (-∞, -√2], [1/2,1], [√2, 3]. The last step is to take a logarithm.
Very difficult problem. Three spheres are tangent to plane P and to each other. Two of the spheres are the same size. The apex of a circular cone is on P, and the cone's axis is perpendicular to the plane P. All three spheres are outside the cone and tangent to it. Find the cosine of the angle between the cone's generatrix and the plane P, if one of the angles of the triangle formed by the intersection points of the spheres and the cone is 150 degrees.
I stumbled upon one of Smullyan's puzzle on Facebook, in Russian. I couldn't find the original text, so I just translated it back for my students.
Puzzle. You are on an island where only truth-tellers and liars live. The truth-tellers always tell the truth, and the liars always lie. You meet an islander who sits with you for a long time, then says, "I already said this sentence." Is he a truth-teller or a liar?
I expected the following solution. If this islander is a truth-teller, then there should have been a time when he said, for the first time, "I already said this sentence." But this would create a contradiction.
However, my students used this puzzle as an opportunity to teach me some intricacies of the English language. They explained to me the ambiguities of my translation. Here is a shortened and lightly edited quote from one of them:
There are two different linguistic opinions that give different answers to this problem. The first is that the truth of a statement is decided at the moment it starts to be delivered: in this case, when the islander starts saying his statement. With this interpretation, for the statement to be true, he had to have said the sentence before, and for that to be true, he had to have said it even before that, and this continues indefinitely. Clearly, he cannot have been alive forever, so he has to be a liar.
The other opinion is that the verity of a statement is decided at the exact conclusion of its deliverance. Then, when the islander finishes saying his sentence, its truth is judged, and he has at that same instant "already" said the sentence, so he is telling the truth. By this interpretation, the islander is a truth-teller.
Another student had a different brilliant idea. Depending on the islander's intonation, it is possible that he says, "I already said 'this sentence'." In that case, there are no self-referencing sentences, and the islander could be either a truth-teller or a liar.
I consulted my best English consultant: my son, Alexey, and here is his reply. "The basic answer is that neither truth nor semantic meaning are absolute, and edge cases will be judged differently by different observers. A sentence whose truth is time-dependent on the same scale as the duration of uttering the sentence is clearly an edge case. That's why mathematicians intentionally try to eliminate ambiguity from their communication."
He suggested the following fix for the puzzle's translation.
Fixed puzzle. You meet an islander who says, "I have said this sentence before." Is he a truth-teller or a liar?
Alexey didn't stop at fixes and suggested the following bonus puzzles.
Bonus puzzle 1. You meet an islander who says, "I will have said this sentence." Is he a truth-teller or a liar?
Bonus puzzle 2. You meet an islander who says, "I will say this sentence again." Is he a truth-teller or a liar?
Ukraine is on my mind. Here is a problem for 9-graders from the 1978 Ukrainian Math Olympiad:
Problem. Prove that for every natural number n, the following number is not an integer.
Oskar van Deventer is a designer of beautiful mechanical puzzles. For the recent mini-MOVES gathering at the MoMath, he asked people in his Zoom breakout room to calculate the average age in the room without revealing their actual ages. I know the following solution to this puzzle.
People agree on a large number N that is guaranteed to be greater than the sum of all the ages. The first person, say Alice, thinks of a uniformly random integer R between 0 and N. Alice adds her age to R modulo N and passes the result to the second person, say Bob. Bob adds his age modulo N and passes the result to the third person, and so on. When the result comes back to Alice, she subtracts R modulo N and announces the sum total of all the ages.
During this process, no one gets any information about other people's ages. But two people can collude to figure out the sum of the ages of the people "sitting" between them.
I gave this problem to my grandson, and he suggested the following procedure. First, people choose two trusted handlers: Alice and Bob. Then, each person splits their age into the sum of two numbers (the splitting should be random and allow one of the numbers to be negative). They then give one number to Alice and another to Bob. Alice and Bob announce the sums of the numbers they receive. After that, the sum total of everyone's ages is the sum of the two numbers that Alice and Bob announce.
The advantage of this method is that no two people, except Alice and Bob, can collude to get more information. The disadvantage is that if Alice and Bob collude, they would know everyone's age. Which method would you prefer?
Many years ago, I wrote a blog post about an amusing fact: John Conway put Moscow, the former capital of the USSR, as a coauthor: A Math Paper by Moscow, USSR. Thus, Moscow got an Erdős number 2, thanks to Conway's Erdős number 1. At that time, my Erdős number was 4, so I wondered if I should try coauthoring a paper with Moscow, my former city of birth, to improve my Erdős number.
This weird idea didn't materialize. Meanwhile, my Erdős number became 2 after coauthoring a paper with Richard Guy, Conway's Subprime Fibonacci Sequences. I relaxed and forgot all about my Erdős status. I couldn't do better anyway, or could I?
I recently heard about a cheater who applied to grad schools. In addition to a bunch of fabricated grades, the cheater submitted an arXiv link to a phony paper. What is fascinating to me is that the cheater put real professors' names from the university the cheater supposedly attended as coauthors. The professors hadn't heard of this student and had no clue about the paper. So the cheater added fake coauthors to add legitimacy to their application and boost the perceived value of the cheater's "research". As a consequence, the cheater got a fake Erdős number.
I hope that the arXiv withdrew the paper. Cheating is the wrong way to improve one's Erdős number.
But here is another story. Robert Wayne Thomason named as coauthor his dead friend, Thomas Trobaugh. The paper in question is Higher Algebraic K-Theory of Schemes and of Derived Categories and can be found at https://www.gwern.net/docs/math/1990-thomason.pdf. This paragraph in the paper's introduction explains the situation.
The first author [Robert Wayne Thomason] must state that his coauthor and close friend, Tom Trobaugh, quite intelligent, singularly original, and inordinately generous, killed himself consequent to endogenous depression. Ninety-four days later, in my dream, Tom's simulacrum remarked, "The direct limit characterization of perfect complexes shows that they extend, just as one extends a coherent sheaf." Awaking with a start, I knew this idea had to be wrong, since some perfect complexes have a non-vanishing K0 obstruction to extension. I had worked on this problem for 3 years, and saw this approach to be hopeless. But Tom's simulacrum had been so insistent, I knew he wouldn't let me sleep undisturbed until I had worked out the argument and could point to the gap. This work quickly led to the key results of this paper.
This precedent gives anyone hope that they might achieve an Erdős number 1. You just need to wait for Paul Erdős to come to you in your dreams with a genius idea.
Last year, our junior PRIMES STEP group studied Latin squares. We invented a lot of different types of Latin squares and wrote a paper about it, Fun with Latin Squares. Recall that a Latin square is an n by n table containing numbers 1 through n in every cell, so that every number occurs once in each row and column. In this post, I want to talk about anti-chiece Latin squares.
First, what's a chiece? A chiece is a portmanteau word made out of two words, chess and piece, and, not surprisingly, it means a chess piece. Given a chiece, an anti-chiece Latin square is a Latin square such that any two cells, where our chiece can move from one cell to the other, according to the rules of chess, can't contain the same number. Let's see what this means.
Let's start with rooks, which move along rows and columns. An anti-rook Latin square can't have the same numbers repeating in any one row or column. Ha, anti-rook Latin squares are just Latin squares. Anti-bishop and anti-queen Latin squares can't have the same numbers repeating on any diagonal.
Now, here is a picture of an anti-knight Latin square in which no two identical numbers are a knight's move apart. This particular Latin square also forms a mini-Sudoku: not only does each row and column, but also each 2 by 2 corner region, contains all distinct numbers.
Consider all instances of some number, say 1, in an anti-chiece Latin square. If the board is n by n, we get n instances of non-attacking chieces. A famous math puzzle asks to place eight non-attacking queens on a standard chessboard. So the instances of any one particular number in an anti-queen Latin square solves the problem of placing n non-attacking queens on an n by n chessboard. Thus, building an anti-queen Latin square is more complicated than solving the non-attacking queens puzzle. The former requires filling the chessboard with n non-overlapping sets of non-attacking queens. The picture below gives an example of an anti-queen 5 by 5 Latin square.
This square has some interesting properties. It can be formed by cycling the first row. It also happens to be one of the chiece Latin squares we study in our paper. A chiece Latin square is a Latin square such that for each number in a cell, there is another cell, a chiece's move apart, containing the same number. You can check that our anti-queen Latin square is at the same time a knight Latin square.
I wonder, can anyone build an anti-queen Latin square on the standard 8 by 8 chessboard?
Here is the famous barber paradox.
Paradox. The barber shaves all those and only those who don't shave themselves. Does the barber shave himself?
If he shaves himself, then he doesn't shave himself. If he doesn't shave himself, then he shaves himself.
English is not my primary language, and I am fascinated by the variety of verb tenses in English as compared to the Russian language. For example, Russian has one present tense while English has four. I wonder what would happen if we use the other present tenses in this paradox.
Present continuous. The barber shaves all those and only those who aren't shaving themselves. Does the barber shave himself?
Does this mean that the barber starts shaving himself and then has to stop, and a moment later he has to start again?
Present perfect. The barber shaves all those and only those who haven't shaved themselves. Does the barber shave himself?
Does this mean that the barber shaves himself every other day?
Present perfect continuous. The barber shaves all those and only those who haven't been shaving themselves. Does the barber shave himself?
Does this mean the barber shaves himself once in his lifetime and then never again?
Gowers starts with several assumptions.
From these assumptions, the following theorem can be deduced.
Theorem. The only possible rule satisfying these assumptions would allow any two people to have sex with each other as long as they both reached some fixed age k.
There is a problem with this type of rule. Suppose k is 18. If two people who are slightly younger than 18 have consensual sex, they can't both be predators. These are two children with raging hormones. There is no reason to punish anyone. Now imagine that one of the partners turns 18. Society would still consider this a Romeo-and-Juliet case and would tend not to punish such a partner. Now imagine a child younger than 18 having sex with a partner over 40. The older partner has no raging hormones, knows what they are doing, and probably knows how to manipulate little children into having sex. So, it might be desirable to have a rule that differentiates between these two cases. The rule would take into account the difference in ages while forgiving younger offenders and still punishing predators.
Consider the most common type of law to resolve this issue: Anyone older than 18 can have sex, and, in addition, a person who is not older than 20 can have sex with someone between the ages of 16 and 18. This law doesn't satisfy monotonicity. It could be that one day the older partner is not yet 20, and the next day, oops, they have a birthday. So, as a birthday gift, they are not allowed to have sex with each other anymore.
Here is a simple idea to resolve the issue by having the law focus on the age gap instead of the age of the older partner. We can have an adjusted law: Anyone older than 18 can have sex, and, in addition, a person can have sex with someone between the ages of 16 and 18 as long as the age gap is not more than four years. This rule doesn't satisfy the simplicity assumption above, but it is simple enough. It is close in spirit to the previous rule and satisfies monotonicity. The problem with this rule is continuity.
According to the adjusted rule, the couple with the age gap of four years and one day might have to wait two years longer to have sex than the couple with the age gap of four years. This seems unfair.
Tim Gowers suggests dropping the simplicity rule. We can use days rather than years. For example, the rule might be that if one person in a couple is under 18, but at least 16, and has age x, then the other partner has to be not more than age y, where for example, y − x = 4 + (x − 16)/2. So when one partner turns 16, their partner has to be not older than 20. When one partner is 16 and two months, the other cannot be older than 20 and three months. With the younger partner getting older, the allowable age gap is increasing slowly. By the time the younger partner is a day from turning 18, their partner can be almost five years older.
It might be complicated for two people to calculate if they are allowed to have sex according to this formula. But Gowers' big idea was that apps and websites could do this easily: two people plug in their birthdays and know whether they are allowed to have sex.
Do you know what an isosceles tetrahedron is? I didn't until recently. An isosceles tetrahedron has all of its faces congruent. Equivalently, all pairs of opposite edges are of equal length. Such tetrahedra are also called disphenoids. Here are some cute statements about them.
Disphenoids have three nontrivial symmetries: 180-degree rotations around three lines connecting the midpoints of opposite edges.
Is it possible to have a tetrahedron with fewer symmetries than disphenoids? Yes, it is. Dan Klain just published a fascinating paper about such tetrahedra: Tetrahedra with Congruent Face Pairs. The results are so elegant and simple that I was surprised that they were new. I got curious and started to google aggressively. I found an official name for this kind of tetrahedron: phyllic disphenoid, but no theorems about them. Their name is quite unappealing: no wonder people didn't want to study them much. Obviously, Dan wasn't as aggressive at googling, so he didn't find this official name and called them reversible tetrahedra. But my favorite name for them is the name Dan thought of but didn't use in his paper: bi-isosceles tetrahedra.
Here is the picture of a bi-isosceles tetrahedron from Dan's paper. It has two faces with sides a, b, and c, and two faces with sides a, b, and d. The edges of this tetrahedron are: a, a, b, b, c, and d. It has one nontrivial symmetry: a 180-degree rotation around the line connecting the midpoints of the unequal opposite edges c and d. The picture emphasizes this symmetry. The figure in the picture is a projection of a bi-isosceles tetrahedron onto a plane, such that the line of symmetry is projected onto the point of symmetry of the projection. The two cute statements above, about disphenoids, can be generalized to the case of bi-isosceles tetrahedra.
The first property is trivial, while the second one is proven in Dan's paper. Dan also shows how to calculate the volume of a bi-isosceles tetrahedron:
Here is a problem from the 1978 Kyiv Olympiad for 7 graders.
Is it possible to place seven points on a plane so that among any three of them, two will be at distance 1 from each other?
Puzzle. Two girls were born to the same mother, at the same time, on the same day, in the same month, in the same year, and yet somehow they're not twins. Why not?
I won't tell you the expected answer, but my students are inventive. They suggested all sorts of scenarios.
Scenario 1. There are two different fathers. I had to google this and discovered that, indeed, it is possible. This phenomenon is called heteropaternal superfecundation. It happens when two of a woman's eggs are fertilized by sperm from two different men. Unfortunately for my students, such babies would still be called twins.
Scenario 2. The girls are born on the same date, but not on the same day. This could happen when transitioning from the Julian to Gregorian calendar. The difference in birth times could be up to two weeks. I had to google this and discovered that twins can be born months apart. The record holders have a condition called uterus didelphys, which means that the mother has two wombs. Unfortunately for my students, such babies would still be called twins.
Scenario 3. The second girl is a clone. This scenario can potentially happen in the future. Fortunately for that student, I suspect that such babies would be called clones, not twins.
I decided to invent my own scenario outside of the actual answer, and I did.
Scenario 4. Two girls are from the same surrogate mother, but they are not twins. I had to google this and discovered that this actually happened: Surrogate mother of 'twins' finds one is hers.
Sometimes life is more interesting than math puzzles.
In his article on Möbius strips, Martin Gardner included a cute construction.
Construction. Cut out a cross from a piece of paper. Then glue one pair of opposite ends to make a cylinder and the other pair to make a Möbius strip. Then Martin instructs, "Trisect the twisted band, then bisect the untwisted one, and open up for a big surprise!"
In my effort to reuse Möbius strips, I started making them out of zippers. So Martin's construction had its destiny zipped. The first picture shows the construction before it is being dissected. I was quite happy with my plan to use zippers as it had its advantages over paper. For the surprise to work, the twisted band shouldn't be cut completely. Meaning, the middle part of the Möbius strip shouldn't be cut. I sewed my zipper monstrosity not to cause any ambiguities: there is nothing to cut, just unzip the zippers.
Little did I know that unzipping is not the issue, but zipping back up is. I tried to zip the surprise back up several times; all of them unsuccessfully, as you can see on the two other pictures. I finally had to invite the real expert — my grandson — to do it.
I used to hate crocheting. Now it's been growing on me.
To prepare for this magic trick, take all the spades out of a deck and place them in the following order: seven, ace, queen, two, eight, three, jack, four, nine, five, king, six, and ten. Turn the assembled deck face down, so that the seven is on top. Now you are ready to do the trick.
Magic trick. Transfer the top card to the bottom of your deck and deal the new top card face-up on the table. Repeat this process until all the cards are dealt. And — abracadabra — the cards are dealt in order.
I showed this trick to my grandchildren, and they decided to reproduce it. They tried to calculate where each card goes, without too much success. Then my son showed them another trick: how to arrange the cards without calculation. He started building his arranged deck from the end of the trick with all the cards in order face-up on the table with the king on top. He took the king and put it face-down into his hand. Then he repeated the following procedure until all the cards were in his hand: He took the next card from the table and put it face-down on top of the one in his hand. Then he moved the card from the bottom of his deck to the top. And — abracadabra — the cards are arranged correctly for the trick.
Next time, I should ask my grandkids to show this trick with the whole deck.
Each time I teach my students about the Möbius strip, I bring paper, scissors, and tape to class. The students make Möbius strips, and then I ask them to cut the strips in half along the midline and predict the result.
Then we move to advanced strips. To glue the Möbius strip, you need one turn of the paper. An interesting experiment is to glue strips with two, three, or more turns. In this case, too, it is fun to cut them along the midline and predict the shape of the resulting thingy. My class ends with a big paper mess.
As you might know, I am passionate about recycling. So I have always wanted to buy Möbius strips that can be cut in half and then put back together. I didn't find them, so I made them myself from zippers. Now I can unzip them along the midline and zip them back together. I hope to have less mess in my future classes. We'll see.
I recently posted my new favorite probability puzzle from the fall 2019 issue of Emissary, submitted by Peter Winkler.
Puzzle. Alice and Bob each have a biased coin that flips heads with probability 51% and 100 dollars to play with. The buzzer rings, and Alice and Bob begin flipping their coins once per minute and betting one dollar on each flip against the house. The bet is at even odds: each round, each of them either loses or wins a dollar. Alice always bets on heads, and poor Bob, always on tails. As it happens, however, both eventually go broke. Who is more likely to have gone broke first?
Follow-up question: They play the same game as above, but this time Alice and Bob are flipping the same coin (biased 51% toward heads). Again, assuming both eventually go broke, who is more likely to have lost their money first?
One might assume that Bob obviously got a bad deal. He will lose his money very fast. So the answer to both questions must be that Bob loses his money first. If you know me, you should realize that I wouldn't have given you this puzzle if the answer was that intuitive. I love counter-intuitive puzzles.
Bob has a disadvantage, so he is guaranteed to lose eventually. Alice has an advantage, so she might lose, or she might not. If she goes broke, that means there should be more tails in the flips than if she doesn't go broke. How does this influence the second scenario, in which they use the same coin? As we are expecting a lot of tails in the flips, the situation should be better for Bob as compared to the first scenario. Given that I posed this puzzle, one might decide that in the follow-up question Bob doesn't go broke first. Is it a tie?
But, if Bob is the first to go broke in the first scenario, why would I include the first part of the puzzle at all? If you know me, you should wonder what makes the first question interesting. Or maybe, you know Peter Winkler, in which case you should also wonder the same thing.
I gave you enough meta information to guess the amazing counter-intuitive answers to these two questions: in the first scenario, they tie; and in the second scenario, Alice goes broke first with higher probability.
To prove that they tie in the first scenario, let me first define a switch on a sequence of coin flips. A switch changes each head into tails and vice versa. The switch creates a one-to-one correspondence between the sequences of flips where Bob goes broke with the sequences where Alice goes broke. Suppose p is the probability that Alice goes broke with a particular sequence a, and q is the probability that Bob goes broke with a `switched' sequence b. Then p = rq, where r = (49/51)200. The reason is that sequence a has exactly 200 more tails than sequence b. The same ratio r works for any pair of switched sequences. Bob is guaranteed to go broke eventually. But to calculate the conditional probability of Alice going broke with sequence a, given that she does go broke, we need to divide the probability of the sequence a occurring by the probability that Alice goes broke. The resulting probability distribution on sequences of length n has to be the same as for Bob because it has to sum to one. If Alice goes broke, then the probability that she goes broke after n flips is the same as for Bob. That means they tie.
To answer the second question, we use the switch again. The switch creates a one-to-one correspondence between sequences of flips where Alice goes broke first and Bob second, and vice versa. The sequence for which Alice loses second has 200 more tails than the corresponding sequence where Bob loses second. Thus, in each pair of two switched sequences, the probability of the sequence where Alice loses second is equal to r times the probability of the sequence where Bob loses second. Thus, the probability of Alice winning is r times the probability of Bob winning, and r is a very small number.
Here are my newly-made Borromean rings: two identical sets of them. They are an example of three linked rings, with any two of them not linked. The top set is positioned the way the Borromean rings are usually presented. You can see that any two rings are not linked by mentally ignoring the third one. For example, the red ring is on top of the green one, the green one is on top of the blue one, and the blue one is on top of the red one. They have a non-transitive ordering.
The bottom set of rings is arranged for a lazier thinker. Obviously, the blue and green rings are not linked.
I used to be proud of my Russian math education. I am still proud of my high school one, but not so much of the one I received in college. In Soviet Russia, a student had to choose their major before applying to college. I wanted to study mathematics, and I got accepted to the best place for it in Soviet Russia: mekhmat — the math school at the Moscow State University. I used to be proud of my education there, but now I have my doubts.
I had to take, on average, four math classes per semester for five years, which totals about 40 math classes. Woo hoo! I don't think American students could even choose to take that many. This was presumably good, but most of the courses were required, and their curriculum remained unchanged for many, many years. Obviously, the system was very rigid. The faculty members feared retaliation from the communist party and forgot how to take initiative. The bureaucracy prevented the department from adding new and exciting math to the outdated curriculum.
This post is not about my grades but about the actual subjects that we were taught then. But, in case anyone is wondering, my only B was in English; everything else was straight As.
Some of the classes listed below lasted two or more semesters, that's why they do not sum up to the promised 40. Unfortunately, I do not remember which ones. These were the required math classes:
An impressive list? But guess what — I remember nothing from most of these classes. As an exception, I remember bits of Differential Equations, taught by Vladimir Arnold, a charismatic teacher. I remember Linear Algebra well, not because of my Linear Algebra class, but because I read Gelfand's book on the subject and loved it. I remember that the Differential Geometry and Topology class was taught by Fomenko with great pictures and boring material. By the time I took Fomenko's class, I already knew topology from an unofficial class taught by Dmitry Fuchs, which was so much better. In fact, in order to learn what I wanted, I had to take many classes unofficially, so my total is actually way above 40.
By junior year, we were finally allowed to choose some classes which would count towards our transcripts, and this is what I picked.
I remember these classes much more vividly. I also wrote a graduate thesis: "Models of Representations of Generalized Clifford Algebras." I loved working on that paper.
We had non-math classes too: everyone had to take them.
To graduate, everyone had to pass two state exams: Mathematics and Scientific Communism. Whatever the latter might mean.
Did I mention that I am no longer proud of my former Soviet college education? What a colossal waste of time!
Pete McCabe presented his trick, Persistimis Possessiamo, at the Gathering for Gardner in 2018.
Trick. Pete asked for two volunteers, let's call them Alice and Bob. Bob took out his favorite card, the Queen of Spades, from the deck and put it back following Pete's instructions. Then Alice dealt the deck alternatively into two piles, Bob's and hers, starting with Bob's. Alice took her pile and repeated the same process several times until only one card was left. And, abracadabra: it was Bob's chosen Queen of Spades.
Pete McCabe is interested in scripting magic. In his blog post, Scripting Magic for Zoom, he describes ways to make sure that Bob inserts his card into the 22nd place without using sleight of hand, but rather using a theatrical script which makes the process magical rather than mathematical. The magic part is related to the fact that the number of letters in the trick title, Persistimis Possessiamo, is 22. As a result, he can do the trick on Zoom without ever touching the cards.
Once a magician knows how to manipulate the volunteer to insert the card into a specific place in the deck, the trick becomes deterministic and works on any-sized deck, as long as the magician can calculate where the card goes. We will now perform this calculation.
We denote our card-inserting sequence as a(n), where n is the size of the deck, and a(n) is the place where the card is inserted. For starters, a(2n+1) = a(2n): when the size of the deck is odd, the last card during the first deal goes to Bob, and doesn't effect the other deals. Now, we obviously have a recursion. First, we observe that in order to end up in Alice's pile after the first deal, Bob's chosen card should occupy an even-numbered place. Suppose we start with 2n cards. After the first deal, Bob's chosen card is in the place number a(2n)/2 from the bottom in Alice's pile. That means, the card is in the place number n + 1 − a(2n)/2 from the top. This gives us an equation: a(n) = n + 1 − a(2n)/2, which is equivalent to a recursion: a(2n) = 2(n + 1 − a(n)).
Given that each element of the sequence a(n) is doubled, we are only interested in even-indexed values. Consider b(n) = a(2n) = a(2n+1). Then b(1) = 2, and the recursion for b is b(n) = 2(n + 1 − b⌊n/2⌋).
From here, we get the sequence, which is now sequence A350652 in the OEIS:
2, 2, 4, 6, 8, 6, 8, 6, 8, 6, 8, 14, 16, 14, 16, 22, 24, 22, 24, 30, 32, 30, 32, 22, 24, 22, 24, ... .
Here is a classical puzzle I often give to my students.
Puzzle. The sultan has three red hats and two blue ones. He wants to test his three wizards, who know his hat collection. He asks them to close their eyes and puts a hat on each of their heads. After the wizards open their eyes, they see each other's hats, but not their own. The sultan asks each of them to guess the color of their own hat, without communicating with each other. In this particular test, the sultan only puts red hats on the wizards' heads. Sometime after the wizards open their eyes, one of them guesses his hat's color. How did he guess?
Here is how my students explain the solution. If a wizard sees two blue hats, he immediately knows that his hat must be red. That means, if no one immediately announces their hat's color, at least two of them are wearing red hats. In this case, if a wizard sees one red hat, he knows that his hat must also be red. So such a wizard can guess the color of his hat. If after some more time, no one announces their hat color, all the hats worn must be red.
After the students solve the problem, I run an evil experiment on them. I show the students my two blue and three red hats and ask three volunteers to close their eyes. Then, I put two red hats and one blue hat on their heads, and the blue hat goes on the fastest thinker in the group. I did this experiment many times. Half the time, the fastest thinker overestimates how fast the other students think and guesses, mistakenly, that s/he is wearing the red hat. Gotcha!
After the experiment, we discuss what is really going on in this puzzle. This is how I start my class on common knowledge.
I plan to teach knot theory to my students. So, I made four blue knots which are actually the four simplest non-trivial knots. Then I made the red ones which are mirror images of the blue ones.
Then I fiddled with the figure-eight knots, which are the second ones from the left. Out of all these four types of knots, the figure-eight knot is the only one that is amphichiral: its mirror image is equivalent to itself. It was fun to physically transform the red one to look identical to the blue one. So, I decided to crochet another pair of figure-eight knots for my students to fiddle with.
Did I mention that I hate crocheting?
I grew up relatively poor, but I wasn't aware of it and didn't care. In 7th grade, I went to a new school for children gifted in math. Looking back, I realize that most of my classmates there were privileged. My first clue about my own financial disadvantages arrived when my math teacher, Inna Victorovna, offered me several of her old dresses. I do not remember what she said to me exactly, but I remember she was tactful, so much so that I felt comfortable taking the dresses.
In an instant, I was better dressed than I had ever been. I especially loved the brown dress which I wore for my first visit to Gelfand's seminar.
A few years passed; I went to college and married Andrey. Things got somewhat better financially, but I was still struggling. My mother-in-law, Veronika, was well-off and loved clothes. She had a habit of ordering a new dress from her tailor, every season, four times a year. In Soviet Russia, this was a lot of dresses.
One day, Veronika decided to give me some of her old dresses. Unlike my math teacher, she said something that I will never forget. She told me that she was getting rid of those dresses because they were out of fashion and made her look old. I was in my twenties at the time and didn't want to look old either. However, I didn't have much choice in clothes, so I wore the dresses. I hated them.
Here is a famous matchstick puzzle based on the given picture.
Puzzle. Can you move three matchsticks to turn the fish around?
Here is my bonus puzzle.
Bonus Puzzle. Can you turn the fish by moving two matchsticks?
I usually collect puzzles related to math after each MIT mystery hunt. I just discovered that I never reviewed the 2013 hunt, though I started writing the post. Plus, I knew the puzzles of that year better than other year's puzzles: I was on the writing team. Not to mention, the hunt had some real gems.
I start with mathematical puzzles:
Logic puzzles:
Computer science puzzles:
Crypto puzzles:
Word puzzles:
Misc puzzles:
Other puzzles I worked on:
Below, you can find a lovely problem from the 2016 All-Russian Olympiad suggested by Bogdanov and Knop. I took some liberties translating it.
Problem. King Hiero II of Syracuse has 11 identical-looking metallic ingots. The king knows that the weights of the ingots are equal to 1, 2, ..., 11 libras, in some order. He also has a bag, which would be ripped apart if someone were to put more than 11 libras worth of material into it. The king loves the bag and would kill if it was destroyed. Archimedes knows the weights of all the ingots. What is the smallest number of times he needs to use the bag to prove the weight of one of the ingots to the king?
And a bonus question from me.
Bonus. Add one more weighing to prove the weight of three more ingots.
Do you know that I participated in Linguistics Olympiads in high school? They are not well-known in the US, but the Soviet Union has been running them since 1965. The first International Linguistics Olympiad was conducted in 2003, and the US joined in 2007. They are called Computational Linguistics because you are expected to discover some phenomenon in an unfamiliar language on the fly instead of knowing a lot of languages already. The problems mostly need logic and are a good fit for a person who likes mathematics. However, a feel for languages is very helpful.
I do not remember why I started attending the Olympiads, but I remember that there were two sets of problems: more difficult for senior and less difficult for non-senior years. I used to be really good at these Olympiads. When I was in 8th grade, I finished my problems before the time ran out and started the senior problems. I got two awards: first place for non-senior years and second place for senior years. In 9th grade, I got two first-place awards. I didn't know what to do in 10th grade, which was a senior year at that time in the USSR. I couldn't get two first-place awards, as I could no longer compete in the non-senior category. I felt ashamed that my result could only be worse than in the previous years, so I just didn't go.
The prizes were terrific: they gave me tons of rare language books. In the picture, a guy from the jury is carrying my prizes for me. I immediately sold the books at used-books stores for a good price. Looking back, I should have gone to the Olympiad in 10th grade: my winter boots had big holes.
What do you give a mathematician who likes only mathematics if you want to expand her geographical horizon? I just got such a gift: A math book that made me feel that I was in Australia. The book, A Dingo Ate My Math Book: Mathematics from Down Under, written by Burkard Polster and Marty Ross, has lovely essays, nice pictures, and a strong Australian flavor.
Last revised September 2026