puzzles – Maths

Managers of the round table

This is an old but good puzzle, which I personally enjoyed solving quite a while ago.

Seats of the round table are all labeled with the names of N managers. All managers have chosen the wrong seat. Prove that you can always rotate the table so that at least two managers sit in the positions with the correct names.

This problem is quite simple, so I don’t provide the solution, but feel free to share it in comments. As a hint, I can say that the whole solution shouldn’t be longer that one or two sentences.

Arbitrary distribution using biased coin

Problem. Let’s assume that you have a biased coin, but you don’t know the probabilities of its sides. Using the coin, how would you choose one of the numbers 1, 2 or 3 with equal probability?

Stop reading here and try solving the problem yourself before moving on.

Solution. First of all, I have to note that this problem have a trivial solution that works only for this particular question, not in a general case. One such solution was proposed by a reader in the comments section. In this post, we present a solution that will work for arbitrary distributions, no matter how asymmetric they are.

The problem becomes easier if we split it into two parts. Firstly we will learn how to emulate a fair coin using a biased one. After this we describe a procedure which allows us to get numbers from an arbitrary probabilistic distribution.

Let’s denote the probability of tails as $p$. Then if we toss the coin twice, we can get one of the four outcomes:

Tails both times, with probability $p^2$,
Heads both times, with probability $(1-p)^2$,
Tails first time, heads second time, probability $p(1-p)$.
Heads first time, tails second time, probability $p(1-p)$.

As you see, outcomes 3 and 4 have equal chances to appear. Thus, in order to emulate an experiment with probability 50/50 (fair coin), we can toss the coin twice. If both tosses give the same outcome, then discard it and toss again. When we get tails in one toss and heads in the other, we choose the outcome which comes first.

Example. Consider a sequence of tosses T, T, H, H, T, H, where I denoted tails as T and heads as H. This sequence describes an experiment in which we toss the coin twice and both times we get tails. We discard this result and toss twice again. This time we get two heads. Now, we toss twice one more time. First, we get tails and then heads. We write “tails” as our outcome.

Since now we can assume that we have a fair coin. We will be repeating tosses sequentially and interpreting them as digits in a binary representation of a number $s$ in interval $[0, 1]$:

$$s=\sum\limits_{i=1}^{+\infty} \frac{t_i}{2^i}$$

Here $t_i$ denotes the outcome of i-th toss and can be either 0 or 1. In order to get one of the three values at random, we split $[0,1]$ into three subintervals $[0, 1/3), [1/3, 2/3], (2/3, 1]$. (Since particular points like 1/3 has zero probability, we don’t care into which interval we include them). The outcome of the experiment is the number of the subinterval in which $s$ lies. Since we assume that each digit of $s$ is uniform, $s$ itself is uniform in $[0,1]$.

In fact we don’t need the exact value of $s$. The only interesting bit is the subinterval in which $s$ lies, so we don’t have to make an infinite number of tosses. Let’s say that the first toss gave us value 1. We know that $s=0.1\ldots$ (in binary) and it lies somewhere in $[1/3, 2/3]$. If the next toss gives us 0, then $s=0.10\ldots$ and $s\in[1/3, 0.59]$. If the next toss gives us 0 again, then $s=0.100\ldots$ and we know that $s\in[1/3, 0.46)$ which is a subinterval of $[1/3, 2/3]$. The outcome is the second value.

This scheme can be generalized in an obvious way. If we want to get an arbitrary distribution we just have to split $[0,1]$ into a given number of subintervals of lengths that match the probabilities of the values.

Impossible puzzle

The following story took place in the Soviet Union, where children started their studies at school at the age of 7. It is important to know this for the solution of the problem.

Two mathematicians who hadn’t seen each other for years met in the park and had the following conversation:

“Hi! How are you? Do you already have kids?”

“Hi! I’m fine, thanks! Yes, I have two kids, both of them are still preschoolers.”

“How old are they?”

“The product of their ages is the number of pigeons around that bench.”

“Hmm. I don’t have enough information to learn their ages.”

“The older takes after his mother.”

“Oh, now I see!”

Question: What are the ages of the children?

I have to admit that when I was given this problem in my teenage years, I wasn’t able to solve it. When I gave up, I was given a hint: “The order of the phrases in the dialogue is important”. This allowed me to solve the problem within minutes. I am not publishing the solution, but instead, I’ll present a set of similar problems below the statements of which can also be used as a hint. Feel free to share and discuss the solution in the comment section though.

Many years after I was given this problem, I learned that it is a simplification of a much harder mathematical puzzle. Here it is.

Alice thought of two distinct numbers, both bigger than 1. She told the sum of the numbers to Sam (this sum appeared to be smaller than 100) and their product to Peter. Then the following conversation between Sam and Peter occurred:

“I know that you don’t know the numbers which Alice thought of,” told Sam to Peter.

“Now I know them,” Peter answered.

“Now I know them too,” said Sam.

Question: What are Alice’s numbers?

This problem is much harder than the puzzle with children’s ages stated above. I was able to solve it only by writing a program which enumerated all of the possibilities, but I know that many people do it manually using simple arithmetic tricks and tedious bookkeeping. If you cannot solve the problem yourself you can check the solution in Wikipedia. Note that the condition for the sum of Alice’s numbers to be less than 100 is critical. It is clear that a too wide range would make the solution non-unique, but what is interesting is that if the range is too small (if the sum is less than 62) the solution also cannot be found. It is quite difficult and instructive to analyze how the number of solutions depends on the allowed range for the sum.

If this problem still appears too difficult, you can also check “Cheryl’s Birthday” problem from Asian Schools Maths Olympiad. It is just another variation of the same problem of less complexity. (It seems that this is the easiest version of all known to me).

There is one more modification of the same problem which is my favorite.

Alice made up three positive natural numbers. She told the sum of these numbers to Sam and the product of these numbers to Peter. Then the following conversation happened:

“If only I knew that the number which you were given is bigger than the number which I was given, then I’d be able to immediately tell what numbers Alice made up”, said Sam.

“No, the number which Alice told me is smaller than yours, and I know all of the numbers”, Peter responded.

Question: What numbers did Alice make?

This problem is not as immediately straightforward as the problems above, although it is much easier computationally. Once again I am not providing the solution, but you can discuss it in the comments section.

For the reference, the answer to the last problem is numbers 1, 1 and 4. It is quite easy to find these numbers, but you should also be able to demonstrate clearly that these numbers are the only solution which is possible. This problem was given in one of the Russian Math Competitions (unfortunately, I’ve lost the reference) and if the correct answer was given, but the uniqueness of the solution wasn’t shown, the solution wouldn’t count.

The hardest logic puzzle ever

Imagine you have a conversation with three gods. One god always tells the truths. Another god always lies. The third god gives random answers. These gods can answer any of your question which admits a yes or no response. The problem is that you don’t know which god is lying, which tells the truths and which is random. Moreover, the gods answer in their own language, in which “yes” and “no” sounds like “da” and “ja”, but you don’t know the translation of these words. By asking as few questions as possible you have to find out which god is random, which god tells the truths and which god always lies.

Take your time to try to solve this problem. Then read on.

First of all, the problem says that we have to solve it using as few steps as possible. It appears that we can estimate the number of required questions even without knowing the questions themselves. We have three gods and three roles for them. The number of different combinations of roles is just a number of permutations of these roles, which is 3!=6. At the same time if you asked n yes/no questions, then you may distinguish between 2ⁿ different situations. We need 2ⁿ to be bigger than 6, which gives us that we need at least three questions to determine the roles of the gods.

So, what these three questions should be? This is a hard problem and we will solve it in several steps:

We will first solve the problem in the assumption that there is no random god and that the gods answer in English.
After this, we will assume that they answer “da” and “ja” instead of “yes” and “no”.
Eventually, we will solve the initial problem with a random god.

Each of these steps is much easier to solve and I advise you to stop here and try to think about the problem again.

So, we have two gods. One is always lying and the other is always telling the truth. Let’s say that S is some statement and we want to learn truthfulness of it. It appears that we can do it by asking only one question to an arbitrary god. To understand how to formulate the question, consider first the following truth table:

T	S	desired answer
0	0	0
0	1	1
1	0	0
1	1	1

Here I denoted by T the fact that we talk to the god which tells the truths and by S, as above, the actual truthfulness of the statement which interests us. 0 means “false” and 1 means “true”. Example: if we talk to the god which tells the truths and the statement S is false, then it matches the third line of a table and the desired answer is “no” (denoted in the table as 0).

The problem is that in the first two rows instead of the desired answer we will get an inverted answer since we are talking to the lying god. But if we ask our question not about S, but about some other statement Q₁, which has inverted truth values in the first two rows of a table, we will get the desired result:

T	S	Q₁	answer we get
0	0	1	0
0	1	0	1
1	0	0	0
1	1	1	1

As you can see, in this case, if we ask a question about the truthfulness of Q₁, we instead get the correct answer about the truthfulness of P. Q₁ just means that both statements T and S are logically equivalent, so our question to a god may sound like this: “Could you tell me please, if either both statements ‘you always tell the truth’ and ‘S’“are true, or both of them are false?” You can do your calculation to make sure that the response to this question always matches to the truth value of S, no matter which god you ask this question.

The second problem requires just a slight extension of this approach and you may want to try to do it yourself before moving on.

So, now instead of “yes” and “no” we have responses “ja” and “da” with unknown meaning. We can make an assumption that “ja” means “yes” (I call this assumption A below) and extend our truth table the same way as we did before:

T	A	S	Q₁	Q₂	answer we get
0	0	0	1	0	da
0	0	1	0	1	ja
0	1	0	1	1	da
0	1	1	0	0	ja
1	0	0	0	1	da
1	0	1	1	0	ja
1	1	0	0	0	da
1	1	1	1	1	ja

Here Q₁ has the same meaning as before and Q₂ inverts the value of Q₁ in case “ja” means “no”. This may be a little bit difficult to digest at first, but the idea here is quite simple. We assume that “ja” means “yes” and we want to hear the response “ja” if S is true. But if “ja” means “no”, we want a god to revert his response so he still answers “ja” in case of truth, and this is the purpose of Q₂.

How to ask the question of the truthfulness of Q₂? We can explain to the god how we build the table above and then ask for a value of Q₂. The god knows the values of T, A, and S and so he knows what number we are interested in. Then he either tells us the truths or lies, using rules of his own language. You may evaluate different possibilities of the answer yourself and see that he will say “ja” if and only if S is true.

Another approach to ask the same question is to ask it in a more direct fashion by using Conjunctive Normal Form of logical statements, but I’ll skip this since it is fairly simple and you can understand how to do it from Wikipedia article.

The question could be formulated much easier. Let’s once again assume that the gods answer “yes” and “no”. How would a god respond to the question “What would you tell me, if I asked you about the truthfulness of S?” The god which tells the truths would give us the correct value of S, this is simple. But the god which lies will be tricked. Let’s assume that S is true. If you ask a question about S directly, the god which lies would answer “no”. But we are not asking about S, we are asking about the answer he would give, so the god will have to lie again and say “yes”, the value of S. The same logic applies if S is false.

It is easy to extend this approach to the case when the gods answer with “ja” and “da”. The question is the following: “Would you say ‘ja’ if I asked you about the truthfulness of S? You can work out the logic behind this question yourself.

There are two reasons why I presented two possible solutions for this problem. First of all, I was asked this question at a job interview and I was able to come up with a solution with truth tables myself, so I am particularly proud of it (although I didn’t get that job). Another reason is that it is interesting that the first solution was achieved using quite trivial formal logic, while the second one is based on a language play, which cannot be formalized by mathematical methods. This means that, for example, the first solution could be potentially found by Artificial Intelligence, but the second, short and elegant, couldn’t even be represented using the methods of AI available today. This is a fundamental limitation of all of the formal systems which mathematics and AI use in comparison to a “real” logic used by humans.

After solving the second subproblem, we know how to ask for any information from truth-telling or lying god using only a single question. We just have to eliminate the god which gives us totally random answers. I’ll present the questions as though we could ask them directly, but you have to keep in mind that these questions should be “translated” to a form which allows us to get a correct response. The next paragraph contains a solution to the entire problem and you know what to do.

Let’s say that we enumerated the gods as 1, 2, 3. We ask the first god: “Is the second god Random?”. If he answers “yes”, it may be the truth, or it may just mean that the first god gave us a random response. In both cases, we can conclude that the third god is not random and we can proceed to ask questions to him. If the response to the question is “no”, then we know for sure that the second god is not random. The rest is trivial.

In the solution presented above, we didn’t define what “random” actually is, but it can mean different things. This puzzle was initially published by George Boolos and the definition which he used assumed that the random god flips the coin before each answer and the result of this flipping defines if he tells the truth or lies.

At first sight, it may look like a valid definition for randomness, since to the question “Are all roses are red?” we may receive responses “yes” or “no” with equal probability. At the same time, to the question “What would you tell me if I asked you whether all the roses are red?” he would give the response “no”. He flips the coin to decide if he tells the truths, but in both cases, he got caught into the trap of our indirect question. “Yes” is impossible and he doesn’t look like random anymore. The solution I presented above works for a truly random god as well, but the fact that the definition of randomness with flipping a coin doesn’t make him truly random is remarkable.

The last bit. We assumed that even if we don’t know the meaning of the words “ja” and “da”, we at least know what possible responses might be. This is a lot of information already! What if we didn’t know even a single possible word in god’s language? It is easy to solve the problem in four steps. First, ask an arbitrary question to learn at least one word from god’s vocabulary. Then apply the strategy derived above. This straightforward solution is easy, but is it possible to solve the problem with fewer steps?

If one of the gods is truly random (without flipping a coin), then the solution in three steps is impossible. It is clear that the last question can be asked only to a non-random god. If you think about it for a bit, this observation is also quite remarkable: we cannot get any information by asking the last question to the random god, but asking a question to the random god the first question is actually giving us information on who is not random (we used this trick in our initial solution). This is quite difficult to explain without going into depths of theory, but a short story is that this happens because a randomized answer can only reduce uncertainty, but cannot give you precise information.

So we have to determine which god is not random by using only two questions. The first response is some word which we’ve never heard before, so it cannot give any information. It means that the second question cannot depend on the response to the first question. If you add to the mixture true randomness, it appears that even though we can get some information from these two responses, we cannot confidently eliminate a random god. Details, unfortunately, are quite complicated and I will skip it.

If the random god is defined by flipping a coin, the solution in three steps is possible. The first two questions are the following:

First ask the first god: “Let’s consider English transliteration of words ‘yes’ and ‘no’ in your language. If I asked you whether you are random would you answer with a response which goes alphabetically first in the list of transliterations?”
Then ask the second god: “Would you give me the same response to the same question which I just asked?”

I leave it as a nice exercise to understand how you can make sense out of responses to these two questions and how to complete the puzzle in this case.

Monty Hall problem

I’ll start my blog with the Monty Hall problem. It is a well-known classic problem and quite a trivial one, but I still want to present it here, because for me personally, it means a lot. It was one of the first “paradoxes” I learned in my life and it has greatly affected my interests and mathematical taste, so I have some special kind of respect for this problem.

Imagine that you are on a TV show in front of three closed doors. There is a car behind one of the doors and if you pick the right door, you win the car. After you select the door, the host doesn’t open it immediately but instead opens another door without a prize. Now you have a choice out of two doors and you are given a chance to change your initial guess. Would it make sense to change the door or not?

This problem doesn’t need any maths knowledge except basic arithmetic. If you don’t know this problem yet, stop reading here and try to solve it on your own.

One incorrect response I saw is the following. We have three doors and the car is behind one of the doors. So the chance to win is 1/3. (This is correct). Since each door has the same chances of having a car behind, it doesn’t matter if you change the door.

In response to the idea above one may propose another incorrect reasoning: after one losing door is eliminated, each of the remaining doors has the probability of 1/2 of being winning. So it is still doesn’t matter if you change the door, you always get 1/2 chance of winning. Can you see what’s wrong with this solution?

The correct answer is the following: if you don’t switch the door, then the probability of winning is 1/3. If you switch the door, the probability is 2/3.

One way to see how this works is to consider the probability that your initial choice is incorrect, which is 2/3. The phrase “the door I’ve chosen is incorrect” may be rephrased as “one of the doors I haven’t chosen is correct”. This probability stays the same after the host eliminates one of the doors. After this you know that the remaining door is “the door I haven’t chosen”, and the probability it has the car is the same that you initially made a mistake. This is 2/3.

This solution gives the right answer, but it doesn’t give the right intuition. It is not entirely clear immediately why this solution is more correct that the solution which gives us answer 1/2. I’ll try to explain this below.

Before I go to the solution, you can try playing this game several times with your kid. You will be a host and your kid will try to win. Play this game 20 times and check how many times your kid was able to win. Then suggest her a strategy to always keep her initial choice. Play another 20 times. After this, she can realize that she is winning less than before (if she was making choices more or less randomly). If you’re lucky, she would suggest playing again, but this time she changes the door each time. If not, you can suggest this idea yourself (or this time she can be the host and you can demonstrate a good result by switching the door each time). Amusingly, when you or your kid changes the door each time, you may expect the results to be better than in two previous tries. Now you can go to an explanation.

The problem can be trivially explained by enumeration of all of the possible cases. Let’s assume that we’ve chosen the first door. There are three possibilities where the car can be:

1. A car is behind the first door (the one you chose). If we don’t change the door when we have the opportunity, we win. If we change the door, we lose.

2. A car is behind the second door. If don’t change the door, we lose. Otherwise, we win.

3. A car is behind the third door. If don’t change, lose. Otherwise, win.

As you see, if we keep the initial door, we win only in one case out of three. If we change the door, we win in two cases out of three. This gives us probabilities of 1/3 for keeping our choice and 2/3 changing the door.

What if initially we chose the second or the third door? The situation will be symmetric to what we’ve just seen, so it doesn’t affect the probability.

If you know the basics of probability theory, you can easily solve this problem with the law of total probability and see that the solution just repeats the solution above. But if we used this law initially, it wouldn’t look so convincing (at least if you’re just learning basics). This is not a coincidence: probability theory is just about counting possibilities at its heart, and it is always useful to remember this. This often makes reasoning simpler and helps you to distinguish the correct reasoning from an incorrect one.

Another approach to take on such kind of problems is to generalize them. Let’s say that instead of 3 doors, TV-show uses 100 doors. Only one has a prize behind. You select one door, then the host opens 98 doors which don’t have prizes. Would you switch the door in this case? The answer should be obvious.

Problem. Let’s say that there are N doors in total, W of them are with prizes. You are allowed to choose one door. After this, the host opens K doors without a prize and you’re allowed to choose another door. What is your probability to win a prize in this case?

This is quite a simple problem if you know about binomial coefficients so I’ll leave it as an exercise. Feel free to post your solution in comments.

Not only the problem itself but also its history is interesting though.

Initially, this problem was proposed by Steve Selvin in 1975, but it became well-known only when a reader of Parade magazine asked this question in the “Ask Marilyn” column. Marylin vos Savant gave a correct answer, but she immediately started receiving letters explaining why she is wrong. Most of these letters were from people with a Ph.D. degree. Here’s a couple of examples, taken from Marylin vos Savant website:

[…] You blew it! Let me explain. If one door is shown to be a loser, that information changes the probability of either remaining choice, neither of which has any reason to be more likely, to 1/2. As a professional mathematician, I’m very concerned with the general public’s lack of mathematical skills. Please help by confessing your error and in the future being more careful.
Robert Sachs, Ph.D.
George Mason University

You are utterly incorrect about the game show question, and I hope this controversy will call some public attention to the serious national crisis in mathematical education. If you can admit your error, you will have contributed constructively towards the solution of a deplorable situation. How many irate mathematicians are needed to get you to change your mind?
E. Ray Bobo, Ph.D.
Georgetown University

I am in shock that after being corrected by at least three mathematicians, you still do not see your mistake.
Kent Ford
Dickinson State University

It seems that Ph.D. status doesn’t guarantee sanity or at least basic knowledge of arithmetic, unfortunately. At the same time, Ms. Savant was also receiving letters from primary school teachers who tried this experiment with young kids. And these kids and teachers did solve the problem correctly and was amused by the result. (My advice above to try it with your kid wasn’t random).

What is more interesting is the difference between confusion which it made in 1990 and the acceptance it has now. This paradox is learned in many schools and universities around the world, and I haven’t heard that it provokes any doubts among the students. The mathematical education hasn’t changed a lot in these 28 years, so what’s going on here? I am afraid that the answer is that students are just taught to believe that the proof from the textbook is correct, but don’t understand it. If people with Ph.D.s weren’t able to solve the problem, then how can 17 y.o. kids solve it in an exam? This is why I not only present the correct solution but at first give incorrect ones to sparkle a doubt.

The last bit. As far as I know, originally the problem didn’t mention any particular TV-show explicitly (I may be wrong, because I didn’t find reliable sources). Monty Hall was a host in a real TV-show called “Let’ make a deal!” in the seventies and Steve Selvin wrote a letter to him. I don’t know what was in that letter (if you know where I can read it, please let me know), but the response from Monty became popular and since then the problem has Monty Hall name:

May 12, 1975

Mr. Steve Selvin
Asst. Professor of Biostatistics
University of California, Berkeley

Dear Steve:

Thank you for sending me the problem from “The American Statistician.”

Although I am not a student of a statistics problems, I do know that these figures can always be used to one’s advantage, if I wished to manipulate same. The big hole in your argument of problems is that once the first box is seen to be empty, the contestant cannot exchange his box. So the problems still remain the same, don’t they? one out of three. Oh, and incidentally, after one is seen to be empty, his chances are no longer 50/50 but remain what they were in the first place, one out of three. It just seems to the contestant that one box having been eliminated, he stands a better chance. Not so. It was always two to one against him. And if you ever get on my show, the rules hold fast for you-no trading boxes after the selection.

Next time let’s play on my home grounds. I graduated in chemistry and zoology. You want to know your chances of surviving with our polluted air and water?

Sincerely,
Monty