Hacker News Reader

Comment by SMackinnon | Hacker News Reader

Spoiler:

Bob always chooses the same as his flip, Alice always chooses the opposite of her flip.

  B A
  H H - Bob chooses heads, Win
  H T - Alice chooses heads, Win
  T H - Alice chooses tails, Win
  T T - Bob chooses tails, Win

View on HN

It helped me to think of it this way: Alice is guessing that their coins are different (one possibility) and Bob is guessing that their coins are the same (the other possibility), so from either direction they are covered.

Thanks. I think this was the reply that actually helped me understand this.

Yeah it still took a minute. The way I realised it was Bob is covering them for the same flips, so if he flips H, he covers if Alice flips a H too. But if she flips a T, Bob is no longer covering her, but she knows when Bob isn't covering her, if she guesses for the opposite, she'll cover them. 100%.

The next level is: Eve joins the game, and the coin gets another side.

And to show how to logically work out this answer (same spoiler warning applies):

I started with a truth table as well. It's pretty easy to show that if Alice (or without loss of generality Bob) uses a fixed "always guess H" or "always guess T" strategy, that wins in two cases, but in the other two cases Bob has no way to reliably win. For instance, if Alice always guesses H, then two cases become wins:

    A B
    H H W
    H T ?
    T H W
    T T ?

But in the other two cases, Bob has the same T each time, so he doesn't have enough information to distinguish those cases, and thus he can't reliably guess correctly.

So Alice needs to use a strategy that depends on her flip. There are only two such strategies that don't trivially reduce to a constant guess: guess what you flip or guess the opposite of what you flip. Going with the former, where Alice guesses what she flips:

    A B
    H H W
    H T ?
    T H ?
    T T W

From this, clearly if Bob guesses the opposite of what he flips, someone wins in all four cases.

The only other solution is to reverse the two: Alice guesses the opposite of what she flips, and Bob guesses what he flips.

This seems like a nice warm-up for other protocols that depend on agreed-upon strategy but not a secure channel for direct communication, such as Diffie Hellman or the Socialist Millionare Problem.

Another way to look at it is either they can both get the same result or they can get different results, if it's the same then Bob will be correct, if it's different then Alice will be correct

Yep, its a nice problem. Reformulating it such that there are two possibilites (the coins are either different or the same) rather than four (permutations of two coins) is the way to solve the problem.

I was going to post a hint rather than the solution, but you beat me to the punch.

I liked showing the four possibilities and thinking about it in the way that one of them has to be responsible for winning in each case.

Yeah, added a little spoiler tag.

Easier explenation There are 16 possibilities

   A Alice's coin
   Ac Alice's choice
   B  Ben's coin
   Bc Ben's choice

They win if A's and Bc's OR B's and Ac's are the same

   A Ac B Bc
   T T  T T  W  
   H T  T T  W
   T H  T T  W
   H H  T T  L
   T T  H T  W
   H T  H T  L
   T H  H T  W
   H H  H T  W
   T T  T H  W
   H T  T H  W
   T H  T H  L
   H H  T H  W
   T T  H H  L
   H T  H H  W
   T H  H H  W
   H H  H H  W

It's easier to check for when they are losing:

   A Ac B Bc
   H H  T T |they both stick to their choices
   H T  H T |they both flip
   T H  T H |they both flip
   T T  H H |they stick

So the winning strategy is if one of them sticks to his choice and other flips it's choice.

Wow, that is way better explanation to check on where they may lose. Thanks!

My experience arriving at this solution made me a bit curious as to how others solved it. Was there reasoning involved before you arrived at a strategy and verified it, or did the strategy just come to you? Did you try multiple strategies, and if so, was there a method to generating/iterating on them, or were they just coming to you and you tried them?

Brainteasers tend to follow a particular pattern. The amount of information the various Alices and Bobs and Charlies have seems at first glance to obviously be inadequate to the task they're given. Then a closer examination reveals that there's some sublte extra scrap of information, and you can generally assume than that the answer is to use that to trace out the possibilities to find the actual answer.

So knowing that, I just looked for what extra, non-obvious piece of information A and B had. It seems impossible to guess what the results of a coin-flip are in another room. But the players also know the result of their own flip, and so basing a strategy on that extra info is certainly going to be the answer. From there, since there are so few combinations of such a strategy, getting the right answer is pretty trivial.

I like this brain teaser (and I suspect the reason that Felton likes it as well) because it shows this general pattern for brain teasers very clearly. The "extra" piece of information is pretty obvious with a moments thought. And once you have it, the number of possible strategies using it is small enough that you can see the correct one quickly.

A lot of other brain teasers require a lot of pen and paper work even after you've guessed the "trick" in order to work through all the possiblities. So this is sort of a nice, boiled down "essence du brainteaser".

One of the main challenges, however, seems like it would rear its head as soon as you leave the confines of a defined brain teaser, where you know for sure that there is a "trick" even if you can't see it, and real world situations such as in programming, where you don't yet know if the specific problem is solvable at all.

I noticed something similar when I was studying math: Exercises of the variety "Prove x" or "Disprove x" were much more than twice as easy as exercises of the variety "Prove or disprove x".

I made a table of all four possibilities:

    A_coin  B_coin  A_guess  B_guess
    H       H       ?        ?
    H       T       ?        ?
    T       H       ?        ?
    T       T       ?        ?

Then I tried to fill in the guesses, given that A_guess has to be based on B_coin and vice-versa. After making Alice guess the same as her coin flip, since that's a simple thing to try first, it was clear that Bob had to guess the opposite of his coin flip for each row to have exactly one correct match.

My thought process: It seemed obvious that fixed-guess strategies couldn't work, both from the proof in the article and from intuition that the inverse of your fixed guesses will always represent a failure case.

If a fixed strategy can't work, then the guesses must be decided dynamically. At the time the guess is made, only one bit of information (their own flip) is available to each participant, so each guess has to be based on that. With one bit of information, you could only choose two things: do the same, or do the inverse. The correct, asymmetric pair of strategies popped into my head at this point, and a quick truth table check confirmed it.

Exact same here. Thanks for analysing this though, because i had trouble rethinking my own process. I more had the feeling to try things a bit randomly and eliminate ranges of similar choices. But in fact it wasn't random, it did follow the exact train of thoughts you described, in that order.

I just thought about what strategies they could actually take without being able to communicate information or use the outcome of the others flip as an input to their decision. There are only a few things you could do- guess either heads or tails every time, guess your roll, or guess the opposite.

Then I realized if one took the "guess same" strategy and the other took the "guess opposite" strategy that would cover the bases.

As a team, they get two guesses. So those two guesses have to cover the space of possibilities, and a guess has to be of a form such that seeing one's own coin implies the guessed value of the hidden coin. (So, "Bob has heads" is not a valid strategy guess. A strategy guess has to describe the state of both coins, so each perskon's strategy guess cannot include two pairs of the form "mine=X, other=H " and also "mine=X, other=T".

This seems a bit awkward, but information theory "guessing" is called "error correction", and parity-checking is the simplest and by far most common strategy. (Advanced algorithms are fancier multidimensional parity computations) So, their two guesses are "same" and "different" (aka parity 0 and 1). A and B each are allocated one of the two strategyGuesses, and translate observedCoin+strategyGuess=hiddenCoinGuess

Purely mechanically. Just writing down the problem statement we get:

    \exists f,g: \forall a,b: (f(b)=a) | (g(a)=b)

where f,g are the guesses and a,b are the flips. Each guess is a function of the information available to the respective player -- the outcome of his own coin flip. There's only 4 unary boolean functions:

    f,g \in {true,false,id,not}

The constant functions are out and order doesn't matter, so we're left with

    {(id,not),(id,id),(not,not)}

Here I just tried (id,not) first, but 3 choices are easy to check exhaustively.

I followed almost exactly the same logic as sgreben, but without the notation.

First, I assume there is an answer, and at least a moderately interesting answer.

There is no way they can communicate information post-flip, therefore they must be able to cover every possible option.

They cannot cover every possible option by deciding what to write in advance, therefore they must decide what to write based on the flip. In fact, they must both decide based on the flip or they will not gain anything.

If you decide what to write based on the flip, there are only two real choices per player: write the same as what you got, or write the other one.

That leaves you with 3 overall options. Both taking the same of these choices won't work (I skipped over the calculation because they're not interesting solutions), so they must agree to take opposite choices.

Honestly the situation was a little confusing because I like to think about a thought experiment which is similar (a coordinated three-person game called "Betrayal" which exemplifies the weirdness of quantum mechanics) and due to this I imagined that the "win criterion" was "Alice and Bob both have to get each other's answer right."

When I re-read the description and said "oh, they only have to have one correct answer between them," it was just like, "how can I make sure that when Alice is wrong then Bob is right?". The solution followed about a second later, "well if Alice guesses the same as her flip, maybe Bob guesses the opposite of his", without any logic tables or further reasoning or anything. Then I drew up the 4 possible coin flips and the resulting predictions and wins, to prove that it was correct, just in case I was somehow missing something.

Yea, I made the exact same mistake at first. (Thinking that Alice AND Bob must always know the answer)

So what I did was wrote out all 16 possible outcomes in an excel spreadsheet. I used T and F for tails and heads, because I'm used to reasoning in true or false. http://i.imgur.com/jKYSo3P.png. Then I noticed the two edge cases of: TTTT, and FFFF and came to the conclusion that is was not possible for them to agree on the same guess beforehand (i.e. Both guess tails or both guess heads). So then, by trial and error, I checked what would happen if one chose the same as their flip, and the other chose different from their flip. I bolded the case where it was valid to my rules, and deleted an invalid case http://i.imgur.com/E3jnIkd.png, and saw that it worked.

This puzzle you can get without being "clever" by just following the logic:

Suppose Alice got Heads. Say she guesses Heads. Then when Bob gets Heads they win. When Bob gets Tails Alice is wrong so Bob needs to guess Heads when he gets Tails.

Flip the scenario around when Alice gets Tails and you get the whole strategy

I personally just worked through a concrete example. So Alice flips her coin and gets heads. I then just assume that she is going to guess the opposite of what she flipped, so she guesses tails.

For Alice to lose, Bob would have to have flipped heads. Now Bob knows, because he has discussed strategy with Alice prior to doing the flips that either Alice flipped tails, in which case she has won, or she has flipped heads, in which case she has lost. But Bob can then bet on heads, in which case he knows that he wins if Alice loses.

That was my way of reasoning things anyhow. As you can see from the other responses, there are many different ways of arriving at the right answer.

Alice and bob can then either do one of 3 (rational!) things - stick to a prior choice, guess their flip result, or guess the opposite of their flip result.

Both of them sticking to prior choice was shown not to work, leaving 8 permutations to investigate at most. But it is easier than that.

I started by assuming Alice will guess her flip result. Looking at the truth table

    A B
    h h :-)
    h t :-(
    t h :-(
    t t :-)

This means the only losing possibilities are when the coins are different. Therefore Bob must guess the opposite of his flip result, to ensure no losing possibilities at all.

One of the things I learned was from the Singapore test question (about Cheryl's birthday) which was to parse the question for any clues. What tipped me off was the requirement that either or both of them could get the correct answer to satisfy the problem statement. Once I figured that out I came to the conclusion to try out the truth table where one participant holds their answer constant and the other does a negation of their answer. The truth table worked out.

I have to say I feel somewhat inadequate coming to the answer experimentally as opposed to what others did here.

Generally, it helps abstracting the problem away into the real constraints, in this case, the outcomes space, (i.e. 4 possibilities, that can be compressed into 2 bits of information bit 1 = 'same or different', bit 2 = 'head or tails', but in this case 'head or tails' is irrelevant), and then reasoning how each person communicates their bit of information to span the entire outcome space.

I wrote out the 4 possible coin flips and expected to try to work it out more or less by brute force but once I looked at the possibilities the answer came to me and seemed obviously correct at once. Brains are weird. Just because I am one doesn't mean I have the faintest clue why or how it does things.

The only information each person has it their own coin, so their strategy is a pair of functions (f,g) from bits to bits, where either fx=y or gy=x (or both) for any bits x and y. There are only four possibilities for f, so picking, at random, f=id, gives g immediately.

For me, I immediately guessed the strategy on my first guess (one same, one opposite) and somehow automagically intuited it was correct, but did not really understand why. Then I understood once I looked at the thread.

That was exactly my experience and the reason I asked the question :)

The answer just appeared with zero awareness of any effort or reasoning that may have lead to it -- the only reasoning I perceived was in verifying the solution. So I got curious as to how intuition could solve this problem roughly on its own, or with so little help from conscious reasoning that I didn't notice it.

From the replies it seems there are two key realizations that combined could lead directly to the solution, and both realizations strike me as things that intuition would be good at noticing. The first is that each player likely has deterministic rule that is dependent on their coin, so there are only two candidate strategies per player. And the second is that the players likely have different strategies.

We had very similar thought processes.

i did it by thinking "let bob pick a strategy, and let alice pick her answer by knowing what bob is going to do. if bob always guesses his own coin, then when alice sees H she knows that either bob has H too and will therefore win for both of them, or bob has T and will therefore lose, but the only way to lose is if bob has T so if alice guesses T then they have all their bases covered". of course there is a simpler way to get the answer, as other posters have noted.

Downvoted because I don't think this should be at the top of the discussion. I always read comments first, especially with a title like "Hello, World" that doesn't give any clue about the content; and now I don't get a chance to think about this puzzle because the spoiler was the first thing I saw.

EDIT: To be clear, I am not downvoting because I think that this comment is unconstructive; clearly it is a useful contribution. At least as good as, and probably better than, having it appear later would be having more whitespace between the spoiler warning and the actual spoiler.

Just a comment: They'll had always a win, by sacrificing the possibility of both of them guessing right.

Yes, the intuitive way to think of it could be that the coins will either be the same (bob gets it right) or they will be different (alice gets it right)

Thank you Professor Falkener. Now how about Alice and Bob play Global Thermonuclear War?

however, if the puzzle is changed from 'either one or both their guesses are correct they win' to 'both their guesses should be correct to win', then the solution becomes tough!

Reply on news.ycombinator.com