Tanya Khovanova's Math Blog

by Andrew Buchanan, Tanya Khovanova, and Alex Ryba

We got this problem from Rados Radoicic:

A 7 by 7 board is covered with 38 dominoes such that each covers exactly 2 squares of the board. Prove that it is possible to remove one domino so that the remaining 37 still cover the board.

Let us call a domino covering of an n by n board saturated if the removal of any domino leaves an uncovered square. Let d(n) be the number of dominoes in the largest saturated covering of an n by n board. Rados’ problem asks us to prove that d(7) < 38.

Let’s begin with smaller boards. First we prove that d(2) = 2. Suppose that 3 dominoes are placed on a 2 × 2 board. Let us rotate the board so that at least two of the dominoes are horizontal. If they coincide, then we can remove one of them. If not, they completely cover the board and we can remove the third one. Similarly, you can check all the cases and show that d(3) = 6.

Now consider a saturated domino covering of an n × n board. We can view the dominoes as vertices of a graph, joining two if they share a cell of the board. No domino can share both cells with other dominoes, or we could remove it. Hence, each domino contains at most one shared cell. This means that all the dominoes in a connected component of the graph must overlap on a single shared cell. Hence, the only possible connected components must have the following shapes:

The largest shape in the picture is the X-pentomino. We can describe the other shapes as fragments of an X-pentomino, where the center and at least one more cell is intact. We call these shapes fragments.

A saturated covering by D dominoes corresponds to a decomposition of the n × n board into F fragments. Note that a fragment with k cells is made from k − 1 dominoes. Summing over the dominoes gives: D = n² − F. Thus, in order to make D as large as possible, we should make F as small as possible. Let f(n) be the minimal number of fragments that are required to cover an n by n board without overlap. Then d(n) = n² − f(n).

Consider the line graph of the n by n board. The vertices of the line graph correspond to cells in the original board and the edges connect vertices corresponding to neighboring cells. Notice that in the line graph our fragments become all star graphs formed by spokes coming out from a single central node. Thus a decomposition of a rectangular board into fragments corresponds to a covering of its line graph by star graphs. Consider an independent set in the line graph. The smallest independent set has the same number of elements as the smallest number of stars that can cover the graph. This number is called a domination number.

Now let’s present a theorem connecting domino coverings with X-pentomino coverings.

Theorem. f(n) equals the smallest number of X-pentominoes that can cover an n by n board allowing overlaps and tiles that poke outside, which is the same as the domination number of the corresponding line graph.

The proof of this theorem and the solution to the original puzzle is available in our paper: “Saturated Domino Coverings.” The paper also contains other theorems and discussions of other boards, not to mention a lot of pictures.

The practical applications of star graph coverings are well-known and widely discussed. We predict a similar future for saturated domino coverings and its practical applications, two examples of which follow:

First, imagine a party host arranging a plate of cookies. The cookies must cover the whole plate, but to prevent the kids sneaking a bite before the party, the cookies need to be placed so that removal of just one cookie is bound to expose a chink of plate. This means the cookies must form a saturated covering of the plate. Of course the generous host will want to use a maximal saturated covering.

For the second application, beam yourself to an art museum to consider the guards. Each guard sits on a chair in a doorway, from where it is possible to watch a pair of adjacent rooms. All rooms have to be observed. It would be a mistake to have a redundant guard, that is, one who can be removed without compromising any room. Such a guard might feel demotivated and then who knows what might happen. This means that a placement of guards must be a saturated domino covering of the museum. To keep the guards’ Union happy, we need to use a maximal saturated covering.

We would welcome your own ideas for applications of saturated coverings.

I recently posted an essay Binary Bulls without Cows with the following puzzle:

The test Victor is taking consists of n “true” or “false” questions. In the beginning, Victor doesn’t know any answers, but he is allowed to take the same test several times. After completing the test each time, Victor gets his score — that is, the number of his correct answers. Victor uses the opportunity to re-try the test to figure out all the correct answers. We denote by a(n) the smallest numbers of times Victor needs to take the test to guarantee that he can figure out all the answers. Prove that a(30) ≤ 24, and a(8) ≤ 6.

There are two different types of strategies Victor can use to succeed. First, after each attempt he can use each score as feedback to prepare his answers for the next test. Such strategies are called adaptive. The other type of strategy is one that is called non-adaptive, and it is one in which he prepares answers for all the tests in advance, not knowing the intermediate scores.

Without loss of generality we can assume that in the first test, Victor answers “true” for all the questions. I will call this the base test.

I would like to describe my proof that a(30) ≤ 24. The inequality implies that on average five questions are resolved in four tries. Suppose we have already proven that a(5) = 4. From this, let us map out the 24 tests that guarantee that Victor will figure out the 30 correct answers.

As I mentioned earlier, the first test is the base test and Victor answers every question “true.” For the second test, he changes the first five answers to “false,” thus figuring out how many “true” answers are among the first five questions. This is equivalent to having a base test for the first five questions. We can resolve the first five questions in three more tests and proceed to the next group of five questions. We do not need the base test for the last five questions, because we can figure out the number of “true” answers among the last five from knowing the total score and knowing the answers for the previous groups of five. Thus we showed that a(mn) ≤ m a(n). In particular, a(5) = 4 implies a(30) ≤ 24.

Now I need to prove that a(5) = 4. I started with a leap of faith. I assumed that there is a non-adaptive strategy, that is, that Victor can arrange all four tests in advance. The first test is TTTTT, where I use T for “true” and F for “false.” Suppose for the next test I change one of the answers, say the first one. If after that I can figure out the remaining four answers in two tries, then that would mean that a(4) = 3. This would imply that a(28) ≤ 21 and, therefore, a(30) ≤ 23. If this were the case, the problem wouldn’t have asked me to prove that a(30) ≤ 24. By this meta reasoning I can conclude that a(4) ≠ 3, which is easy to check anyway. From this I deduced that all the other tests should differ from the base test in more than one answer. Changing one of the answers is equivalent to changing four answers, and changing two answers is equivalent to changing three answers. Hence, we can assume that all the other tests contain exactly two “false” answers. Without loss of generality, the second test is FFTTT.

Suppose for the third test, I choose both of my “false” answers from among the last three questions, for example, TTFFT. This third test gives us the exactly the same information as the test TTTTF, but I already explained that having only one “false” answer is a bad idea. Therefore, my next tests should overlap with my previous non-base tests by exactly one “false” answer. The third test, we can conclude, will be FTFTT. Also, there shouldn’t be any group of questions that Victor answers the same for every test. Indeed, if one of the answers in the group is “false” and another is “true,” Victor will not figure out which one is which. This uniquely identifies the last test as FTTFT.

So, if the four tests work they should be like this: TTTTT, FFTTT, FTFTT, FTTFT. Let me prove that these four tests indeed allow Victor to figure out all the answers. Summing up the results of the last three tests modulo 2, Victor will get the parity of the number of correct answers for the first four questions. As he knows the total number of correct answers, he can deduce the correct answer for the last question. After that he will know the number of correct answers for the first four questions and for every pair of them. I will leave it to my readers to finish the proof.

Knop and Mednikov in their paper proved the following lemma:

If there is a non-adaptive way to figure out a test with n questions by k tries, then there is a non-adaptive way to figure out a test with 2n + k − 1 questions by 2k tries.

Their proof goes like this. Let’s divide all questions into three non-overlapping groups A, B, and C that contain n, n, and k − 1 questions correspondingly. By our assumptions there is a non-adaptive way to figure out the answers for A or B using k tries. Let us denote subsets from A that we change to “false” for k − 1 non-base tests as A₁, …, A_k-1. Similarly, we denote subsets from B as B₁, …, B_k-1.

Our first test is the base test that consists of all “true” answers. For the second test we change the answers to A establishing how many “true” answers are in A. In addition we have k − 1 questions of type Sum: we switch answers to questions in A_i ∪ B_i ∪ C_i; and type Diff: we switch answers to (A ∖ A_i) ∪ B_i. The parity of the sum of “false” answers in A − A_i + B_i and A_i + B_i + C_i is the same as in A plus C_i. But we know A‘s score from the second test. Hence we can derive C_i. After that we have two equations with two unknowns and can derive the scores of A_i and B_i. From knowing the number of “true” answers in A and C, we can derive the same for B. Knowing A and A_i gives all the answers in A. Similarly for B. QED.

This lemma is powerful enough to answer the original puzzle. Indeed, a(2) = 2 implies a(5) ≤ 4, and a(3) = 3 implies a(8) ≤ 6.

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?