Puzzles in Fermat’s Room

I watched Fermat’s Room — a mathematical thriller in Spanish language — few weeks ago. Although I did enjoy watching this movie, I am hesitant to recommend it due to sloppy direction (too pretentious, IMO) and average acting performances. But the premise on which the movie is based was quite intriguing: Four mathematicians are invited by an anonymous stranger (Fermat) to solve a great mathematical enigma. But soon after they convene, they get trapped in the room and must solve puzzles in order to survive. The room, with moving walls, begins to shrink as soon as they receive the puzzle from the host and it won’t stop contracting until they solve the puzzle.

Disappointingly, the puzzles were quite basic – most of them are classic riddles that I was already familiar with. I’ve listed some of them below:

• Using a 4 minute hourglass and a 7 minute hourglass how would you measure exactly 9 minutes?
• You have three opaque boxes. One box contains chocolate candies, another contains mint candies, and the last box contains a mixture of chocolate and mint. The boxes are labeled Chocolate, Mint and Mixed. None of the boxes are labeled correctly. You can take one candy out of each box (without looking directly into the box) and see what you get. What is the minimum number of boxes you have to open (and take one candy out) to assign correct labels to all boxes?
• There are three switches outside a room. One of them controls a lightbulb that’s inside the room, while the other two are not connected to anything. You can turn the switches ‘on’ or ‘off’ and also enter the room to see the lightbulb. What is the fewest number of times you will need to enter the room to determine which switch is connected to the bulb? (You can’t see if the lightbulb is ‘on’ or ‘off’ from the outside. And all switches are in the ‘off’ position when you start.)
• A mother is 21 years older than her son. In exactly 6 years, the son will be one-fifth his mother’s age. The question is: what is the father doing right now?

I think the following is probably the best one in the lot:

• A student asks his professor: “What are the ages of your three children?” The professor replies: “If you multiply their ages you get 36, and if you add them you get my house number.” “I know your house number, but that’s not enough information!” says the student. To that the professor answered: “True. The oldest lives upstairs.” What are the ages of the three children?

And finally, a classic Martin Gardner riddle: What is special about the number 8,549,176,320?

[Picture Courtesy: IFC Films]

The Mystery of Counterfeit Coins

I came across this very interesting coin weighing puzzle on Concrete Nonsense blog (with a hat tip to Tanya Khovanova). It might sound familiar but I can assure you that it’s not that one! The solution involves the concept of zero-knowledge proof.

First, let’s start with a warm-up version, shall we?

You present 100 identical coins to a judge, who knows that among them are either one or two fake coins. All the real coins weigh the same and all the fake coins weigh the same, but the fake coins are lighter than the real ones.

You yourself know that there are exactly two fake coins and you know which ones they are. Can you use a balance scale to convince the judge that there are exactly two fake coins without revealing any information about any particular coin?

This one is quite easy to solve. You can divide the coins into two equal groups. And when the judge sees that both groups balance on the scale (i.e. have equal weight), she is convinced that there can’t be one fake coin. Which means that there are two fake coins.

Note that the this solution doesn’t reveal any information about any particular coin (i.e. the judge doesn’t know if any particular coin is fake or real – all coins are equally likely to be fake or real). However, in addition to proving that there are two fake coins, some additional information is also passed on to the judge.

Initially, if the judge randomly picked two coins from the pile, the probability that she picked the fake coins is 1 out of 4950. (The probability that the first coin is fake is 2/100 since initially there are two fake coins. And the probability that the second coin that the judge picked is also fake is 1/99 since there is one fake coin left in the remaining 99 coins. By multiplying both probabilities, you get the combined probability of both coins being fake. Alternatively, you can get this number by doing ‘2 choose 100’ — which equals 4950.)

After you divide the coins into two groups and show that there is one fake coin in each one, the judge can now pick two fake coins with a probability of 1/2500. (The probability of picking a fake coin from each of the two groups is 1/50. Hence, overall probability of picking two fake coins is 1/50 multiplied with 1/50 = 1/2500.)

This shows that the solution is not a zero-knowledge proof. The judge has greater chances of picking the fake coins after your illustration – the probability increased from 1/4950 to 1/2500.

Now keep that (concept of zero-knowledge proof) in mind and let’s move on to the next level:

A judge is presented with 100 coins that look the same, knowing that there are two or three fake coins among them. All the real coins weigh the same and all the fake coins weigh the same, but the fake coins are lighter than the real.

You yourself know that there are exactly three fake coins and you know which ones they are. Can you use a balance scale to convince the judge that there are exactly three fake coins, without revealing any information about any particular coin?

If you’re thinking that this one is also easy like the previous one, think again!

Please don’t read further if you want to try to solve this puzzle yourself.

For example, dividing the coins into three groups with 33 coins in each and leaving one coin aside, and then showing that those three groups weigh equal does prove that there are three fake coins BUT what about the coin that you put aside? The judge is certain now that the coin that was put aside is real. That’s a deal breaker. Remember, you can’t reveal information about any particular coin.

***

Here’s one solution that I initially thought of:

Split the coins into two groups with 50 coins in each. Keep two fake coins in group A and one in group B. Group A will weigh lighter on the scale. Now let’s say the judge thinks that there are only two fake coins. In that case, she is convinced that both fake coins are in group A, because A weighed lighter.

To prove the judge wrong, all you needs to show is that group B also contains one fake coin.  Which can be easily shown by dividing group B in half – let’s call them B1 and B2 (25 coins in each). Upon balancing B1 and B2, and seeing they don’t balance equally, it’s proven that group B also contains one fake coin. Hence, the judge’s assumption (that there are only two fake coins) is wrong. Which obviously  means that there must be three fake coins.

But the problem with this solution is that it’s not a zero-knowledge proof.

***

Here’s another solution by Mary from the comment section of Tanya Khovanova’s blog post:

Make three groups A, B and C, with 32 coins in each one. And put four coins aside for now. Three consecutive weighing will show the equality of weights among A, B and C. Then swap those four coins that were initially set aside with four coins from A, B and C. And three more consecutive weighing can demonstrate that A, B and C weighs the same – which proves that each group contains one fake coin (either in the first round or in the second.)

Further Explanation: Let’s say you put aside three fake coins – let’s say w,x,y – and a real one – z. Hence, all three groups contain all real coins. Now after demonstrating that A, B and C weighs equal, you can swap w with a real coin from A, x with a real coin from B, and y and z with two real coins from C. After the swap, the A, B and C will still balance because there is exactly one fake coin in each group. Another possibility is that you can put aside four real coins initially. In that case, all three groups will still weigh equally before the swap, as well as after the swap – you can swap in such a way that each of the three groups end up with exactly one fake coin or replace all fake coins with a real one so that A, B and C contain no fake coin.]

Note that in any case, the judge has no way of knowing whether the initial four coins were all real or three fake plus one real.

Do you think this is a zero-knowledge proof? (I think it is.)

Are there any other solutions that you can think of?

***

P. S. If you liked that concept of zero-knowledge proof, here’s another interesting problem: [The Millionaire Problem] Alice and Bob are two millionaires who want to find out who is richer without revealing the precise amount of their wealth. [Solution]

A Mathamatical Conundrum

Imagine a rope wrapped around the equator of the earth. For simplicity, let’s assume that the earth is perfectly spherical. Now imagine that we increase the length of that rope by 1 meter. This will create some gap between the circle made by the extended rope and the surface of the earth. Let’s say the distance (between the extended rope and the surface of the earth) is equal to L. Now repeat the same experiment with a golf ball. Let’s say the distance (between the extended rope and the surface of the golf ball) is equal to l. How different would you say L and l are?

Would you believe me if I told you that L and l are identical?

I didn’t believe this at first either. Here’s a simple mathematical proof.

The length of the original rope (before it was extended) is equal to the circumference of the object (i.e. earth or golf ball). Thus,

Length of the rope before if was extended, C = 2πr (where r is the radius of the object)

Now, we add 1 meter to the length of the original rope.

So length of the extended rope, (C + 1) = 2πR (where R is the radius of the annulus)

We’re interested in the length of the gap between the annulus and the surface of the object, i.e. R – r. (Refer to the picture on the left.)

The two formulas above can also be expressed as:

r = C / 2π, and

R = (C + 1) / 2π

Thus, R – r = {(C+1) / 2π} – {C/2π} = 1/ 2π

Which is a constant! Hence, the gap (R – r) does not depend on the size of the object under consideration. No matter how big or small the object is (be it the earth, golf ball, or the universe), the length of the gap created by an equally extended rope is always the same.

Isn’t that mind boggling?

Hat Tip and Picture Courtesy: Math~Blog.

Originally from the book Impossible?: Surprising Solutions to Counterintuitive Conundrums.