You are viewing a read-only archive of the Blogs.Harvard network. Learn more.
header image

A brainteaser from the White House

It is well known that President Obama was a strong supporter of computer science, and was the first US President to write code. During his presidency, brain teasers were published from the White House web page. I came across this nice riddle that illustrates how Boolean logic can be used  to achieve  success in cooperation. Here is the riddle [1]:

Alice and Bob are playing a game.  They are teammates, so they will win or lose together.  Before the game starts, they can talk to each other and agree on a strategy.

When the game starts, Alice and Bob go into separate soundproof rooms – they cannot communicate with each other in any way.  They each flip a coin and note whether it came up Heads or Tails.  (No funny business allowed – it has to be an honest coin flip and they have to tell the truth later about how it came out.)  Now Alice writes down a guess as to the result of Bob’s coin flip; and Bob likewise writes down a guess as to Alice’s flip.

If either or both of the written-down guesses turns out to be correct, then Alice and Bob both win as a team.  But if both written-down guesses are wrong, then they both lose.

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

The idea is simple. Alice will write down her coin toss, and Bob will write down the opposite of his coin toss. One can write a formal proof that this works, but the idea is simple: this strategy is equivalent to Alice guessing that the two coin tosses are identical, and Bob guessing that they are opposite, the success is guaranteed.

The support of computer science has to spread not only in USA, but in other countries as well, as it provides an algorithmic way of thinking about problems. With respect to my home country Greece the situation has improved since my days at high school, but unfortunately the book used for teaching as of today does not take the teaching approach illustrated by this riddle, that is accessible to students of high-school age.