Tanya Khovanova's Math Blog

Computational Linguistics Olympiads started in Moscow in 1962. Finally in 2007 the US caught up and now we have the NACLO — North American Computational Linguistics Olympiad.

The problems from past Soviet Olympiads are hard to find, so here I present a translation from Russian of a sample problem from the Moscow Linguistics Olympiad website:

You are given sentences in Niuean language with their translations into English:

1. To lele e manu. — The bird will fly.
2. Kua fano e tama. — The boy is walking.
3. Kua koukou a koe. — You are swimming.
4. Kua fano a ia. — He is walking.
5. Ne kitia he tama a Sione. — The boy saw John.
6. Kua kitia e koe a Pule. — You are seeing Pule.
7. To kitia e Sione a ia. — John will see him.
8. Ne liti e ia e kulï. — He left the dog.
9. Kua kai he kulï e manu. — The dog is eating the bird.

Translate the following sentences into Niuean:

1. John swam.
2. You will eat the dog.
3. Pule is leaving you.
4. The bird will see the boy.
5. The dog is flying.

Here is a baby puzzle. On Monday the baby said A, on Tuesday AU, on Wednesday AUUA, on Thursday AUUAUAAU. What will she say on Saturday?

You can see that this very gifted baby increases her talking capacity twice each day. The first half of what she says repeats her speech of the day before; and the second half is like the first half, but switches every A and U. If the baby continues indefinitely, her text converges to an infinite sequence that mathematicians call the Thue-Morse sequence (A010060). Of course, mathematicians use zeroes and ones instead of A and U, so the sequence looks like 0110100110010110100….

This sequence has many interesting properties. For example, if you replace every zero by 01 and every one by 10 in the Thue-Morse sequence, you will get the Thue-Morse sequence back. You can see that this is so if you code A in the baby’s speech by 01 and U by 10. Thus the Thue-Morse sequence is a fixed point under this substitution. Moreover, the only two fixed points under this substitution are the Thue-Morse sequence and its negation (A010059).

The Thue-Morse sequence possesses many other cool properties. For example, the sequence doesn’t contain substrings 000 and 111. Actually any sequence built from the doubles 01 and 10 can’t contain the triples 000 and 111 because we switch the digit after every odd-indexed term of such a sequence. A more general and less trivial statement is also true for the Thue-Morse sequence: it doesn’t contain any cubes. That is, it doesn’t contain XXX, where X is any binary string.

I stumbled upon this sequence when I was playing with evil and odious numbers invented by John H. Conway. A number is evil if the number of ones in its binary expansion is even, and odious if it’s odd. We can define a function, called the odiousness of a number, in the following way: odiousness(n) is one, if n is odious and 0 otherwise. We can apply the odiousness function to a sequence of non-negative integers term-wise. Now I can describe the Thue-Morse sequence as the odiousness of the sequence of non-negative numbers. Indeed, the odiousness of the number 2ⁿ + k is opposite of the odiousness of k, if k is less than 2ⁿ. That means if we already know the odiousness of the numbers below 2ⁿ, the next 2ⁿ terms of the odiousness sequence is the bitwise negation of the first 2ⁿ terms. So odiousness is built the same way as the Thue-Morse sequence, and you can easily check that the initial terms are the same too.

Let me consider as an example the sequence which is the odiousness of triangular numbers A153638: 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0…. What can we say about this sequence? We can say that the number of zeroes is infinite, as all the terms with indices of the form 2^n-1(2ⁿ+1) are zeroes. Also, the number of ones is infinite because all the terms with indices of the form 2^2n-1(2^2n-1-1) are ones.

Obviously, we can define the evilness of a number or of a sequence with non-negative terms. Namely, the evilness of a number is 1 if the number is evil, and 0 if it is not. The evilness is the bitwise negation of the odiousness. The evilness of the sequence of non-negative integers is the negation of the Thue-Morse sequence. The odiousness sequence of any sequence of zeroes and ones is the sequence itself, and the evilness sequence is its negation.

I would like to define an inverse odiousness operation on binary sequences. Many different sequences can have the same odiousness sequence. In such a case mathematicians usually define the inverse operation as a minimal non-negative sequence whose odiousness is the given sequence. Obviously, the minimal inverse of a binary sequence is the sequence itself, and thus not very interesting. I suggest that we define the inverse as a minimal increasing sequence. In this case the odiousness inverse of the Thue-Morse sequence is the sequence of non-negative numbers.

For example, let me describe the inverse odiousness of the sequence of all ones. Naturally, all the numbers in the sequence must be odious, and by minimality property this is the sequence of odious numbers A000069: 1, 2, 4, 7, 8, 11, 13, 14, 16, 19…. Analogously, the odiousness inverse of the sequence of all zeroes is the sequence of evil numbers A001969: 0, 3, 5, 6, 9, 10, 12, 15, 17, 18, 20….

Let us find the odiousness inverse of the alternating sequence A000035: 0, 1, 0, 1, 0, 1…. This is the lexicographically smallest sequence of numbers changing putridity. By the way, “putridity” is the term suggested by John Conway to encompass odiousness and evilness the same way as parity encompasses oddness and evenness.

The odiousness inverse of the alternating sequence is the sequence A003159: 0, 1, 3, 4, 5, 7, 9, 11, 12, 13…. By my definition we can describe this sequence as indices of terms of the Thue-Morse sequence that are different from the previous term. This sequence can be described in many other ways. For example, the official definition in the OEIS is that this sequence consists of numbers whose binary expansion ends with an even number of zeroes. It is fun to prove that this is the case. It is also fun to show that this sequence can be built by adding numbers to it that are not doubles of previous terms.

Let us look at the first differences of the previous sequence. This is the sequence A026465: 1, 2, 1, 1, 2, 2, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2… — the length of n-th run of identical symbols in the Thue-Morse sequence. As we know that the Thue-Morse sequence doesn’t contain three ones or three zeroes in a row, we can state that the terms of this sequence will continue to be ones or twos.

You can define putridity sequences for any non-negative sequence. Which of them are interesting? I do not know, but I know which of them are not very interesting. For example, the putridity of pronic (oblong) numbers sequence is the same as the putridity of the triangular numbers sequence. This is because pronic numbers are twice triangular numbers and putridity is independent of factors of two. Another uninformative putridity sequence is the odiousness of the powers of two. This sequence consists only of ones.

I bet that my readers can find putridity sequences that are interesting.

I ran an experiment. I copied multiple choices from the 2007 AMC 8 into a file and asked my son Sergei to try to guess the answers, looking only at the choices. I allowed him to keep several choices. The score I assigned depended on the number of leftover choices. If the leftover choices didn’t contain the right answer, the score for the problem was zero. Otherwise, it was scaled according to the number of choices he left. For example, if he had four choices left and the right answer was among them he got 1/4 of a point. Here are the choices:

1. 9, 10, 11, 12, 13.
2. 2/5, 1/2, 5/4, 5/3, 5/2.
3. 2, 5, 7, 10, 12.
4. 12, 15, 18, 30, 36.
5. 24, 25, 26, 27, 28.
6. 7, 17, 34, 41, 80.
7. 25, 26, 29, 33, 36.
8. 3, 4.5, 6, 9, 18.
9. 1, 2, 3, 4, cannot be determined.
10. 13, 20, 24, 28, 30.
11. Choose picture: I, II, III, IV, cannot be determined.
12. 1:1, 6:5, 3:2, 2:1, 3:1.
13. 503, 1006, 1504, 1507, 1510.
14. 5, 8, 13, 14, 18.
15. a+c < b, ab < c, a+b < c, ac < b, b/c = a.
16. Choose picture: 1, 2, 3, 4, 5.
17. 25, 35, 40, 45, 50.
18. 2, 5, 6, 8, 10.
19. 2, 64, 79, 96, 131.
20. 48, 50, 53, 54, 60.
21. 2/7, 3/8, 1/2, 4/7, 5/8.
22. 2, 4.5, 5, 6.2, 7.
23. 4, 6, 8, 10, 12.
24. 1/4, 1/3, 1/2, 2/3, 3/4.
25. 17/36, 35/72, 1/2, 37/72, 19/36.

It is clear that if you keep all choices, your score will be 5, which is the expected score for AMC if you are randomly guessing the answers. Sergei’s total score was 7.77, which is noticeably better than the expected 5.

There were two questions where Sergei felt that he knew the answer exactly. First was question number two with choices: 2/5, 1/2, 5/4, 5/3, 5/2. All but one of the choices has a 5 in it, so 1/2 must be wrong. Numbers 2/5 and 5/2 are inverses of each other, so if organizers expect you to make a mistake by inverting the right answer, then one of these choices must be the right answer. But 5/4 and 5/3 are better suited as a miscalculation of 5/2, than of 2/5. His choice was 5/2, and it was correct. The second question for which he was sure of the answer was question 19, with his answer 79. I still do not have a clue why.

Sergei’s result wasn’t too much better than just guessing. That means that AMC 8 organizers do a reasonably good job of hiding the real answer. You can try it at home and see if you can improve on Sergei’s result. I will publish the right answers as a comment to this essay in a week or so.

Browsing Braingle I stumbled upon a standard probability puzzle which is very often misunderstood:

Suppose I flip two coins without letting you see the outcome, and I tell you that at least one of the coins came up heads. What is the probability that the other coin is also heads?

The standard “wrong” answer is 1/2. Supposedly, the right answer is 1/3. Here is the explanation for that “right” answer:

For two coins there are four equally probable outcomes: HH, HT, TH and TT. Obviously, TT is excluded in this case, and of the remaining three possibilities only one has two heads.

Here is the problem with this problem. Suppose I flip two coins without letting you see the outcome. If I get one head and one tail, what will I tell you? I can tell you that at least one of the coins came up heads. Or, I can tell you that at least one of the coins came up tails. The fact that I can tell you different things changes the a posteriori probabilities.

You need to base your calculation not only on your knowledge that there are only three possibilities for the outcome: HH, HT and TH, but also on the conditional probabilities of these outcomes, given what I told you. I claim that the initial problem is undefined and the answer depends on what I decide to say in each different case.

Let us consider the first of two strategies I might use:

I flip two coins. If I get two heads, I tell you that I have at least one head. If I get two tails I tell you that I have at least one tail. If I get one head and one tail, then I will tell you one of the above with equal probability.

Given that I told you that I have at least one head, what is the probability that I have two heads? I leave it to my readers to calculate it.

Suppose I follow the other strategy:

I flip two coins. If I get two tails, I say, “Oops. It didn’t work.” Otherwise, I say that I have at least one head.

Given that I told you that I have at least one head, what is the probability that I have two heads? If you calculate answers for both strategies correctly, you will have two different answers. That means the problem is not well-defined in the first place.

When I came to the US, I heard about Mensa — the high IQ society. My IQ had never been tested, so I was curious. I was told that there was a special IQ test for non-English speakers and that my fresh immigrant status and lack of English knowledge was not a problem. I signed up.

There were two tests. One test had many rows of small pictures, and I had to choose the odd one out in each row. That was awful. The test was English-free, but it wasn’t culture-free. I couldn’t identify some of the pictures at all. We didn’t have such things in Russia. I remember staring at a row of tools that could as easily have been from a kitchen utensil drawer as from a garage tool box. I didn’t have a clue what they were.

But the biggest problem was that the idea of crossing the odd object out seems very strange to me in general. What is the odd object out in this list?

Cow, hen, pig, sheep.

The standard answer is supposed to be hen, as it is the only bird. But that is not the only possible correct answer. For example, pig is the only one whose meat is not kosher. And, look, sheep has five letters while the rest have three.

Thus creative people get fewer points. That means, IQ tests actually measure how standard and narrow your mind is.

The second test asked me to continue patterns. Each page had a three-by-three square of geometric objects. The bottom right corner square, however, was empty. I had to decide how to continue the pattern already established by the other eight squares by choosing from a set of objects they provided.

This test is similar to continuing a sequence. How would you continue the sequence 1,2,3,4,5,6,7,8,9? The online database of integer sequences has 1479 different sequences containing this pattern. The next number might be:

• 10, if this is the sequence of natural numbers;
• 1, if this is the sequence of the digital sums of natural numbers;
• 11, if this the sequence of palindromes;
• 0, if this is the sequence of digital products of natural numbers;
• 13, if this is the sequence of numbers such that 2 to their powers doesn’t contain 0;
• 153, if this is the sequence of numbers that are sums of fixed powers of their digits;
• 22, if this is the sequence of numbers for which the sum of digits equals the product of digits; or
• any number you want.

Usually when you are asked to continue a pattern the assumption is that you are supposed to choose the simplest way. But sometimes it is difficult to decide what the testers think the simplest way is. Can you replace the question mark with a number in the following sequence: 31, ?, 31, 30, 31, 30, 31, … You might say that the answer is 30 as the numbers alternate; or, you might say that the answer is 28 as these are the days of the month.

Towards the end of my IQ test, the patterns were becoming more and more complicated. I could have supplied several ways to continue the pattern, but my problem was that I wasn’t sure which one was considered the simplest.

When I received my results, I barely made it to Mensa. I am glad that I am a member of the society of people who value their brains. But it bugs me that I might not have been creative enough to fail their test.

Browsing the Internet, I stumbled upon a coin puzzle which I slightly shrank to emphasize my point:

Carl flipped two coins and was asked if at least one of the two coins landed “heads up”. He replied, “Yes. In fact the first coin I flipped landed heads up.” What is the chance that Carl’s coins both landed heads up?

The standard answer is 1/2, because there are only two possibilities for the coin flips: HH and HT. But how do we know that these possibilities are equally probable?

The answer depends on what we expect Carl to say when he flips two heads. My personal assumption is that Carl is a perfectionist and always volunteers extra information. If Carl gets two heads, I would expect him to say, “Yes. In fact both coins I flipped landed heads up.” In this case the answer to the puzzle is 0.

Another strange but reasonable assumption is that upon flipping two heads, there is an equal probability that Carl would say either, “Yes. In fact the first coin I flipped landed heads up;” or, “Yes. In fact the second coin I flipped landed heads up.” In this case, the answer to the puzzle is 1/3.

I could describe an assumption for Carl’s answering strategy that leads to the puzzle’s answer of 1/2, but it looks too artificial to me.

This puzzle is not well-defined, but unfortunately there are many versions of it floating around the Internet with incorrect solutions.

Here is a standard logic puzzle:

A criminal is sentenced to death. He is allowed to make one last statement. If the statement is true, the criminal will be sent to the electric chair. It the statement is false, he will be hanged. Can you suggest a good piece of advice for this man?

I can offer many pieces of advice to this man. The simplest thing is to keep silent. Or he can communicate without making statements, like asking, “Can I have some crème brûlée, please?”

One can argue that the puzzle implies that it’s a favor to allow the prisoner to make a last statement, but without it he will die anyway. In this case the standard piece of advice to this man would be to create a paradoxical situation by saying, “I will be hanged.”

Another, less standard, idea is to state something that is very difficult to check. For example, to give the exact number of planets in our galaxy, or posit that P = NP. My son, Sergei, suggested saying that “Schrödinger’s cat is dead.”

But the most popular idea among my AMSA students is to say, “I am sorry.” I’m not 100% sure that they mean it as a statement that is impossible to check. Maybe they think that these words can do magic and save lives. Or maybe it could be the best thing for a criminal to say before dying.

Anyone knows that sometimes the text is not exactly what it seems to be. There are many different simple ways to hide a secret message inside your text. So, your humble blogger decided to run an experiment. How should we go about it? I decided to hide a secret message inside this short essay. Do you see it? Do you notice that my text is artificially adjusted for some extra purpose? Everyone can feel that this text sounds different than my usual postings. Nothing should stop you from solving this puzzle now.

I’ve got this puzzle from Nick Petry.

Captain Flint is dying. All his treasures are buried far away. He only has 99 pieces of gold with him. Filled with remorse at the last moments of his life, he decides that he only wants to take one piece of gold with him to his grave. The rest of the gold he will give to the families of two men that he had killed the day before.

Though Captain Flint is heavily drunk he notices that no matter which piece he takes for himself, he can divide the leftover 98 pieces into two piles of 49 pieces each of the same weight. Prove that all the gold pieces are of the same weight.

For an additional challenge, Sasha Shapovalov suggested the following generalization of the previous puzzle.

Captain Flint has N gold pieces and yesterday he killed not two but K men. He wants to take one piece with him to his grave and to divide the rest into equi-weighted piles, not necessarily of the same number of pieces. If he can choose any piece to take with him and is able to divide the rest, prove that N – 1 is divisible by K.

Both of these puzzles can be easily solved if the weight of every gold piece is an integer or even a rational number. If you don’t assume that the weights are rational numbers, then I do not know an elementary solution, but I do know a simple and beautiful solution using linear algebra for both puzzles.

Even pirates need linear algebra to divide their treasure. Hooray for linear algebra!

Here is a logic puzzle for kids:

— John has more than a thousand books, said Pete.
— No, he has less than one thousand books, said Ann.
— Surely, he has at least one book, said Mary.

If only one statement is true, are you sure you know how many books John has?