Fog Creek Software
Discussion Board




The answer to "Painfully Easy" is false--but why?

"Pop quiz, hotshot," the Villain said, "I've just flipped two coins. At least one of them is showing heads.

"If you can't tell me, given what I've told you, the chances that the other coin shows heads also, I'm going to KILL this cute, defenseless kitten. "

"Oh, that's easy," said the Hero, "I read it on Techinterview.org. There's a one in three chance that the other coin shows heads."

"WRONG! But just to show I am a fair Villain, I'm giving you and the kitten one more chance." The Villian pickes up two coins from behind his curtain and flipped them, letting them land outside our protagonist's view. "At least one of these coins shows tails. With the life of this poor little kitten at stake: Can you tell me the chances that both coins show tails? CAN YOU?"

Ham Fisted
Monday, November 10, 2003

Don't you think this horse has been flogged enough already?

Paul Viney
Tuesday, November 11, 2003

Given that no one has correctly answered the problem, and the posted solution is false, no.

Hint: the answer is not 50%, either.

Ham Fisted
Tuesday, November 11, 2003

I really think 1 in 3 is right. There are 4 outcomes:

HH
HT
TH
TT

And we've been told that HH is not correct. TT is thus 1 of 3 remaining outcomes, each equally likely.

Joe Jewell
Wednesday, November 12, 2003

Why are each equally likely?

Ham Fisted
Wednesday, November 12, 2003

The rules of probability. An individual coin is as likely to be heads as it is tails. Thus each outcome has an equal probability of 1/4. Regardless of whether or not we through out some results, can you tell me why any of those outcomes should be less likely than another?

You can run an experiment with this if you like. Take two coins, flip them, throw out all the results in which both are heads... 1/3 of the remaining results will be two tails.

I did a simulation of this using a random number generator, 1 for heads and 0 for tails in an Excel file, which you can download and run yourself, if you like, at http://www.joejewell.com/coinflip.xls

The results for a run, after 2000 pairs of flips:

Two Heads: 493
Two Tails:    520
HT/TH:        987

Empirically, it's fairly easy to see that after throwing out all of the two heads results, the two tails results comprise 1/3 of remaining possibilities.

Joe Jewell
Wednesday, November 12, 2003

Why would you throw out only the two heads results?

Ham Fisted
Wednesday, November 12, 2003

From the problem statement: "At least one of these coins shows tails."

I am interpreting that to mean: "Either one coin or two coins are showing tails, but there is no chance that neither coin is showing tails (i.e. no chance that bothcoins are showing heads)."

Unless there is some "trick" to this in the problem statement itself, or he's using double-headed coins or something, I fail to see how it can be any other way.

I would be interested in reading your explanation as to how the odds are NOT 1/3, and as to what you calculate the odds to actually be. Please do post it!

Joe Jewell
Wednesday, November 12, 2003

I'll hold off a little while longer.

There is an important hint up above. On the first flip the villain claims "At least one is heads," while on the second he claims "At least one is tails."

Ham Fisted
Wednesday, November 12, 2003

If the answer depends upon the fact that he phrases the question differently, why is the initial answer of 1/3 wrong--before we even hear of the second (independent!!) set of flips?

If this is some trick question with the language supporting a claim that the two sets of flips are not independent... well, that's pretty lame.

I've devoted too much energy to explaining this already--feel free to Google to find that this is not an uncommon problem (at least disregarding any "trick" you have thrown in with the wording), and it has been treated (correctly, as it originally was here on Techinterview) many times in the past. An example follows:

http://www.economics.pomona.edu/GarySmith/Econ57Smith/Econ57final98.HTML

http://www.economics.pomona.edu/GarySmith/Econ57Smith/Econ57final98ans.HTML

Joe Jewell
Wednesday, November 12, 2003

Of course both flips are independent. And both coins are fair, and the villain always makes true statements.

The reasoning given in your links is correct. It does not answer the question asked here:

http://www.techinterview.org/Puzzles/fog0000000028.html

I'll even supply the answer to my villain's question. The answer is "no."

Ham Fisted
Wednesday, November 12, 2003

(well except for the first threat involving the kitten. That was a false statement.)

Ham Fisted
Wednesday, November 12, 2003

I've personally seem many discussions of 'Painfully Easy' on this site alone. The same conclusion was reached each time. Assuming that 'one of the coins is heads' means 'at least one of the coins is heads', and there are no tricks in the working, then the chance of the other (i.e. both) coins being heads is 1/3. If anyone thinks differently please post your thoughts now.

David Clayworth
Friday, November 14, 2003

no tricks in the working -> no tricks in the wording

David Clayworth
Friday, November 14, 2003

David, please compare the problem statement of "painfully easy" with the problem statement that Joe linked to. There is a difference and it is no "trick of wording."

It is fairly obvious. I would not be posing it in the form of a question otherwise.

Have you read Monty Hall's objection to the problem named after him?

http://www.wiskit.com/marilyn/gameshow.html
(see the section "Monty Hall's Reaction")

Ham Fisted
Friday, November 14, 2003

Sorry, Ham, not obvious to me.

David Clayworth
Friday, November 14, 2003

Martin Gardner wrote regarding the second-sibling paradox.

I quote from his October 1959 column in Scientific American:

"Another example of ambiguity arising from a failure to specify the randomizing procedure appeared in this department last May. Readers were told that Mr. Smith had two children, at least one of whom was a boy, and were asked to calculate the probability that both were boys. Many readers correctly pointed out that the answer depends on the procedure by which the information "at least one is a boy" is obtained. If from all families with two children, at least one of whom is a boy, a family is chosen at random, then the answer is 1/3. But there is another procedure that leads to exactly the same statement of the problem. From families with two children, one family is selected at random. If both children are boys, the informant says "at least one is a boy." If both are girls, he says "at least one is a girl." And if both sexes are represented, he picks a child at random and says "at least one is a ..." naming the child picked. When this procedure is followed, the probability that both children are of the same sex is clearly 1/2. (This is easy to see because the informant makes a statement in each of the four cases -- BB, BG, GB, GG -- and in half of these case both children are of the same sex.) That the best of mathematicians can overlook such ambiguities is indicated by the fact that this problem, in unanswerable form, appeared in one of the best of recent college textbooks on modern mathematics."

Does that help?

Ham Fisted
Friday, November 14, 2003

The correct answer then has to be that you can't tell. Depending on the procedure used, the answer could be 1/3, 1/2 or 1. If the villian acts randomly, then 1/3 is the correct answer. If the villian follows a preset pattern, then other answers are possible.
e.g. strategy
HH -> at least one is heads
TT,HT,TH -> at least one is tails

if we hear 'at least one is heads' then the chance of the other being heads is 100%.

So it wasn't a well defined question. *Shrug*

Paul Viney
Monday, November 17, 2003

Right. It's either 1/3 or poorly-asked.

Joe Jewell
Monday, November 17, 2003

I don't think you can form a coherent definition of what it means for the villain to "act randomly." If you mean picking one of the coins to reveal at random, then it's 1/2, unfortunately.

Any sort of job that requires you to work with conditional probabilities--any job that might be justified in asking you "painfully easy" in the interview--is definitely going to require you to spot sources of bias which might or might not be explicit. This is the point of the exercise.

Since y'all were too caught up in defending the "right answer" to realize that that answer was completely unfounded, perhaps you might be able to recommend some better hints. What would have pointed you in the right direction here?

Ham Fisted
Tuesday, November 18, 2003

English is not my mother tongue, so I will try my best to explain my point of view.

By the villain to "act randomly," it means that he would always state the same fact and poses the same question, no matter what the results of the flipping were, saved having flipped two tails, because then he would have to lie to say at least one is heads.

If by chance he flips two tails, then as someone has already mentioned, it is assumed that the villain would discard the results and flip again, until he get at least one of the coins to be heads, or he would simply not pose the question.

This problem is not unanswerable, as long as one is willing to make certain assumptions to simplify the problem.  Otherwise ANY conditional probabilities problem would be unanswerable, or is that your point exactly?

For example, consider this simple problem:
A fair coin is flipped twice, the first time it came up heads, what is the probability that the second flip was heads also?  First, one has to assume that a fair coin means chance of getting heads is 1/2 and chance of getting tails is 1/2.  (To some person in a remote country, fair coin may mean heads 1/4 and tails 3/4, who knows.)  One has to assume the coin does not land on its edge instead of its face, or that it was flipped so hard its speed exceeded escape velocity of the earth and never land, or that it was caught and swallowed by a bird while in mid air...  The possibilities are endless.

More importantly, one has to assume that this question is not posed ONLY when the second flip came out heads, because if that were true, then the chance of second flip being heads is 100%.

After all the assumptions to ensure that the problem has no accidents and is unbiased, one came to the conclusion that the chance of the second flip being heads is 1/2 because it is independent of the first flip.

This process of making assumptions is similar to when one is deriving the Ideal Gas Law; one has to make several assumptions to make the situation ideal, to simplify the problem.  For example, imaging having the problem of calculating the velocity of a lead ball dropped from the Leaning Tower Pisa after t seconds.  One would probably assume the rotation of the earth has insignificant effect on the velocity of the lead ball, even though it does affect it, perhaps even air resistance could be ignored, if one is not so meticulous.

Finally, thanks to Ham for bringing up this topic and especially the quote from Martin Gardner.  It was insightful.

Thanks for reading my humble opinion.

JHY
Wednesday, November 19, 2003

You should have also said that both coins were lying flat and not on their side (however remote and improbable that was).

Tom Williams
Wednesday, January 07, 2004

I'm surprised that Ham Fisted says that both coins are fair. Although this assumption seems reasonable, the first question and answer sequence indicates otherwise. If the coins are fair, then the first answer must be correct.

Given that the first answer is incorrect, it opens the door to assume that the coins are not fair. One can write down the combinations of "tricky" coins (also the two coins/four faces must consist of at least one head and one tail), and see that the answer to "CAN YOU TELL the chance of ... ? " is no.

May Bee
Saturday, January 10, 2004

Ham Fisted is saying that the coins are fair, but the villain is not.  Hence (s)he is the villain, I guess.

How do we know this?  If we go back to the very first post in this thread, we can see that:

First flips: the villain says, "At least one of them is showing heads," and asks for "the chances that the other coin shows heads also."

Second flips: the villain says, "At least one of these coins shows tails," and asks for "the chances that both coins show tails."

Why is this important?  It is important because we do not know under what circumstances the villain will say "At least one of these coins shows heads" and we do not know under what circumstances the villain will say "At least one of these coins shows tails."  If you have no idea what this paragraph just said, don't worry, look at the example below, which is modified from Ham's post.

To show how 1/3 could be the wrong answer, consider this:
The villain flips two coins.
If the result is two heads(HH), (s)he says "At least one of these coins shows heads."
If the result is two tails(TT), (s)he says "At least one of these coins shows tails."
If the result is one head one tail(HT or TH), (s)he randomly chooses heads or tails and says "At least one of these coins shows [heads or tails, whichever (s)he randomly chose]."
In this case, when the villain asks for the chance that both coins show heads or both show tails, the answer is 1/2, not 1/3.

Ham also stated that the answer is not 1/2, so what's up?
Again, this is because we do not know when the villain will say "At least one of these coins shows heads" and when the villain will say "At least one of these coins shows tails."  According to Ham, we cannot assume that the villain will act in any particular pattern, including the pattern given in the above example, because the villain did not give a pattern for the hero to work on and the villain did not say we can assume that he acts according to any rule.

Of course, if we assume that the villain says "At least one of these coins shows heads" when he flips HH, TH, or HT, then the chance of both coins showing heads is obviously 1/3.  However, because we do not know when the villain will say what and we cannot assume anything at all, the answer to the villain's question is we do not know what the chance of both coins showing heads are.  So the villain posed an unanswerable question, and Ham posted an unsolvable problem.

Basically, there is nothing the hero can do, and the cute, defenseless kitten dies!

The main point of this thread is to show that we cannot assume anything.  Remember, assume is ass+u+me, to assume is to "ass u and me".

JHY
Monday, January 12, 2004

Are you people nuts?
If I have a coin that is heads, then I flip another coin, the odds that they will both be heads is 1 out of 2
the odds that they both wont be heads is....1 out of 2.

Niether coin has the knowledge of the other coin.
Since you know one of the coins, there is only two remaining choices: a head or a tail.

Now, if you didn'l know what one of the coice where, and where asked "I fliped 2 coins, One is tails, what are the odds that THEY ARE BOTH TAILS That woulds be 1 out of four.:
HT
HH
TH
TT

Either the question is asked in such a way that the coins are 'one unit' or two seporit 'units'

the original question:
what is the chance that the other coin also came up heads?
it is 1 out of 2 becasue there are only 2 remaining possibilitis. a head, or a tail.

Unless they want to take i the probability of the edge, in which case the poster shoud state that, and then run far, far, away.

ADA
Wednesday, January 21, 2004

ADA,

If the villian says "At least one of the coins is tails" then there are only THREE possibilities:

TT
TH
HT

HH is not a possibility, so it is not counted, making the probability 1/3, not 1/4.  Also, JHY, it does not matter what pattern or lack of pattern the villian uses to when (s)he gives the hero his/her clue because (as long as the villian is honest) what the villian says limits the possibilities of what combination of coins has been flipped.  So, if the villian says that at least one of the coins shows tails, then the probability of HH being the combination is 0.  We all know that the sum of the probabilities of all the options should equal 1, so with one option whose probability is known to be 0, and three options whose probabilities are known to be equal, there is only one solution, 1/3.

If anyone sees any flaws with my reasoning, let me know.

Tyler
Tuesday, February 03, 2004

Tyler,

The pattern the villain uses does matter. For instance, the villain could be using the rule "say 'one of these coins is heads' if it is true, otherwise say 'one of these coins is tails.'"

Upon hearing 'one of these coins is tails,' if you knew the rule, you would immediately conclude that the other coin is tails and be 100% certain--otherwise the villain would have said 'one of these coins is heads.'

Or the villain could be using the pattern 'pick one of the coins at random, and say what it is." In this case we can enumerate the possibilities:

HH ->Villain picks the first coin and says "one is heads," and the other is heads.
HH ->Villain picks the second coin and says "one is heads," and the other is heads.
HT ->Villain picks the first coin and says "one is heads," and the other is tails.
HT ->Villain picks the second coin and says "one is tails," and the other is heads.
TH ->Villain picks the first coin and says "one is tails," and the other is heads.
TH ->Villain picks the second coin and says "one is heads." and the other is tails.
TT ->Villain picks the first coin and says "one is tails," and the other is tails.
TT ->Villain picks the second coin and says "one is tails." and the other is tails.

If we know the villain is using this rule, we look at all the possibilities where the villain said "one is tails," and we find that half of them have the other coins being tails too.

Ham Fisted
Wednesday, February 04, 2004

*  Recent Topics

*  Fog Creek Home