Tanya Khovanova's Math Blog

I stumbled upon one of Smullyan’s puzzle on Facebook, in Russian. I couldn’t find the original text, so I just translated it back for my students.

Puzzle. You are on an island where only truth-tellers and liars live. The truth-tellers always tell the truth, and the liars always lie. You meet an islander who sits with you for a long time, then says, “I already said this sentence.” Is he a truth-teller or a liar?

I expected the following solution. If this islander is a truth-teller, then there should have been a time when he said, for the first time, “I already said this sentence.” But this would create a contradiction.

However, my students used this puzzle as an opportunity to teach me some intricacies of the English language. They explained to me the ambiguities of my translation. Here is a shortened and lightly edited quote from one of them:

There are two different linguistic opinions that give different answers to this problem. The first is that the truth of a statement is decided at the moment it starts to be delivered: in this case, when the islander starts saying his statement. With this interpretation, for the statement to be true, he had to have said the sentence before, and for that to be true, he had to have said it even before that, and this continues indefinitely. Clearly, he cannot have been alive forever, so he has to be a liar.
The other opinion is that the verity of a statement is decided at the exact conclusion of its deliverance. Then, when the islander finishes saying his sentence, its truth is judged, and he has at that same instant “already” said the sentence, so he is telling the truth. By this interpretation, the islander is a truth-teller.

Another student had a different brilliant idea. Depending on the islander’s intonation, it is possible that he says, “I already said ‘this sentence’.” In that case, there are no self-referencing sentences, and the islander could be either a truth-teller or a liar.

I consulted my best English consultant: my son, Alexey, and here is his reply. “The basic answer is that neither truth nor semantic meaning are absolute, and edge cases will be judged differently by different observers. A sentence whose truth is time-dependent on the same scale as the duration of uttering the sentence is clearly an edge case. That’s why mathematicians intentionally try to eliminate ambiguity from their communication.”

He suggested the following fix for the puzzle’s translation.

Fixed puzzle. You meet an islander who says, “I have said this sentence before.” Is he a truth-teller or a liar?

Alexey didn’t stop at fixes and suggested the following bonus puzzles.

Bonus puzzle 1. You meet an islander who says, “I will have said this sentence.” Is he a truth-teller or a liar?

Bonus puzzle 2. You meet an islander who says, “I will say this sentence again.” Is he a truth-teller or a liar?

Ukraine is on my mind. Here is a problem for 9-graders from the 1978 Ukrainian Math Olympiad:

Problem. Prove that for every natural number n, the following number is not an integer.

Oskar van Deventer is a designer of beautiful mechanical puzzles. For the recent mini-MOVES gathering at the MoMath, he asked people in his Zoom breakout room to calculate the average age in the room without revealing their actual ages. I know the following solution to this puzzle.

People agree on a large number N that is guaranteed to be greater than the sum of all the ages. The first person, say Alice, thinks of a uniformly random integer R between 0 and N. Alice adds her age to R modulo N and passes the result to the second person, say Bob. Bob adds his age modulo N and passes the result to the third person, and so on. When the result comes back to Alice, she subtracts R modulo N and announces the sum total of all the ages.

During this process, no one gets any information about other people’s ages. But two people can collude to figure out the sum of the ages of the people “sitting” between them.

I gave this problem to my grandson, and he suggested the following procedure. First, people choose two trusted handlers: Alice and Bob. Then, each person splits their age into the sum of two numbers (the splitting should be random and allow one of the numbers to be negative). They then give one number to Alice and another to Bob. Alice and Bob announce the sums of the numbers they receive. After that, the sum total of everyone’s ages is the sum of the two numbers that Alice and Bob announce.

The advantage of this method is that no two people, except Alice and Bob, can collude to get more information. The disadvantage is that if Alice and Bob collude, they would know everyone’s age. Which method would you prefer?

Here is the famous barber paradox.

Paradox. The barber shaves all those and only those who don’t shave themselves. Does the barber shave himself?

If he shaves himself, then he doesn’t shave himself. If he doesn’t shave himself, then he shaves himself.

English is not my primary language, and I am fascinated by the variety of verb tenses in English as compared to the Russian language. For example, Russian has one present tense while English has four. I wonder what would happen if we use the other present tenses in this paradox.

Present continuous. The barber shaves all those and only those who aren’t shaving themselves. Does the barber shave himself?

Does this mean that the barber starts shaving himself and then has to stop, and a moment later he has to start again?

Present perfect. The barber shaves all those and only those who haven’t shaved themselves. Does the barber shave himself?

Does this mean that the barber shaves himself every other day?

Present perfect continuous. The barber shaves all those and only those who haven’t been shaving themselves. Does the barber shave himself?

Does this mean the barber shaves himself once in his lifetime and then never again?

Here is a problem from the 1978 Kyiv Olympiad for 7 graders.

Is it possible to place seven points on a plane so that among any three of them, two will be at distance 1 from each other?

Puzzle. Two girls were born to the same mother, at the same time, on the same day, in the same month, in the same year, and yet somehow they’re not twins. Why not?

I won’t tell you the expected answer, but my students are inventive. They suggested all sorts of scenarios.

Scenario 1. There are two different fathers. I had to google this and discovered that, indeed, it is possible. This phenomenon is called heteropaternal superfecundation. It happens when two of a woman’s eggs are fertilized by sperm from two different men. Unfortunately for my students, such babies would still be called twins.

Scenario 2. The girls are born on the same date, but not on the same day. This could happen when transitioning from the Julian to Gregorian calendar. The difference in birth times could be up to two weeks. I had to google this and discovered that twins can be born months apart. The record holders have a condition called uterus didelphys, which means that the mother has two wombs. Unfortunately for my students, such babies would still be called twins.

Scenario 3. The second girl is a clone. This scenario can potentially happen in the future. Fortunately for that student, I suspect that such babies would be called clones, not twins.

I decided to invent my own scenario outside of the actual answer, and I did.

Scenario 4. Two girls are from the same surrogate mother, but they are not twins. I had to google this and discovered that this actually happened: Surrogate mother of ‘twins’ finds one is hers.

Sometimes life is more interesting than math puzzles.

In his article on Möbius strips, Martin Gardner included a cute construction.

Construction. Cut out a cross from a piece of paper. Then glue one pair of opposite ends to make a cylinder and the other pair to make a Möbius strip. Then Martin instructs, “Trisect the twisted band, then bisect the untwisted one, and open up for a big surprise!”

In my effort to reuse Möbius strips, I started making them out of zippers. So Martin’s construction had its destiny zipped. The first picture shows the construction before it is being dissected. I was quite happy with my plan to use zippers as it had its advantages over paper. For the surprise to work, the twisted band shouldn’t be cut completely. Meaning, the middle part of the Möbius strip shouldn’t be cut. I sewed my zipper monstrosity not to cause any ambiguities: there is nothing to cut, just unzip the zippers.

Little did I know that unzipping is not the issue, but zipping back up is. I tried to zip the surprise back up several times; all of them unsuccessfully, as you can see on the two other pictures. I finally had to invite the real expert — my grandson — to do it.

I recently posted my new favorite probability puzzle from the fall 2019 issue of Emissary, submitted by Peter Winkler.

Puzzle. Alice and Bob each have a biased coin that flips heads with probability 51% and 100 dollars to play with. The buzzer rings, and Alice and Bob begin flipping their coins once per minute and betting one dollar on each flip against the house. The bet is at even odds: each round, each of them either loses or wins a dollar. Alice always bets on heads, and poor Bob, always on tails. As it happens, however, both eventually go broke. Who is more likely to have gone broke first?
Follow-up question: They play the same game as above, but this time Alice and Bob are flipping the same coin (biased 51% toward heads). Again, assuming both eventually go broke, who is more likely to have lost their money first?

One might assume that Bob obviously got a bad deal. He will lose his money very fast. So the answer to both questions must be that Bob loses his money first. If you know me, you should realize that I wouldn’t have given you this puzzle if the answer was that intuitive. I love counter-intuitive puzzles.

Bob has a disadvantage, so he is guaranteed to lose eventually. Alice has an advantage, so she might lose, or she might not. If she goes broke, that means there should be more tails in the flips than if she doesn’t go broke. How does this influence the second scenario, in which they use the same coin? As we are expecting a lot of tails in the flips, the situation should be better for Bob as compared to the first scenario. Given that I posed this puzzle, one might decide that in the follow-up question Bob doesn’t go broke first. Is it a tie?

But, if Bob is the first to go broke in the first scenario, why would I include the first part of the puzzle at all? If you know me, you should wonder what makes the first question interesting. Or maybe, you know Peter Winkler, in which case you should also wonder the same thing.

I gave you enough meta information to guess the amazing counter-intuitive answers to these two questions: in the first scenario, they tie; and in the second scenario, Alice goes broke first with higher probability.

To prove that they tie in the first scenario, let me first define a switch on a sequence of coin flips. A switch changes each head into tails and vice versa. The switch creates a one-to-one correspondence between the sequences of flips where Bob goes broke with the sequences where Alice goes broke. Suppose p is the probability that Alice goes broke with a particular sequence a, and q is the probability that Bob goes broke with a `switched’ sequence b. Then p = rq, where r = (49/51)²⁰⁰. The reason is that sequence a has exactly 200 more tails than sequence b. The same ratio r works for any pair of switched sequences. Bob is guaranteed to go broke eventually. But to calculate the conditional probability of Alice going broke with sequence a, given that she does go broke, we need to divide the probability of the sequence a occurring by the probability that Alice goes broke. The resulting probability distribution on sequences of length n has to be the same as for Bob because it has to sum to one. If Alice goes broke, then the probability that she goes broke after n flips is the same as for Bob. That means they tie.

To answer the second question, we use the switch again. The switch creates a one-to-one correspondence between sequences of flips where Alice goes broke first and Bob second, and vice versa. The sequence for which Alice loses second has 200 more tails than the corresponding sequence where Bob loses second. Thus, in each pair of two switched sequences, the probability of the sequence where Alice loses second is equal to r times the probability of the sequence where Bob loses second. Thus, the probability of Alice winning is r times the probability of Bob winning, and r is a very small number.

Here is a classical puzzle I often give to my students.

Puzzle. The sultan has three red hats and two blue ones. He wants to test his three wizards, who know his hat collection. He asks them to close their eyes and puts a hat on each of their heads. After the wizards open their eyes, they see each other’s hats, but not their own. The sultan asks each of them to guess the color of their own hat, without communicating with each other. In this particular test, the sultan only puts red hats on the wizards’ heads. Sometime after the wizards open their eyes, one of them guesses his hat’s color. How did he guess?

Here is how my students explain the solution. If a wizard sees two blue hats, he immediately knows that his hat must be red. That means, if no one immediately announces their hat’s color, at least two of them are wearing red hats. In this case, if a wizard sees one red hat, he knows that his hat must also be red. So such a wizard can guess the color of his hat. If after some more time, no one announces their hat color, all the hats worn must be red.

After the students solve the problem, I run an evil experiment on them. I show the students my two blue and three red hats and ask three volunteers to close their eyes. Then, I put two red hats and one blue hat on their heads, and the blue hat goes on the fastest thinker in the group. I did this experiment many times. Half the time, the fastest thinker overestimates how fast the other students think and guesses, mistakenly, that s/he is wearing the red hat. Gotcha!

After the experiment, we discuss what is really going on in this puzzle. This is how I start my class on common knowledge.

Here is a famous matchstick puzzle based on the given picture.

Puzzle. Can you move three matchsticks to turn the fish around?

Here is my bonus puzzle.

Bonus Puzzle. Can you turn the fish by moving two matchsticks?