Top View [Puzzle]

If the first image below is a side view, and the second image is the front view (as viewed from the arrow). What’s the top view of this object?

top view

[Source: Rob Eastaway]

Advertisements

Counterfeit Coin [Puzzle]

There are 12 coins, one of which is a counterfeit. The false coin differs in weight from the true ones, but you don’t know whether it’s heavier or lighter. Find the counterfeit coin using three weighings in a pan balance.

[From Futility Closet]

Giant Jelly [Puzzle]

click to embiggen

[Source: DataGenetics, Pic Courtesy: CREATTICA]

The Defective Doyle [Puzzle]

Shurl and Watts, at a base on Pluto, are in charge of distributing doyles to more distance outposts. Doyels are the size of peas, all identical, each weighing precisely 1 gram. They are indispensable in hyperspace propulsion systems.

Doyles come in cans of 100 doyles each, and shipments are made up of six cans at a time. The Pluto base has a sensitive spring scale capable of registering fractions of milligrams.

One day, a week after a shipment of doyles, a radio message came from the manufacturing company in Hong Kong, “Urgent. One can is filled with defective doyles, each with an excess weight of 1 milligram. Identify the can and destroy its doyles at once.”

“I suppose,” said Watts, “we’ll have to make six weighings, one doyle from each can.”

“Not so, my dear Watts,” said Shurl. “we can identify the can of defectives with just one weighing.” [And then he goes on to explain how this can be achieved using a single weighing.]

“How absurdly simple!” exclaimed Watts, while Shurl shrugged.

A month later, after the next shipment, another message arrived: “Any of the six cans, perhaps all of them, may be full of defective doyles, each 1 milligram overweight. Identify and destroy all defective doyles.”

“This time,” said Watts, “I suppose we’ll have to weight separately a doyle from each can.”

Shurl put his fingertips together and gazed at a picture of Isaac Asimov on the wall. “A capital problem, Watts. No, I think we can still do it in just one weighing.”

What algorithm does Shurl have in mind?

[From Mathematical Puzzle Tales by Martin Gardner]

PS: The solution of the first weighing problem (one defective can) is actually provided in the original text of this puzzle. I’ve removed it for those who are not familiar with the solution and want to give it a shot.

Two Prizes [Puzzle]

Suppose I offer you two prizes: prize A and prize B. You are to make a statement – any statement you like.

If the statement is clearly true, I will give you a prize. You will win either A or B, I am not saying which one.

And if your statement is false, you won’t get any prize.

It’s clear from this that you want to make a statement that is clearly true, because otherwise you won’t win any prize. You can say something like “One plus one equals two.” This is clearly true, and you will win either A or B.

However, let’s say you really would like to win prize A. The question is: what statement can you make that will ensure that you will win prize A?

[From Forever Undecided: A Puzzle Guide to Gödel]

Wise Men with Hats [Puzzles]

The first one is an old classic hat puzzle; I’ve put it here as a warm-up for the second one which is a tad more challenging.

Puzzle #1 Three wise men are told to stand in a straight line, one in front of the other. A hat is put on each of their heads. They are told that each of these hats was selected from a group of five hats: two black hats and three white hats. The first man, standing at the front of the line, can’t see either of the men behind him or their hats. The second man, in the middle, can see only the first man and his hat. The last man, at the rear, can see both other men and their hats.

None of the men can see the hat on his own head. They are asked to deduce its color. Some time goes by as the wise men ponder the puzzle in silence. Finally the first one, at the front of the line, makes an announcement: “My hat is white.”

He is correct. How did he come to this conclusion?

Puzzle #2 One hundred persons will be lined up single file, facing north. Each person will be assigned either a red hat or a blue hat. No one can see the color of his or her own hat. However, each person is able to see the color of the hat worn by every person in front of him or her. That is, for example, the last person in line can see the color of the hat on 99 persons in front of him or her; and the first person, who is at the front of the line, cannot see the color of any hat.

Beginning with the last person in line, and then moving to the 99th person, the 98th, etc., each will be asked to name the color of his or her own hat. If the color is correctly named, the person lives; if incorrectly named, the person is shot dead on the spot. Everyone in line is able to hear every response as well as hear the gunshot; also, everyone in line is able to remember all that needs to be remembered and is able to compute all that needs to be computed.

Before being lined up, the 100 persons are allowed to discuss strategy, with an eye toward developing a plan that will allow as many of them as possible to name the correct color of his or her own hat (and thus survive). They know all of the preceding information in this problem. Once lined up, each person is allowed only to say “Red” or “Blue” when his or her turn arrives, beginning with the last person in line.

Your assignment: Develop a plan that allows as many people as possible to survive. [Source: TienrneyLab ]

I’ll provide answers in the Comments section next week.

The Hardest Logical Puzzle Ever

The original version of this puzzle was published in What Is the Name of This Book? written by mathematician and logician Raymond Smullyan:

There are three guardians, A, B and C. Their names are Knight, Knave and Chaos. Knight always speaks truly, Knave always lies. Chaos tossed a coin this morning to decide whether today he would behave like Knight or like Knave.

Your task is simple: ask three yes-no questions, and determine which is Knight, which is Knave, and which is Chaos.

There is, alas, a complication: the guardians understand English but will answer in the local language, in which “Da” means yes and “Ja” means no. Or possibly “Ja” means yes and “Da” means no – you cannot remember. [source]

Note that the three guardians know each others’ identities (but they may not know whether Chaos has decided – based on his coin flip in the morning – to speak truth or lie.)

Also, it could be that some guardian gets asked more than one question (and hence some guardian is not asked any question at all.)

I have posted a (big) hint in the comment section.

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]

The Monty Hall Paradox

During one of my Management Science classes at the university few weeks ago, our professor introduced the Monty Hall problem to the class and asked everyone what they think the right answer was. Since I was familiar with this problem, I asked him not to count my vote. But majority of the students got their answers wrong – which was obvious because otherwise this problem wouldn’t have been called a veridical paradox!

Here’s the statement of the famous Monty Hall problem (source):

Suppose you’re on a game show, and you’re given the choice of three doors. Behind one door is a car, behind the others, goats. You pick a door, say #1, and the host, who knows what’s behind the doors, opens another door, say #3, which has a goat. He says to you, “Do you want to [switch and] pick door #2?” Is it to your advantage to switch your choice of doors?

Please think about this before reading further: should you switch or stay with your initial choice? Needless to say, you win if you pick the door that has a car behind it. There are no tricks or loopholes here, it has a purely logical – and alternatively, a probabilistic – solution.

***

Most people think that after the host opens a door (revealing a goat behind it), both of the remaining doors have equal chances (50/50) of having a car. Hence, it doesn’t matter if you switch or not, your chances of winning remain the same.

But the correct answer is – and this might surprise you if you’ve never heard of this problem before – you should switch. Switching will actually increase your chances from 1/3 to 2/3.

***

The simplest explanation (IMO) is: Let’s say you pick door A. The probability of having a car behind A is 1/3. Hence, the probability of not having car behind A is 2/3. Which also means that the probability of having a car in the other two doors combined – B and C – is 2/3. Now, the host, by exposing a goat behind one of those two doors, eliminates that door – let’s say B. So the probability of having a car behind the remaining door C is 2/3.

Hence, if you don’t switch, your probability of winning remains the same (1/3). But if you switch your probability of winning increases (2/3).

This wonderfully counter-intuitive answer was challenged by many intellectuals and mathematicians including Ph.D.’s when it was first published during the early 90’s, and it’s considered to be one of the best mathematical brain teasers. If you’re not convinced with the answer there’s a Wikipedia page (link) for you. And if that’s not enough, there’s an entire book written about it: The Monty Hall Problem: The Remarkable Story of Math’s Most Contentious Brain Teaser (which I haven’t read yet.)

***

Addendum: There’s an interesting variant of this problem called Monty Fall or Ignorant Monty Problem (PDF link):

In this variant, once you have selected one of the three doors, the host slips on a banana peel and accidentally pushes open another door, which just happens not to contain the car. Now what are the probabilities that you will win the car if you stick with your original selection, versus if you switch to the  remaining door?

The answer to this is: your probability of winning is the same (50/50) whether you stick or switch.

*

If you liked this puzzle, you might also enjoy some of my older posts: The Blue-eyed Islander Puzzle, Impatient IntelligencePetals Around the Rose, A Mathematical Conundrum.

Enter your email address to subscribe to this blog and receive notifications of new posts by email.

Join 66 other followers

On Twitter

Categories