Tanya Khovanova's Math Blog

Do you remember how to divide three apples among four people? Make apple sauce, of course. In the following two puzzles you are not allowed to cut apples. Here is an old riddle:

There are four apples in a basket. How can you divide them among four people, so that one apple remains in the basket?

Here is a variation from Konstantin Knop’s blog:

There are four apples in a basket. How can you divide them among three people, so that no one has more than the others and one apple remains in the basket?

Imagine a magician who comes on stage and performs the following magic trick:

He asks someone in the audience to think of a two-digit number, then subtract the sum of its digits. He waves his wand and guesses that the result is divisible by nine. Ta-Da!

This is not magic. This is a theorem. To make it magical we need to disguise the theorem.

First, there are many ways to hide the fact that we subtract the sum of the digits. For example, we can ask to subtract the digits one by one, while chatting in between. It is better to start with subtracting the first digit. Indeed, if we start with subtracting the second digit, the audience might notice that the result is divisible by 10 and start suspecting that some math is involved here. You can be more elaborate in how you achieve the subtraction of the sum of digits. For example, subtract twice the first digit, then the second, then add back the original number divided by 10.

Second, we need to disguise that the result is divisible by 9. A nice way to do this is implemented in the online version of this trick. The website matches the resulting number to a gift that is described on the page in pale letters. Paleness of letters is important as it is difficult to see that the same gift reappears in a pattern. In my work with students I use the picture on the left. At the end I tell them, “Ta-Da! the resulting number is blue.” Here is the full sized version of the same picture that you can download.

My students are too smart. They see through me and guess what is going on. Then I ask them the real question, “Why do I have some cells with question marks and other symbols?” To give you a hint, I can tell you that the symbols are there for the same reason some blue numbers are not divisible by 9.

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.

Several years ago my son Sergei started a new movement: Sergeism. Followers of this philosophy seek to maximize Sergei’s happiness. Since Sergei’s happiness involves everyone being happy, becoming happy is a consequential goal of his followers.

Let me explain why this might be a perfect religion for many people, not the least myself. My parents didn’t teach me to love myself. They taught me to sacrifice myself and put other peoples’ interests ahead of my own. After reading tons of books and spending hours in therapy, I’ve learned to love myself — well, somewhat. But the truth is, I still feel guilty when I pamper myself. Sergeism eliminates this guilt. I can freely invest in my happiness as a committed member of this movement.

I became a Sergeist when I lost all hope of losing weight. I realized that my own health wasn’t a strong enough motivation. But I’m always glad to skip a cookie in tribute to Sergeism. If, like me, you put others ahead of yourself and never find the time to exercise or the will to refuse deserts, join me. Become a Sergeist and lose weight for Sergei.

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.