Tanya Khovanova's Math Blog

Kvant was a very popular science magazine in Soviet Russia. It was targeted to high-school children and I was a subscriber. Recently I discovered that a new magazine appeared in Russia. It is called Kvantik, which means Little Kvant. It is a science magazine for middle-school children. The previous years’ archives are available online in Russian. I looked at 2012, the first publication year, and loved it. Here is the list of the math puzzles that caught my attention.

The first three problems are well known, but I still like them.

Problem 1. There are 6 glasses on the table in a row. The first three are empty, and the last three are filled with water. How can you make it so that the empty and full glasses alternate, if you are allowed to touch only one of the glasses? (You can’t push one glass with another.)

Problem 2. If it is raining at midnight, with what probability will there be sunshine in 144 hours?

Problem 3. How can you fill a cylindrical pan exactly half-full of water?

I like logic puzzles, and the next two seem especially cute. I like the Parrot character who repeats the previous answer: very appropriate.

Problem 4. The Jackal always lies; the Lion always tells the truth. The Parrot repeats the previous answer—unless he is the first to answer, in which case he babbles randomly. The Giraffe replies truthfully, but to the previous question directed to him—his first answer he chooses randomly.
The Wise Hedgehog in the fog stumbled upon the Jackal, the Lion, the Parrot, and the Giraffe, although the fog prevented him from seeing them clearly. He decided to figure out the order in which they were standing. After he asked everyone in order, “Are you the Jackal?” he was only able to figure out where the Giraffe was. After that he asked everyone, “Are you the Giraffe?” in the same order, and figured out where the Jackal was. But he still didn’t have the full picture. He started the next round of questions, asking everyone, “Are you the Parrot?” After the first one answered “Yes”, the Hedgehog understood the order. What is the order?

Problem 5. There are 12 cards with the statements “There is exactly one false statement to the left of me,” “There are exactly two false statements to the left of me.” …, “There are 12 false statements to the left of me.” Pete put the cards in a row from left to right in some order. What is the largest number of statements that might be true?

The next three problems are a mixture of puzzles.

Problem 6. Olga Smirnov has exactly one brother, Mikhail, and one sister, Sveta. How many children are there in the Smirnov family?

Problem 7. Every next digit of number N is strictly greater than the previous one. What is the sum of the digits of 9N?

Problem 8. Nine gnomes stood in the cells of a three-by-three square. The gnomes who were in neighboring cells greeted each other. Then they re-arranged themselves in the square, and greeted each other again. They did this one more time. Prove that there is at least one pair of gnomes who didn’t get a chance to greet each other.

As I told you before I was recently diagnosed with severe sleep apnea. My doctor ordered me to use a CPAP machine&mdasha Continuous Positive Airway Pressure machine&mdashthat blows air into my nose and improves the quality of overnight breathing.

I was elated, hoping for a miracle. I haven’t had a good night’s sleep in 20 years. I was so looking forward to waking up rested.

When I went to bed, I put on my nose mask and turned on the machine. The mask was uncomfortable. It gave me headaches and I had to sleep on my back which I do not like. It also had this annoying plastic smell. It took me some time to fall asleep, but eventually I did.

To my disappointment I didn’t wake up rested; I woke up tired as usual. Still, I decided not to give up and continued trying the machine.

Several days passed and I found myself mopping the kitchen floor. I never ever mop floors. I have my cleaning crew do that. That mopping was my first positive sign. Then my relatives started telling me that my voice had changed and had become more energetic. A week later I invited my son and his family for my weekly family dinner, which I have been canceling every previous week for several months.

A month after I began sleeping with the machine, I started having night dreams, something I forgot even existed. After two months, I would wake up and my first thought would be, “What day is it today?” Prior to using the machine, my first waking thought was, “My alarm clock must be broken. It’s impossible that I have to get up now. I feel too weak to stand up.”

My machine is very smart. It records the data from my sleep and uploads it to a website, which my doctor and I can access. Instead of the 37 apnea episodes per hour I had during my sleep study, now I have 1 episode per hour. The quality of my life has changed gradually. I am not yet ready to conquer the world, but I have so much more energy. I’ve even accepted two more job offers, and now I have six part-time jobs. (I’ll tell you all about this some other time.)

There have been some side effects. For some reason I gained 10 pounds during the first two weeks of using the machine. And I feel like an elephant. Not because of my heavy frame, but because my nose mask with its pipe looks like a trunk.

But I prefer feeling like an elephant to feeling like a zombie. This indeed was a miracle, though a very slow-acting miracle.

One day you meet your friend Alice enjoying a nice walk with her husband Bob and their son Carl. They are excited to see you and they invite you to their party.

Alice: Please, come to our party on Sunday at our place at 632 Elm St. in Watertown.
Bob: My wife likes exaggerating and multiplies every number she mentions by 2.
Carl: My dad compensates for my mom’s exaggerations and divides every number he mentions by 4.
Alice: Our son is not like us at all. He doesn’t multiply or divide. He just adds 8 to every number he mentions.

Where is the party?

Since I was a child I prided myself on knowing arithmetic. I knew how to add fractions. I knew that 2/3 plus 1/4 is 11/12. Some kids around me were struggling and often summed it up the wrong way by adding numerators and denominators separately and getting 3/7 as a result.

As I grew older I found more reasons to ignore the wrong way. For example, the result of such addition depends on the representation of a fraction, not on the fraction itself, and this was bad.

Oh well. I was growing older, but not wiser. Now mathematicians study this wrong addition of fractions. They call such a sum a mediant of two rational numbers. To avoid the dependency on the representation of fractions, the fractions are assumed to be in the lowest terms.

Let us start with the sequence of fractions: 0/1 and 1/0. This sequence is called the Stern-Brocot sequence of order 0. The Stern-Brocot sequence of order n is generated from the Stern-Brocot sequence of order n − 1 by inserting mediants between consecutive elements of the sequence. For example, the Stern-Brocot sequence of order 2 is 0/1, 1/2, 1/1, 2/1, 1/0.

Where are the trees promised in the title? We can build a portion of this binary tree out of the sequence of order n in the following manner. First, ignore the starting points 0/1 and 1/0. Then assign a vertex to every number in the sequence. After that, connect every mediant to one of the two numbers it was calculated from. More precisely, if a number first appeared in the i-th sequence, its only parent is the number that first appeared in the sequence i−1.

There is beautiful theorem that states that every non-negative rational number appears in the Stern-Brocot sequences. The proof is related to continued fraction. Suppose a rational number r is represented as a continued fraction [a₀;a₁,a₂,…,a_k], where a_k is assumed to be greater than 1 for uniqueness. Then this number first appears in the Stern-Brocot tree of order a₀ + a₁ + a₂ + … + a_k + 1, and its parent is equal [a₀;a₁,a₂,…,a_k − 1].

My PRIMES student, Dhroova Ayilam, was working on a project suggested by Prof. James Propp. The goal was to find out what happens if we start with any two rational numbers in lowest terms. Dhroova proved that as with the classical Stern-Brocot trees, any rational number in a given range appears in the tree. His paper Modified Stern-Brocot Sequences is available at the arXiv.

I was afraid of my advisor Israel Gelfand. He used to place unrealistic demands on me. After each seminar he would ask his students to prove by the next week any open problems mentioned by the speaker. So I got used to ignoring his requests.

He also had an idea that it is good to learn mathematics through problem solving. So he asked different mathematicians to compile a list of math problems that are important for undergraduate students to think through and solve by themselves. I still have several lists of these problems.

Here I would like to post the list by Andrei Zelevinsky. This is my favorite list, partially because it is the shortest one. Andrei was a combinatorialist, and it is surprising that the problems he chose are not combinatorics problems at all. This list was compiled many years ago, but I think it is still useful, just keep in mind that by calculating, he meant calculating by hand.

Problem 1. Let G be a finite group of order |G|. Let H be its subgroup, such that the index (G:H) is the smallest prime factor of |G|. Prove that H is a normal subgroup.

Problem 2. Consider a procedure: Given a polygon in a plane, the next polygon is formed by the centers of its edges. Prove that if we start with a polygon and perform the procedure infinitely many times, the resulting polygon will converge to a point. In the next variation, instead of using the centers of edges to construct the next polygon, use the centers of gravity of k consecutive vertices.

Problem 3. Find numbers a_n such that 1 + 1/2 + 1/3 + … + 1/k = ln k + γ + a₁/k + … + a_n/kⁿ + …

Problem 4. Let x₁ not equal to zero, and x_k = sin x_k-1. Find the asymptotic behavior of x_k.

Problem 5. Calculate the integral from 0 to 1 of x^−x over x with the precision 0.001.

I regret that I ignored Gelfand’s request and didn’t even try to solve these problems back then.

I didn’t have any photo of Andrei, so his widow, Galina, sent me one. This is how I remember him.

I recently had a home sleep study. I was given a small box which I attached to my chest. I also had to attach a thingy to my finger and put small tubes into my nose. It was relatively easy. Now I have my report:

The total time in bed is 468 minutes. Overall AHI is 37 events per hour. The supine AHI is 58 events per hour. The oxygen saturation baseline is 91%. The hypoxemic burden is 58 minutes. The oxygen saturation nadir is 63%. The heart rate ranges from 76-118 beats per minute.

I didn’t have a clue what all that meant so I hit the Internet. AHI means Apnea–Hypopnea Index, and a normal score is below 5. Anything above 30 indicates severe sleep apnea. Because mine is 37, I now have my diagnosis. My 63% oxygen saturation scared me the most. Wikipedia says 65% or less means impaired mental function. I do not need mental function when I sleep, but Wikipedia also says that loss of consciousness happens at 55%. What would happen if I lose consciousness while I sleep? Can I die? Will I wake up?

Overall the sleep study was a great thing. Now I know the diagnosis and there are ways to treat it. So I am looking forward to my improved energy and health.

But there was something in this report that would bother any mathematician. As you can see apnea gets worse when people sleep on their backs. (Thanks to this study I learned a new English word: supine means lying on the back.) The apparatus that I had to attach to my chest prevented me from sleeping on my stomach, one of my favorite sleep positions.

This report doesn’t say anything about my average AHI when I am not supine. If this average is low, then the solution might be to learn to never sleep on the back. It also means that the oxygen saturation nadir number is not very meaningful. It shows how bad it can be if I am forced to sleep on my back. It doesn’t say much about my standard sleep situation.

When I next see my doctor, I hope she’ll have answers to all my questions.

This story started when my student asked for an explanation for his grade B in linear algebra. He was slightly above average on every exam and the cut-off for an A was the top 50 percent of the class. I wrote a post in which I asked my readers to explain the situation. Here is my explanation.

The picture below contains histogram for a typical first midterm linear algebra exam.

The spike in the lowest range indicates zeros for those who missed the exam.

The mean is 74.7 and the median 81.5. As you can see the median is 7 points higher than the mean. That means that if a student performs around average on all the exams, s/he is in the bottom half of the class.

But this is not the whole story. In addition to the above, MIT allows students to drop the class after the second midterm. Suppose 30 students with lower grades drop the class; then the recalculated median for the first midterm for the students who finish the course goes up to 85. This is a difference of more than 10 points from the original average.

If this was a statistics class, then I could have told the puzzled student that he deserves that B. Instead I told him that he didn’t even have the highest score among those with Bs. Somehow that fact made him feel better.

Here is my new logic puzzle.

I thought of a positive integer that is below 100 and is divisible by 7. In addition to the public knowledge above, I privately tell the units digit of my number to Alice and the tens digit to Bob. Alice and Bob are very logical people, but their conversation might seem strange:

Alice: You do not know Tanya’s number.
Bob: I know Tanya’s number.

What is my number?

I recently posted a cute puzzle about the emperor and his wizards from 2015 Moscow Math Olympiad. It is time for the solution and two new variations. But first let me repeat the puzzle.

The emperor invited 2015 of his wizards to a carnival. Some of the wizards are good and others are evil. The good wizards always tell the truth, whereas the evil ones are free to say anything they want. The wizards know who is who, but the emperor does not.

During the carnival, the emperor asks every wizard a yes-or-no question. Then he expels one of the wizards from his kingdom. The expelled wizard leaves through a magic door, which allows the emperor to discover what kind of wizard s/he was. After that the emperor starts the next round of questions and expels another wizard. He continues the rounds until he decides to stop.

Prove that it is possible to expel all the evil wizards, while expelling not more than one good wizard.

Solution: Suppose the emperor knows one good wizard. Then he can create a chain that leads him to an evil wizard, as follows: Suppose Alice is the known good wizard. The emperor chooses some other wizard, say Bob, and asks Alice “Is Bob evil?” (which question Alice, being good, will answer truthfully). If Bob turns out to be evil, the emperor can expel him, and repeat this (starting with Alice) next round. If Bob turns out to be good, the emperor can continue, asking Bob about Carl, etc, until he either reaches an evil wizard or determines that all remaining wizards are good.

The above means that, if the emperor can find a good wizard sacrificing at most one (other) good wizard, the emperor will succeed. Here is one way to do this: Let the emperor pick Anne and ask everyone else whether Anne is good. Suppose at least one wizard, say Bill, says that Anne is good. The emperor expels Bill. If Bill is revealed to be evil, then nothing is lost, and the emperor can try again next round. If Bill is revealed to be good, then the emperor knows for sure that Anne is good and can proceed to expel all the remaining evil wizards with the chain method above. If, on the other hand, no one says that Anne is good, then the emperor expels Anne. If Anne proves evil, the emperor didn’t lose anything and can conduct another trial next round. If Anne proves good, then everyone else is evil, and the emperor can expel them all without asking any more questions.

I like the mathematical part of the puzzle, but I hate when innocent people are punished. So I couldn’t stop thinking about the puzzle until I found a variation where no good wizard need be expelled (the magic properties of the gate are redundant now, since the emperor only ever sends evil wizards through it):

The setting is the same as before, except the emperor knows how many evil wizards there are. He wants to expel all the evil wizards without expelling a good one. For which numbers of evil wizards can he do that?

In addition, my reader Leo Broukhis couldn’t get through my CAPTCHAs to post a comment (I think there’s something wrong with the plugin) but sent me a variation of the original puzzle by email:

There is again an emperor with a magic gate plagued with a superfluity of evil wizards, but this time the carnival is not very long, so the emperor does not have the luxury of asking the wizards many questions. In fact, he is restricted to asking all of them the same single question, after which he will conduct a series of expulsions that must rid the empire of evil wizards while expelling at most one good one. The one saving grace to this difficult situation is that the question need not be limited to “Yes” or “No” answers—an unbounded (single) integer is permissible.

My favorite problem at the 2015 Moscow Olympiad was about an emperor and his wizards.

8-10th grade. Designed by I.V. Mitrofanov. The emperor invited 2015 of his wizards to a carnival. Some of the wizards are good and others are evil. The good wizards always tell the truth, whereas the evil ones are free to say anything they want. The wizards know who is who, but the emperor does not.

During the carnival, the emperor asks every wizard a yes-or-no question. Then he expels one of the wizards from his kingdom. The expelled wizard leaves through a magic door, which allows the emperor to realize what kind of wizard s/he was. After that the emperor starts the next round of questions and expels another wizard. He continues the rounds until he decides to stop.

Prove that it is possible to expel all the evil wizards, while expelling not more than one good wizard.

Two other problems at the Olympiad were noteworthy—because no competitor solved them:

11th grade. Designed by O.N. Kosuhin. Prove that it is impossible to put the integers from 1 to 64 (using each integer once) into an 8 by 8 table so that any 2 by 2 square considered as a matrix has a determinant that is equal to 1 or −1.

9th grade. Designed by A.Y. Kanel-Belov. Do there exist two polynomials with integer coefficients such that each of them has a coefficient with absolute value exceeding 2015, but no coefficient of their product has absolute value exceeding 1?