Tanya Khovanova's Math Blog

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.

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?

I want to come back to a middle-school Olympiad problem I posted a while ago.

Streamline School Olympiad 2000 (8th grade). You have six bags of coins that look the same. Each bag has an infinite number of coins and all the coins in the same bag weigh the same amount. Each different bag contains coins of a different weight, ranging from 1 to 6 grams exactly. There is a label (1, 2, 3, 4, 5, 6) attached to each bag that is supposed to correspond to the weight of the coins in that bag. You have only a balance scale. What is the least number of times you need to weigh the coins in order to confirm that the labels are correct?

The answer is unpretentious: one weighing is enough. We can take one 5-gram coin, two 4-gram coins, three 3-gram coins, four 2-gram coins and five 1-gram coins for the total of 35 grams. This number is not divisible by 6, so we can add one more 1-gram coin and weigh all of them against six 6-gram coins. I leave it to the reader to show that this solution works and to extrapolate the solution for any number of bags.

My new challenge is to find a weighing for the above problem using the smallest number of coins. What is the number of coins in such a weighing for a given number of bags?

I manually calculated this number for a small number of bags, but I would like to get a confirmation from my readers. Starting from 6 bags, I don’t know the answer. Can you help me?

I lead recitations for a Linear Algebra class at MIT. Sometimes my students are disappointed with their grades. The grades are based on the final score, which is calculated by the following formula: 15% for homework, 15% for each of the three midterms, and 40% for the final. After all the scores are calculated, we decide on the cutoffs for A, B, and other grades. Last semester, the first cutoff was unusually low. The top 50% got an A.

Some students who were above average on every exam assumed they would get an A, but nonetheless received a B. The average scores for the three midterm exams and for the final exam were made public, so everyone knew where they stood relative to the average.

The average scores for homework are not publicly available, but they didn’t have much relevance because everyone was close to 100%. However, a hypothetical person who is slightly above average on everything, including the homework, should not expect an A, even if half the class gets an A. There are two different effects that cause this. Can you figure them out?

Have you ever solved a CalcuDoku puzzle, or a MathDoku puzzle? Maybe you have, but you do not know it. Many incarnations of this puzzle are published under different names. The MIT’s Tech publishes it as TechDoku. What distinguishes this puzzle type from most others is that it is trademarked. The registered name is KenKen. So anyone can invent and publish a KenKen puzzle as long as they do not call it KenKen.

In this variously named puzzle you need to reconstruct a Latin square, where cells of a square are grouped into regions called cages. Each cage has a number and an operation (addition, subtraction, multiplication, division) in the upper-left corner of the cage. The operation applied to the numbers in the cage must result in a given value. For non-commutative operations (subtraction and division), the operation is applied starting from the largest number in the cage.

These are my two NOT KenKen puzzles. I will call them TomToms, the name for this puzzle used by Tom Snyder in his The Art of Puzzle LINK blog. In the TomTom variation, cages without a number in a corner are allowed and the operation might be missing, but it has to be one of the standard four. The first puzzle I call Three Threes and the second is a minimalistic version where only one number without the operation is given.

But my goal today is not to discuss KenKen or its ekasemans. Ekaseman is the reverse of the word namesake. My son Alexey invented the term ekaseman to denote a different name for the same thing. My real goal is to discuss a new type of puzzle that can be called Crypto KenKen. In this puzzle the digits in the corner are encrypted using a substitution cipher: each digit corresponds to its letter. I first saw this puzzle at Tom Snyder’s blog, where it is called TomTom (Cipher). I think the crypto version of this puzzle deserves its own name. So I suggest PamPam: it is an encryption of KenKen as well as TomTom. And it would be nice to have a female name for a change.

Skyscraper puzzles are one of my favorite puzzles types. Recently I discovered a new cute variation of this puzzle on the website the Art of Puzzles. But first let me remind you what the skyscraper rules are. There is an n by n square grid that needs to be filled as a Latin square: each number from 1 to n appears exactly once in each row and column. The numbers in the grid symbolize the heights of skyscrapers. The numbers outside the grid represent how many skyscrapers are seen in the corresponding columns/row from the direction of the number.

The new puzzle is called Skyscrapers (Sum), and the numbers outside the grid represent the sum of the heights of the skyscrapers you see from this direction. For example, if the row is 216354, then from the left you see 8(=2+6); and from the right you see 15(=4+5+6).

Here’s an easy Skyscrapers (Sum) puzzle I designed for practice.

The Art of Puzzles has four Skyscrapers (Sum) puzzles that are more difficult than the one above:

• Skyscrapers (Sum) by Grant Fikes
• Skyscrapers (Sum) by Thomas Snyder
• Dr. Sudoku Prescribes #146 — Skyscrapers (Sum)
• Dr. Sudoku Prescribes #69 — Skyscrapers (Sum)

I recently wrote a post about the ApSimon’s Mints problem:

New coins are being minted at n independent mints. There is a suspicion that some mints might use a variant material for the coins. There can only be one variant material. Therefore, fake coins weigh the same no matter where they’ve been minted. The weight of genuine coins is known, but the weight of fake coins is not. There is a machine that can precisely weigh any number of coins, but the machine can only be used twice. You can request several coins from each mint and then perform the two weighings in order to deduce with certainty which mints produce fake coins and which mints produce real coins. What is the minimum total of coins you need to request from the mints?

The post was accompanied by my paper Attacking ApSimon’s Mints.

Unfortunately, both the post and the paper contain wrong information. They both state that the number of coins as a sequence of the number of mints is 1, 2, 4, 8, 15, 38, 74. This is wrong. I took this data from the sequence A007673 in the OEIS database. The sequence had incorrect data lying dormant for 20 years. I believe that the sequence was generated from the paper of R. K. Guy and R. J. Nowakowsky, ApSimon’s Mints Problem, published in Monthly in 1994. To the credit of Guy and Nowakowsky, they never claimed to find the best solution: they just found a solution, thus providing a bound for the sequence. Someone mistook their solution for the optimal one and generated the sequence in the database.

After my post, my readers got interested in the problem and soon discovered the mistake. First Konstantin Knop found a solution for 6 mints with 30 coins and for 7 mints with 72 coins. Konstantin is my long-time collaborator. I trust him so I was sure the sequence was flawed. Then someone located a reference to a paper in Chinese A New Algorithm for ApSimon’s Mints Problem. Although none of my readers could find the paper itself nor translate the abstract from Chinese. But judging from the title and the formulae it was clear that they found better bounds than the sequence in the database. My readers got excited and tried to fix the sequence. David Reynolds improved on Konstantin’s results with a solution for 6 mints with 29 coins and for 7 mints with 52 coins. David did even better on his next try with 28 and 51 coins correspondingly. He also found a solution with 90 coins for 8 mints. Moreover, his exhaustive search proved that these were the best solutions.

Now the sequence in the database is fixed. It starts 1, 2, 4, 8, 15, 28, 51, 90.

For future generations I would like to support each number of the sequence by an example. I use the set P(Q) to represent the sequence of how many coins are taken from each mint for the first(second) weighing. For one mint, only one coin and one weighing is needed. ApSimon himself calculated the first five values, so they were not in dispute.

• a(2) = 2: P=(1,0) and Q=(0,1). Found by ApSimon.
• a(3) = 4: P=(0,1,2) and Q=(1,1,0). Found by ApSimon.
• a(4) = 8: P=(0,1,2,3) and Q=(1,0,2,2) or P=(0,1,1,4), Q=(2,0,1,1). Found by ApSimon.
• a(5) = 15: P=(0,1,1,4,5) and Q=(2,1,2,5,0). Found by ApSimon.
• a(6) = 28: P=(1,2,2,5,5,0) and Q=(0,1,2,1,8,10). Found by Robert Israel, Richard J. Mathar, and David Reynolds,
• a(7) = 51. P=(2,3,7,2,8,12,0) and Q=(0,2,1,7,7,12,12). Found by David Applegate and David Reynolds.
• a(8) = 90. P=(4,6,6,7,3,13,15,3) and Q=(4,0,1,6,12,12,1,27). Found by David Applegate and David Reynolds.

There is a solution for nine mints using 193 coins that is not confirmed to be optimal. It was found by David Reynolds: P=(1,2,4,12,5,4,20,39,43) and Q=(0,1,3,3,25,33,34,18,27). In addition, David Reynolds provided a construction that reduces the upper bound for n mints to (3⁽ⁿ⁺¹⁾−2n−3)/4. The following set of coins work: P=(1,3,7,15,…,2ⁿ−1) and Q=(1,4,13,40,…,(3ⁿ−1)/2).