Wednesday, 27 April 2005

Logic Puzzle

Here's a puzzle that Zbigniew Michalewicz gave at the Complex Systems 2004 conference in Cairns, though I don't know where he got it from. It was phrased with a lot of redundant information; here's the essential, stripped down version. I think it's quite clever and has an elegant solution (even though I didn't solve it myself :p )

You and a number of other people are seated facing each other in a circle in a plain room, with no prior knowledge of what is about to happen. One person, the host, enters the room, blindfolds everyone seated in the circle, paints a dot of some colour on everyone's forehead, and then removes the blindfolds.
Looking around, you see that multiple colours have been used and that some people, seemingly spaced at random, share the same colour dot as one another.
The host tells you three things:
"You may not communicate in any way the colour of a person's dot."
"I will ring this bell at regular intervals; when I ring the bell, stand up and leave if you know the colour of your dot."
"At some point, you will know the colour of your dot."

The question is, how can you know what colour dot you have?

Hints (in order of revelation - highlight text to read)
  1. It is crucial that everyone knows that the problem is solvable.
  2. There are an infinite number of colours (but assume for the sake of the problem that you can still tell when two people have the same colour :) ).
  3. Can you know what colour you have if you are the only person with that colour?
  4. Goto 1.
Yeah, I think everyone who reads this blog has heard this problem anyway, but I still think it's good :p

No comments: