Tanya Khovanova's Math Blog

The following variation of a Bulls and Cows problem was given at the Fall 2008 Tournament of the Towns:

A test consists of 30 true or false questions. After the test (answering all 30 questions), Victor gets his score: the number of correct answers. Victor doesn’t know any answer, but is allowed to take the same test several times. Can Victor work out a strategy that guarantees that he can figure out all the answers after the 29th attempt? after the 24th attempt?

Let’s assume that we have a more general problem. There are n questions, and a(n) is the smallest number of times we need to take the test to guarantee that we can figure out the answers. First we can try all combinations of answers. This way we are guaranteed to know all the answers after 2ⁿ attempts. The next idea is to start with a baseline test, for example, to say that all the answers are true. Then we change answers one by one to see if the score goes up or down. After changing n − 1 answers we will know the answers to the first n − 1 questions. Plus we know the total number of true answers, so we know the answers to all the questions. We just showed that a(n) ≤ n.

This is not enough to answer the warm-up question in the problem. We need something more subtle.

Let’s talk about the second part of the problem. As we know, 24 = 4 ⋅ 6. So to solve the second part, on average, we need to find five correct answers per four tests. Is it true that a(5) ≤ 4? If so, can we use it to show that a(30) ≤ 24?

The following three cases are the most fun to prove: a(5) = 4, a(8) ≤ 6, and a(30) ≤ 24. Try it!

By the way, K. Knop and L. Mednikov wrote a paper (available in Russian) where they proved that a(n) is not more than the smallest number k such that the total number of ones in the binary expansion of numbers from 1 to k is at least n − 1. Which means they proved that a(30) ≤ 16.

Tanya Khovanova and Richard Stanley

On the left is a puzzle from the 2000 Qualifying Test for USA and Canada teams to compete in the world puzzle championship. A set of all 21 dominoes has been placed in a 7 by 6 rectangular tray. The layout is shown with the pips replaced by numbers and domino edges removed. Draw the edges of the dominoes into the diagram to show how they are positioned.

We would like to discuss the mathematical theory behind this puzzle using a toy example below. Only three dominoes: 1-1, 1-2, 2-2 are positioned on the board and the goal is to reconstruct the positioning:

Let’s connect adjacent numbers with segments to show potential dominoes and color the segments according to which domino they represent. The 1-1 edge is colored green, the 1-2 — blue, and the 2-2 — red. Now our puzzle has become a graph, where the numbers are vertices, the segments are edges, and the edges are colored. In this new setting, the goal of the puzzle is to find edges of three different colors so that they do not share vertices.

The next picture represents the line graph of the previous graph. Now the colors of the vertices correspond to different potential dominoes. Vertices are connected if the corresponding dominoes share a cell. In the new setting finding dominoes that do not share a cell is equivalent to finding an independent set. The fact that we need to use all possible dominoes means that we want the most colorful independent set.

I just discovered a Russian Internet Linguistics Olympiad. Even though most linguistics problems are not translatable, this time we are lucky. My favorite problem from this Olympiad is related to chemical elements — their names in Russian have the same logical structure as in English. Keep in mind, the problem doesn’t assume any knowledge of chemistry. Here is the problem:

The formulae for chemical elements and their names are given below in mixed order:
C₃H₈, C₄H₆, C₃H₄, C₄H₈, C₇H₁₄, C₂H₂;
Heptene, Butine, Propane, Butene, Ethine, Propine.

1. Match the formulae with their names. Explain your solution.
2. Write the names of the elements with the following formulae: C₂H₄, C₂H₆, C₇H₁₂.
3. Write the formulae for the following elements: Propene, Butane.

My co-author Konstantin Knop wrote a charming book, Weighings and Algorithms: from Puzzles to Problems. The book contains more than one hundred problems. Here are a couple of my favorites that I translated for you:

There is one gold medal, three silver medals and five bronze medals. It is known that one of the medals is fake and weighs less than the corresponding genuine one. Real medals made of the same metal weigh the same and from different metals do not. How can you use a balance scale to find the fake medal in two weighings?

There are 15 coins, out of which not more than seven are fake. All genuine coins weigh the same. Fake coins might not weigh the same, but they differ in weight from genuine coins. Can you find one genuine coin using a balance scale 14 times? Can you do it using fewer weighings?

You might get the impression that the latter problem depends on two parameters. Think about it: It is necessary that the majority of the coins are genuine in order to be able to solve the problem. In fact, the number of weighings depends on just one parameter: the total number of coins. Denote a(n) the optimal number of weighings needed to find a genuine coin out of n coins, where more than half of the coins are genuine. Can you calculate this sequence?

Hint. I can prove that a(n) ≤ A011371(n-1); that is, the optimal number of weighings doesn’t exceed n − 1 − (number of ones in the binary expansion of n−1).

Tanya Khovanova and Alexey Radul

We all heard this paradoxical statement:

This statement is false.

Or a variation:

True or False: The correct answer to this question is ‘False’.

Recently we received a link to the following puzzle, which is similar to the statement above, but has a cute probabilistic twist:

If you choose an answer to this question at random, what is the chance you will be correct?

1. 25%
2. 50%
3. 60%
4. 25%

There are four answers, so you can choose a given answer with probability 25%. But oops, this answer appears twice. Is the correct answer 50%? No, it is not, because there is only one answer 50%. You can see that none of the answers are correct, hence, the answer to the question—the chance to be correct—is 0. Now is the time to introduce our new puzzle:

If you choose an answer to this question at random, what is the chance you will be correct?

1. 25%
2. 50%
3. 0%
4. 25%

I found a new Russian Olympiad for high schools related to universities. I translated my favorite problems from last year’s final round. These are the math problems:

8th grade. In a certain family everyone likes their coffee with milk. At breakfast everyone had a full cup of coffee. Given that Alex consumed a quarter of all consumed milk and one sixth of all coffee, how many people are there in the family?

8th grade. How many negative roots does the equation x⁴ − 5x³ − 4x² − 7x + 4 = 0 have?

10th grade. Find a real-valued function f(x) that satisfies the following inequalities for any real x and y: f(x) ≤ x and f(x+y) ≤ f(x) + f(y).

I liked the physics problems even more:

8th grade. Winnie-the-Pooh weighs 1 kg. He hangs in the air with density 1.2kg/m³ next to a bee hive. He is holding a rope connected to a balloon. Estimate the smallest possible diameter of the balloon, assuming that this happens on Earth.

10th grade. Two containers shaped like vertical cylinders are connected by a pipe underneath them. Their heights are the same and they are on the same level. The cross-sectional area of the right container is twice bigger than the left’s. The containers are partially filled with water of room temperature. Someone put ice into both containers: three times more ice into the right one than into the left one. After that, the containers are closed hermetically. How will the water level will change after the ice melts completely:

• The levels will not change.
• The level on the left will be higher than on the right.
• The level on the left will be lower than on the right.
• The answer depends on the initial volume of water in the containers.

Once I talked to my friend Michael Plotkin about IQ tests, which we both do not like. Michael suggested that I run an experiment and send a standard IQ question for children to my highly-educated friends. So I sent a mass email asking:

What’s common between an apple and an orange?

I believe that the expected answer is that both are fruits.

Less than half of my friends would have passed the IQ test. They gave four types of answer. The largest group chose the expected answer.

The second group related the answer to language. For example, apples and oranges both start with a vowel and they both have the letters A and E in common.

The third group connected the answer to what was on their minds at the time:

• Apples and oranges are both healthy foods that I enjoy, but do not eat as often as I should.
• They have the same thing in common as do a saxophone and a guitar.
• You can’t shave with either one.
• They both are much worse than a cucumber in the bedroom.

And the last group were people who just tried to impress me:

• One should not decide that n apples is better than m oranges just because n > m.
• They both can provoke the discovery of gravity.
• You can’t compare apples and oranges.
• Existence.
• They both have fundamental meaning in food tongue.
• They’re topologically homeomorphic.

If my friends with high IQs have given so many different answers, I would expect children to do the same. The variety of answers is so big that no particular one should define IQ. By the way, my own well-educated kids’ answers are quoted above — and they didn’t go with the standard answer. I’m glad they never had IQ tests as children: I’m sure they would never have passed.

I am just wondering:

What is the largest integer consisting of distinct digits such that, in its English pronunciation, all the words start with the same letter?

I continue to wonder:

What is the largest integer consisting of the same digit such that, in its English pronunciation, all the words start with distinct letters?

I already gave an example of the kinds of problems that were given to Jewish people at the oral entrance exam to the math department of Moscow State University. In fact, I have a whole page with a collection of such problems, called Jewish problems or Coffins. That page was one of the first pages I created when I started my website more than ten years ago.

When my son Alexey was in high school, I asked him to help me type these problems into a file and to recover their solutions from my more than laconic notes, and solve the problems that I didn’t have notes for. He did the job, but the file was lying dormant on my computer. Recently I resurrected the file and we prepared some of the solutions for a publication.

The problems that were given during these exams were very different in flavor: some were intentionally ambiguous questions, some were just plain hard, some had impossible premises. In our joint paper “Jewish Problems” we presented problems with a special flavor. These are problems that have a short and “simple” solution, that is nonetheless very difficult to find. This way the math department of MSU was better protected from appeals and complaints.

Try the following problem from our paper:

Find all real functions of real variable F(x) such that for any x and y the following inequality holds: F(x) − F(y) ≤ (x − y)².

I will give a talk on the subject for UMA at MIT on October 18, at 5pm.

What’s “plagiarism”? It’s when you take someone else’s work and claim it’s your own. It’s basically STEALING.

Ideas improve. The meaning of words participates in the improvement. Plagiarism is necessary. Progress implies it. It embraces an author’s phrase, makes use of his expressions, erases a false idea, and replaces it with the right idea.

Perhaps the Russians have done the right thing, after all, in abolishing copyright. It is well known that conscious and unconscious appropriation, borrowing, adapting, plagiarizing, and plain stealing are variously, and always have been, part and parcel of the process of artistic creation. The attempt to make sense out of copyright reaches its limit in folk song. For here is the illustration par excellence of the law of Plagiarism. The folk song is, by definition and, as far as we can tell, by reality, entirely a product of plagiarism.

If you copy from one author, it’s plagiarism. If you copy from two, it’s research.