Tanya Khovanova's Math Blog

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:

• Analysis
• Analytical Geometry
• Advanced Algebra
• Theoretical Mechanics
• Linear Algebra and Geometry
• Differential Equations
• Partial Differential Equations
• Functions of Complex Variables
• Probability and Statistics
• Differential Geometry and Topology
• Numerical Methods
• Introduction to Mathematical Logic
• Control Theory
• Analysis III
• Computer Science and Programming
• Programming Practice
• Physics
• History and Methodology of Mathematics
• Thesis Work

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.

• Infinite-Dimensional Representations of Lie Groups
• Theory of Functions of Many Complex Variables
• Representations of Lie Groups
• Discrete Mathematics

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.

• History of the Communist Party of the USSR
• Philosophy of Marxism-Leninism
• Political Economy
• Scientific Communism
• Foundations of Scientific Atheism
• Soviet Law
• Foreign Language (English)
• Physical Education
• Foundations of Marx-Lenin’s Aesthetics

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:

• In the Details by Derek Kisman. This is one of my favorite puzzles ever involving evil fractal word search. I even posted the puzzle and the solution on my blog.
• Integers and Sequence by me. I used my number gossip database to include cool facts about numbers. The numbers form sequences, as hinted by the title. (The title had a typo: sequences should be plural.)
• Permuted by Victoria de Quehen, David Roe, and Andrew Fiori, with illustrations by Kiersten Brown, Turing machine by Adam Hesterberg, and ideas from Daphna Harel and David Farhi. The puzzle has many mini puzzles related to different areas of mathematics.
• Basic Alphametics by David Farhi and Casey McNamara. I love this puzzle and often give it to my students.
• 50/50 by Derek Kisman; server by Ben Buchwald. This is a multi-layered statistics puzzle with a fantastic design and should be included in statistics books. It was the most difficult puzzle of the hunt. Unfortunately, the link is broken, but luckily, I blogged about this puzzle.

Logic puzzles:

• Color Sudoku by Byon Garrabrant and Tanya Khovanova.
• Turnary Reasoning by Timothy Chow, Alan Deckelbaum, and Tanya Khovanova. The puzzle looks like a mixture of chess, checkers, and Magic the Gathering.
• Paint-by-Symbols by R.M. Baur, based on an idea by Eric Wofsey. As the name suggests, this is a paint-by-numbers puzzle.
• Time Conundrum by David Farhi. Many people loved this puzzle.
• Portals by Palmer Mebane. Ten interconnected Nikoli-type logic puzzles. It is a very difficult puzzle with a fantastic design; I immensely enjoyed testing it.
• Random Walk by Jeremy Sawicki. Another Nikoli-type masterpiece that I enjoyed.
• Lineup by Charles Steinhardt and Palmer Mebane. Another paint-by-numbers with a twist.
• Agricultural Operations by Palmer Mebane, based on an idea by Dan Zaharopol. Kenken with a mathematical twist. It might be the most mathematical puzzle in the hunt, a masterpiece that I greatly enjoyed.
• Lojicomix by Robyn Speer and Alex Rozenshteyn; art by DD Liu.

Computer science puzzles:

• This Page Intentionally Left Blank by Dan Gulotta, with some help from Robyn Speer. Another puzzle worthy of textbooks: It covers different ways how information can be hidden.
• Halting Problem by Dan Gulotta. You have to analyze programs in different languages: the programs are designed to run for a VERY LONG time.
• Evolution by Karen Rustad; idea and some screenshots by Asheesh Laroia. A puzzle about email clients.
• Git Hub by Robyn Speer. A git repository puzzle.
• Call and Response by Asheesh Laroia, Glenn Willen, and Charles Steinhardt. You are given only an IP address.

Crypto puzzles:

• Infinite Cryptogram by Anders Kaseorg.
• Security Theater by Sean Lip. I enjoyed this puzzle that uses various ways to encrypt information.
• Open Secrets by Tanya Khovanova and Robyn Speer. A puzzle with many famous ciphers.
• Caesar’s Palace by Jason Alonso, with casino-formatting by Robyn Speer, clue phrase by Adam Hesterberg. An encrypted crossword which I greatly enjoyed.
• Famous Last Letters by David Farhi. Another encrypted crossword.

Word puzzles:

• Split the Difference by R.M. Baur and Eli Bogart. A puzzle with cryptic clues, which I enjoyed.
• Mind the Gaps by R.M. Baur and Eli Bogart. You are given an empty rectangular grid without black cells and cryptic crossword clues.
• Changing States by Charles Steinhardt, Robyn Speer, and David Roe. A lovely easy puzzle which I enjoyed tremendously.
• Wordplay by Ken Fan, Matt Jordan, Tanya Khovanova, Derek Kisman, and Ali Lloyd. You are given grouped cryptic clues.
• Plead the Fifth by Eli Bogart and R.M. Baur, based on an idea by Eric Wofsey. An elegant puzzle with several AHA moments.
• CrossWord Complex by Robin Baur, Eli Bogart, and Jeff Manning. The puzzle consists of six crosswords that turn into serious mathematics.
• Ex Post Facto by Derek Kisman; idea by Tom Yue. An inventive multi-layered crossword, which I greatly enjoyed.
• The Alphabet Book by Halimeda Glickman-Hoch and Robyn Speer, based on an idea by Bryce Herdt. Loved it.
• Funny Story by Lilly Chin, Eric Mannes, and Jenny Nitishinskaya.
• Loss By Compression by Charles Steinhardt and Robyn Speer. A cool puzzle.
• A Regular Crossword by Dan Gulotta, based on an idea by Palmer Mebane. A hexagonal crossword with regular expressions as clues.
• A Set of Words by David Farhi. You are given several boggle grids. I loved this puzzle very much.
• Czar Cycle by Yasha Berchenko-Kogan. This is a weird puzzle that uses English, Russian, and Greek alphabets.

Misc puzzles:

• Substance Abuse by David Reiley and Timothy Chow, with assistance from Jill Sazama, Shrenik Shah, and Glenn Willen.
• Puzzle-Regarding Vehicle by Katie Steckles, Paul Taylor, and Ali Lloyd. An interesting and difficult puzzle.
• A Walk Around Town by Sean Lip, Ludwig Schmidt, and Freddie Manners, with help from Mary Fortune and Jonathan Lee. The puzzle looks like a walk around town but has more to it. The idea is awesome.
• Something in Common by Dan Gulotta and Tanya Khovanova.
• Too Many Seacrest by Robyn Speer. A cool and funny puzzle.
• Analogy Farm by Robyn Speer, Adam Hesterberg, and Alan Deckelbaum; additional code by Anthony Lu and John Stumpo. A superb analogy game. I loved it so much that after we solved it, I came back and resolved it myself. I am not sure it works anymore, though.
• I Can See For Miles by David Roe, based on an idea by Charles Steinhardt. You are given aerial views of buildings. I usually do not like puzzles that involve googling, but using google maps in this puzzle made me feel like I am flying around the world.

Other puzzles I worked on:

• Cambridge Waldo by Tanya Khovanova starring Ben Buchwald, Adam Hesterberg, Yuri Lin, Eric Mannes, and Casey McNamara. The goal of this puzzle was to allow a chance for people to go for a walk around Cambridge. I am not sure we were successful: it could be that people used Google street-views to solve this puzzle.
• Lost in Translation Gaetano Schinco, Natalie Baca, and Tanya Khovanova. You are given tangrams.
• Linked Pairs by Herman Chau and Rahul Sridhar, with crosswords by Adam Hesterberg, Dan Gulotta, and Jenny Nitishinskaya, Manya Tyutyunik, and Tanya Khovanova. You are given three crossword grids, each with two sets of clues.
• Magic: The Tappening by John Wiesemann, with help from Dan Gulotta and Tanya Khovanova.

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.