Prisoner hat and light riddles?

Favorite Answer

Riddle 1: I think there's probably more than one way to do this, the question is, which strategy is likely to free the inmates the soonest? A safe but lengthy strategy would be to pick a guy whose job is to keep track, and to make the announcement, as follows:

Tracker: If he sees the light OFF, he leaves it alone. If he sees it ON, he turns it OFF, and adds 1 to his count, which begins at 0. When he reaches a count of 1000, he makes the announcement.

All Others: If any see the light OFF, and have never turned it ON before, they turn it ON. Otherwise, do nothing.

This could take a while before all the inmates gain their freedom. To see how this works, try using 3 or 4 prisoners, not 1000.

Riddle 2: I'll get back to this one later.

Edit: Riddle 2 is really, really difficult. I'd like for you to extend this question, because it seems unlikely that I'll have anything resembling a full solution by tomorrow. What I have right now, work in progress, is for the inmates to first consider all possible sequences of red and blue hats, and then partition them all into sets, each set having a "root" sequence such that all the remaining members of the set differs from the root in only one position. All inmates agree to only assume the root, if they recognize that the actual sequence they see after colors are assigned belong to one particular set. That is, the set that has the sequence they see, which includes their own hat being either red or blue. There's a number of things I need to prove to make this a real solution, I'm not there yet. Of course, I make the assumption that these inmates have God-like powers of being able to not only see an infinite sequence of red and blue hats, but being able to remember an infinity of sets after having constructed them, each having an infinity of member sequences each infinitely long. Otherwise, I do believe that a practical solution that can be done by ordinary people is probably impossible.

Edit 2: Brian, that wiki article about this, clear as mud. What I fear is that "a solution exists only if there's an infinity of inmates", i.e., no improvement over random deaths in the case of a finite number of inmates. In which case, I'll just throw up my hands. It could end up being dependent on assumptions made about infinity, which could very well be arbitrary. That is, to one mathematician, a solution "definitely" exists, to another, "definitely does not" exist, depending on which assumptions they hold to be true about infinity and drawing up sets from it.

As of right now, I can't see a way to improve odds for a finite number of inmates. That is, achieving some kind of an asymptotic less-than-infinite number of inmates killed as the total number increases. Until I am at least able do that, I think I'll pass on this problem. I don't want to get into speculations about the nature of infinity.

Edit 3: Not to be disrespecting mathematicians, just because something is "accepted by almost all modern mathematicians" doesn't make it true. It simply means it's a axiom that's popularly deemed to be valid in order to have some interesting math to go with it. The whole point of an axiom is that what shall be an axiom is a matter of choice (no pun intended here). I don't want to get into things that "only happens at infinity", I prefer things that have at least some practical realization....Show more

Prisoner Hat Riddle...Show more

1...Show more

@Josh: sorry i missed that detail about prisoners not being able to hear each other.

***************edit 2:
Brian, i was thinking about this riddle riding my bike earlier and I'm amazed at how close i was to the solution. I was actually thinking of equivalence classes of sequences and was gonna suggest that it might need the axiom of choice and something like vitali sets! Then i clicked on your link. Oh well...
Great Riddle btw!

***************edit 1:
Riddle 1:
I don't know how to save all but a finite number of them. The best I can do so far is to save a fraction of the prisoners that can be made to approach 1 arbitrarily fast. The prisoners agree on a strictly (and preferably a very rapidly) increasing sequence (a.n) of natural numbers with a.1 = 1. For each n, they designate the a.n-th prisoner to take one for the team. They agree that red = 1 and blue = 0.¹ When it's the a.n-th prisoner's turn, he calls out the the mod 2 sum S of colors over the block of prisoners (a.n + 1), ...., (a.(n+1)-1).² If he's lucky, his hat is the same color. But meanwhile, each prisoner in that block now knows hisr own color, which equals (S - the sum of all other colors in that block) mod 2. Since the blocks get bigger and bigger, the survival rate tends to 1.
_______________
¹ The scheme generalizes to any number k of colors – just make all calculations mod k.
² The prisoners agree not to extend the blocks to a.(n+1) to spare the poor chap the agony of knowing he'll be shot and the temptation to call out his own color.

****************edit 0:
Riddle 2:
For the first 999 visits the rules are
If it's off and you're a returning visitor, turn it on. Otherwise do nothing.

For the 1000th visitor the rules are
If it's off, go tell the warden everyone's been to the room. Otherwise turn it off and you become the counter. Set the count at 1.

After the 1st 1000 visits the rules are
If you're the counter and the light is on, turn it off and add 1 to the count and if the count is now 1000, go to the warden; otherwise do nothing. If you're not the counter and the light is off, turn it on; otherwise do nothing....Show more

This Site Might Help You.

RE:
Prisoner hat and light riddles?
Riddle 1:
A prison has 1000 inmates and a room with a light switch, initially off. Every day, a random prisoner is let into the room, and they may flip the switch if they wish. Once a prisoner believes every prisoner has been in the room, he may tell the warden. If he's right, all the inmates......Show more