Tanya Khovanova's Math Blog

As you might have guessed from the title, this essay is about domino tilings.

Suppose a subset of a square grid has area N, and the number of possible domino tilings is T. Let’s imagine that each cell is contributing a factor of x tilings to the total independently of the others. Then we get that x^N = T. This mental exercise suggests a definition: we call the nth root of T the degree of freedom per square for a given region.

Let’s consider a 1 by 2k rectangle. There is exactly one way to tile it with dominoes. So the degree of freedom per square of such a rectangle is 1. Now consider a 2 by k rectangle. It has the same area as before, and we know that there should be more than one tiling. Hence, we expect the degree of freedom to be larger than the one in the previous example. The number of tilings of a 2 by k rectangle is F_k-2, where F_k is k^th Fibonacci number. So the degree of freedom for large k will be approximately the square root of the golden ratio, which is about 1.272.

You might expect that squares should give larger degrees of freedom than rectangles of the same area. The degree of freedom for a large square is about 1.3385. You can find more information in the beautiful paper Tilings by Federico Ardila and Richard P. Stanley.

Let’s move from rectangles to Aztec diamonds. They are almost like squares but the side of the diamond is aligned with diagonals of the dominoes rather than with their sides. See the sample diamonds in the picture above, which Richard Stanley kindly sent to me for this essay.

It is easier to calculate the degree of freedom for Aztec diamonds than for regular squares. The degree is the fourth root of 2, or 1.1892…. In the picture below created by James Propp’s tiling group you can see a random tiling of a large Aztec diamond.

Look at its colors: horizontal dominoes are yellow and blue; vertical ones are red and aquamarine. You might wonder what rule decides which of the horizontal dominoes are yellow and which are blue. I will not tell you the rule; I will just hint that it is simple.

Back to freedom. As you can see from the picture, freedom is highly non-uniform and depends on where you live. Freedom is concentrated inside a circle called the arctic circle, perhaps because the areas outside it are frozen for lack of freedom.

Now I would like to expand the notion of freedom to give each cell its own freedom. For a large Aztec diamond, I will approximate freedom with a function that is one outside the arctic circle and is uniform inside. The Aztec diamond AZ(n) consists of 2n(n+1) squares, shaped like a square with side-length n√2. So the area of the circle is πn²/2. Hence we can calculate the freedom inside the circle as the π^th root of 2, which is about 1.247. This number is still much less than the degree of freedom of a cell in a large square.

Jorge Tierno sent me a link to the following puzzle:

There is a certain country where everybody wants to have a son. Therefore, each couple keeps having children until they have a boy, then they stop. What fraction of the children are female?

If we assume that a boy is born with probability 1/2 and children do not die, then every birth will produce a boy with the same probability as a girl, so girls will comprise half of all children.

Now, I wonder why everyone would want a boy? Y-chromosomes are much shorter than X-chromosomes. If a man wants to pass his genes to the next generation, a daughter should be preferable as she keeps more genes from the father. I am a mother of two boys, so my granddaughters will have my X-chromosome while my grandsons will have my ex-husband’s Y-chromosome, so to keep my genes in the pool I should be more interested in granddaughters.

But I digress. I started writing this essay because in the original puzzle link the answer was different from mine. Here is how the other argument goes:

Half of all families have zero girls, a quarter have 1/2 girls, 1/8 have 2/3 girls, and so on. If we sum this up the expected ratio of girls to boys is (1/2)0 + (1/4)(1/2) + (1/8)(2/3) + (1/16)(3/4) + … which adds to 1 − ln 2, which is about 30%.

What’s wrong with this solution?

I found this cute problem in the Russian book Sharygin Geometry Olympiad by Zaslavsky, Protasov and Sharygin.

Find numbers p and q that satisfy the equation: x² + px + q = 0.

The book asks you to find a mistake in the following solution:

By Viète’s formulae we get a system of equations p + q = − p, pq = q. Solving the system we get two solutions: p = q = 0 and p = 1, q = −2.

What is wrong with this solution?

I wrote how the written entrance exam was used to keep Jewish students from studying at Moscow State University, but the real brutality happened at the oral exam. Undesirable students were given very difficult problems. Here is a sample “Jewish” problem:

Solve the following equation for real y:

Here is how my compatriots who studied algebra in Soviet high schools would have approached this problem. First, cube it and get a 9th degree equation. Then, try to use the Rational Root Theorem and find that y = 1 is a root. Factoring out y − 1 gives an 8th degree equation too messy to deal with.

The most advanced students would have checked if the polynomial in question had multiple roots by GCDing it with its derivative, but in vain.

We didn’t study any other methods. So the students given that problem would have failed it and the exam.

Unfortunately, this problem is impossible to appeal, because it has an elementary solution that any applicant could have understood. It goes like this:

Let us introduce a new variable: x = (y³ + 1)/2. Now we need to solve a system of equations:

This system has a symmetry which we can exploit. The graphs of the functions x = (y³ + 1)/2 and y = (x³ + 1)/2 are reflections of each other across the line x = y. As both functions are increasing, the solution to the system of equations should lie on the line x = y. Hence, we need to solve the cubic y = (y³ + 1)/2, one of whose roots we already know.

Now I offer you another problem without telling you the solution:

Four points on a plane used to belong to four different sides of a square. Reconstruct the square by compass and straightedge.

by Tanya Khovanova and Alex Ryba

The following problem appeared at the Gillis Math Olympiad organized by the Weizmann Institute:

A foreign government consists of 12 ministers. Each minister has 5 friends and 6 enemies amongst the ministers. Each committee needs 3 ministers. A committee is considered legitimate if all of its members are friends or all of its members are enemies. How many legitimate committees can be formed?

Surprisingly, this problem implies that the answer doesn’t depend on how exactly enemies and friends are distributed. This meta thought lets us calculate the answer by choosing an example. Imagine that the government is divided into two factions of six people. Within a faction people are friends, but members of two different factions dislike each other. Legitimate committees can only be formed by choosing all three members from the same faction. The answer is 40.

We would like to show that actually the answer to the problem doesn’t depend on the particular configuration of friendships and enmities. For this, we will count illegitimate committees. Every illegitimate committee has exactly two people that have one enemy and one friend in the committee. Let’s count all the committees from the point of view of these “mixed” people. Each person participates in exactly 5*6 committees as a mixed person. Multiply by 12 (the number of people), divide by 2 (each committee is counted twice) and you get the total 180. This gives an answer of 40 for the number of legitimate committees without using a particular example.

What interests us is the fact that the number of illegitimate, as well as legitimate, committees is completely defined by the degree distribution of friends. For any set of people and who are either friends or enemies with each other, the number of illegitimate committees can be calculated from the degree distribution of friends in the same way as we did above.

Any graph can be thought of as representing friendships of people, where edges connect friends. This cute puzzle tells us that the sum of the number of 3-cliques and 3-anti-cliques depends only on the degree distribution of the graph.

As a non mathematical comment, the above rule for legitimate committees is not a bad idea. In such a committee there is no reason for two people to gang up on the third one. Besides, if at some point in time all pairs of friends switch to enemies and vice versa, the committees will still be legitimate.

In 1976 I was about to become a student in the math department at Moscow State University. As an IMO team member I was accepted without entrance exams, but all of my other classmates had to take the exams. There were four exams: written math, oral math, physics, and an essay.

The written math exam was the first, and here are the problems. I want my non-Russian readers to see if they notice anything peculiar about this exam. Can you explain what is peculiar, and what might be the hidden agenda?

Problem 1. Solve the equation

Problem 2. Solve the inequality

Problem 3. Consider a right triangle ABC with right angle C. Angle B is 30° and leg CA is equal to 1. Let D be the midpoint of the hypotenuse AB, so that CD is a median. Choose F on the segment BC so that the angle between the hypotenuse and the line DF is 15°. Find the area of CDF. Calculate its numeric value with 0.001 precision.

Problem 4. Three balls, two of which are the same size, are tangent to the plane P, as well as to each other. In addition, the base of a circular cone lies on the plane P, and its axis is perpendicular to the plane. All three balls touch the cone from the outside. Find the angle between a generatrix of the cone and the plane P, given that the triangle formed by the points of tangency of the balls and the plane has one angle equal to 150°.

Problem 5. Let r < s < t be real numbers. If you set y equal to any of the numbers r, s or t in the equation x² − (9 − y)x + y² − 9y + 15 = 0, then at least one of the other two numbers will be a root of the resulting quadratic equation. Prove that −1 < r < 1.

Let me describe some background to this exam. Applicants who solve fewer than two problems fail the exam and are immediately rejected. People who solve two or three problems are given 3 points. Four problems earn 4 points, and five problems earn 5 points.

If you still do not see the hidden agenda, here is another clue. People who get 5 points on the first exam and, in addition, have a gold medal from their high school (that means all As) are admitted right after the first exam. For the others, if they do not fail any of the exams, points are summed up with their GPAs to compute their scores. The so-called half-passing score is then calculated. Scores strictly higher than the half-passing score qualify applicants for admission. However, there are too many applicants for the available openings with at least the half-passing score. As a result only some people with exactly the half-passing score are accepted, at the discretion of the department.

Now my readers have enough information to figure out the hidden agenda behind that particular exam.

Suppose that we choose all families with two children, such that one of them is a son named Luigi. Given that the probability of a boy to be named Luigi is p, what is the probability that the other child is a son?

Here is a potential “solution.” Luigi is a younger brother’s name in one of the most popular video games: Super Mario Bros. Probably the parents loved the game and decided to name their first son Mario and the second Luigi. Hence, if one of the children is named Luigi, then he must be a younger son. The second child is certainly an older son named Mario. So, the answer is 1.

The solution above is not mathematical, but it reflects the fact that children’s names are highly correlated with each other.

Let’s try some mathematical models that describe how the parents might name their children and see what happens. It is common to assume that the names of siblings are chosen independently. In this case the first son (as well as the second son) will be named Luigi with probability p. Therefore, the answer to the puzzle above is (2-p)/(4-p).

The problem with this model is that there is a noticeable probability that the family has two sons, both named Luigi.

As parents usually want to give different names to their children, many researchers suggest the following naming model to avoid naming two children in the same family with the same name. A potential family picks a child’s name at random from a distribution list. Children are named independently of each other. Families in which two children are named the same are crossed out from the list of families.

There is a problem with this approach. When we cross out families we may disturb the balance in the family gender distributions. If we assume that boys’ and girls’ names are different then we will only cross out families with children of the same gender. Thus, the ratio of different-gender families to same-gender families will stop being 1/1. Moreover, it could happen that the number of boy-boy families will differ from the number of girl-girl families.

There are several ways to adjust the model. Suppose there is a probability distribution of names that is used for the first son. If another son is born, the name of the first son is crossed out from the distribution and following that we proportionately adjust the probabilities of all other names for this family. In this model the probability of naming the first son by some name and the second son by the same name changes. For example, the most popular name’s probability decreases with consecutive sons, while the least popular name’s probability increases.

I like this model, because I think that it reflects real life.

Here is another model, suggested by my son Alexey. Parents give names to their children independently of each other from a given distribution list. If they give the same name to both children the family is crossed-out and replaced with another family with children of the same genders. The advantage of this model is that the first child and the second child are named independently from each other with the same probability distribution. The disadvantage is that the probability distribution of names in the resulting set of families will be different from the probability distribution of names in the original preference list.

I would like my readers to comment on the models and how they change the answer to the original problem.

by Olivier Bernardi and Tanya Khovanova

The Cookie Monster is a peculiar creature that appeared in The Inquisitive Problem Solver (Vaderlind, Guy & Larson, MAA, P34). Presented with a set of cookie jars, the Cookie Monster will try to empty all the jars with the least number of moves, where a move is to select any subset of the jars and eat the same number of cookies from each jar in the subset.

Even an untalented Cookie Monster would be able to empty n jars in n moves: to fulfill this strategy the Monster can devour all the cookies of one jar at a time. If the Monster is lucky and some jars have the same number of cookies, the Monster can apply the same eating process to all these identical jars. For example, if all the jars have the same number of cookies, the Monster can gulp down all of them in one swoop.

Now, let us limit our discussion to only cases of n non-empty jars that contain distinct numbers of cookies. If indeed all the numbers are distinct, can the Monster finish eating faster than in n moves?

The answer depends on the actual number of cookies in each jar. For example, if the number of cookies in jars are different powers of 2, then even the most talented Monsters can’t finish faster than in n steps. Indeed, suppose the largest jar contains 2^N cookies. That would be more than the total number of cookies in all the other jars together. Therefore, any strategy has to include a step in which the Monster only takes cookies from the largest jar. The Monster will not jeopardize the strategy if it takes all the cookies from the largest jar in the first move. Applying the induction process, we see that we need at least n steps.

On the other hand, sometimes the Monster can finish the jars faster. If 2^k−1 jars contain respectively 1, 2, 3, …, 2^k−1 cookies, the Cookie Monster can empty them all in k steps. Here is how. For its first move, the Monster eats 2^k-1 cookies from each of the jars containing 2^k-1 cookies or more. What remains are 2^k-1−1 pairs of identical non-empty jars containing respectively 1, 2, 3, …, 2^k-1−1 cookies. The Monster can then continue eating cookies in a similar fashion, finishing in k steps. For instance, for k=3 the sequences of non-empty jars are: 1,2,3,4,5,6,7 → 1,1,2,2,3,3 → 1,1,1,1 → all empty.

Now we would like to prove a theorem that shows that the example above is the lowest limit of moves even for the most gifted Cookie Monsters.

Theorem. If n non-empty jars contain distinct numbers of cookies, the Cookie Monster will need at least ⌈log₂(n+1)⌉ steps to empty them all.

Proof. Suppose that n jars contain distinct numbers of cookies and let f(n) be the number of distinct non-empty jars after the first move of the Cookie Monster. We claim that n ≤ 2f(n)+1. Indeed, after the first move, there will be at least n − 1 non-empty jars, but there cannot be three identical non-empty jars. That means, the number of jars plus 1 can’t decrease faster than twice each time.

Now here is something our readers can play with. Suppose a sequence of numbers represents the number of cookies in the jars. Which sequences are interesting, that is, which can provide interesting solutions for the Cookie Monster problem?

Lionel Levine invented a new hat puzzle.

The sultan decides to torture his hundred wise men again. He has an unlimited supply of red and blue hats. Tomorrow he will pile an infinite, randomly-colored sequence of hats on each wise man’s head. Each wise man will be able to see the colors of everyone else’s hats, but will not be able to see the colors of his own hats. The wise men are not allowed to pass any information to each other.
At the sultan’s signal each has to write a natural number. The sultan will then check the color of the hat that corresponds to that number in the pile of hats. For example, if the wise man writes down “four,” the sultan will check the color of the fourth hat in that man’s pile. If any of the numbers correspond to a red hat, all the wise men will have their heads chopped off along with their hats. The numbers must correspond to blue hats. What should be their strategy to maximize their chance of survival?

Suppose each wise man writes “one.” The first hat in each pile is blue with a probability of one-half. Hence, they will survive as a group with a probability of 1 over 2¹⁰⁰. Wise men are so wise that they can do much better than that. Can you figure it out?

Inspired by Lionel, I decided to suggest the following variation:

This time the sultan puts two hats randomly on each wise man’s head. Each wise man will see the colors of other people’s hats, but not the colors of his own. The men are not allowed to pass any info to each other. At the sultan’s signal each has to write the number of blue hats on his head. If they are all correct, all of them survive. If at least one of them is wrong, all of them die. What should be their strategy to maximize their chance of survival?

Suppose there is only one wise man. It is clear that he should write that he has exactly one blue hat. He survives with the probability of one-half. Suppose now that there are two wise men. Each of them can write “one.” With this strategy, they will survive with a probability of 1/4. Can they do better than that? What can you suggest if, instead of two, there is any number of wise men?

In a puzzle book by Mari Berrondo (in Russian), I found the following logic problem:

Alfred, Bertran and Charles are asked about their profession. One of them always lies; another one always tells the truth; and the third one [who I will refer to as a “half-liar”] sometimes lies and sometime tells the truth. Here are their answers:

Bertran: I am a painter, Alfred is a piano-tuner, Charles is a decorator.
Alfred: I am a doctor, Charles is an insurance agent. Concerning Bertran, if you ask him, he will tell you that he is a painter.
Charles: Alfred is a piano-tuner. Bertran is a decorator, and I am an insurance agent.
What is the profession of the half-liar?

The solution in the book is the following. As Alfred is right about what Bertran would say, Alfred can’t be a liar. If Alfred is a half-liar then the other two people would give the opposite statements, since one will be a truth-teller and the other a liar. But they both say that Alfred is a piano-tuner, therefore Alfred must be a truth-teller. Hence, Alfred’s statement about everyone’s profession must be the truth. Now we know that Charles is an insurance agent. As Charles confirms that, thus telling the truth in this instance, we recognize that he must be a half-liar. The answer to the problem is that the half-liar is an insurance agent.

But I have a problem with this problem. You see, a liar can say many things. He can say that he is a conductor, a mathematician, a beekeeper or whatever. So there is no way of knowing what a person who decides to lie can say. Let’s just analyze the statement by Alfred: “Concerning Bertran, if you ask him, he will tell you that he is a painter.”

If Alfred tells the truth about what Bertran would say, he needs to know for sure that Bertran will say that he is a painter. Hence, Bertran must be a truth-teller and a painter. If Alfred lies, he needs to be sure that Bertran won’t say that he is a painter. So Bertran must be either a truth-teller and not a painter, or a liar and a painter. Bertran can’t be a half-liar, because a half-liar can say that he is a painter as well as he can say something else, no matter what his real profession.

There is one interesting aspect of this that many people overlook. There are different types of people who are half-liars. In some books half-liars are introduced as people who, before making a statement, flip a coin to decide whether to lie or to tell the truth. Such a person needs to know in advance exactly what other people are saying, in order to construct a statement about what those people might say that corresponds to the coin flip. On the other hand, other types of half-liars exist. One half-liar can say something and then see later whether it is true. If Alfred is a half-liar who doesn’t care in advance about the truth of his statement, he can say that Bertran will claim that he is a painter.

I leave it to my readers to finish my analysis and see that the problem doesn’t have a solution. To end my essay on a positive note, I decided to slightly change the problem, so that there is no contradiction. In the same setting:

Bertran: I am a painter, Alfred is a piano-tuner, Charles is a decorator.
Alfred: I am a doctor, Charles is an insurance agent. Concerning Bertran, if you ask him, he will tell you that he is not a painter.
Charles: Alfred is a piano-tuner. Bertran is a decorator, and I am an insurance agent.
What is the profession of the half-liar?