Hello, World

Yeah, added a little spoiler tag.

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.

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.

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.

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.

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

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.

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.

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.

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.

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.

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".

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.

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 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.

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.

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.

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

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.

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

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

that's exactly it

Gurl pna trg svsgl creprag ol rirelbar thrffvat fhpu gung gur ahzore bs oynpx ungf vf rira (be bqq).

I wouldn't be surprised if this is optimal, but I also wouldn't be surprised if it's not.

Very clever. So I'm assuming they just don't write any links that involve using the full domain. (i.e. /somepage instead of http://www.whitehouse.gov/somepage)

During Carter's era or today. In 90 I was trained for a year in computer engineering for our sonar computer mainframe including Assembly. The idea was that if we were on deployment and a bug caused a problem we could potentially figure it out and maybe fix it without stopping the mission. I was programming on my own for 8 years prior to that as a hobby so was actually correcting the instructor on a couple of occasions. There is also the rate DT which does programming all the time I think. I wanted to get into that rate but the wait was a year and I was impatient.

LOL. Good one!

But slightly more Haskell... ;)

`zip toss toss` only produces 2 of the possible outcomes. Try `liftA2 (,) toss toss` instead.

slightly less Haskell :)

https://gist.github.com/Chronial/e091dc5deb9234a2a7a1

Absolutely. That makes him even worse.

"Antitrust" is a bogus concept.

It is never and was never in the public interest.

It is also a massive violation of the rights of companies and their shareholders.

Consider that if Windows/IE were really that bad, people would have just switched more readily to a Microsoft competitor. Desktop-quality Linux would have come about/come about sooner, or something equivalent.

This is an example of the point that there is no such thing as a monopoly unless it's created through legal channels (i.e. is granted by the government).

There is no business that can't be competed against with sufficient capital.

And the global economy accumulates spare capital over time (because in the net, the species produces more than it consumes).

Even "natural monopolies" are a function of a mistaken way to implement property rights, as opposed to being "natural." Because you can always build underneath or around whatever is already there.

edit: This is a serious intellectual comment that deserves to be read. It also matters a lot for our industry. Consider Google in Europe right now.