I set you a problem on Monday and promised you the answer "tomorrow". It turned out I was using a slightly generalised sense of the word, and I meant "on Thursday". Anyway, the answer is 19 people and the strategy for doing this was emailed me on Tuesday by Chip which saves me having to write it out for myself!
"This is a bit of a weird situation, where writing the problem down exactly in mathematical language solves it for you! I'd started typing this by setting out my assumptions, then I was going to work on the 2-colour case and generalise from there, and as I was doing that, I realised I'd actually nearly typed the full answer! (This is with two unstated assumptions - 1. that the prisoners know all of the possible hat colours in advance and 2. that all the prisoners can hear everything that's said in the room).
If they are true, then you can always guarantee the survival of everyone except the first guy, and he'll survive with probability 1/m (where m = number of hat colours). What the prisoners do is assign a number value to each of the colours - let's say black = 1, white = 2, red =3, etc., then prisoner 1 adds up the colour values of all the other people's hats (call that T), and says the colour that corresponds to T mod m. Prisoner 2 can work out what his hat colour is by adding all the hat values he can see (call that S) and then his hat has colour (T - S) mod m, and lather, rinse, repeat. Prisoner 1 survives if his hat happens to be colour T mod m - I think it's reasonably self-evident (translation - I think it's so obvious that I can't put why into words!) that his survival can never be guaranteed."
Easy!
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment