Prisoner hat and light riddles?

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.

Prisoner Hat Riddle

1

@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.

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...

The following is likely one of the solutions to Riddle 2 that you already have, but it

might provide some guidance to others in generating their own novel solutions:

http://en.wikipedia.org/wiki/Prisoners_and_hats_pu...

Edit: @jibz. Sorry, I guess I should have waited until you had a chance to

complete your post. :( Apparently you have very productive bike rides. :)

@Scythian. Yes, my red-hatted neurons and blue-hatted neurons were

having an argument as to the validity of this solution, (not to mention its clarity),

but I thought it was still worth posting, if only to serve as a point of discussion.

@Michael. Yes, if I were a prisoner and I saw a finite number of hats of one

color or another I'd be feeling pretty good about my chances, although I'd be

feeling sorry for those who were wearing the finite-numbered hat color.

All the prisoners would be optimistic in this scenario about their own chances,

even though many would end up dead. This is a riddle worthy of Kafka. :)

You are doing this for the mugglenetinteractive as well right. So are my friend and I. I pretty much found out the answer the the one where the boy is learning to drive, but not the second and third questions, but I did some research and here is what I found. You have two ropes. Each one takes exactly an hour to burn, but they are not the same length or width, and their width is not uniform (so burning half the length of a rope does not mean half an hour has elapsed). By burning the ropes, how do you measure exactly 45 minutes? (Hint: you can burn the ropes however you like.) click for answer Light both ends of one rope and one end of the second rope. When the first rope burns out, half an hour will have elapsed (since it was burning twice as fast), and so the second rope has half an hour left to burn. Now light the other end of the second rope, halving this time to 15 minutes, thereby measuring the exact 45 minutes

riddle 1

the prisoners will make a strategy that the 1st person entering the room will turn the light on and every day he will count no. of people in the room.the light is on.so,he can see.when the no. reaches 1000 he will tell the warden.

TOO EASY..................

second one maybe coming soon.

====Problem 1====The expected time to the first success in repeated independent experiments, each with success probability p, is 1/p. Thus, the expected time of Scythian's algorithm is:

E[Scythian's time]

= (1000/999 + 1000) + (1000/998 + 1000) + … + (1000/1 + 1000)

= 1000*999 + 1000*(1 + 1/2 + 1/3 + … + 1/999) = 1006484.47 days.

Here is a better way. Start all people in state "NOT COUNTED." For the first 1000 days, the first person turns the light ON, and all remaining people keep it ON until the first person to visit a second time. That person turns it OFF and is designated the TRACKER, with COUNT=k-2 (for day k). All other people keep it OFF until day 1001, when we run Scythian's algorithm from then on, but with the tracker starting with a value COUNT that is typically 30something. Note that:

E[COUNT] = -1 + sum_{i=1}^{1000} prod_{k=0}^{i-1} (1000-k)/1000 = 38.303213

***

Define C=COUNT. Then E[New Time | C=999] = 1000, and for c in {0, 1, 2, …, 998}:

E[New Time | C=c]

= 1000 + [(1000/(1000-c-1) + 1000) + (1000/(1000-c-2) + 1000) + … + (1000/(1) + 1000)]

<= 1000 + E[Scythian's time] - 1000*c

From this it can be shown:

E[New time] <= E[Scythian's] - 37303.212926 days = 969181.25 days.

====Problem 2====Here is a solution that works in limited circumstances: If you see a finite number of RED hats, guess "BLUE." If you see a finite number of BLUE hats, guess "RED." Else, guess anything.

In the (unlikely) case that one color has only a finite number of hats, this strategy guarantees only a finite number will die. Otherwise, if all hats are independently and equally likely to be RED or BLUE, it does not seem possible: If we only base our guess on a (perhaps random) function of the observed hats of others, then we are right with probability exactly 1/2 (regardless of the function that specifies our guess). So everyone is right with probability 1/2, which ultimately implies that, with positive probability, there are an infinite number of wrong answers.

Unless you look for "trick" answers, like "she can never finish sequentially questioning an infinite number of people…." or "If your predecessor's hat is RED, stick our your tongue…"

====Edit: Riddle 1: Here is a better way that gets an average of less than 300000 days. Designate 50 trackers, one of which is a "super tracker."

Phase 1 (day 1-99999): If you are not a tracker and see the light OFF for the first time in Phase 1, turn it ON. If you are a tracker, see the light ON during this time, and have a count less than 19, turn it OFF and increase your count by 1. This phase is successful if all trackers meet their quota of 19 during this time. Define p as the probability this phase is not successful.

Phase 2 (day 100000): Turn the light OFF.

Phase 3 (day 100001-199999): If you are a super tracker, each of the 49 other trackers turns the light ON during this time if it first sees it OFF, and if it obtained a count of 19 on the previous phase. The super tracker turns the light OFF during this phase, and keeps a new counter. If he turns the light off 49 times in this phase, and if he met his own quota on phase 1, we are done and he talks to the warden. Assuming phase 1 was successful, define q as the probability that phase 3 fails.

Phase 4 (day 200000): Turn the light OFF.

Phase 5 (day> 200000): If we reach this phase, we know the previous phases failed. So we start over.

Each round takes 200000 days, and fails with probability z = p + (1-p)q. I believe that z < 1/10. Thus E[Time] < 200000 + (1/10)E[Time], so E[Time] < 200000*(10/9) = 222222.222 days. This could be fine-tuned with more accurate values for p and q. I think my bounds are conservative.

**

@Josh: If each one dies with prob 1/2: Let D(k), L(k) be the number of deaths and lives in the first k. Then E[D(k)]=E[L(k)]=k/2 for all k. By the Markov inequality: Pr[L(k) > 3k/4] <= E[L(k)]/(3k/4)=(k/2)/(3k/4)=2/3. So Pr[D(k)>=k/4]>=1/3 for all k. So Pr[DEATHS=infinity]>=1/3.

@Brian: I see. Your link solves via non-measurable guess functions (assuming axiom of choice). =) My proof above assumes measurability.

@Josh: The algorithm indeed terminates successfully. It operates over independent rounds of 200000 days. In each round, a person reports to the warden if and only if he is SURE that all others visited the room in that round. This happens with probability 1-z. The expected number of rounds is 1/(1-z). In phase 3 of each round, the 49 trackers send the message "I met my quota" to the super-tracker.

If we wanted an answer that finishes successfully "with high probability" we can do MUCH better: The probability we are not done by t days is, by union bound, less than 1000*(999/1000)^t. If t=12000 days, this probability is less than 1%.