A Friendly Competition

This week, in a session run by Jan, we were split into teams comprising one student from each of the first, second and third years and presented with a series of increasingly difficult problems to solve. There were fantastic prizes such as chocolates, flapjacks and even bottled water available for the winners, the runners up and, well, pretty much everyone.

Three people enter a room, each one with either a blue or a red hat on their head. They do not know the colour of their own hat but they can see the hats of the other two people. Once they had a chance to observe the colour of the other hats, they can guess what colour their hat is or say nothing. All guesses happen simultaneously and no other communication is allowed. if no one guesses wrong and at least one person guesses correctly, they win, otherwise they lose. Given that the colour of each hat is assigned randomly by a flip of a fair coin, what is the best strategy and how often does it win?

The first question was one of probability. Surprisingly unintuitive, perhaps you wouldn’t expect there to be a strategy any better than picking at random, but you’d have to think again. Radu, on my team, got to the answer fairly quickly but it took much longer for him to convince Holly and me that he was correct!

You are given two hourglasses. One measures 4 minutes and the others measures 7. Can you measure 9 minutes?

Bonus: given two hourglasses that measure n and m minutes, what values of k minutes can you measure and how much set up time do you need?

This question is closely related to the perhaps more widely known problem of measuring a specific amount of water given two unmarked jugs that are known to hold n and m litres respectively. You can fill the jugs up, empty them, or transfer water from one jug to the other until one is either full or empty. You can’t, say, pour out half of the water, however: you have no way of measuring exactly half, just as you have no way of knowing when exactly half of the time from one of the hourglasses is up in this problem.

Our team solved the hourglasses question more quickly than the first one, perhaps because all of us had seen the isomorphic water jugs question before.

Given a standard 52 card deck, 5 cards are randomly chosen by a member of the audience and given to a magician. He then selects one of the cards and keeps it, while arranging the remaining four cards on a table face up. A second magician then determines what card the first magician kept. What strategy did they use?

Note that while arranging the cards on the table, only their order can be significant, e.g. you cannot rotate them in any way to give extra information to the second magician.

In this clever question, it appears at first as if you do not have enough bits of information available to communicate which of the remaining 48 cards has been selected. Indeed, our team almost didn’t believe that was possible at first, and not one of the teams present was able to solve the problem after almost twenty minutes of discussion.

Eventually, Jan stepped up to the whiteboard and explained the solution — after a few people left the room, determined to come up with an answer themselves and refusing to have the game given away to them. Even once it had been explained, many of us didn’t see how the solution worked until we had discussed it amongst ourselves for another five minutes!

Following this question, the hour for the meeting was almost over, and besides, the non-muggles among us had to leave to go to a Harry Potter themed formal hall. But the dedicated computer scientists stayed for one final enigma.

You are given 3 Turing Machines and want to determine which ones terminate and which ones don’t. You have access to an Oracle that, given a Turing Machine, tells you whether it terminates or not. However you can only query it twice.

Again, this question seems impossible because you are only given two bits of information and must seemingly use those to distinguish between 8 different possibilities. However, a solid understanding of the theory of computation led Eduard to a brilliant way of generating that final bit that the Oracles cannot themselves provide.