Hello, World

[SMackinnon]

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

[ColinDabritz]

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.

[JoshTriplett]

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.

[kolodny]

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

[sdab]

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.

[yorkyorkyork]

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.

[furyofantares]

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?

[JadeNB]

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.

[lucio]

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

[TheSoftwareGuy]

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)

[Toenex]

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

[gamekathu]

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!

[rjtobin]

Some discrete mathematicians are interested in this sort of problem, which they call "simultaneous hat guessing". There are quite a few papers, in case anyone is interested and unfamiliar with this sort of thing.

Another fun problem, probably better known, is sequential hat guessing: take 100 people in a line, arranged so that each person can see everyone in front of them, but no-one can see any of the people behind them. Everyone is given either a red or black hat to wear, but no one can see the color of their own hat, or the hat of anyone behind them. So the person at the back of the line can see everyone's hat but their own, the next person can see everyone's hat except the first person and their own, etc.

Now starting with the back of the line, each person is asked to publicly guess the color of their hat. The participants are allowed to agree upon a strategy, how many people can they guarantee guess correctly?

Things get crazy if you allow an infinite countable line of people, and put ear-muffs on anyone so that no one gets to hear anyone else's guess. Surprisingly, you can still save almost everyone (if you allow the axiom of choice).

[judk]

The solution requires infinite memory (not just arbitrary finite memory, but an actual, non-compressible infinite value) which is of course impossible in reality.

Usually problems on "countable" structures need only finite memory (to process infinite streaming input), so this problem is rather misleading.

[d0m]

Yes, this is a great one. Unless I'm mistaken, the best strategy has potentially one error, but all the rest would get it right, yes?

[praptak]

An actual fun problem:

100 prisoners are each assigned a black or white hat, at random. As always, they cannot communicate after the hats are assigned. Then they are shown each other. None sees own hat, everyone sees everyone elses hat. Then they are led into separate rooms and each guesses their own hat color.

They win only if everybody guesses correctly. What strategy maximizes the probability of that event?

[thewarrior]

I haven't looked at any of the solutions. Or any of the other comments.So at the risk of posting a redundant comment :

Alice guesses that Bob's coin is the same as hers. Bob guesses that Alice's coin is the opposite to hers.

It's fairly straightforward. I'd like to know the computer science angle to this though.

EDIT: From the computer science that I know :

We need to find an invariant that all permutations of coin flips always satisify. Intuition tells us that Alice's coin might be the same as Bob or vice versa :

If you construct a truth table :

  Alice  Bob     Alice's Coin same as bob    Bob's opposite to Alice

  H      H               YES                            NO

  T      T               YES                            NO

  H      T               NO                             YES

  T      H               NO                             YES

The expression :

  Alice's coin same as Bob || Bob's opposite to Alice

Always evaluates to true. So Alice can guess her flip and Bob can guess the opposite.

But what if we had Alice , Bob and George and atleast one of them had to get the other two right ?

Is there a general pattern ?

  Alice Bob George
  H     H   H
  H     H   T
  H     T   H
  H     T   T
  T     H   H
  T     H   T
  T     T   H
  T     T   T

Will try and figure it out over dinner :D .

[est]

This is off topic, but when the next president takes office, all of current whitehouse.gov content will be gone and replaced, no?

[trvr]

I'm guessing they will do something similar to when Obama took office: http://georgewbush-whitehouse.archives.gov/

[chx]

I am not sure what will happen to https://petitions.whitehouse.gov/ -- can you imagine that just wiped off?

[pelario]

"Coding is exciting: you can decide what is supposed to happen, and the computer will do it…the only limit is your skill and imagination!"

Someone didn't learn about the halting problem :-)

[JacobEdelman]

Bonus points: What if only one of them gets a coin to flip and then they must both come to an agreement on what the result was. They can talk but the NSA overhears everything they say and can crack every cipher they use. Can you maximize the chance that the NSA can't guess who got that coin AND Alice and Bob agree on the correct result?

Note: An open problem. You can look up cryptogenography for current results.

[bandrami]

From the first link: I find it difficult to believe that in the entirity of Jimmy Carter's Navy career, he wrote zero lines of code.

[waterlesscloud]

Considering he left the Navy in 1953, I find it easy to believe.

I wouldn't be shocked if W had written some excel macros, though. Even less so if Romney had.

[protomyth]

Might be close, 1953 was the year of his discharge, so he might not have written anything.

[cheapsteak]

Jimmy Carter aside, what kind of code do navy people write?

[pokstad]

Reminds me of Dr Ebert's hat problem: http://web.csulb.edu/~tebert/hatProblem/nyTimes.htm

[giltleaf]

I think I was slow coming up with this, but basically I wrote a lot of tables out and came up with...SPOILER...

Alice always guessing the same as what she flips and Bob always guessing different.

But - my question is this: Are there any other possible solutions to this puzzle?

Either way, I'm pretty sure this is just an Illuminati code plot from the White House to find the world's top coders and recruit them into some CIA program.

[titanomachy]

OK, we get it, most HN readers were able to solve the puzzle in a minute or two. Most of us have done interview problems much more difficult.

I'm more interested to know what people think about Obama's proselytizing of computer science. It seems like a great move to me. Is he going about this in a smart way? Do you think he'll get the results that he's looking for?

[gigias]

It seems too simple to be right, but can Bob just say heads all the time, and Alice say tails all the time?

[lobe]

No, there are two different coins. So if Bob flipped heads (which Alice guessed tails for) then they lose.

[noreasonw]

I solved (believe) the puzzle in 3 minutes.

A says B result is the same as A result. B says A result is different from B result,

so that A covers (H,H) and (T,T), B covers (H,T) and (T, H), so always A or B is true, so they always win.

[mmcclellan]

Just adding the Python test I used:

https://gist.github.com/mmcclellan/4b01bf781393395526e3

[namelezz]

One writes down what s/he sees. The other writes down what s/he does not see.

[JacobEdelman]

So, "a paper" and "a gigantic ostrich juggling American Space Kangaroo"?

[pipermerriam]

fun.

https://gist.github.com/pipermerriam/d1b5a24230f2f9ec4446

[anishathalye]

slightly less verbose:

https://gist.github.com/1751cebe44d88dc7db15

[idohealth]

Can't Alice just always pick heads, and Bob always pick tales?

[halter73]

This fails if Alice flips heads and Bob flips tails.

[startupfounder]

> The puzzle is this: Can you think of a strategy Alice and Bob can use that is guaranteed to win every time?

Raise campaign finance from the wealthy so that they can make it past the lesterland election[0].

Now that you have a war chest and are in the general election you just need to raise more capital from the 0.1%, buy more advertising, hire the best staff in Washington and bam!

I know this is not the coding question at hand, but a more important question on how unequal our political system is and I couldn't forgo the opportunity to ever so gently show the obvious reality - once you past the lesterland wealthy elite and get their backing, winning is only a matter of time.

[0] http://lesterland.lessig.org/

[happyscrappy]

If Lessig's theory is correct then how in the world is pot being legalized?

[alexashka]

If the answer is 'at least one of them always write down "heads or tails"', then lol

[alexashka]

I had assumed there was no real solution and figured it being a clever semantic play.

I stand corrected, very nice puzzle :)

[javert]

I have zero respect for someone who would take a role like that.

[hkmurakami]

So you have no respect for a researcher who took rhe stand against Microsoft in the Microsoft antitrust case?