Tanya Khovanova's Math Blog

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.

by Pavel Etingof and Tanya Khovanova

We worked for several years with RSI where we supervised summer math research projects by high school students. Now, we’ve started an additional program at MIT’s math department called PRIMES, where local high school students do math research during the academic year. In this essay we would like to discuss what makes a good math research project for a high school student.

A doable project. The project should not be believed to be extremely difficult to yield at least results. It is very discouraging for an aspiring mathematician not to produce anything during their first project.

An accessible beginning. The student should be able to start doing something original soon after the start of the project. After all, they don’t come to us for coursework, but for research.

Flexibility. It is extremely important to offer them a project that is adjustable; it should go in many directions with many different potential kinds of results. Since we do not know the strength of incoming students in advance, it is useful to have in mind both easier and harder versions of the project.

Motivation. It is important for the project to be well motivated, which means related to other things that have been studied and known to be interesting, to research of other people, etc. Students get more excited when they see that other people are excited about their results.

A computer component. This is not a must for a good project. But modern mathematics involves a lot of computation and young students are better at it than many older professors. Such a project gives young students the opportunity to tackle something more senior people are interested in but might not have enough computer skills to solve. In addition, through computer experiments students get exposed to abstract notions (groups, rings, Lie algebras, representations, etc.) in a more “hands-on” way than when taking standard courses, and as a result are less scared of them.

A learning component. It is always good when a project exposes students to more advanced notions.

The student should like their project. This is very difficult to accomplish when projects are chosen in advance before we meet the students. However, we try to match them to great projects by using the descriptions they give of their interests on their applications. It goes without saying that mentors should like their project too.

Having stated the desired properties of a good project, let us move on to giving examples: bad projects and good projects. We start with a bad one:

Prove that the largest power of 2 that doesn’t contain 0 is 2⁸⁶.

The project satisfies only one requirement: it contains a computer component. Otherwise, it doesn’t have an accessible beginning. It is not very flexible: if the student succeeds, the long-standing conjecture will be proven; if s/he doesn’t, there is not much value in intermediate results. The question is not very interesting. The only motivation is that it has been open for a long time. Also, there is not much to learn. Though, almost any theoretical question can be made flexible. We can start with the question above and change its direction to make it more promising and enticing.

Another bad example is a project where the research happens after the programs are written. This is bad because it is difficult to estimate the programming abilities of incoming students. It doesn’t have an accessible beginning and there is no flexibility until the programming part is finished. If the student can’t finish the programming quickly, s/he will not have time to look at the results and produce conjectures. For example, almost any project in studying social networks may fall into this category:

Study an acquaintance graph for some epic movies or fiction, for example Star Wars or The Lord of the Rings. In this graph people are vertices and two people are connected by an edge if they know each other. The project is to compare properties of such graphs to known properties of other social networks.

Though the networks in movies are much smaller than other networks that people study, the amount of programming might be substantial. This project can be a good project for a person with a flexible time frame or a person who is sure in advance that there will be enough time for him/her to look at the data.

Now on to an example of a good project. Lynnelle Ye and her mentor, Tirasan Khandhawit, chose to analyze the game of Chomp on graphs during RSI 2009.

Given a graph, on each turn a player can remove an edge or a vertex together with all adjacent edges. The player who doesn’t have a move loses. This game was previously solved for complete graphs and forest graphs, so the project was to analyze the game for other types of graphs.

It is clear how to analyze the game for any particular new graph. So that could be a starting point providing an accessible beginning. After that the next step could be to analyze other interesting sets of graphs. The flexibility is guaranteed by the fact that there are many sets of graphs that can be used. In addition, the project entails learning some graph theory and game theory. And the project has a computational component.

Lynnelle Ye successfully implemented this project and provided a complete analysis of complete n-partite graphs for arbitrary n and all bipartite graphs. She also gave partial results for odd-cycle pseudotrees. The paper is available at the arxiv. Not surprisingly, Lynelle got fourth place in the Intel Science Talent Search and second place in the Siemens Competition.

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.

I am reading the book Eat to Live by Joel Fuhrman. It contains a formula that as a math formula doesn’t make any sense. But as an idea, it felt like a revelation. Here it is:

HEALTH = NUTRIENTS/CALORIES

The idea is to choose foods that contain more nutrients per calorie. The formula doesn’t make sense for many reasons. Taken to its logical conclusion, the best foods would be vitamins and tea. The formula doesn’t provide bounds: it just emphasizes that your calories should be nutritious. However, too few calories — nutritious or not — and you will die. And too many calories — even super nutritious — are still too many calories. In addition the formula doesn’t explain how to balance different types of nutrients.

Let’s see why it was a revelation. I often crave bananas. I assumed that I need bananas for some reason and my body tells me that. Suppose I really need potassium. As a result I eat a banana, which contains 800 milligrams of potassium and adds 200 calories as a bonus. If I ate spinach instead, I would get the same amount of potassium at a price of only 35 calories.

The book suggests that if I start eating foods that are high in nutrients, I will satisfy my need for particular nutrients, and my cravings will subside. As a result I will not want to eat that much. If I start my day eating spinach, that might eliminate my banana desire.

I’ve been following an intuitive eating diet. I am trying to listen to my body hoping that my body will tell me what is better for it. It seems that my body sends me signals that are not precise enough. It’s not that my body isn’t communicating with me, but it is telling me “potassium” and all I hear is “bananas.” What I need to do is use my brain to help me decipher what my body really, really wants to tell me.

As Dr. Fuhrman puts it, we are a nation of overfed and malnourished people. But Fuhrman’s weight loss plan is too complicated and time-consuming for me, so I designed my own plan based on his ideas:

I will start every meal with vegetables, as they are the most nutritious. I hope that vegetables will provide the nutrients I need. That in turn will make me less hungry by the next meal, at which time I’ll take in fewer calories. I will report to my readers whether or not my plan works. I’m off to shop for spinach. Will I ever love it as much as bananas?

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?

I read an interesting article on the paradoxes involved in allocating seats for the Congress. The problem arises because of two rules: one congressperson has one vote, and the number of congresspeople per state should be proportional to the population of said state.

These two rules contradict each other, because it is unrealistic to expect to be able to equally divide the populations of different states. Therefore, two different congresspeople from two different states may represent different sizes of population.

Let me explain how seats are divided by using as an example a country with three states: New Nevada (NN), Massecticut (MC) and Califivenia (C5). Suppose the total number of congresspeople is ten. Also suppose the population distribution is such that the states should have the following number of congresspeople: NN — 3.33, MC — 3.34 and C5 — 3.33. As you know states generally do not send a third of a congressperson, so the situation is resolved using the Hamilton method. First, each state gets an integer portion of the seats. In my example, each state gets three seats. Next, if there are seats left they are allocated to states with the largest remainders. In my example, the remainders are 0.33, 0.34 and 0.33. As Massecticut has the largest reminder it gets the last seat.

This is not fair, because now each NN seat represents a larger population portion than each MC seat. Not only is this not fair, but it can also create some strange situations. Suppose there have been population changes for the next redistricting: NN — 3.0, MC — 3.4 and C5 — 3.6. In this case, NN and MC each get 3 seats, while C5 gets the extra seat for a total of 4. Even though MC tried very hard and succeeded in raising their portion of the population, they still lost a seat.

Is there any fair way to allocate seats? George Szpiro in his article suggests adding fractional congresspersons to the House of Representatives. So one state might have three representatives, but one of those has only a quarter of a vote. Thus, the state’s voting power becomes 2 1/4.

We can take this idea further. We can use the Hamilton method to decide the number of representatives per state, but give each congressperson a fractional voting power, so the voting power of each state exactly matches the population. This way we lose one of the rules that each congressperson has the same vote. But representation will be exact. In my first example, NN got three seats, when they really needed 3.33. So each congressperson from New Nevada will have 1.11 votes. On the other hand MC got four seats, when they needed 3.34. So each MC representative gets 0.835 votes.

Continuing with this idea, we do not need congresspeople from the same state to have the same power. We can give proportional voting power to a congressperson depending on the population in his/her district.

Or we can go all the way with this idea and lose the districts altogether, so that every congressperson’s voting power will be exactly proportionate to the number of citizens who voted for him/her. This way the voting power will reflect the popularity — rather than the size of the district — of each congressperson.

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?

* * *

Today I saw an ad — “A printer for sale” — handwritten. Hmm.

* * *

What do you call a motherboard on your spouse’s computer?
The motherboard-in-law.

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?