Tanya Khovanova's Math Blog

Warning: this essay contains solutions to math problems.

Here is a famous hat puzzle:

A king decides to give 100 of his wise men a test. If together they pass, they can go free. Otherwise, the king will execute all of them. The test goes as follows: the wise men stand in a line one after another, all facing in the same direction. The king puts either a black or a white hat on each wise man. The wise men can only see the colors of the hats in front of them. In any order they want, each one guesses the color of the hat on his own head. Other than that, the wise men cannot speak. To pass, no more than one of them may guess incorrectly. Given that they have time to agree on a strategy beforehand, how can they assure that they will survive?

Instead of discussing the puzzle above, I’d like to look at a different version. It is an infinite variation of the puzzle that my son Sergei brought back from the Canada/USA Mathcamp last year.

The king has a countable number of wise men. The line starts from the left and is infinite in the right direction. The wise men are all facing to the right and they see the infinite tail of the line. Again, the king places either a black or white hat on each head and they can only say one of two words: black or white. Will they be able to devise a strategy beforehand that ensures that not more than one person makes a mistake?

Oh, I forgot to mention: you are allowed to use the axiom of choice.

Here is the solution. You can build an equivalence relation on the possible placements of hats. To be equivalent, two ways of placing the hats should have the same tail. In other words, there is a person such that both hat arrangements to his right are the same. By the axiom of choice you can pick a representative in any equivalence class. The first wise man looks at all the other hats and calculates in how many places the tail differs from the representative of the class they picked. This is a finite number, and by stating one color or the other, he signals the parity of that number. After that, all the wise men say their colors from left to right. Everyone sees the tail and everyone hears the color choices of the people behind. So every wise man can reconstruct the color of his hat with this information. Only the first person may potentially be mistaken.

Many things about this solution bother me. Where is this country that can fit an infinite number of people? What kind of humans can see into infinity? How much time will this procedure take?

Aside from the practical matters, there are mathematical matters that bother me, too. By the axiom of choice you can pick an element in every class. The problem is that all of the wise men have to pick the same element. The axiom of choice claims the existence of a choice function, which picks an element in each set. So the function exists, but can we distribute this function to many wise men? Remember, they need to agree on this function the night before.

We already implicitly assumed that our wise men have a lot of magical abilities. So we can add to those the ability to go through all the possible tails and memorize the representatives for all the tails in one evening.

But still, I am very curious to know what follows from the axiom of choice. Tell me what you think: does the axiom of choice imply that we can distribute the choice function, or do we need a new axiom? In your opinion, will these wise men live?

Let me remind you of a very interesting problem from my posting Oleg Kryzhanovsky’s Problems.

You have 6 coins weighing 1, 2, 3, 4, 5 and 6 grams that look the same, except for their labels. The number (1, 2, 3, 4, 5, 6) on the top of each coin should correspond to its weight. How can you determine whether all the numbers are correct, using the balance scale only twice?

I do not want you to find the weight of each coin; I just want you to say yes if the labels are correct, or no if they are not.

I have given this problem to a lot of people, and not one of them solved it. Some of my students mistakenly thought that they succeeded. For example, they would start by putting the coins labeled 1 and 2 on the left cup of the scale and 3 on the right cup. If these coins balanced, the students assumed that the coins on the left weighed 1 and 2 grams and that the coin on the right weighed 3 grams. But they’d get the same result if they had 1 and 4 on the left, for example, and 5 on the right. I am surprised that no one has solved it yet, as I thought that this problem could be offered to middle-schoolers, since it does not actually require advanced mathematical skills.

If you want to try to solve this problem, pause here, as later in this essay I will be providing a number of hints on how to do it. The problem is fun to solve, so continue reading only if you are sure you’re ready to miss out on the pleasure of solving it.

I propose the following sequence a(n). Suppose we have a set of n coins of different weights weighing exactly an integer number of grams from 1 to n. The coins are labeled from 1 to n. The sequence a(n) is the minimum number of weighings we need on a balance scale to confirm that the labels are correct. The original Oleg Kryzhanovsky’s problem asks to prove that a(6) = 2. It is easy to see that a(1) = 0, a(2) = 1, a(3) = 2. You will enjoy proving that a(4) = 2 and a(5) = 2.

In general, we can prove that a(n) ≤ n-1. For any k < n, the k-th weighing compares coins labeled k and k+1. If we get the expected result every time, then we can confirm that the weights are increasing according to the labels.

On the other hand, we can prove that a(n) ≥ log₃(n). Indeed, suppose we conducted several weighings and confirmed that the labels are correct. To every coin we can assign a sequence of three letters L, R, N, corresponding to where the coin was placed during each weighing — left cup, right cup or no cup. If two coins are assigned the same letters for every weighing, then we can’t confirm that the labels on these two coins are accurate. Indeed, if we switch the labels on these two coins, the results of all the weighings will be the same.

My son, Alexey Radul, sent me the proof that a(10) = a(11) = 3. As 3 is the lower bound, we just need to describe the weighings that will work.

Here is the procedure for 10 coins. For the first weighing we put coins labeled 1, 2, 3, and 4 on one side of the scale and the coin labeled 10 on the other. After this weighing, we can divide the coins into three groups (1,2,3,4), (5,6,7,8,9) and (10). We know to which group each coin belongs, but we do not know which coin in the group is which. The second weighing is 1, 5 and 10 on the left, and 8 and 9 on the right. The left side should weigh less than the right side. The only possibility for the left side to weigh less is when the smallest weighing coins from the first and the second group and 10 are on the left, and the two largest weighing coins from the first two groups are on the right. After the second weighing we can divide all coins into groups we know they belong to: (1), (2,3,4), (5), (6,7), (8,9) and (10). The last weighing contains the lowest weighing coin from each non-single-coin group on the left and the largest weighing coin on the right, plus, in order to balance them, the coins whose weights we know. The last weighing is 2+6+8+5 = 4+7+9+1.

Here is Alexey’s solution, without explanation, for 11 coins: 1+2+3+4 < 11; 1+2+5+11 = 9+10; 6+9+1+3 = 8 +4+2+5.

Let me denote the n-th triangular number as T_n. Then a(T_n) ≤ a(n) + T_n – n – 1. Proof. The first weighing is 1+2+3 … +n = T_n. After that we can divide coins into groups, where we know that the labels stay within the group: (1,2,…,n), (n+1,n+2,…,T_n-1), (T_n). We can check the first group in a(n) weighings, the second group in T_n – n – 2 weighings, and we already used one. QED.

Similarly, a(T_n+1) ≤ a(n) + T_n – n.

For non-triangular numbers there are sometimes weighings that divide coins into three groups such that the labels can only be permuted within the same group. For example, with 13 coins, the first weighing could be 1+2+3+4+5+6+7+8 = 11+12+13. After that weighing we can divide all coins into three groups (1,2,3,4,5,6,7,8), (9,10), (11,12,13).

In all the examples so far, each weighing divided all the coins into groups. But this is not necessary. For example, here is Alexey’s solution for 9 coins. The first weighing is 1+2+3+4+5 < 7+9. When we have five coins on the left weighing less than two coins on the right, we have several different possibilities of which coins are where. Other than the case above, we can have 1+2+3+4+6 < 8+9 or 1+2+3+4+5 < 8+9. But let’s look at the next weighing that Alexey suggests: 1+2+4+7 = 6+8. Or, three coins from the previous weighing’s left cup, plus one coin from the previous weighing’s right cup equals the sum of the two coins that were left over. This can only be true if the coins in the first weighing were indeed 1+2+3+4+5 on the left and 7+9 on the right. After those two weighings everything divides into groups (1,2,4), (3,5), (6,8), (7) and (9). The last weighing 1+7+9 = 4+5+8, resolves the rest.

To check 7 or 8 coins in three weighings is simpler than the cases for 9, 10, and 11 coins, so I leave it as an exercise. As of today I do not know if it is possible to check 7, 8 or 9 coins in two weighings. Consider this a starred exercise.

I invite you to play with this amusing sequence and calculate some bounds. Also, let me know if you can prove or disprove that this sequence is non-decreasing.

When my son Sergei made it to the International Linguistics Olympiad I got very excited. After I calmed down I realized that training for this competition is not easy because it is very difficult to find linguistics puzzles in English. This in turn is because these Olympiads started in the USSR many years ago and were adopted here only recently. So I started translating problems from Russian and designing them myself for my son and his team. For this particular problem I had an ulterior motive. I wanted to remind my son and his team of rare words in English with Greek origins. Here is the problem:

We use many words that have Greek origins, for example: amoral, asymmetric, barometer, chronology, demagogue, dermatology, gynecologist, horoscope, mania, mystic, orthodox, philosophy, photography, polygon, psychology, telegram and telephone. In this puzzle, I assume that you know the meanings of these words. Also, since I am a generous person, I will give you definitions from Answers.com of some additional words derived from Greek. If you do not know these words, you should learn them, as I picked words for this list that gave me at least one million Google results.

• Agoraphobia — an abnormal fear of open or public places.
• Anagram — a word or phrase formed by reordering the letters of another word or phrase, such as satin to stain.
• Alexander — defender of men.
• Amphibian — an animal capable of living both on land and in water.
• Anthropology — the scientific study of the origin, the behavior, and the physical, social, and cultural development of humans.
• Antipathy — a strong feeling of aversion or repugnance.
• Antonym — a word having a meaning opposite to that of another word.
• Bibliophile — a lover of books or a collector of books.
• Dyslexia — a learning disability characterized by problems in reading, spelling, writing, speaking or listening.
• Fibromyalgia — muscle pain.
• Hippodrome — an arena for equestrian shows.
• Misogyny — hatred of women.
• Otorhinolaryngology — the medical specialty concerned with diseases of the ear, nose and throat.
• Pedophilia — the act or fantasy on the part of an adult of engaging in sexual activity with a child or children.
• Polygamy — the condition or practice of having more than one spouse at one time.
• Polyglot — a person having a speaking, reading, or writing knowledge of several languages.
• Tachycardia — a rapid heart rate.
• Telepathy — communication through means other than the senses, as by the exercise of an occult power.
• Toxicology — the study of the nature, effects, and detection of poisons and the treatment of poisoning.

In the list below, I picked very rare English words with Greek origins. You can derive the meanings of these words without looking in a dictionary, just by using your knowledge of the Greek words above.

• Barology
• Bibliophobia
• Cardialgia
• Dromomania
• Gynophilia
• Hippophobia
• Logophobia
• Misandry
• Misanthropy
• Misogamy
• Monandry
• Monoglottism
• Mystagogue
• Pedagogue
• Philanthropism

Here are some other words. You do not have enough information in this text to derive their definitions, but you might be able to use your erudition to guess the meaning.

• Antinomy
• Apatheist
• Axiology
• Dactyloscopy
• Enneagon
• Oology
• Paraskevidekatriaphobia
• Philadelphia
• Phytology
• Triskaidekaphobia

Robert Calderbank and Ingrid Daubechies jointly taught a course called “The Theory of Games” at Princeton University in the spring. When I heard about it I envied the students of Princeton — what a team to learn from!

Here is a glimpse of this course — a problem on Evolutionarily Stable Strategy from their midterm exam with a poem written by Ingrid:

On an island far far away, with wonderful beaches
Lived a star-bellied people of Seuss-imagin’d Sneetches.

Others liked it there too — they loved the beachy smell,
From their boats they would yell “Can we live here as well?”
But it wasn’t to be — steadfast was the “No” to the Snootches:
For their name could and would rhyme only with booches …

Until with some Lorxes they came!
These now also enter’d the game;
A momentous change this wrought
As they found, after deep thought.

Can YOU tell me now
How oh yes, how?
In what groupings or factions
Or gaggles and fractions
They all settled down?

Sneetches and Snootches only:

Sneetches and Snootches and Lorxes:

Find all the ESSes, in both cases.

Due to the popularity of my previous posting of linguistics puzzles, I’ve translated some more puzzles from the online book Problems from Linguistics Olympiads 1965-1975. I’ve kept the same problem number as in the book; and I’ve used the Unicode encoding for special characters.

Problem 180. Three Tajik sentences in Russian transliteration with their translations are below:

• дӯсти хуби ҳамсояи шумо — a good friend of your neighbor
• ҳамсояи дӯсти хуби шумо — a neighbor of your good friend
• ҳамсояи хуби дӯсти шумо — a good neighbor of your friend

Your task is to assign a meaning to each out of four used Tajik words.

Problem 185. For every sequence of words given below, explain whether it can be used in a grammatically correct English sentence. If it is possible show an example. In the usage there shouldn’t be any extra signs between the given words.

1. could to
2. he have
3. that that
4. the John
5. he should
6. on walked
7. the did

Problem 241. In a group of relatives each person is denoted by a lower-case letter and relations by upper-case letters. The relations can be summarized in a table below:

The table should be read as following: if the intersection of the row x and the column y has symbol Z, then x is Z with respect to y. It is known that e is a man.

You task is to find out the meaning of every capital letter in the table (each letter can be represented as one English word).

Of course you can. Can you do it in Russian? You do not need to know Russian to do it; you just need to solve my puzzle. Below are some numerals written in Russian. You have enough information to write any number from 1 to 99 inclusive in Russian.

• 1 — один
• 10 — десять
• 11 — одиннадцать
• 12 — двенадцать
• 13 — тринадцать
• 14 — четырнадцать
• 15 — пятнадцать
• 18 — восемнадцать
• 22 — двадцать два
• 31 — тридцать один
• 33 — тридцать три
• 40 — сорок
• 44 — сорок четыре
• 46 — сорок шесть
• 55 — пятьдесят пять
• 88 — восемьдесят восемь
• 97 — девяносто семь
• 99 — девяносто девять

If you are too lazy to write all the Russian numerals I requested, try the most difficult ones: 16, 17, 19, 67 and 76.

If you know Russian, then I have a back-up puzzle for you. Do the same thing for French:

• 1 — un
• 10 — dix
• 11 — onze
• 12 — douze
• 13 — treize
• 14 — quatorze
• 16 — seize
• 17 — dix-sept
• 21 — vingt-et-un
• 22 — vingt-deux
• 31 — trente-et-un
• 33 — trente-trois
• 40 — quarante
• 44 — quarante-quatre
• 46 — quarante-six
• 48 — quarante-huit
• 55 — cinquante-cinq
• 61 — soixante-et-un
• 71 — soixante et onze
• 72 — soixante-douze
• 75 — soixante-quinze
• 79 — soixante-dix-neuf
• 80 — quatre-vingts
• 81 — quatre-vingt-un
• 91 — quatre-vingt-onze
• 98 — quatre-vingt-dix-huit

And again, if you are lazy, you can concentrate on translating 15, 18, 19, 41, 51, 56, 65, 78 and 99 into French.

I invite my readers to create similar puzzles in all languages.

In Psilvania no one knows English, except for one retired professor Mary Bobs. That is why every year the organizers of the linguistics Olympiad in Psilvania beg Mary to design a puzzle in English. Kids in Psilvania know other languages — which gives individuals an advantage if the puzzle is in those languages. An English puzzle would create a level playing field.

Here is the puzzle that Mary proposed. I’m omitting the Psilvanian text, because the characters do not match anything in Unicode tables.

Professor Bobs provided the following sentences in English, accompanied by their translations into Psilvanian. She called these sentences Raw Materials:

• Kate is devouring a pencil.
• A laptop is being devoured by Paul.
• A fig is eating Kate.
• Kate is dating a fig.
• Jane is defenestrating Paul.
• Pete is being defenestrated by Paul.

The first task that she required was to translate the following sentences into Psilvanian:

• Paul is being dated by a laptop.
• Jane is being devoured by Paul.

Professor Mary Bobs had quit smoking that very week and she couldn’t concentrate. It seems that she may have given more information than is necessary. Is it possible to remove any of the Raw Materials (one or more translated sentences) and keep the puzzle solvable? If so, what is the largest number of Raw Materials you can eliminate? Explain.

Her second task was to translate some sentences from Psilvanian into English, and the answers she hoped the students would calculate were:

• A fig is being eaten by Paul.
• A pencil is being devoured by a laptop.
• A laptop is being defenestrated by Pete.

For each of the three English sentences above, decide whether the participants of the Olympiad will be capable of getting this particular answer. If for any of these three sentences you suspect that they will not be able to arrive at the correct answer, explain why.

I would like to discuss the solution to one of the linguistics puzzles I posted a while ago. Here is problem number 211 from the online book Problems from Linguistics Olympiads 1965-1975:

You are given words in Swahili: mtu, mbuzi, jito, mgeni, jitu and kibuzi. Their translations in a different order are: giant, little goat, guest, goat, person and large river. Make the correspondence.

First, lets say that a giant is a large man. The Swahili translation of “giant” may have elements of Swahili words for a “man” and a “large river”. Next we notice that each of these Swahili words naturally divides into two parts. We can put them in a table such that the first part is the same for every row and the second part is the same for every column.

When I gave this problem to my students, they loved the idea that the word “giant” is comprised of the two words “large” and “man”, so they assumed that in Swahili a “guest” would also have a two-part translation, such as a “man who visits.” In the list of words we have three different types of “man”: man, giant and guest. Once they noticed that “m” appears three times, they concluded that “m” must mean a man. Therefore, the object must be the first part of a Swahili word, while the second part contains its description.

Next, they noted that the first part “ji” appears twice. They decided that “ji” must be a goat and thus “ki” must be a river. All of this gives us sufficient information to derive the translations: “mgeni” a guest, “kibuzi” a large river, “mbuzi” a giant, “mtu” a man, “jitu” a goat and “jito” a little goat.

My students were very proud of themselves, but I was dissatisfied with this solution. Here are the problems I’ve identified:

• If “buzi” means large, then what does “tu” mean?
• If “tu” means normal size, then what is the size of the guest?
• If everything is about sizes, then the descriptive part “geni” is an odd one out.
• In a real language what part should be smaller: the one describing the size of the object or the one describing the object itself?

I would suggest a different approach. Let’s say that the puzzle is about sizes, and we have three objects (man, guest, goat) of normal size, two large objects (giant and large river), and one small object (little goat). That means “m” must mean normal, and the size description is in front. If the first part is the size, then “ki” is small, “ji” large. From here “mgeni” is a guest, “kibuzi” a little goat, “mbuzi” a goat, “mtu” a man, “jitu” a giant, and “jito” is a large river.

I love this puzzle because it teaches us to continue pondering, even after everything seems to fit. If you stumble upon the first solution you need to go back and think some more. Only after you discover the second solution does it become clear that the second one is right.

I have a tiny book written by Vladimir Arnold Problems for Kids from 5 to 15. A free online version of this book is available in Russian. The book contains 79 problems, and problem Number 6 criticizes American math education. Here is the translation:

(From an American standardized test) A hypotenuse of a right triangle is 10 inches, and the altitude having the hypotenuse as its base is 6 inches. Find the area of the triangle.
American students solved this problem successfully for 10 years, by providing the “correct” answer: 30 inches squared. However, when Russian students from Moscow tried to solve it, none of them “succeeded”. Why?

Arnold has inflated expectations for kids. The book presents the problems according to the increasing order of difficulty, and this suggests that he expects kids under 10 to solve Number 6.

Arnold claimed that every student from Moscow would notice what is wrong with this problem. I can forgive his exaggeration, because I’ve met such kids. Anyways, I doubt that Arnold ever stumbled upon an average Russian student.

My own fundamental interest is in the state of American math education, so I decided to check his claim concerning American students. I asked my students to calculate the area of the triangle in the above puzzle.

Here are the results of my experiment. Most of them said that the answer is 30. Some of them said that it is 24. In case you’re wondering where the 24 is coming from, I can explain. They decided that a right triangle with hypotenuse 10 must have two other legs equal to 8 and 6.

Some of the students got confused, not because they realized that there was a trick, but because they thought the way to calculate the area of the right triangle is to take half the product of its legs. As lengths of legs were not given, they didn’t know what to do.

There was one student. Yes, there was one student, who decided that he could calculate the legs of the triangle from the given information and kept wondering why he was getting a negative number under the square root.

You decide for yourself whether there is hope for American math education. Or, if you are a teacher, try running the same experiment yourself. I hope that one day I will hear from you that one of your students, upon reading the problem, immediately said that such a triangle can’t exist because the altitude of the right triangle with the hypotenuse as the base can never be bigger than half of the hypotenuse.

A long ago my son Sergei went to the Streamline School Olympiad. Some of the problems were really nice and I asked the organizer, Oleg Kryzhanovsky, where he took the problems from. It seems that he himself supplied all the problems, many of which are his original creations. He told me that he can invent a math Olympiad problem on demand for any level of difficulty on any math topic. No wonder that he is the author of almost all math problems at the Ukraine Olympiad.

The following is a sample of his problems from the Streamline Olympiad. For my own convenience I have chosen problems without figures and equations. Note: I edited some of them.

1998 (8th – 9th grade). Find three numbers such that each of them is a square of the difference of the two others.

1999 (9th – 10th grade). The positive integers 30, 72, and N have a property that the product of any two of them is divisible by the third. What is the smallest possible value of N?

1999 (9th – 10th grade). You have 6 coins weighing 1, 2, 3, 4, 5 and 6 grams that look the same. The number (1, 2, 3, 4, 5, 6) on the top of each coin should correspond to its weight. How can you determine whether all the numbers are correct, using the balance scale only twice?

1999 (11th – 12th grade). In how many ways can the numbers 1, 2, 3, 4, 5, 6 be ordered such that no two consecutive terms have a sum that is divisible by 2 or 3.

2000 (6th – 7th grade). Let A be the least integer such that the sum of all its digits is equal to 2000. Find the left-most digit of A.

2000 (8th grade). You have six bags with coins that look the same. Each bag has an infinite number of coins and all coins in the same bag weigh the same amount. Coins in different bags weigh 1, 2, 3, 4, 5 and 6 grams exactly. There is a label (1, 2, 3, 4, 5, 6) attached to each bag that is supposed to correspond to the weight of the coins in that bag. You have only a balance scale. What is the least number of times do you need to weigh coins in order to confirm that the labels are correct?