Late Friday Puzzler -- 100 Prisoners

Re: Late Friday Puzzler -- 100 Prisoners

david weaver

Figuring there are 100 prisoners and disregarding the light, it seems like 96 visits can occur each day. So day one is a bad day to claim freedom, even if it starts at midnight.

the chance that an individual is not chosen at least once by the end of day one is 0.99^(96)

Dumping this into a spreadsheet, I figure that (I'm missing something, but) the chance that someone has visited the warden after a certain number of iterations is 1-(0.99^(number of 15 minute sessions))

then, there are a hundred individuals, so after a certain larger number of iterations, the probability that all of the individuals have seen the warden is 1 minus this (per individuals) ^(100)

after 200 separate visits, that would yield a chance of claiming on the 200th that everyone had visited the warden of 1 in 1.8 million. Not good.

After 600 iterations, there's a 78% chance that everyone has been to the room. A drastic difference. Many, of course, have been there multiple times.

I need to factor in the light now.

23 years since probability, I think I'm out of steam to figure out how many times a chosen person should see the light on before they turn it off and claim all have been to the room.

Re: Late Friday Puzzler -- 100 Prisoners

david weaver

I may not be reading this question right, but adding the light confuses me.

I used rand in excel to check my ailing probability abilities and with 1000 numerical draws, i have individuals visiting the room between 4 and 17 times.

If I do the same thing reflecting only 300 draws, there are many zeros in my chart. If the prisoners know these things, they'd be hesitant to declare that all prisoners have visited the room. Even with some zeroes, a couple of prisoners have visited 9 times by then, so it wouldn't be safe for a prisoner who visited 7 times to say "ghee, everyone must've been here by now".

Re:Question

Larry Barrett

Can we assume that the prisoners know when the selection process starts? That is, after they consider their strategy, a bell goes off or there is some signal when the first prisoner is selected?

And can we assume that the prisoners can see a clock or have some means of tracking time? Maybe each can start one one thousand, two one thousand, ... so that as time goes by they know how many times a prisoner has been selected to go to the room?

More correct than the "right" answer

Alex Y

David, you are absolutely correct. And carrying your calcs a little further, I figure after 1000 trials (=250 hours = ~ 10.5 days) they could claim freedom with about a 96% chance of success. Double that time and get a chance of execution of only 3x10^-6. I like those odds! After a month, the answer is 100% chance of freedom, at least as far as my calculator's resolution is concerned.

The original puzzle has an answer that is deterministic, and uses the light and switch. I will present it in another post. However, the original statement of the puzzle has the jailer calling up a person every day. As an actuary, I had to change it to every 15 minutes, since the daily test would have too many prisoners dying of natural causes before the solution is completed, and that would "break" the solution. (And as an actuary, I am embarrassed that I did not catch the probabilistic answer until you presented it!)

Nice job!

Re:Question

Alex Y

Good questions, and yes, you will need a starting signal and a way of telling passage of time (tally of days?) for David's solution.

Neither of those is necessary for the deterministic solution, but the deterministic solution takes probably 10 or more times as long.

Re:Question

Larry Barrett

The only strategy I can think of using the light switch is this: the prisoners decide that when each one goes into the room for the first time he notices the light position (on or off); then, when he leaves he flips the switch. If the prisoner returns to the room the second or more times he notices the light position but does not flip the switch when leaving.

So when a prisoner comes into the room for his first time, if the light is off he knows that an even number of prisoners have been in the room, and if the light is on he knows that an odd number of prisoners have been in the room.

If he also knows when the process started and knows how many times some prisoner has been in the room then he can start to make inferences using the probability approach that David has outlined.

If there are only two prisoners instead of 100, this approach would allow the second prisoner to enter the room for the first time to know that the other prisoner had already been in the room one or more times (but in this case he also would know by counting the 15 minute intervals). If there are three prisoners and prisoner #3 enters the room after 2 or more selections and he notices the light is off he would know that the other two have been in the room. If the light is on he would know that one of the others has been in the room twice and the remaining prisoner has not been in the room. Probabilities enter the equation as the number of prisoners increase.

And in any event, if there are n prisoners each prisoner must wait for at least n/4 hours to elapse before there is even a chance for all prisoners to have been in the room.

Deterministic solution

Alex Y

Pick one prisoner as the counter. We'll choose #1.

#1's job is to turn on the light if it is off, and count how many times he has to turn on the light.

Every other prisoner is to turn off the light the first time they enter the room and see that the light is on. if the light is off, or if he has turned off the light on a previous turn, he does not use the switch.

Each time #1 turns on the light, he is counting one distinct prisoner who has turned off the light (except the first time, when he is counting himself). So once he has turned on the light 100 times, he knows all the prisoners have been into the room.

The practical problem, which makes David's solution far more attractive, is that #1 will be chosen on average every 100 tries, and #1 needs to be chosen 100 times, and some of those times the light will still be on. So he has to be chosen more than 100 times before he turns on the light 100 times. That means at least 10,000 tries, and with some tries not needing to turn on the light, that would probably be 30+ years, during which surely some prisoner would take to his grave the information about whether he had turned off the light. Even with 15 minute intervals, that would be 3+ months. I'd be more than willing to take at 0.0003% chance on David's solution after 3 weeks.

Now I know why I like your puzzles and ...

david weaver

..often think, "I've forgotten to look at the puzzles for a while, I should go look".

I'm also an actuary, but none of my day to day work ever looks like balls in an urn. So I've gotten rusty and lost some of my sense of feel with this kind of stuff.

Re: Now I know why I like your puzzles and ...

Larry Barrett

When I was in college I had a summer job in the actuarial dept in an insurance company. This would have been around 1960 and I used a Marchant mechanical calculator. One of the actuaries introduced us to probability problems during lunch hours.

Marchant calculator

Alex Y

That brings back memories!

Re: Now I know why I like your puzzles and ...

david weaver

I'm in my mid 40s. I've heard stories about slide rules and punch cards, but have never seen them. One of my superiors liked to describe a situation at an insurer where everyone sat at open desks like a classroom. If you got promoted, they added a wing to your desk (like a tablesaw, I guess).

If you got promoted and then failed exams or did something else to get demoted (lucky if you didn't end up out of the department), the company minions would very publicly remove the wings from your desk in the middle of the work day so that everyone could see it.

My supervisor often discussed the art of looking busy when you were not since everyone was visible to everyone else, along with the need to "carry the punch cards as if your life depends on it, because your continued employment might".

The slide rule generation is retired now, at least at my workplace. My generation's stories won't be as fun or interesting.