This blog has a modern version at http://blog.tanyakhovanova.com/, where you can leave comments. This page contains the copies of recent blog entries. The older copies are here:
If you enjoy this page you can support it by shopping at amazon through this link. Thank you.
"Follow your heart!" This is the most common advice for young people contemplating their future career path. This is not good advice. At some point in my life, the most popular aspiration among my friends' children was to become opera singers. But the world only has room for a few opera singers. All of these children ended up doing something completely unrelated.
Aspiring to be a mathematician is a much more practical dream. There are so many professions that are friendly to mathematicians: actuary, finance, economics, teaching, computer science, cryptography, and programming, to name a few. Unlike opera singers, skilled mathematicians can find a way to get paid for their mathematical gifts.
However, most of the youngsters around me want to be research mathematicians. This is a different story. My adviser, Israel Gelfand, told everyone that if they could survive without mathematics, they should drop it. I did drop mathematics for some time to care for my children, but I couldn't live without mathematics. I fed math to my children for breakfast and pursued math hobbies that could fit a single mother's lifestyle. Well, that means I was mostly working with sequences for the Online Encyclopedia of Integer Sequences and building the database for my Number Gossip website. But I digress.
I agree with Gelfand. Research in math as a career choice is non-trivial. Here are some of the big issues:
So what would I suggest for young people who love math?
Many people who love math do not really love math per se. They love the way of thinking that math encourages. They love logic, generating ideas, precision, innovation, and so on. This makes their potential job search much wider. Such people might enjoy programming, cryptography, data science, actuarial science, finance, economics, computer science, engineering, etc. I know students planned to become mathematicians but tried an internship in finance and found their real passion.
For those who want to be closer to mathematics, there is always teaching: the world needs way more math teachers than research mathematicians. Plus, teaching provides a strong feeling of making an impact.
So what do I suggest for young people who love opera singing?
Many skills are less in demand than mathematics. It is important to be realistic. So here is my advice:
I know a former Soviet mathematician who worked as a night guard and used his quiet work time to invent theorems. He was a good mathematician but couldn't find a research position because he was Jewish. He later immigrated to the US and found a professorship. So sometimes my advice for opera singers works for mathematicians too.
Puzzle. "I guarantee," said the pet-shop clerk, "that this parrot will repeat every word it hears." A customer bought the parrot but found it wouldn't speak a single word. Nevertheless, the clerk told the truth. Explain.
The official answer:
Indeed, in this case, it is not a lie that the parrot will repeat every word it hears. My students had some other ideas. The following answer differs from the official one by one letter, but the spirit of the solution is the same.
Another idea my students had was to introduce a time component.
And a couple of outside-of-the-box answers.
Puzzle. Alice and Bob divide a pie. Alice cuts the pie into two pieces. Then Bob cuts one of those pieces into two more pieces. Then Alice cuts one of the three pieces into two pieces. In the end, Alice gets the smallest and the largest piece, while Bob gets the two middle pieces. Given that both want to get the biggest share of the pie, what is Alice's strategy? How much can she get?
Many years ago, I visited a distant country and rekindled my friendship with a nice couple, Alice and Bob. I changed the names and do not remember the exact words. But here is the story.
One evening, I found myself chatting with Bob, and he decided to open up. He told me he was having an affair. After he finished his long story, I asked him whether he thought Alice might also be having an affair. He replied, "It's impossible. She was never a passionate person. And recently, she became even more cold and distant." I didn't follow his logic but didn't pursue the topic.
Several days later, I chatted with Alice, and she decided to open up. She told me that she had met someone and was having an affair. She told me that she never quite enjoyed sex with her husband, but the new guy fitted her perfectly. For the sake of symmetry, I asked her whether she thought her husband might also be having an affair. She replied, "It's impossible. He is too busy at work, and recently, even more so. He goes on business trips twice a week and is always tired."
I invented this puzzle. It's a variation of something I saw on Facebook.
Puzzle. The future dinner of an anthropophagusphagusphagus met for dinner the past study object of an anthropophaguslogist. What's for dinner?
Here is a famous old joke about Russian propaganda. I heard it when Leonid Brezhnev was General Secretary of the Communist Party of the Soviet Union and Ronald Reagan was the president of the US.
Joke. A Russian newspaper wrote an article about a two-person race between the Russian and the US leaders. They wrote, "Brezhnev got an honorable second place, while Reagan was almost last".
Here is a modern version of this joke I heard going around.
Joke. A Russian TV commentator: Biden cowardly goes to war-torn Kyiv, while Putin heroically hides in his bunker.
Before dividing chores, let's divide a cake. Suppose I bought a two-layer cake. One layer is chocolate and the other is vanilla. Suppose I love chocolate and hate vanilla, My friend, Joe, is the opposite: he loves vanilla and hates chocolate. It's very easy to divide the cake. I take all the chocolate, and Joe takes all the vanilla. I think I am lucky to get the full value of the whole cake. Joe feels lucky too.
My point is that people with different tastes can divide things so that both get more than half by their own estimates.
Let's look at another example. Suppose Alice and Bob are divorcing. Their estate consists of one valuable thing: a portrait of Alice's grandfather. Alice loved her grandfather and values the portrait at 10,000 dollars. Meanwhile, Bob values it the same as its market value, 2,000 dollars. There exists a division algorithm, called the Knaster procedure, which allows them to divide the portrait so that both of them end up with the same amount of money on top of their perceived half of the estate.
I will skip the calculations. The end result is that Alice gets the portrait and pays Bob 3,000 dollars. In her view, she gets a portrait worth 10,000 and loses 3,000. Her total gain is 7,000 dollars, which is 2,000 more than her estimated half. Bob gets 3,000 dollars. In his view, half of the estate is 1,000 dollars, and he gets 2,000 more than that.
The bigger the difference in perceived value, the more each person gets in addition to their expected half. Suppose this difference is D. If you trust my calculations, the Knaster procedure means each person gets D/4, in addition to one half of their estate's perceived value.
The same idea can be applied to chores. Suppose I hate shopping while my husband hates doing the dishes. So, I can do the dishes, and he can shop. And we can live happily ever after without doing the things we hate.
So, theoretically, it is very profitable for two people to live together. Have you seen couples where each one thinks that they won the lottery by marrying their partner? Such couples benefit from dividing chores, appreciate their partners' help, and are happy.
I have seen such couples, though not many. Actually, not many at all. If mathematics says that living together should be profitable, then why are happy couples such a rarity?
I will divide unhappy couples into four categories depending on whether they both benefit from dividing the chores and whether they both appreciate each other.
Benefit and appreciate. In this case, other parameters could affect their happiness: love, sex, children, jobs, and so on. Consider, for example, Alice and Bob. Alice relies on her husband for financial support for her and their small children and appreciates said support. Bob likes how Alice cares for the children and appreciates her for that. However, Alice doesn't love Bob anymore, and Bob wants something special in his sex life but is afraid to request it from Alice. They are both profoundly unhappy.
Benefit and do not appreciate. It is possible that both people do not appreciate each other, or it could be just one. In addition, it could be that a person underestimates the real value of the partner's contribution, or it could be that the appreciation is not enough for the partner. This became a more complicated paragraph than I initially expected. As Lev Tolstoy said, "All happy families are alike; each unhappy family is unhappy in its own way." So, let me have two subcases.
Benefit and do not appreciate. Case 1. Underestimation. Such couples have a good division of labor but underestimate each others' contribution. For example, Bob thinks that staying at home with children is a walk in the park. He thinks his job is way more difficult than his wife's daily caring for the house and the children. He assumes that when he returns from work, the house needs to be clean and dinner ready. He is very angry when this doesn't happen. Alice is very unhappy as she knows how much she actually works.
Benefit and do not appreciate. Case 2. No gratitude. Such couples have a good division of labor but do not express their gratitude sufficiently for the other partner. For example, Alice wants Bob to take her out to dinner as a thank you. Or to say thank you on a regular basis. But Bob brags to his friends that he is lucky in marriage and thinks that this is enough. Everyone but her knows that he feels lucky.
Do not benefit. It is usually one person who is used. There are many ways for people to force their spouses to divide the chores in their favor. There are many types of abusive relationships. I do not even want to give an example. After all, my goal was to discuss the mathematics of chores' division, not to analyze why people do not divide their labor fairly.
Special cases. Life is complicated. Here is the case that doesn't quite fit the cases above as the division of chores with time delays. For example, Alice worked and cared for the children while Bob went to medical school. The benefit for Alice was implied in the future. Bob promised to shower her with money when he would get rich. However, as soon as he got rich, he showered someone else.
The mathematics show that living with a partner can be extremely beneficial for both. But people's emotions are complicated. They do not follow mathematics and often mess it up in more ways than I can imagine.
I got immediately attracted to the puzzle Oleg Polubasov recently posted on Facebook.
Puzzle. A rectangular clearing in a forest is an N-by-M grid, and some of the cells contain a tower. There are no towers in the cells that neighbor the forest. A tower protects its own cell completely and parts of the eight neighboring cells at a depth of half of a cell. Here by neighbors, we mean the cells horizontally, vertically, and diagonally adjacent to the given cell. In particular, if each cell is one square unit, a tower protects four square units. The protected area forms a square with borders that lie in between the grid lines. A tsar knows the towers' locations and wants to calculate the protected area. Prove that the following formula gives the answer: the number of 2-by-2 subgrids that contain at least 1 tower.
I like this puzzle because it has an elegant solution. But there is more. The puzzle reminds me of one of my favorite novels by Arkady and Boris Strugatsky: The Inhabited Island, also known as Prisoners of Power. This is a science fiction novel where Max Kammerer, a space explorer, ends up on a planet with desolate people who, twice daily, experience sudden bouts of enthusiasm and allegiance to the government. Later, it becomes clear that the love for the rulers comes from towers that broadcast mind-control signals suppressing critical thinking and making people prone to believe propaganda.
The novel was written in 1969 but accurately describes the modern Russian propaganda machine. It appears that there is no need for a secret signal. Just synchronized propaganda on government-controlled TV turns off people's brains.
A Whitney umbrella is a cool surface I wanted to crochet. The umbrella continues to infinity, and there is no way I want to crochet the whole thing. I wanted to make a finite portion of a Whitney umbrella surrounding the most exciting point.
The result is seen in the picture. Technically, I crocheted not Whitney umbrellas but topologically equivalent surfaces. I am most proud of my secret — and painful — method of crocheting the self-intersecting segment. One day I will spill it.
As Wikipedia defines it: the Whitney umbrella is the union of all straight lines that pass through points of a fixed parabola and are perpendicular to a fixed straight line parallel to the parabola's axis and lies on its perpendicular bisecting plane. If you look at the picture, the fixed straight line is the self-intersection line, which is a continuation of the line segment where the colors are woven through each other. You can find the parabola as the curve formed by the two-colored edge on either side of the umbrella. Oops, I forgot that only three of these umbrellas are made of two colors.
The Whitney umbrella is a ruled surface, meaning that for every point, there is a straight line on the surface that passes through the point. A ruled surface can be visually described as the set of points swept by a moving straight line.
Oh, look, the stitched rows can pretend to be these straight lines. Actually, if I fold these thingies, the stitched rows ARE straight lines. But, when I make the edges into parabolas, the rows stop being straight. In the real Whitney umbrella, if you look along the intersection line, the straight lines are closer to each other than they are along the parabola. But in crochets, the distances between rows have to be fixed. If my crochets are folded, they become rectangles and ruled surfaces. The real Whitney umbrella does not fold into a plane.
The Whitney umbrella is famous for being the only stable singularity of mappings from R2 to R3. I am grateful to Paul Seidel for emailing me the proof. This singularity is so famous it even has two names: pinch point and cuspidal point. Though my crochets are not exactly Whitney umbrellas, they show this singularity. Hooray! I found a secret way to crochet the most famous stable singularity!
My favorite of the Escher plane tessellations is the one with shells. It is stunning, and the mathematics behind it is beautiful. I want to thank the late John Conway for teaching me the secret of this drawing.
Mathematicians are interested in tessellations because of the symmetries behind them. This tessellation has translational and rotational symmetries. Can you find them?
When I ask my students to find the rotational symmetries, they immediately tell me that they see two different 4-fold points, aka points where 90-degree rotations preserve the drawing. One point, I call G, is where four greenish shells meet, and one point, I call R, is where four reddish shells meet.
As you might have guessed, the students' answer is not quite correct. There is more to the picture. Look at a dark-brown shell that looks like a curvy rectangle. This shape has markings. Now look at a specific point R and its four closest brown shells. You can see that going around this point R, the brown shells alternate their orientation: the darker side of these shells either faces towards point R or away.
The big secret of this artwork is that it contains TWO symmetry groups: a group and a subgroup. If we ignore the markings on the brown shells and consider them one solid color, then point R is indeed a 4-fold symmetry point. In addition, the center of the brown shape is a 2-fold symmetry point. Thus, the symmetry group of this simplified drawing is 442 in orbifold notation.
If we take the markings of the brown shells into account, then point R is not a 4-fold rotation, it is a 2-fold rotation. Point G keeps the property of being a 4-fold rotation. If you know your symmetry groups, you can conclude that there should be another 4-fold rotation. But where is it?
I will spill my answer. The symmetry point G is not ONE symmetry point anymore. There are two different points where greenish shells meet. The dark side of the brown shells faces one of them and looks away from the other.
The dark secret of this drawing is that it demonstrates two symmetry groups: group 442 and its subgroup 442, with different fundamental regions. To see the secret, you must look closely at a dark brown shell and find its darker side.
Here is one of my all-time favorite problems.
Puzzle. Four glasses are placed on the four corners of a square rotating table; each glass is either right-side up or upside down. You need to turn them all in the same direction, either all facing up or all down. You may do so by grasping any two glasses and turning either none, one of them, or both over.
There are two catches: 1) You are blindfolded, and 2) the table is spun after each round. Assuming a bell rings when you have them all facing the same way, how do you do it?
When I first heard this problem, the person who tortured me with it forgot to mention the bell. The problem was impossible: there was no feedback. Then, the bell was mentioned. It was an aha moment: you get information, but only a confirmation that the problem is solved. I tried to think about the puzzle backwards. What could be my last step? Assume that I know that the glasses alternate around the table: up, down, up, down. Then, as my last step, I can reach for the diagonal glasses and turn them over.
This is how you might start thinking about this puzzle. You can find the rest of the solution on the puzzle's Wikipedia page.
Here is a wonderful variation, proposed by Michael Hotiner from Ukraine, that appeared ten years ago at a puzzle competition. This variation is not cheap; the players must pay with their lives, albeit virtual ones.
Puzzle setup. Consider a computer game where at level M, there is an M-sided rotating table with glasses at each corner. The setup is similar to the four-glasses puzzle above. The player is blindfolded, and the table rotates between rounds. As soon as level M is over, if all the glasses face one direction, the bell rings, and the player moves to the next level, M+1.
At each round, the player can decide on the number N of glasses to touch. Upon deciding, they have to pay N! lives for that round. Then, the player can touch the glasses one by one, choosing the next glass depending on how the previous glasses are oriented. After all the glasses are touched, the player can decide which ones to turn upside down.
Let's see what happens at the very beginning of this game. The game starts at level 1, with only one glass. The round is solved before it starts. The cost is 0. The bell rings, and the game immediately goes to level 2.
Consider level 2. If the bell doesn't ring immediately, the glasses face different directions. The cheapest way to proceed is to choose N = 1 and turn any glass. The cost is 1.
Consider level 3. A player can solve it in one round by touching all three glasses and turning them the same way. The cost is 3! = 6. There is a cheaper method that costs 4 lives in two rounds. In the first round, the player can touch any two glasses and turn both of them up. If the bell doesn't ring, then the third glass is upside down. In the next round, the player can touch two glasses. If one is upside down, that glass should be turned up. If both glasses are right side up, then the player should turn both of them over to finish the round.
Puzzle tasks.
- Find a way to pass level 3 using only three lives.
- Find the cheapest way to pass level 4.
- Find the cheapest way for level 6.
- Find a way to pass level 5 using only 30 lives.
"Do you really hope to get hired here? We will never hire a woman physicist." This was my friend's job interview here in the US, though many years ago.
Another friend had an adviser who insisted that to recommend her for a PhD he needed to get into her pant first.
I heard more stories over the years, but my personal experience with gender bias was not so dramatic. Or, it could be that I didn't pay attention. Let me start with my most memorable story.
Why did I get an NSF postdoc? Thirty years ago, I had recently arrived in the US, and just had a baby. A friend suggested that I apply for an NSF postdoc. I applied, and I got it. I was elated, but my happiness didn't last long. It lasted until some bitter guy, who didn't get into a postdoc, told me I got the position only because I was a woman. This was the first time I heard that gender might play a role in such decisions. I was devastated. To this day, I still do not know whether it was my talents or my gender that got me the postdoc. For many years after, I had impostor syndrome.
I wrote a blog essay, Polite Gender Bias, about some of my other stories. Each individual case might not seem gender-related, but they were repeated too many times, so I became sensitive. I call these stories:
Here is a more recent story. I do not know whether I should be proud, angry, or embarrassed.
Where is the sugar? From time to time, in the MIT math department tea room, I am asked where is the sugar, or some similar things. This often happens when there are several males in the room. Why was I chosen? It could be that I look friendly and have a great smile, and this is why people approach me. Or people might assume that, being a woman, I am a secretary who knows everything about the kitchen. Or, they might assume that, being overweight, I love sugar and know about every secret sugar stash in any kitchen.
Here is a story where I know exactly how I felt: I was angry.
Can I say a word? I was invited to a lunch discussion on gender issues at our MIT math department. I am not faculty, so I was sure the only reason I was there was because they wanted more female participants. People around me enthusiastically praised our department's handling of gender issues. I tried to speak many times, but some guy would always interrupt me. I was about to start laughing very loudly at the irony of the situation when our department head finally noticed what was going on and gave me a chance to say a word. The situation was resolved then, but I regret that I didn't start laughing.
As stories pile up, I become more vocal. I am tired of being nice at my own expense. Now people think I am a bitch. So be it.
Putin's bodyguards `collect his excrement on trips abroad and take it back to Russia with them'. This was an article in the Independent. Presumably, Putin is afraid that someone can analyze his waste to get information about his health. Here is a quote from the article.
According to the report, members of the Russian president's Federal Protection Service (FPS) are responsible for collecting his bodily waste in specialised packets which are then placed in a dedicated briefcase for the journey home.
Here is my joke on the subject.
Joke. Putin's guard collecting his waste wrote a book of memoirs. The book has two chapters: Number One and Number Two.
One of my all-time favorite puzzles is about tiling a chessboard with 1-by-2 dominoes. But the chessboard is special: two cells at the opposite corners are removed. A similar elegant chessboard puzzle recently appeared on Facebook.
Puzzle. Our special chessboard has one corner cell removed. On each of the remaining cells, there is an ant. At a signal, each ant moves two cells horizontally or vertically (for example, an ant can move from b3 to b5). Is it possible that after all the ants perform their move, each of the 63 cells will have an ant?
This puzzle is a variation of another puzzle, where all the setup is the same, but each ant moves only one cell horizontally or vertically. You can start with this variation, as it is easier.
This puzzle was in a homework assignment I gave to my students.
Puzzle. In the given configuration of matches, move two matches to form three squares.
I assume that the intended solution is the one below. Its appeal is that it has three squares of the same size and no dangling matches.
As usual, my students were inventive and suggested many alternative solutions.
I recently stumbled upon the following challenge on Facebook.
Puzzle. Type the number of seconds in a week using the smallest number of characters.
I lied. The challenge was to type the same number using the smallest number of clicks on a computer keyboard. There is a slight difference, and I like my version better.
The Wythoff array is an array of integers that can be defined through Wythoff's game. For my purposes, I will skip over Wythoff's game and define his array using Fibonacci numbers.
You probably heard about binary, ternary, decanary, and other bases. I am sure you know the decanary base: it is our standard decimal system. But, have you ever heard about the Fibonacci base?
Let me define it. Any positive integer can be represented uniquely as a sum of distinct Fibonacci numbers that are not neighbors. For example, 16 is 13 + 3. Now, we just write ones for Fibonacci numbers that we used and zeros for unused Fibonacci numbers, so that the digit corresponding to Fibonacci number 1 is last. (The digit corresponding to Fibonacci number 2 is second to last). Thus, 16 in the Fibonacci base is 100100. The result looks like binary, but it will never have two consecutive ones. Such a representation is called the Zeckendorf representation.
What happens if we add 0 at the end of a number in its Zeckendorf representation? This is like multiplying by 2 in binary. But, in the Fibonacci base, it corresponds to replacing every Fibonacci number in the sum with the next Fibonacci number. The result is called the Fibonacci successor. For example, the Fibonacci successor of 16 has the Zeckendorf representation 1001000 and is equal to 21 + 5 = 26.
Now back to the Wythoff array. The first row consists of the Fibonacci numbers in order. Their Zeckendorf representations look like powers of two in binary. The first column consists of numbers ending in 1 in the Zeckendorf representation, in increasing order. In other words, the Zeckendorf representations of numbers in the first column resemble odd numbers in binary. To finish the definition of the array, each number in the nth column is the Fibonacci successor of a number to its left.
As an example, let's calculate the first three numbers of the second row. The smallest number that is not a Fibonacci number and looks odd in its Zeckendorf representation is 4, represented as 101 (remember, we are not allowed to have two consecutive ones). We place 4 in the first column of the second row. The next number in the second row has to be the Fibonacci successor of 4, so its Zeckendorf representation has to be 1010. This number equals 5+2 = 7. The Fibonacci successor of 7 is 11, with Zeckendorf representation 10100.
John Conway and Alex Ryba wrote a paper where they studied the Wythoff array. They continued the array to the left and drew walls according to a few rules. Here is a picture of their result. The picture is too small to make out the numbers, but you can see the shape, which looks like the Empire State Building. Oops, I forgot to mention, the paper is called The Extra Fibonacci Series and the Empire State Building.
My last year's PRIMES STEP senior group (Eric Chen, Adam Ge, Andrew Kalashnikov, Ella Kim, Evin Liang, Mira Lubashev, Matthew Qian, Rohith Raghavan, Benjamin Taycher, and Samuel Wang) studied the Conway-Ryba paper and decided to generalize it to Tribonacci numbers.
Just a reminder. The Tribonacci sequence starts as 0, 0, 1, 1, 2, 4, 7, 13, 24, 44, and continues so that any next term is the sum of the three previous terms. For example, the next term after 44 is 81.
Now we need an analog of the Wythoff array for Tribonacci numbers. My readers might by now guess why I chose the above definition of the Wythoff array. Yes, this definition is perfect for generalizing to Tribonacci numbers.
We start by defining the Tribonacci base. We can represent every integer uniquely as a sum of distinct Tribonacci numbers on the condition that there are no three consecutive Tribonacci numbers in the sum. This is called a Tribonacci representation. We can express it with zeros and ones, and there will never be three ones in a row. For example, 16 can be expressed as a sum of Tribonacci numbers in the following way: 16 = 13 + 2 + 1. Thus, its Tribonacci representation is 10011.
We can define a Tribonacci successor, similarly to the Fibonacci successor, by adding a zero in the Tribonacci representation. For example, the Tribonacci successor of 16 has to have the Tribonacci representation 100110 and is equal to 24 + 4 + 2 = 30.
Now, we define the Tribonacci array similarly to the Wythoff array. The first row of the Tribonacci array consists of distinct Tribonacci numbers in order. The first column consists of integers whose Tribonacci representations end in 1. The number in the nth column is a Tribonacci successor of the number to its left.
We found many cool properties of the Tribonacci array. They are in our paper, Generalizing the Wythoff Array and other Fibonacci Facts to Tribonacci Numbers, posted on the arXiv. Let me give you three examples of these awesome properties.
It is easy to extend the Tribonacci array to the left, but this extension doesn't have the same nice properties as the extension of the Wythoff array. So finding an Empire State Building, or any other building, in the Tribonacci array is futile.
I agreed to review the book, The Raven's Hat, because of the hats. I love hat puzzles. When I give them to my students, I bring hats to class to reenact the solutions.
The book contains eight awesome puzzles as well as ideas for playing with them. I both loved and hated this book. I loved it because it is great, and hated it because it isn't perfect. Let me start with three places I didn't like.
Consider a famous hat puzzle when there are hats of N colors. The sages are in a line, and hats are put on their heads. As usual, they are not allowed to give each other signals. Each of them has to announce their hat's color, and they want to minimize the number of mistakes.
The big idea is to number the colors. The book suggests that the last sage in line calculates the total number of colors they see modulo N and announces the result to the rest. Then the others, starting from the end of the line, one by one, can calculate and name their hat colors. With this strategy, only the last sage in line might be mistaken.
This is a correct solution, but this is the first place I didn't like. I prefer a different strategy, where everyone assumes that the total sum of the hat colors is 0 modulo N. In this case, every sage makes the same calculation: each sage sums up everything they see or hear and subtract the result from 0 modulo N. This solution is more elegant, since all the sages follow the same rule.
Then the book extends the same puzzle to an infinite number of sages. My second point of contention is that the authors think that, in this case, two sages might be mistaken. No. The answer is still the same, there is a strategy where not more than one sage is mistaken. See my blog post for the solution.
My third pet peeve happened when the authors introduced ballroom dancing in the puzzle on picture hanging. What is the connection between picture hanging and ballroom dancing? I'll keep the book's secret. My beef is with how the roles in ballroom dancing are described. Ballroom dancing is usually danced in pairs with asymmetric roles, which, in the past, were designated for males and females. Gender doesn't play such a big role anymore; anyone can dance any role.
The authors are afraid to be politically incorrect by calling the dancers male and female. Instead, they say that the dancers dance male and female parts. Though formally, this choice of words might be politically correct, it still sounds awkward and draws attention to gender. If the authors ever talked to any person who has ever danced, they would have known that there is a much simpler way to describe dance roles. The dancers are divided into leaders and followers.
Did I ever tell you that reviewing my students' writing is part of my job? So I am good at it and like critiquing other people's writing. Now that my complaints are out, the issues with the book are actually minor.
The book is great. I even bought a second inflatable globe because of this book. The game, described in the book, is to rotate two globes randomly and then find a point on the globes in the same relative position towards the center. The game helped me teach my students that any movement of a sphere is a rotation.
My main goal in this post is to describe the only puzzle in the book that I haven't seen before.
Puzzle. In a group of opera singers, there are two stars who are either friends or enemies. Surprisingly, only the host, who is not an opera singer, knows who the stars are and the nature of their relationship (the stars do not know that they are stars and whether or not they are friends). The group's common goal is to identify the stars and to determine whether they are friends or enemies. To do so, they send a few of the singers to sing opera on a stage, which is divided into two halves: left and right. During the opera, the singers do not move between the halves. After the opera is over, the host classifies the opera. If there were no stars or only one star on stage, he classifies it as "neutral". If both stars were on stage, the opera is a big success or a disaster. If both stars are friends and sing on the same half of the stage, or if they are enemies and sing on different halves, then the opera is a big success. Otherwise, it is a disaster. What is the best strategy for a group of five singers to determine who are the stars and what is their relationship? What is the smallest number of operas they have to sing to guarantee that they can figure everything out?
It is weird that two people do not know whether they are friends. But sacrifices are needed for mathematics. I am excited that there is a nontrivial puzzle related to information theory, and it is ternary based. All other such puzzles I know are about weighing coins on a balance scale. I wrote too many papers about coin weighing. Now I can switch to opera singers with passionate relationships, secret from themselves.
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.
2022 is abundant, composite, even, evil, square-free, and untouchable.
In addition, 2022 is the smallest number n such that n, n+1, n+2, and n+3 have the maximal exponents in prime factorization equal 1, 2, 3, and 4 correspondingly. Indeed, 2022 = 2·3·337, 2023 = 7·172, 2024 = 23·11·23, and 2025 = 34·52.
Problem. The numbers 22021 and 52021 are expanded, and their digits are written out consecutively on one page. How many total digits are on the page?
Drabble cartoon, Jun 15 1987, by Kevin Fagan.
Problem. For how many prime numbers p, the expression 2p + p2 is a prime?
* * *
My daughter was talking at her kindergarten about what her parents do for work. She said that her mom catches bugs, invokes demons, and talks to clods.
* * *
I have neither Twitter nor Instagram. I just go for a walk to tell strangers what I ate and drank and how things are at work and at home. I have three followers: a doctor and two policemen.
* * *
Life is like Rubik's cube: fix one side, better not look at the rest.
* * *
My Roomba just devoured a piece of cheese I wanted to pick up and eat. The war between humans and robots is already here.
My friend, John Conway, had a trick to help him with tricky situations. Whenever he needed to make a non-trivial decision, he would ask himself, "What would John Conway do?" As he explained to me, he had in mind the public image he himself created. He liked the image and thought this mental trick helped him be a better, more productive, and not-to-forget, flashier person.
From time to time, I catch myself in need of a decision and ask myself, "What would John Conway do?" And he gave me the answer: I should change the question and ask myself, "What would Tanya Khovanova do?"
Here are some snowball sentences suggested by my students.
Can you invent some other snowball sentences? But first, you need to figure out what they are.
Each year I look at the MIT Mystery hunt puzzles and pick ones related to mathematics, logic, and computer science. I usually give additional comments about the puzzles, but this year's titles are quite descriptive. Let's start with mathematics.
Now Nikoli-type logic puzzles. I really enjoyed "Fun with Sudoku" during the hunt.
And computer science.
I recently wrote a post, A Splashy Math Problem, with an interesting problem from the 2021 Moscow Math Olympiad.
Problem (by Dmitry Krekov). Does there exist a number A so that for any natural number n, there exists a square of a natural number that differs from the ceiling of An by 2?
The problem is very difficult, but the solution is not long. It starts with a trick. Suppose A = t2, then An + 1/An = t2n + 1/t2n = (tn + 1/tn)2 − 2. If t < 1, then the ceiling of An differs by 2 from a square as long as tn + 1/tn is an integer. A trivial induction shows that it is enough for t + 1/t to be an integer. What is left to do is to pick a suitable quadratic equation with the first and the last term equal to 1, say x2 - 6x + 1, and declare t to be its largest root.
Today I present three problems from the 41-st Tournament of the Towns that I liked: an easy one, one that reminds me of the Collatz conjecture, and a hard one.
Problem 1 (by Aleksey Voropayev). A magician places all the cards from the standard 52-card deck face up in a row. He promises that the card left at the end will be the ace of clubs. At any moment, an audience member tells a number n that doesn't exceed the number of cards left in the row. The magician counts the nth card from the left or right and removes it. Where does the magician need to put the ace of clubs to guarantee the success of his trick?
Problem 2 (by Vladislav Novikov). Number x on the blackboard can be replaced by either 3x + 1 or ⌊x/2⌋. Prove that you can use these operations to get to any natural number when starting with 1.
Problem 3 (by A. Gribalko). There are 2n consecutive integers written on a blackboard. In one move, you can split all the numbers into pairs and replace every pair a, b with two numbers: a + b and a − b. (The numbers can be subtracted in any order, and all pairs have to be replaced simultaneously.) Prove that no 2n consecutive integers will ever appear on the board after the first move.
Here is a cute old problem that Facebook recently reminded me of.
Puzzle. By mistake, a clock-maker made the hour hand and the minute hand on a clock exactly the same. How many times a day, you can't tell the current time by looking at the clock? (It is implied that the hands move continuously, and you can pinpoint their exact location. Also, you are not allowed to watch how the hands move.)
Here is the solution by my son who was working on it together with my grandson.
The right way to think about it is to imagine a "shadow minute hand", like this: Start at noon. As the true hour hand advances, the minute hand advances 12 times faster. If the true minute hand were the hour hand, there would have to be a minute hand somewhere; call that position the shadow minute hand. The shadow minute hand advances 12 times faster than the true minute hand. The situations that are potentially ambiguous are the ones where the shadow minute hand coincides with the hour hand. Since the former makes 144 circuits while the latter makes 1, they coincide 143 times. However, of those, 11 are positions where the true minute hand is also in the same place, so you can still tell the time after all. So there are 132 times where the time is ambiguous during the 12-hour period, which leads to the answer: 268.
I love the problem and gave it to my students; but, accidentally, I used CAN instead of CAN'T:
Puzzle. By mistake, a clock-maker made the hour hand and the minute hand on a clock exactly the same. How many times a day can you tell the current time by looking at the clock?
Obviously, the answer is infinitely many times. However, almost all of the students submitted the same wrong finite answer. Can you guess what it was? And can you explain to me why?
Puzzle. What is the probability of getting five Mondays in a 31-days month?
This is easy if we assume that the day of the week for the first day of the month is chosen at random. But we should know better. What is the actual probability? Bonus question: for which day of the week the probability of having this day five times in a 31-days month is the highest?
A cute puzzle found on Facebook:
Puzzle. Four wizards A, B, C, and D, were given three cards each. They were told that the cards had numbers from 1 to 12 written without repeats. The wizards only knew their own three numbers and had the following exchange.
- A: “I have number 8 on one of my cards.”
- B: “All my numbers are prime.”
- C: “All my numbers are composite. Moreover, they all have a common prime factor.”
- D: “Then I know the cards of each of you.”
Given that every wizard told the truth, what cards does A have?
* * *
I surveyed many people who had played Russian roulette. Seems like the probability of dying is actually 0%.
* * *
What has the probability of one in five million?
Zero: there's no 1 in 5000000. Only a five and six zeros.
* * *
Two classmates:
—What did you think of our probability exam yesterday?
—All means to an end.
* * *
My classmate didn't study for our test in probability.
"I'll take my chances", he said.
* * *
I saw my math teacher with a piece of graph paper yesterday. I think he must be plotting something.
* * *
Not all math puns are terrible. Just sum.
* * * (submitted by Sergei Bernstein)
A programmer walks into a bar, holds up two fingers, and says, "I'll have three beers please."
* * *
What is the similarity between me and an experiment involving a biased coin with two tails?
The probability of getting a head is zero.
I've been crocheting hyperbolic surfaces of constant curvature. The process is time-consuming, so while I am crocheting, I wonder about the mathematics of crocheting.
Hilbert's theorem says that I can't embed a hyperbolic plane in 3-dimensional space. The proof is rather involved. But here, I have an explanation from the point of view of a crochet hook. My hook starts with a tiny cycle of four stitches. Then for every x stitches the hook makes y stitches in the next row, where y is greater than x. The extra stitches should be evenly distributed to guarantee that locally every small area is approximately isomorphic to other areas, meaning that the surface has a constant curvature.
The ratio of stitches in the next row to the current row is r = y/x. Thus, the number of stitches in each row increases exponentially. But each row is a fixed height h. That means after k rows, my thingy has to fit inside a ball of radius kh. But the length of the last row is 4rk-1. It becomes huge very fast. As the last row is a physical curve made out of stitches, there is a limit of how much of it I can fit into a given volume, creating a contradiction.
That means, if I start crocheting, something should happen that won't allow me to continue. I decided to experiment and see what actually would happen. Being lazy, I preferred the disaster to happen sooner rather than later. So I chose the ratio of three: for each stitch on my perimeter, I added three new stitches. Shortly after I started to work, the process became more and more difficult. The ball was too tight. It was challenging to hold that thing in the place where I needed to insert the hook. And the loops were getting tighter, making it more exhausting to insert the hook into the proper hole. So each new stitch was taking more and more time to complete.
To my disappointment, the thing didn't explode, as I was secretly hoping: I just couldn't work on it anymore.
I like rewarding my students. Before covid, I used to give them star stickers for good ideas. When I started to teach remotely, I wondered what I should do instead. I could tell them that they had won a star, but it felt too weak. The next idea was to show them a star and tell them that it belonged to them. But that still felt insufficient. Then I had an epiphany. I would say to them they earned a star, show it to them, and stick it to my face. So they, and all the other students, would see it for the rest of the class. The photo shows how I looked at the end of a successful lesson.
Another picture shows what my MathRoots students posted on our Discord channel.
Now that I am back teaching in person, my students asked me to continue sticking their stars to my face. Sometimes I forget about the stars and, after my class, wander around MIT star-covered.
My son, Alexey Radul, wrote a program that finds the largest numbers to start a sequence in the Online Encyclopedia of Integer Sequences (OEIS). To my surprise, the top ten are all numbers consisting of ones only. The largest number is 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111: a number with 128 ones. The sequence is A095646: a(n) is 128 written in base n. It starts with base 1, or more precisely, the unary expansion, which indeed requires 128 ones to express the number 128.
I decided to expand my top list to 50. Again, most of the numbers are bunches of ones: 48 out of the top 50 numbers are unary expansions of numbers 81 through 128. There are two more numbers in the top 50 that are different and belong to awesome sequences.
The first sequence is sequence A033290: Ten consecutive primes in arithmetic progression. It starts with the number 100996972469714247637786655587969840329509324689190041803603417758904341703348882159067229719, which has 93 digits. This number takes 37th place on my list.
The second sequence is sequence A291042: One powerful arithmetic progression with a nontrivial difference and maximal length. The sequence corresponds to a cool puzzle that appeared in the American Mathematical Monthly in 2000. The question was, "What is the length of the longest non-constant arithmetic progression of integers with the property that the kth term is a perfect kth power?" The answer is 5. John P. Robertson proved that such progression can't have 6 terms and provided an example of a sequence with 5 terms, which is the sequence in the OEIS.
Here is how to construct this sequence. Start with an arithmetic progression 1, 9, 17, 25, 33, and multiply each term by 32453011241720: the result is also an arithmetic progression. The first term is trivially a first power. The second term is 32653011241720 = (31351511121710)2 and a square. The third term is 32453011241721 = (38510118177)3 and a cube. The fourth term is 32453211241720 = (3658116175)3 and a fourth power. The fifth term is 32553011251720 = (3556115174)5 and a fifth power.
The sequence starts with the number 10529630094750052867957659797284314695762718513641400204044879414141178131103515625. It has 83 digits, and it takes 48th place on my list.
My students (Matvey Borodin, Eric Chen, Aidan Duncan, Boyan Litchev, Jiahe Liu, Veronika Moroz, Matthew Qian, Rohith Raghavan, Garima Rastogi, Michael Voigt) and I recently wrote a paper connecting the stable marriage problem and Sudoku. I just blogged about it. By the way, my students are in grades 7-9.
On the way, we invented a new type of Sudoku, which we call joint-groups Sudoku. This type is in contrast to a famous type of Sudoku, called disjoint-groups Sudoku. In a disjoint-groups Sudoku, in a particular place in a 3 by 3 box, all the digits are distinct across all the boxes. For example, the top-left corners of nine boxes have all the digits 1 thought 9. This creates nine additional disconnected regions (depending on the placements inside a 3 by 3 box) to add to columns, rows, and boxes that have to contain distinct digits.
For our new type, we wanted the digits in a particular place in each box, instead of being different, to be the same as much as possible. How much of sameness is possible? The first row contains three top-left corners. Thus, by Sudoku rules, these top-left corners have to be distinct. Thus, the top-left corners in all nine boxes have to contain at least three distinct digits. So here is the rule for the joint-groups Sudoku: the nine digits in a particular place in a 3 by 3 box contain not more than three distinct digits. It is easy to see that it means they contain exactly 3 distinct digits, each of them three times.
Here are two Sudoku puzzles from our paper. Each puzzle, when completed, forms a joint-groups Sudoku.
As you may know, I run PRIMES STEP, a local program where we do mathematical research with students in grades 6-9. Last academic year, we looked at the stable marriage problem and discovered its connection to Sudoku. Our paper The Stable Matching Problem and Sudoku (written jointly with Matvey Borodin, Eric Chen, Aidan Duncan, Boyan Litchev, Jiahe Liu, Veronika Moroz, Matthew Qian, Rohith Raghavan, Garima Rastogi, Michael Voigt) is now available at the arxiv.
Consider 3 men and 3 women who want to be married to each other in heterosexual couples. They rank each other without ties. The resulting 6 permutations of numbers 1, 2, and 3 that describe the six rankings are called the preference profile of this group of people. A matching is unstable if two people would be happier to run away together than to marry into the assigned couples. The two potential runaways are called a rogue couple. A matching is called stable if no rogue couple exists. The Gale-Shapley algorithm, invented by Gale and Shapley, finds a stable matching for any preference profile, implying that stable matching is always possible.
We discovered that preference profiles form a natural bijection with ways to place one digit into a Sudoku grid. So we wrote a paper describing the stable marriage, rogue couples, the Gale-Shapley algorithm, soulmates, and such in terms of Sudoku.
Oops, I forgot to explain who the soulmates are. We invented this term to describe two people who rank each other first. Though it is possible to have several stable matchings for the same preference profile if the soulmates exist, they must always be matched together.
We also invented a new Sudoku type, which I will explain next time.
I recently posted my puzzle designed for the MoMath meet-up.
What's in the Name?
Now it is time for the solution.
The solvers might recognize some sequences and numbers. For example, numbers 6, 28, and 496 are famous perfect numbers. Otherwise, the solvers are expected to Google the numbers and the pieces of the sequences with or without X. The best resource for finding the sequences is the Online Encyclopedia of Integer Sequence.
The first “AHA!” happens when the solvers notice that the sequences’ names are in alphabetical order. The order serves as a confirmation of the correctness of the names. It also helps in figuring out the rest of the sequences’ names. The alphabetical order in such types of puzzles hints that the real order is hidden somewhere else. It also emphasizes that the names might be important. The sequences names in order are:
The second “AHA!” moment happens when the solvers realize that the Xs all have different indices. The indices serve as the final order, which in this case is the following:
The third “AHA!” moment happens when the solvers realize that the number of terms is different in different sequences. It would have been easy to make the number of terms the same. This means that the number of terms has some significance. In fact, the number of terms in each sequence matches the length of the name of the sequence. The solvers then can pick the letter from each of the names corresponding to X. When placed in order, the answer reads: NUMBERS.
The answer is related to the puzzle in two ways:
The advantage of this puzzle for zoomed group events is that the big part of the job — figuring out the sequences — is parallelizable. Additionally, it has three “AHA!” moments, which means different people can contribute to a breakthrough. The puzzle also has some redundancy in it:
How can a square be square-free? In order for square-freeness to be interesting, it must be, and is, defined in terms of divisibility by non-trivial squares. So to create this particular mathematical oxymoron, one just needs a trivial square, namely 1.
I collect exciting properties of integers on my Number Gossip website. Did you know that forty is the only number whose letters appear in alphabetical order when written in English? Or that the largest amount of money one can have in US coins without being able to make change for a dollar is 119 cents?
Recently I wrote about a weird occasion that motivated me to search for new properties. Here is a sample of some amusing new updates.
This is the puzzle I designed for yesterday's event at the Museum of Mathematics. This puzzle is without instructions — figuring out what needs to be done is part of the fun. Solvers are allowed to use the Internet and any available tools. The answer to this puzzle is a word.
I've been too busy lately, so I stopped checking my Number Gossip website. Luckily, my website has fans. So one of them, Neil, notified me that my website was hijacked, and instead of describing properties of numbers, was selling steroids. I emailed Dreamhost, my hosting provider. They requested proof that I owned the domain. Why didn't they request proof from the people selling steroids? Or were they selling steroids themselves?
I fixed my steroid issue and since I was thinking about it anyway, I decided to update Number Gossip. I ended up spending tons of time on it — I had ten years of emails with suggestions for new properties, and I went through all of them and added the interesting ones. For example, Joshua Gray emailed me a cute property of 1331 mentioned on Wikipedia: 1331 was said to be the only cube of the form x2 + x − 1. I didn't see how to prove it, so I posted it as a question on mathoverflow. It turns out that 1331 is actually not the only cube of this form. There are three of them: −1 (for x = 0 or −1), 1 (for x = 1 or −2), and 1331 (for x = 36 or −37). So 1331 is the only non-trivial cube with this property. I had to fix Wikipedia. By the way, did you notice a symmetry? Plugging in x and −x − 1 into the quadratic produces the same value.
After processing all the emails related to Number Gossip, I got excited, so I continued working on it and added tons of new unique properties. Some of them I invented myself, some more were inspired by sequences in the OEIS database. I now have a collection of my new favorite unique properties, which I will post soon.
This is the sequence of numbers n such that 3 times the reversal of n plus 1 is the number itself. In other words, n = 3*reversal(n)+1. For example, 742 = 3*247+1. In fact, 742 is the smallest number with this property. How does this sequence continue, and why?
I recently published Sergei Bernstein's awesome Star Battle called Swiss Cheese. Another lovely Star Battle from him is called Hooks. You can play it online at puzz.link.
Star Battle is one of my favorite puzzle types. The rules are simple: put two stars in each row, column, and bold region (one star per cell). In addition, stars cannot be neighbors, even diagonally.
My son, Sergei Bernstein, recently designed a Star Battle with a beautiful solve path. This is my favorite Star Battle so far. I like its title too: Swiss Cheese.
You can also solve it at the puzz.link Star Battle player.
A familect is a portmanteau word formed by squashing together two words: family and dialect. It means words that a family uses that are not a part of a standard vocabulary. This story is about two words that my son Sergei invented, and twenty years later, my family still uses them.
As you might know, I was married three times, and I have two sons, from two different fathers. These fathers were also married several times and had other children. My two sons are half-brothers, and they also have half-siblings through their fathers. Thus a half-sister of a half-brother became a quarter-sister. Inventing this term was quite logical for a son of two mathematicians.
As you can imagine, our family tree is complicated. One day Sergei pointed out that our tree doesn't look like a standard tree and called it a family bush.
A problem from the 2021 Moscow Math Olympiad went viral on Russian math channels. The author is Dmitry Krekov.
Problem. Does there exist a number A so that for any natural number n, there exists a square of a natural number that differs from the ceiling of An by 2?
Yesterday I stumbled upon a picture of John Conway I completely forgot I had: it was saved in a wrong folder. The photo was taken at the MOVES conference in 2015. There is a third person in the original shot, but I do not remember her. I decided to cut her out as I didn't know how to contact her for permission to post this photo.
Konstantin Knop, the world's top authority on coin-weighing puzzles, suggested the following problem for the 2019 Russian Math Olympiad.
Puzzle. Eight out of sixteen coins are heavier than the rest and weigh 11 grams each. The other eight coins weigh 10 grams each. We do not know which coin is which, but one coin is conspicuously marked as an "Anniversary" coin. Can you figure out whether the Anniversary coin is heavier or lighter using a balance scale at most three times?
Found the following cute puzzle on Facebook.
Puzzle. Discover the rule governing the following sequence to find the next term of the sequence: 8, 3, 4, 9, 3, 9, 8, 2, 4, 3.
This is one of my favorite problems given at the 2017 Moscow Olympiad to grades 6 and 7. It was suggested by one of my favorite problem writers: Alexander Shapovalov.
Problem. We are given eight unit cubes. The third of the total number of their faces are blue, and the rest are red. We build a large cube out of these cubes so that exactly the third of the unit cube's visible faces are red. Prove that you can use these cubes to build a large cube whose faces are entirely red.
For the last year, I've been obsessed with Penney's game. In this game, Alice picks a string of coin tosses, say HHH for three heads. After that, Bob picks his string of tosses of the same lengths, say HTH. Then they toss a fair coin. The person whose string shows up first wins. For example, if the tosses are THTTHHH, then Alice wins after the seventh toss. For these particular choices, Bob wins with probability 3/5.
With my PRIMES student, Sean Li, we looked at this game and asked a different question. Suppose Alice picks a pattern of three tosses in a row that are the same. Suppose after that, Bob chooses a pattern of three alternating tosses. Then they toss a fair coin. Alice is hoping for HHH or TTT, while Bob is hoping for HTH or THT. The person whose pattern shows up first wins. For example, if the tosses are THTTHHH, then Bob wins after the third toss. For these particular choices, Bob wins with probability 1/2.
In this example, what actually happens. We assume that the group of two elements acts on the alphabet of two letters. The group's non-identity element swaps letters H and T. We assume that two strings are equivalent if they belong to the same equivalency class under the group action. We call such an equivalency class a pattern.
In the new game we invented, we have an alphabet of any size and any group acting on the alphabet. Then Alice and Bob pick their patterns. After that, they play the Penney's game on these patterns. The answers to all the relevant questions are in our paper, The Penney's Game with Group Action, posted at the math.CO arxiv 2009.06080.
I wrote a paper Confirming the Labels of Coins in One Weighing together with my PRIMES STEP students Isha Agarwal, Paul Braverman, Patrick Chen, William Du, Kaylee Ji, Akhil Kammila, Shane Lee, Alicia Li, Anish Mudide, Jeffrey Shi, Maya Smith, and Isabel Tu. The paper is available at math.HO arxiv:2006.16797. Below my students describe what happens in the paper in their own words.
Tragedy has struck in an iCOINic land known as COINnecticut. One day, while everyone was minding their own business, the vault door of the bank was found to have been forcefully opened. COINcerns spread amongst the COINmoners that someone had tampered with their n sacred COINtainers of coins! The COINtainers are labeled with the integers 1 through n, which usually describe the weight of each of the countless coins inside that corresponding COINtainer. For example, the COINtainer labeled 1 should only COINtain coins that weigh 1 gram, the COINtainer labeled 2 should only COINtain coins that weigh 2 gram, and so on, you get the COINcept.
The acCOINtants COINclude that someone may have switched around the labels on the COINtainers. To resolve this COINplication, aka to check if the labels have been tampered with, they bought a balance scale for a microsCOINpic amount of money. However, they can only use the scale to COINduct one weighing as the angry COINmoners are impatient and wish to withdraw their money ASAP.
The COINfused acCOINtants COINvinced 11 COINspicuous students from Boston's COINmunity to help them. With their COINbined efforts, they COINcluded that indeed, no matter how many COINtainers there are, their labels can be COINfirmed as correct or incorrect with just one weighing! Unfortunately, sometimes, such a weighing requires the use of many coins or coins with a large COINbined weight, which could potentially break the scale. Seeing this COINundrum, the students wished to be eCOINomical and find the least amount of coins or weight they need to place on the scale.
The acCOINtants and the 11 students COINtinued examining the nature of these weighings and discovered patterns that occur within them. They COINfined their research to special weighings they called downhill. They COINfirmed the effectiveness of such weighings to solve the problem at hand. The students estimated the weight and the number of coins, thus COINpleting their task.
My PRIMES STEP students invented several variations of Penney's game. We posted a paper about these new games at math.HO arxiv:2006.13002.
In Penney's game, Alice selects a string of coin-flip outcomes of length n. Then Bob selects another string of outcomes of the same length. For example, Alice chooses HHT, and Bob chooses THH. Then a fair coin is tossed until Alice's or Bob's string appears. The player whose string appears first wins. In our example, Bob has a greater probability of winning, namely, 3/4. If the first two flips are HH, then Alice wins; otherwise, Bob wins.
The reader can check that HHT beats HTT with 2 to 1 odds. Thus, the game contains a non-transitive cycle it is famous for: THH beats HHT beats HTT beats TTH beats THH.
I already wrote about the No-Flippancy game that my students invented. It starts with Alice and Bob choosing different strings of tosses of the same length.
However, in the No-Flippancy game, they don't flip a coin but select a flip outcome deterministically according to the following rule: Let i ≤ n be the maximal length of a suffix in the sequence of "flips" that coincides with a prefix of the current player's string. The player then selects the element of their string with index i + 1 as the next "flip." Alice goes first, and whoever's string appears first in the sequence of choices wins.
My favorite game among the invented games is the Blended game, which mixes the No-Flippancy game and Penney's game.
In the game, they sometimes flip a coin and sometimes don't. Alice and Bob choose their strings as in Penney's game and the No-Flippancy game. Before each coin flip, they decide what they want by the rule of the No-Flippancy game above. If they want the same outcome, they get it without flipping a coin. If they want different outcomes, they flip a coin. Whoever's string appears first in the sequence of `flips' wins.
For example, suppose Alice selects HHT, and Bob selects THH. Then Alice wants H and Bob wants T, so they flip a coin. If the flip is T, then they both want Hs, and Bob wins. If the first flip is H, they want different things again. I leave it to the reader to see that Bob wins with probability 3/4. For this particular choice of strings, the odds are the same as in Penney's game, but they are not always the same.
This game has a lot of interesting properties. For example, similar to Penney's game, it has a non-transitive cycle of choices. Surprisingly, the cycle is of length 6: THH beats HHT beats THT beats HTT beats TTH beast HTH beat THH.
I spend a lot of time working on my blog, and I used to think it would be nice to get some money out of it.
Years ago I got two emails from different ad agencies at the same time. They wanted to place ads at particular essays for $50 a year. I decided to give them a try.
My first correspondent wanted a link on my "Does Alcohol in Teens Lead to Adult Woes?" essay, connecting to a website offering help to alcoholics. I agreed. But when I read the actual text, I couldn't stop laughing. The text they wanted to use was, "Many studies have already claimed that teenage alcoholism could lead to more problems later in life." How ironic! This ad would follow my essay explaining that one of the studies is completely bogus. I rejected them.
The second agency wanted an ad accompanying the essay "Subtraction Problems, Russian Style." I placed it. They wrote to me (and I reproduce it with all of their errors intact):
I really appreciate your efforts on this. As I checked the text link, I have seen that the text link has been label as "Sponsor ad". Kindly omit or delete the word "Sponor ad:" or you may changed it to "Recommended site or Relevant Site" but I would love to prefer the text link be seen as natural meaning no labeled inserted on it.
They wanted me to pretend that I recommend their product. I was naive enough to think that I was selling space on my page, but what they really wanted was for me to lie that I like their product.
Before this experiment, I hoped to find some honest ads for my blog. After this experiment, I realized how much stupidity and falsehood are involved. Since then, I ignore all offers of ads that come my way. That's why my blog is ad-free.
My STEP students invented a coin-flipping game that doesn't require a coin. It is called The No-Flippancy Game.
Alice and Bob choose distinct strings of length n consisting of the letters H (for heads) and T (for tails). The two players alternate selecting the outcome of the next "flip" to add to the sequence by the rule below.
The "flip" rule: Let i < n be the maximal length of a suffix of the sequence of chosen outcomes that coincides with a prefix of the current player’s string. The player then selects the element of their string with index i + 1 as the next term in the sequence.
Alice goes first, and whoever's string appears first in the sequence of choices wins. In layman terms, the game rules mean that the players are not strategizing, but rather greedily finishing their strings.
Suppose n = 2 and Alice chose HH. If Bob chooses HT, then Bob wins. Alice has to choose H for the first flip. Then Bob chooses T and wins. On the other hand, if Bob chooses TT for his string, the game becomes infinite. On her turn, Alice always chooses H, while on his turn Bob always chooses T. The game outcome is an alternating string HTHTHT... and no one wins.
Suppose n = 4, Alice chooses HHTT, and Bob chooses THHH. The game proceeds as HTHHTHHH, at which point Bob wins.
This game is very interesting. The outcome depends on how Alice's and Bob's chosen strings overlap with each other. We wrote a paper about this game, which is available at math.CO arXiv:2006.09588.
Every year I write about latest MIT Mystery Hunt puzzles that might be appealing to mathematicians. Before diving into mathy puzzles, I would like to mention two special ones:
Unfortunately math wasn't prominent this year:
On the other hand, Nikoli-type puzzles were represented very well:
Some computer sciency puzzles:
Cryptography:
A couple of puzzles with the mathy side hidden:
The academic year is over and my junior PRIMES STEP group finished their paper about a classification of magic SET squares. A magic SET square is a 3 by 3 square of SET cards such that each row, column, and diagonal is a set. See an example below. The paper is posted at the arXiv:2006.04764.
In addition to classifying the magic SET squares, my students invented the game of SET tic-tac-toe. It is played on nine cards that form a magic SET square. Two players take turns picking a card from the square. The first player who has a set wins.
One might think that this game is the same as tic-tac-toe, as a player wins as soon at they have cards from the same row, column, or diagonal. But if you build a magic SET square, you might notices that each magic SET square contains 12 sets. In addition to rows, columns, and diagonals, there are sets that form broken diagonals. The picture below shows all the sets in a magic SET square.
There are more ways to win in this game than in a regular tic-tac-toe game. My students proved that ties are impossible in this game. They also showed, that, if played correctly, the first player always wins.
You probably heard in the news that more men are dying from coronavirus than women. But not in Massachusetts. Here the proportion of women is about 52 percent. Why is this the case? Being a woman, should I be worried that I live in Massachusetts?
We know that coronavirus strikes older people harder than younger ones. Thus, we should take age into account. In the US more boys are born than girls. By the age of 40 the ratio evens out. Starting from 40 there are more women than men. With each next age group, the disparity increases. According to a recent US population report and for ages 85 and over there are about 4.22 million women versus 2.33 men: the proportion is almost 2 to 1.
As the coronavirus targets older people, were it gender-neutral, we would have had way more female deaths than male. This is not the case. So it hits males harder than females. But why are the ratios of female to male deaths different for different countries and states?
One simple explanation is that this is related to life expectancy and the age of the population. The older the population, the bigger the percentage of females. Which in turn increases the proportion of female deaths.
It could also be that Massachusetts has good health care making the average age of dying patients older than the average age for the country. This in turn will increase the proportion of females dying from coronavirus. No, I am not worried about living in Massachusetts.
I grew up in the USSR, where I was clueless about the race issues in the US. I have now lived in the US for 30 years, and still feel that there are many things about race that I do not understand. As a result, I am afraid to speak about it. I am worried that I'll say something wrong. Recent events have encouraged me to say something. This is my first piece about race.
I came back to mathematics 10 year ago and started working at MIT. I love it. With some exceptions.
Many mathematicians are introverts or snobs or gender-biased. They are not usually friendly. I often walk down a corridor and people who are coming towards don't notice me. If I say hello, they might not even reply or raise their eyes. It could be they are thinking about their next great theorem and do not notice me. It could be that I am not faculty and therefore do not deserve their attention. It could be that as a women I am not worth of their hello.
Soon after I started working at MIT, I was reminded of one of the reasons I left academia. It was this unfriendliness. But this time was different. First, I had grown a thicker skin. Second, I was working within a group. People who were working with me were nice to me. It was enough and so I stayed.
With time I adopted the same style: passing people without saying `Hello.' Mostly I got tired of people not replying to my hello.
One day I was passing this man who, as had happened many times before, purposefully didn't look at me. I thought my usual thought: another introverted/snobbish/gender-biased mathematician. Then I suddenly stopped in my tracks. My logic was wrong. This guy was Black. The unfriendliness of mathematicians is surely way worse for him than for me. It could be that he is looking at the floor for the same reason I do it: he is afraid that people will ignore his greeting. I failed to think about race deep enough before this realization. What happened next should have happened years earlier.
I took the initiative and the next couple of times I saw him, I said hello. This was all it took—two hellos—to change the whole feeling between us. The guy has a great smile.
It was reported last week that that 37 NYPD members died of covid-19. I assume that they were way below 65. It is known that the coronovirus death rate for people below 65 is a quarter of the total death rate. That means, 37 people in NYPD correspond to at least 150 people in general. Assuming that the mortality rate of coronavirus is 1 percent, the number of infected NYPD members a month ago was 15000.
By now, it could be that more than half of NYPD was infected.
NYPD members have to communicate with people a lot due to the nature of their work. That means they are more prone to being infected. At the same time, they transmit more than people in many other professions.
I can conclude, that about half of the people that are high transmitters in NY have antibodies by now. Assuming they are immune, the covid transmission rate in NY has to be down.
Assuming the immunity stays with people for a while, the second wave in NY can't be as bad as the first one.
Suppose we want to pack a unit square with non-overlapping rectangles that have sides parallel to the axes. The catch is that the lower left corners of all the rectangles are given. By the way, such rectangles are called anchored. Now, given some points in the unit square, aka the lower left corners, we want to find anchored rectangles with the maximum total area.
When the given points are close to the right upper corner of the square, the total area is small. When a single point is in the bottom left corner of the square, we can cover the whole square. The problem becomes more interesting if we add one extra assumption: one of the given points has to be the bottom left corner of the square. In the 1960's, it was conjectured by Allen Freedman that any set of points has an anchored rectangle packing with the area of at least one half. The problem is quite resistant. In 2011, Dumitrescu and Tóth showed that every set of points has a packing of area at least 0.09, which was the first constant bound found, and is the best bound currently known.
I gave this problem to my PRIMES student Vincent Bian. He wrote a paper, Special Configurations in Anchored Rectangle Packings, that is now available at the arxiv. When you look at this problem you see that the number of ways to pack depends on the relative coordinates of the points. That means you can view the points as a permutation. Vincent showed that the conjecture is true for several different configurations of points: increasing, decreasing, mountain, split layer, cliff, and sparse decreasing permutations.
An increasing permutation is easy. There are two natural ways to pack the rectangles. One way, when rectangles are horizontal and each rectangle reaches to the right side of the square (see picture above). Another way, when rectangles are vertical. When you take the union of both cases, the square is completely covered, which means at least one of the cases covers at least half of the square. The worst case scenario, that is, the case when the maximum possible area is the smallest is when your points are placed equidistantly on the diagonal.
Other cases are more difficult. For example, Vincent showed that for a decreasing permutation with n points, the worst case scenario is when the points are arranged equidistantly on a hyperbola xy = (1-1/n)n. The picture shows the configuration for 15 points. The total area is more than one half.
(I wrote this piece for La Recherche. It was translated into French by Philippe PAJOT. You can find this piece and pieces by others at John Horton Conway: a magician of maths disappears.)
Unlike many other mathematicians I know, John Conway cared a lot about the way he presented things. For example, in the puzzle he invented—known as Conway's Wizards—the wizards had to be riding on a bus. Why was the bus so important? You see, the numbers in the puzzle were related to the age of one of the wizards, the number of the bus, and the number of the wizard's children. It was important to John that the readers be able to use a convenient notation a, b and c for these numbers and remember which number is which.
When I give my lecture on integers and sequences, I show my students a list of different famous sequences. The first question from the audience is almost always: "What are the Evil Numbers?" As you can guess the name for this sequence was invented by John Conway. This name was invented together with the name of another sequence which is called Odious Numbers. These two sequences are complementary in the same sense as even and odd numbers are complementary: every natural number is either evil or odious. The names are good, not only because they attract, but also because they help remember what the sequences are. Evil numbers are numbers with an even number of ones in their binary representation. I assume that you can interpolate what the odious numbers are.
When he was lecturing, John used all sorts of tricks to emphasize important points: From time to time I saw him shouting or throwing his shoes. Once I remember him staring at his statement written on the blackboard for a really long time. My neighbor in the lecture hall got uncomfortable. He assumed that John, who was at that time way over 70, was blanking out and had forgotten what he wanted to say. I calmed my neighbor down. It was my fourth time listening to the same lecture, including the same pause. John Conway didn't forget.
The picture was taken on December 21 of 2019 at Parker Life care facility right before dinner.
Every year I review MIT mystery hunt from a mathematician's point of view. I am way behind. The year is 2020, but I still didn't post my review of 2019 hunt. Here we go.
Many puzzles in 2019 used two data sets. Here is the recipe for constructing such a puzzle. Pick two of your favorite topics: Star Trek and ice cream flavors. Remember that Deanna Troi loves chocolate sundae. Incorporate Deanna Troi into your puzzle to justify the use of two data sets.
On one hand, two data sets guarantee that the puzzle is new and fresh. On the other hand, often the connection between two topics was forced. Not to mention that puzzle solving dynamic is suboptimal. For example, you start working on a puzzle because you recognize Star Trek. But then you have to deal with ice cream which you hate. Nonetheless, you are already invested in the puzzle so you finish it, enjoying only one half of it.
Overall, it was a great hunt. But the reason I love the MIT mystery hunt is because there are a lot of advanced sciency puzzles that can only appear there. For example, there was a puzzle on Feynman diagrams, or on characters of representations. This year only one puzzle, Deeply Confused, felt like AHA, this is the MIT Mystery hunt.
Before discussing mathy puzzles I have to mention that my team laughed at Uncommon Bonds.
I will group the puzzles into categories, where the categories are obvious.
Mathy puzzles.
Here are some logic puzzles, in a sense that Sudoku is a logic puzzle.
Now we have logic puzzles or another type, where you need to draw a grid. These are puzzles of the type: Who lives in the White House?
Now we have logic puzzles or yet another type, where you need to figure out which statements are true and which are false.
Now some cryptography.
And some programming.
Miscellaneous.
Every day I check coronavirus numbers in the US. Right now the number of deaths is 288 and the number of recovered is 171. More people died than recovered. If you are scared about the mortality rate, I can calm you and myself down: our government is incompetent—the testing wasn't happening—that means the numbers do not show people who had mild symptoms and recovered. The real number of recovered people should be much higher.
Scientists estimated the mortality rate of coronavirus as being between 1 and 3.5 percent. Also, they say that it usually takes three weeks to die. That means three weeks ago the number of infected people in the US was between 8,000 and 29,000. The official number of cases three weeks ago was 68. I am panicking again—our government is incompetent—three weeks ago they detected between 0.25 and 1 percent of coronavirus cases. If this trend continues, then the official 19,383 infected people as of today means, in reality, somewhere between 2 million and 8 million infected people.
I can calm you and myself down: the testing picked up pace. This means, the ratio of detected cases should be more than 1 percent today. Probably the number of infected people today in the US is much less than 8 million. I am not calm.
My former student, Dai Yang, sent me the following cute puzzle:
Puzzle. You are playing a game with the Devil. There are n coins in a line, each showing either H (heads) or T (tails). Whenever the rightmost coin is H, you decide its new orientation and move it to the leftmost position. Whenever the rightmost coin is T, the Devil decides its new orientation and moves it to the leftmost position. This process repeats until all coins face the same way, at which point you win. What's the winning strategy?
My friend Zeb, aka Zarathustra Brady, invented a new game that uses chess pieces and a chessboard. Before the game, the players put all chess pieces on white squares of the board: white pieces are placed in odd-numbered rows and black pieces are in even-numbered rows. At the beginning all white squares are occupied and all black squares are empty. As usual white starts.
On your turn, you can move your piece from any square to any empty square as long as the number of enemy neighbors doesn't decrease. The neighbors are defined as sharing a side of a square. Before the game starts each piece has zero enemy neighbors and each empty square has at least one white and one black neighbor. That means that on the first turn the white piece you move will increase the number of neighbors from zero to something. As usual, the player who doesn't have a move loses.
As you can immediately see, that number of pairs of enemy neighbors is not decreasing through the game. I tried to play this game making a move which minimizes the increase of the pairs of neighbors. I lost, twice. I wonder if there is a simple strategy that is helpful.
It is important that this game is played with chess pieces in order to confuse your friends who pass by. You can see how much time it takes them to figure out that this game is not chess, but rather a Chessnot. Or you can enjoy yourself when they start giving you chess advice before realizing that this is not chess, but rather a Chessnot.
I heard this puzzle many years ago, and do not remember the origins of it. The version below is from Peter Winkler's paper Seven Puzzles You Think You Must Not Have Heard Correctly.
Puzzle. Jan and Maria have fallen in love (via the internet) and Jan wishes to mail her a ring. Unfortunately, they live in the country of Kleptopia where anything sent through the mail will be stolen unless it is enclosed in a padlocked box. Jan and Maria each have plenty of padlocks, but none to which the other has a key. How can Jan get the ring safely into Maria's hands?
I don't know whether this puzzle appeared before the Diffie-Hellman key exchange was invented, but I am sure that one of them inspired the other. The official solution is that Jan sends Maria a box with the ring in it and one of his padlocks on it. Upon receipt Maria affixes her own padlock to the box and mails it back with both padlocks on it. When Jan gets it, he removes his padlock and sends the box back, locked only with Maria's padlock. As Maria has her own key, she can now open it.
My students suggested many other solutions. I wonder if some of them can be translated to cryptography.
Now that we've looked at the Padlock Puzzle, let's talk about cryptography. I have an imaginary student named Charlie who doesn't know the Diffie-Hellman key exchange. Charlie decided that he can adapt the padlock puzzle to help Alice send a secret message to Bob. Here's what Charlie suggests:
Suppose the message is M. Alice converts it to binary. Then she creates a random binary key A and XORs it with M. She sends the result, M XOR A, to Bob. Then Bob creates his own random key B and XORs it with what he receives and sends the result, M XOR A XOR B, back to Alice. Alice XORs the result with her key to get M XOR A XOR B XOR A = M XOR B and sends it to Bob. Bob XORs it with his key to decipher the message.
Each sent message is equivalent to a random string. Intercepting it is not useful to an evil eavesdropper. The scheme is perfect. Or is it?
Here is a logic puzzle.
Puzzle. You are visiting an island where all people know each other. The islanders are of two types: truth-tellers who always tell the truth and liars who always lie. You meet three islanders—Alice, Bob, and Charlie—and ask each of them, "Of the two other islanders here, how many are truth-tellers?" Alice replies, "Zero." Bob replies, "One." What will Charlie's reply be?
The solution proceeds as follows. Suppose Alice is a truth-teller. Then Bob and Charlie are liars. In this situation Bob's statement is true, which is a contradiction. Hence, Alice is a liar. It follows, that there is at least one truth-teller between Bob and Charlie. Suppose Bob is a liar. Then the statement that there is one truth-teller between Alice and Charlie is wrong. It follows that Charlie is a liar. We have a contradiction again. Thus, Alice is a liar and Bob is a truth-teller. From Bob's statement, we know that Charlie must be a truth-teller. That means, Charlie says "One."
But here is another solution suggested by my students that uses meta considerations. A truth-teller has only one possibility for the answer, while a liar can choose between any numbers that are not true. Even if we assume that the answer is only one of three numbers—0, 1, or 2—then the liar still has two options for the answer. If Charlie is a liar, there can't be a unique answer to this puzzle. Thus, the puzzle question implies that Charlie is a truth-teller. It follows that Alice must be lying and Bob must be telling the truth. And the answer is the same: Charlie says, "One."
You might have noticed that my blogging slowed down significantly in the last several months. I had mono: My brain was foggy, and I was tired all the time. Now I am feeling better, and I am writing again. What better way to get back to writing than to start with some jokes?
* * *
The wife of a math teacher threw him out from point A to point B.
* * *
At the job interview at Google.
—How did you hear about our company?
* * * (submitted by Sam Steingold)
50% of marriages end with divorce. The other 50% end with death.
* * *
People say that I am illogical. This is not so, though this is true.
* * *
Humanity invented the decimal system, because people have 10 fingers. And they invented 32-bit computers, because people have 32 teeth.
* * *
When a person tells me, "I was never vaccinated, and, as you can see, I am fine," I reply, "I also want to hear the opinion of those who were never vaccinated and died."
* * *
I will live forever. I have collected a lot of data over the years, and in all of the examples, it is always someone else who dies.
* * *
Just got my ticket to the Fibonacci convention! I hear this year is going to be as big as the last two years put together.
* * *
I am afraid to have children as one day I will have to help them with math.
This is my favorite puzzle in the last issue of the Emissary, proposed by Peter Winkler.
Puzzle. Alice and Bob each have 100 dollars and a biased coin that flips heads with probability 51%. At a signal, each begins flipping his or her coin once per minute, and betting 1 dollar (at even odds) on each flip. Alice bets on heads; poor Bob, on tails. As it happens, however, both eventually go broke. Who is more likely to have gone broke first?
Follow-up question: As above, but this time Alice and Bob are flipping the same coin (biased 51% toward heads). Again, assume both eventually go broke. Who is more likely to have gone broke first?
Puzzle. You got two envelopes with two distinct real numbers. You chose one of them and open it. After you see the number you are allowed to swap envelopes. You win if at the end you pick the larger number. Find a strategy that gives you a probability more than 1/2 of winning.
Another cute puzzle found on Facebook.
Puzzle. A teacher wrote four positive numbers on the board and invited his students to calculate the product of any two. The students calculated only five of six products and these are the results: 2, 3, 4, 5, 6. What is the last product? What are the original four numbers?
I found this puzzle on Facebook:
Puzzle. Solve this:
1+4 = 5,
2+5 = 12,
3+6 = 21,
5+8 = ?
97% will fail this test.
Staring at this I decided on my answer. Then I looked at the comments: they were divided between 34 and 45 and didn't contain the answer that initially came to my mind. The question to my readers is to explain the answers in the comments and suggest other ones. Can you guess what my answer was?
Puzzle. The length of the day today in Boston is the same as the length of the coming night tonight. What is the total length of both?
My friend Alice reminds me of me: she has two sons and she is never straight with her age. Or, maybe, she just isn't very good with numbers.
Once I visited her family for dinner and asked her point blank, "How old are you?" Here is the rest of the conversation:
Alice: I am two times older than my younger son was 5 years ago.
Bob: My mom is 12 times older than my older brother.
Carl: My younger brother always multiplies every number he mentions by 24.
Bob: My older brother is 30 years older than me.
Carl: My mom is 8 times older than me.
Alice: My older son always multiplies every number he mentions by 2.
How old is everyone?
Last year, when I read an application file of Wayne Zhao to PRIMES, I got very excited because he liked puzzles. And I've always wanted to have a project about puzzles. After Wayne was accepted to PRIMES we started working together. Wayne chose to focus on a variation of Sudoku called Sudo-Kurve.
We chose a particular shape of Sudo-Kurve for this project, which ended up being very rewarding. It is called Cube Sudo-Kurve. The Cube Sudo-Kurve consists of three square blocks. The gray bent lines indicate how rows and columns continue. For example, the first row of the top left block becomes the last column of the middle block and continues to the first row of the bottom right block. As usual each row, column, and square region has to have 9 distinct digits.
Wayne and I wrote a paper Mathematics of a Sudo-Kurve, which has been published at Recreational Mathematics Magazine.
A Cube Sudo-Kurve needs at least 8 clues to have a unique solution. Here we have a puzzle with 8 clues that we designed for our paper.
I've been invited to help with the Puzzle Column at the MSRI newsletter Emissary. We prepared six puzzles for the Fall 2018 issue.
I love the puzzles there. Number 2 is a mafia puzzle that I suggested. Number 6 is a fun variation on the hat puzzle I wrote a lot about. Here is puzzle Number 3.
Puzzle. Let A = {1,2,3,4,5} and let P be the set of all nonempty subsets of A. A function f from P to A is a "selector" function if f(B) is in B, and f(B union C) is either equal to f(B) or f(C). How many selector functions are there?
When I was in grade school, one of the teachers called me Cave Lioness. She hated my unruly hair, which reminded her of a lion's mane. This teacher was obviously very uninformed, for female lions do not have manes.
This name calling had the opposite to the desired effect. I became proud of my mane and didn't ever want to cut it. When I grew older, I opted for convenience and started to cut my hair short—sometimes very short.
Last year I was too busy for barbers, and my hair grew more than I intended. As it turned into a mane, I remembered the story of this nickname.
Once I was giving a math lecture and my phone, which I've never quite understood, was on the desk in front of me. Suddenly it rang. I didn't pick it up, as I proceeded with my lecture. The ringing stopped, while I was explaining a particularly interesting mathematical point. After a minute, my phone said, "I do not understand a word you are saying."
Detective Radstein is investigating a robbery. He apprehends three suspects: Anne, Bill, and Caroline. The detective knows that no one else could have participated in the robbery. During the interrogation the suspects make the following statements:
Detective Radstein also discovered that all three suspects are members of a club called The Halfsies. Every time they speak, they make two statements, one of which is a lie and the other one is true. Who committed the robbery?
I already wrote about my first experience crocheting hyperbolic surfaces. In my first surface I added two more stitches per current stitch. It took me hours to crochet the last row: the same hours it took me to crochet the rest.
For my next project, I reduced the ratio. The light blue thingy has ratio 3/2. I continued making my life simpler. The next project, the purple surface on the left, has ratio 4/3. The last project on the right has a ratio of 5/4 and is my favorite. Mostly because I am lazy and it was the fastest to make.
How much time will it take you to answer the following question?
Can the equation 29x + 30y + 31z = 366 be solved in natural numbers?
Happy 2019, the first 4 digit number to appear 6 times in the decimal expansion of Pi.
By the way, 2019 is the product of two primes 3 and 673. The sum of these two prime factors is a square.
This is not all that is interesting about factors of 2019. Every concatenation of these two prime factors is prime. Even more unusual, 2019 is the largest known composite number such that every concatenation of its prime factors is prime. [Oops, the last statement is wrong, Jan 3,2019]
Happy Happy-go-Lucky year, as 2019 is a Happy-go-Lucky number: the number that is both Happy and Lucky.
In case you are wondering, here is the definition of Happy numbers: One can take the sum of the squares of the digits of a number. Those numbers are Happy for which iterating this operation eventually leads to 1.
In case you are wondering, to build the Lucky number sequence, start with natural numbers. Delete every second number, leaving 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, …. The second number remaining is 3, so delete every third number, leaving 1, 3, 7, 9, 13, 15, 19, 21, …. The next number remaining is 7, so delete every 7th number, leaving 1, 3, 7, 9, 13, 15, 21, …. The next number remaining is 9, so delete every ninth number, etc.
Last revised November 2021