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?
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.
Do you love or hate abstractions?
Do you prefer discreet or continuous problems?
Is the real-life impact or inner beauty of your project more important to you?
Do you enjoy having a visual component to your project?
Do you like when problems involve programs and calculations?
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.
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.
