Tanya Khovanova's Math Blog

Here is a setup that works for the several puzzles that follow it:

The sultan decides to test his hundred wizards. Tomorrow at noon he will randomly put a red or a blue hat—from his inexhaustible supply—on every wizard’s head. Each wizard will be able to see every hat but his own. The wizards will not be allowed to exchange any kind of information whatsoever. At the sultan’s signal, each wizard needs to write down the color of his own hat. Every wizard who guesses wrong will be executed. The wizards have one day to decide together on a strategy.

I wrote about puzzles with this setup before in my essay The Wizards’ Hats. My first request had been to maximize the number of wizards who are guaranteed to survive. It is easy to show that you cannot guarantee more than 50 survivors. Indeed, each wizard will be right with probability 0.5. That means whatever the strategy, the expected number of wizards guessing correctly is 50. My second request had been to maximize the probability that all of them will survive. Again, the counting argument shows that this probability can’t be more than 0.5.

Now here are some additional puzzles, including the first two mentioned above, based on the same setup. Suggest a strategy—or prove that it doesn’t exist—in which:

1. 50 wizards will be guaranteed to survive.
2. 100 wizards will survive with probability 0.5.
3. 100 wizards will survive with probability 0.25 and 50 wizards will survive with probability 0.5.
4. 75 wizards will survive with probability 1/2, and 25 wizards survive with probability 1/2.
5. 75 wizards will survive with probability 2/3.
6. The wizards will survive according to a given distribution. For which distributions is it possible?

As I mentioned, I already wrote about the first two questions. Below are the solutions to those questions. If you haven’t seen my post and want to think about it, now is a good time to stop reading.

To guarantee the survival of 50 wizards, designate 50 wizards who will assume that the total number of red hats is odd, and the rest of the wizards will assume that the total number of red hats is even. The total number of red hats is either even or odd, so one of the groups is guaranteed to survive.

To make sure that all of them survive together with probability 0.5, they all need to assume that the total number of red hats is even.

There are too many Olympiads. Now there is even a special undergraduate Olympiad in probability, called Kolmogorov Student Olympiad in Probability. It is run by the Department of Probability Theory of Moscow State University. I just discovered this tiny Olympiad, though it has been around for 13 years.

A small portion of the problems are accessible for high school students. These are the problems that I liked. I edited them slightly for clarity.

Second Olympiad. Eight boys and seven girls went to movies and sat in the same row of 15 seats. Assuming that all the 15! permutations of their seating arrangements are equally probable, compute the expected number of pairs of neighbors of different genders. (For example, the seating BBBBBBBGBGGGGGG has three pairs.)

Third Olympiad. One hundred passengers bought assigned tickets for a 100-passenger railroad car. The first 99 passengers to enter the car get seated randomly so that all the 100! possible permutations of their seating arrangements are equally probable. However, the last passenger decides to take his reserved seat. So he arrives at his seat and if it is taken he asks the passenger in his seat to move elsewhere. That passenger does the same thing: she arrives at her own seat and if it is taken, she asks the person to move, and so on. Find the expected number of moved passengers.

Third Olympiad. There are two 6-sided dice with numbers 1 through 6 on their faces. Is it possible to “load” the dice so that when the two dice are thrown the sum of the numbers on the dice are distributed uniformly on the set {2,…,12}? By loading the dice we mean assigning probabilities to each side of the dice. You do not have to “load” both dice the same way.

Sixth Olympiad. There are M green and N red apples in a basket. We take apples out randomly one by one until all the apples left in the basket are red. What is the probability that at the moment we stop the basket is empty?

Seventh Olympiad. Prove that there exists a square matrix A of order 11 such that all its elements are equal to 1 or −1, and det A > 4000.

Twelfth Olympiad. In a segment [0,1] n points are chosen randomly. For every point one of the two directions (left or right) is chosen randomly and independently. At the same moment in time all n points start moving in the chosen direction with speed 1. The collisions of all points are elastic. That means, after two points bump into each other, they start moving in the opposite directions with the same speed of 1. When a point reaches an end of the segment it sticks to it and stops moving. Find the expected time when the last point sticks to the end of the segment.

Thirteenth Olympiad. Students who are trying to solve a problem are seated on one side of an infinite table. The probability that a student can solve the problem independently is 1/2. In addition, each student will be able to peek into the work of his or her right and left neighbor with a probability of 1/4 for each. All these events are independent. Assume that if student X gets a solution by solving or copying, then the students who had been able to peek into the work of student X will also get the solution. Find the probability that student Vasya gets the solution.

The Russian website problems.ru has a big collection of math problems. I use it a lot in my work as a math Olympiad coach. Recently I was giving a statistics lesson. While there was only one statistics problem on the website, it was a good one.

Assume that every person in every country was tested for IQ. A country’s IQ rating is the average IQ of the population. We also assume that for the duration of this puzzle no one is born and no one dies.

• A group of citizens of country A emigrated to B. Show that the rating of both countries can go up.
• After that a group of citizens of B (which may include former citizens of A) emigrated to A. Is it possible that the ratings of both countries go up again?
• A group of citizens of A emigrated to B, and a group of citizens of B emigrated to C. As a result, the ratings of each country increased. After that the migration went the opposite way: some citizens of C moved to B, and some citizens from B moved to A. As a result, the ratings of all three counties went up once more. Is this possible? If yes, then how? If no, then why not?

My AMSA students loved the following puzzle from the 2003 Math Kangaroo contest for grades 7-8:

The children A, B, C and D made the following assertions.

• A: B, C and D are girls.
• B: A, C and D are boys.
• C: A and B are lying.
• D: A, B and C are telling the truth.

How many of the children were telling the truth?
A) 0   B) 1   C) 2   D) 3   E) Impossible to determine

I was given this puzzle at the last Gathering for Gardner.

Use arithmetic operations to express 6 using three identical digits. For each digit from 0 to 9 find at least one way to express 6.

For example, I can express 6 using three twos in many ways: 2 + 2 + 2, or 2 · 2 + 2, or 2² + 2. But the problem doesn’t ask for many ways. One way is enough, but you need to do it for every digit. So nine more cases to go: 0, 1, 3, 4, 5, 6, 7, 8, and 9.

This is one of my favorite jokes:

Three logicians walk into a bar. The waitress asks, “Do you all want beer?”
The first logician answers, “I do not know.”
The second logician answers, “I do not know.”
The third logician answers, “Yes.”

This joke reminds me of hat puzzles. In the joke each logician knows whether or not s/he wants a beer, but doesn’t know what the others want to drink. In hat puzzles logicians know the colors of the hats on others’ heads, but not the color of their own hats.

This is a hat puzzle which has the same answers as in the beer joke. Three logicians walk into a bar. They know that the hats were placed on their heads from the set of hats below. The total number of available red hats was three, and the total number of available blue hats was two.

Three logicians walk into a bar. The waitress asks, “Do you know the color of your own hat?'”
The first logician answers, “I do not know.”
The second logician answers, “I do not know.”
The third logician answers, “Yes.”

The puzzle is, what is the color of the third logician’s hat?

This process of converting jokes to puzzles reminds me of the Langland’s Program, which tries to unite different parts of mathematics. I would like to unite jokes and puzzles. So here I announce my own program:

Tanya’s Program: Find a way to convert jokes into puzzles and puzzles into jokes.

There is a famous puzzle about three light bulbs, that is sometimes given at interviews.

Suppose that you are standing in a hallway next to three light switches that are all off. There is another room down the hall, where there are three incandescent light bulbs—each light bulb is operated by one of the switches in the hallway. You can’t see the light bulbs from the hallway. How would you figure out which switch operates which light bulb, if you can only go to the room with the light bulbs one and only one time?

This puzzle worked much better in the past when we only had incandescent light bulbs and so didn’t need to specify the type of bulbs. Unfortunately, the standard solution only works with incandescent bulbs and the word “incandescent” nowadays needs to be stated. But the use of “incandescent” is a big hint. Indeed, incandescent light bulbs generate heat when they are on, so the standard solution is to turn on the first light switch, to keep the second switch off, and to turn the third switch on for five minutes before turning it off. In the room, the light bulb corresponding to the first switch will be lit, and out of the two unlit bulbs, the one corresponding to the third switch will be warm.

It’s a cute solution, but there could be so many other approaches:

• You can ask a friend to help you. You can come to the room with the light bulbs and shout to her which switch to turn on.
• You can place mirrors from the room to the hall, so you can see bulbs through the multiple reflections. You might not need to enter the room at all.
• Before playing with the switches, you can place a video camera in the room to transmit the scene in real time. You will not be allowed to enter the room again to get the camera back, but what the heck: the job will be done.
• You can put timers on the switches and set them to turn on at different times.
• You can attach strings to switches and turn them on or off from a distance.

I invite my readers to invent other methods to solve this problem. Be creative. After all, if I were to interview you for a job, I would be more impressed by a new solution than the one that is all over the Internet.

You arrive at an archipelago of many islands. On each island there are two villages. In one village truth-tellers live, and they always tell the truth. In the other village liars live, and they always lie. The islanders all know each other.

On the first island you stumbled upon three islanders and you ask each of them your question:

How many truth-tellers are there among you?

Here are their answers:

A: One.
B: A is wrong.
C: A and B are from the same village.

Can you determine who is a truth-teller and who is a liar?

This island is called a classic island, where all behave as if they were in a standard logic puzzle. It is a perfectly nice puzzle but B and C didn’t answer the question: B ratted on A, and C went on a tangent. When I was younger, I never cared about the motivations of A, B, or C. Their answers are enough to solve the puzzle. But now that I am older, I keep wondering why they would choose these particular answers over other answers. So I invented other islands to impose rules on how the villagers are allowed to answer questions.

Now you travel to the next island that is called a straightforward island, where everyone answers your question exactly. You are in the same situation, and ask the same question, with the following result:

A: One.
B: One.
C: Ten.

Can you determine who is a truth-teller and who is a liar?

Once again we wonder about their motivation. This time C told an obvious lie, an answer that is impossible. Why on earth did he say 10? Isn’t the goal of lying to deceive and confuse people? There is nothing confusing in the answer “ten.”

Now you come to the third island, which is a straightforward inconspicuous island. To answer your question, a liar wouldn’t tell you an obvious lie. For this particular situation, the liar has to choose one of the four answers that are theoretically possible: zero, one, two, or three. You are again in the same situation of asking three people how many truth-tellers are among them, and these are the answers:

A: Two.
B: Zero.
C: One.

Can you determine who is a truth-teller and who is a liar?

When you think about it, a truth-teller cannot answer zero to this question. So although zero is a theoretically possible answer, we can deduce that the person who said it is a liar. If liars are trying to confuse a stranger, and they’re smart, they shouldn’t answer “zero.”

The next island is a straightforward inconspicuous smart island. The liars on this island are smart enough not to answer zero. You are in the same situation again and ask the same question with the following outcome:

A: Two.
B: Two.
C: One.

Can you determine who is a truth-teller and who is a liar? You shouldn’t be able to. There are three possibilities. There are two truth-tellers (A and B), one truth-teller (C), or zero truth-tellers.

Let us assign probabilities to liars’ answers. Assume that liars pick their answers randomly from the subset of wrong answers out of the set: one, two, three. If two of these answers are incorrect, they pick a wrong answer with probability one half. If all three of the answers are incorrect, they pick one of them with probability one-third. Suppose the people you meet are picked at random. Suppose that the probability that a random person is a truth-teller is 1/2. Given the answers above, what is more probable: that there are two truth-tellers, one truth-teller, or zero truth-tellers?

You visit an island of three towns: Trueton, Lieberg and Alterborough. Folks living in Trueton always tell the truth. Those who live in Lieberg, always lie. People from Alterborough alternate strictly between truth and lie. You meet an islander who says:

Two plus two is five. Also, three plus three is six.

Can you determine which town he is from?

It should be easy. He made two statements: the first one is false, the second is true. So he must be from Alterborough.

But what about “also”? How should we interpret this transition? There are many ways to interpret this “also.” On one hand it could mean: In addition to the previous statement I am making another statement. On the other hand it could mean: The previous pause shouldn’t be considered as the end of the statement; the whole thing should be interpreted as one statement. Besides this person was speaking not writing. Are we sure that the first period was not meant to be a comma or a semi-colon? If we assume that the quote is one statement, then the speaker might be either a liar or an alternator.

Here is a puzzle for you from the same island:

One night a call came into 911: “Fire, help!” The operator couldn’t ID the phone number, so he asked, “Where are you calling from?” “Lieberg.” Assuming no one had overnight guests from another town, is there an emergency? If so, where should help be sent? And was it a fire?

Now find the ambiguities.

The MIT Mystery Hunt starts on Friday. My old team—Manic Sages— fell apart after last years’ hunt. My new team—Death and Mayhem—started sending us daily practice puzzle to prepare for the hunt.

Today’s puzzle was written by Paul Hlebowitsh. As usual, the answer is a word or a phrase.

Puzzle 3: Humans

“After a long day taking care of the animals, it’s good to unwind by letting the taps flow.”

Tap 1: Sierra Nevada Pale Ale
Tap 2: Lagunitas Pale Ale
Tap 3: 21st Amendment “Brew Free! or Die IPA”
Tap 4: Wachusett Blueberry
Tap 5: Harpoon UFO

Alice, Bob, Carol, Danny, Erica, Fred, and Gregario, the seven children of Noah, went to a local bar before the flood to get drinks. Accounts of night vary, and no one remembers exactly what happened, but some facts have become clear:

1. Everyone had two drinks, in some order.
2. Danny liked his first drink so much he had it again. Everyone else had drinks from different breweries.
3. Erica was the only person to drink an IPA.
4. Four people had the Wachusett Blueberry as their first drink.
5. One person had the Sierra Nevada Pale Ale as their first drink.
6. Alice only drank beers with headquarters in California, in order to spite Bob and Danny.
7. Two Harpoon UFOs were ordered, as well as two Sierra Nevada Pale Ales. 8
8. Alice’s second drink was the same as Fred’s first drink.
9. Bob and Danny hate California and refuse to drink any beer from a company that’s headquartered there.
10. Alice and Erica had the same first drink.
11. Fred had a Harpoon UFO.

Who ordered which drinks and in what order?