[bushindo]

This is an variation on the 100 prisoners and the light bulb.

Suppose that there are 100 prisoners who are involved in a game. Each one of them has a chance to enter a room with five light switches. Each switch can be set to an OFF position or an ON position.

The rules are as follows

1) The prisoners MUST flip either 1 or 2 switches of their choice during their turns. Flipping a switch here means changing the state of a light switch to the opposite of its current state. Not flipping anything during a turn is NOT an option.

2) They can not communicate to the other prisoners in ANY other fashion once the game starts. The prisoners are free to develop a strategy beforehand with knowledge of all these rules.

3) The prisoner chosen to enter the room at each turn is selected randomly from the pool of 100 prisoners with equal probability for each.

4) All 5 switches are initially in the OFF position, and this is KNOWN by all prisoners.

5) The time between visits is variable.

If any prisoner can at any point correctly declare that ALL prisoners have been the the room, everyone wins. Otherwise they lose. Obviously this can be reduced to the original light-switch problem (e.g. use only 1 switch to communicate), but that would be vastly inefficient in that it would require many more visits than necessary to win the game. What is the optimal strategy to win the game? Optimal means the expected number of visits to win is smallest.

Edited July 28, 2010 by bushindo

[Guest]

Use the Force, it sounds like you are seeking a modification of the solution presented in an article for 100 Prisoners and a Light Bulb, posted on the CTK Exchange. Basically, it says the claim that 100 prisoners have visited the central living area can be reasonably made in 4 to 5 years. phillip1882's posts seem to venture this direction. Kerry, who posted the probablistic approach did provide other equations that might give a more accurate probability to when the claim can be made, but said that the outcome would not be significant. With the four tally switches, an equation such as Kerry presented might be formulated to give an even more accurate probability, but, again, the outcome would probably not be significant, as the number of visits by the tallyman have no real bearing on the number of visits by the prisoners as a whole.

The basic equation for the possibility of all 100 prisoners to be chosen after a given number of years is:

100^−365y*Sigma_{[k=0 to 100]}[(−1)^k*(100!/(k!*(100-k)!)*(100−k)^365y]

P.S. If your interpretation as to the variablitiy of time between visits applies to each and every visitor, then Kerry's equation loses scope. I understood the variablity applied to the time between visits for a single prisoner (for each prisoner), and that a prisoner visited the central area each day.

[Guest]

Use the Force, it sounds like you are seeking a modification of the solution presented in an article for 100 Prisoners and a Light Bulb, posted on the CTK Exchange. Basically, it says the claim that 100 prisoners have visited the central living area can be reasonably made in 4 to 5 years. phillip1882's posts seem to venture this direction. Kerry, who posted the probablistic approach did provide other equations that might give a more accurate probability to when the claim can be made, but said that the outcome would not be significant. With the four tally switches, an equation such as Kerry presented might be formulated to give an even more accurate probability, but, again, the outcome would probably not be significant, as the number of visits by the tallyman have no real bearing on the number of visits by the prisoners as a whole.

The basic equation for the possibility of all 100 prisoners to be chosen after a given number of years is:

100^−365y*Sigma_{[k=0 to 100]}[(−1)^k*(100!/(k!*(100-k)!)*(100−k)^365y]

P.S. If your interpretation as to the variablitiy of time between visits applies to each and every visitor, then Kerry's equation loses scope. I understood the variablity applied to the time between visits for a single prisoner (for each prisoner), and that a prisoner visited the central area each day.

About your P.S. first, I didn't see anything in the problem that said that one prisoner would be brought to the room with the switches each day. I was under the impression that "time between visits is variable" meant that time between every visitor (not just one prisoner) is variable. In other words, the first prisoner to enter the room goes in and then 5 minutes later the second prisoner to enter the room might go in. Then there might be a three day gap before a third prisoner goes in. I would assume that one would assume that the time between visits for a single prisoner would vary simply because they are chosen randomly. Even if one prisoner went into the room per day then the time between visits for one individual would still vary. Thus, I interpreted "time between visits is variable" to mean time between every visit by any prisoner to the room varies. Thus, the only information you have is what the switches say and what you remember them saying on previous visits. You know nothing about how many prisoners have gone before you since your last visit, etc (as you would if one prisoner went each day). Is this the correct condition of the problem? Or did I misinterpret it?

As for my method I have a simple modification. The modification is that I can use your 16 count system from 0 to 15 and have the 15th count repeat back to 0000. I didn't realize before that the only count that has to be able to be reset to 0000 with one switch is the last count in the cycle. None of the other counts ever get reset. Thus, your 15 count system works for this method. Thus, my method is just your method except that there is no designated tallyman and also when the count is at 15 and someone visits the room for their first time, then they add one to the count by resetting it to 0000.

I also recently realized that the count will always stop going up at the same point. That's because 100 prisoners will have added 1 to the count (resetting it counts as adding a count). Thus it will start at 0000, the first 15 new prisoners to enter the room will bring the count up to 15. Then the 16th new prisoner will reset it to 0000 and the 17th will bring it to the first count, the 18th to the second count, etc. Thus, the cycle will repeat itself 6 times completely and on the 7th time will stop on the fourth count (16*6+4=100). The 4th count is the 4th count after 0000, so for your count system it is 1101:

_0 0000 _0

_1 1100 12

_2 1111 15

_3 1110 14

_4 1101 13

A prisoner will guess that all 100 prisoners have been to the room after visiting the room n consecutive times and seeing a count of 4 (1101) on all n occasions. I think it would be quite simple to make a program to simulate this prisoner-light-switches game using this method to test what the best value of n would be. Obviously a high n value would cause the chances of a win (a correct guess that all 100 prisoners have been to the room) to increase and approach 100%. On the other hand, a low n value would result in a lower winning percentage, but would also result in fewer visits to the room, thus making it a more efficient way to win the game. If I had such a program to test out this method, I would try n values of 3, 4, and 5 first.

I think that this method might be better than your method of a designated tallyman because in this method a guess is made (that all 100 prisoners have been to the room) by the first prisoner to see a count of 4 (1101) n times. Because this means that you are giving 100 prisoners the opportunity to recognize that everyone has most likely entered the room, rather than a single tallyman prisoner, you are avoiding the possibility that there might be an unlucky streak and the tallyman might not be picked to go into the room for his (m+1)th time until 500 prisoner-visits after the tallyman's mth visit. So in my method the prisoner who is eventually the one who guesses that all prisoners have been to the room might have visisted the room a total of 10 times, but the total number of visits to the room by all prisoners might only be 500 (and thus the prisoner who makes the guess to end the game just got selected more commonly than average).

Actually now that I think about it, the expected number of visits before all 100 prisoners have entered the room is independent of the method used by the prisoners to figure out when they have all gotten to the prison. Thus, the best strategy for this game is really the strategy that realizes that all 100 prisoners have visited the room as soon as possible after it became true that all 100 prisoners visited the room. Because of this, I would again think that my strategy (where everyone is a tallyman) might be more efficient than yours (where there is only one prisoner). I would think this because your tally man might have a count of 94 and then the next time he visits he gets a count of 98 and then the next time he visits he gets a count of 99 and cashes in for victory, but unfortunately chance alone might result in 500 visits to the room in between the two visits in which the tallyman had a count of 98 and a count of 99. In my method, as soon as any prisoner visited the room n times (3,4,5?) after all 100 prisoners have entered the room (and thus after the count is at 4), then he would recognize that everyone has very likely been there (by the fact that the count remains at 4 for n of his consecutive visits) and guess and win the game. There would be a max of ~n100 visits to the room after all 100 prisoners have entered the room in my system (although it would likely be a lot less than n100 because some prisoners would, by chance, be picked more often than every 100 visits), but in your system the tallyman could get unlucky and not show up for a good while after.

Another reason why my system may be more efficient is because my system allows every new prisoner to add 1 to the count (this is because the count system is a cycle). On the other hand, in your system a prisoner might visit the room and see that it is maxed out at 15 and then proceed to use the placebo switch and wait until next time to record with the count that he has visited the room. This would mean that your tallyman would likely find out (with confidence) that every prisoner has entered the room a long while after every prisoner actually has entered the room. So the problem with your system's efficiency is that there are 100 prisoners, but the count only goes to 15, so a lot of prisoners who visit the room will have to use the placebo switch because there will be no room to record that they have been there.

I will also note that in my system the only way that someone would guess wrongly would be if they visited the room n times and saw a count of 4 n times, but there were still either 16, 32, 48, 64, 80, or 96 prisoners who have yet be to the room. I ask, what are the chances that 84 prisoners have been to the room and then one of those 84 prisoners arrives at the room n times before an of the 16 remaining prisoners gets chosen to get to the room? I would say slim, even for an n as low as 3. I think an n of 4 or 5 would make it very slim, thus causing the game to be won with this strategy to rise to close to 100% (at least in the upper 90s%).

What do you think? I think it would be very helpful and interesting to make two computer programs (one for each of our strategies) and see how often mine wins if you give it a strategy that ends the game a couple hundred prisoner-visits faster (on average) than your system takes. I would bet that it could be adjusted (n value would be adjusted) to win over 95% of games and be significantly more efficient/optimal than your system (in terms of total number of visits by all prisoners to the room during the game). Do you know of anybody that could make a program for this (I don't know how, but I think it would be simple enough for anyone who knows how to program)?

Thank you for providing the info for me in your last post. I appreciate that there are people out there (like you) who are willing to help me discover how efficient this cycle-count system would be verses your tallyman-count system.

[Guest]

i decided to run a few simulations. I'm a bit uncertain of your strategy, Force, do the prisoners only count when it reaches their number again? or do they count the way i specified in my posts plus number of entrances? or is it as i think and a roll over thing, that is if it reaches their number or higher they count?

with my simulation, i sought to find the minimum number of entrances required to get all 100 prisoners in with perfect knowledge. (that is as soon as all 100 prisoners are in they declare.) it seems the average is about 570 entrances, with max average prisoner count under my method of 228.

[Guest]

i decided to run a few simulations. I'm a bit uncertain of your strategy, Force, do the prisoners only count when it reaches their number again? or do they count the way i specified in my posts plus number of entrances? or is it as i think and a roll over thing, that is if it reaches their number or higher they count?

with my simulation, i sought to find the minimum number of entrances required to get all 100 prisoners in with perfect knowledge. (that is as soon as all 100 prisoners are in they declare.) it seems the average is about 570 entrances, with max average prisoner count under my method of 228.

The first time any prisoner enters the room they add one to the count. They do this whether the count is at 0 or whether it is at 15. If it's at 15 they add one to it by changing it back to 0. Thus, yes, the counts do "role over." It is a cycle that is 16 long. Thus, after 6 cycles (6*16=96 different prisoners) it will return to 0 and it will only need the 4 remaining prisoners (bringing the count to 4).

I think it might be helpful for each prisoner to keep track of how many prisoners they know have been to the room with the light bulb, but I don't think that it would help the odds too significantly. If you wanted to add this into your program (it might be a little complicated) then you would do so by having each prisoner keep a tally of how many prisoners they know have been in the room. For example, say a prisoner goes into the room for his first time and sees the count at 5 then changes it to 6 and leave. The next time he arrives at the prison he might see the count at 12. This would mean that he would know for certain that at least 6 prisoners have entered the room. So you can have the prisoner record this number (6) and also record the fact that it is his second time in the room and that the count is still not at 4.

Eventually, after the prisoner visits the room a few times he should find the count stopped at 4. This could happen 1 in 16 times by chance, but it will also happen once all 100 prisoners have entered the room. Thus, my strategy to win the game is a "guess." You play a statistics game and have a prisoner "guess" that all 100 prisoners have entered the room as soon as he enters the room n times (say 4 or 5 as the n value to start) in a row and sees the count at 4 all of those times. The probability that after these 4 times seeing the count at 4, that all 100 prisoners have NOT been to the room, is very very slim. If it's at 4 and all 100 prisoners have not been to the room then that means that there are at least 16 prisoners who have not been to the room (there could be 32, or another multiple of 16 as well). Thus, statistically if you have the n value high enough (at least 4 I would say, maybe 5 or 6), then you should guess correctly almost always (high 90%s) and win the game. I think if you play by this strategy though you will find that you will win the game in fewer total visits to the light bulb by all prisoners, than in Dej Mar's method. This is because everybody acts as a tallyman and also because the tally doesn't max out at 15, but rather goes in a cycle, thus meaning that you record every time somebody gets to the room for the first time (unlike in Dej Mar's method where it may be maxed out at 15 and thus someone new to the light bulb room would have to wait until his next visit (or the one after that possibly) in order to record that he has been there).

As for, "with my simulation, i sought to find the minimum number of entrances required to get all 100 prisoners in with perfect knowledge. (that is as soon as all 100 prisoners are in they declare.) it seems the average is about 570 entrances, with max average prisoner count under my method of 228." Because the prisoners are chosen randomly, it's possible that a prisoner won't be chosen (due to chance alone) to go into the room at all until the millionth prisoner is chosen. Thus, your "max average" of 228 doesn't make any sense. There is no max. Due to chance alone it might take a million visits to the room before the 100th prisoner finally shows up thus causing the "average prisoner count" to be 10,000.

Thanks for replying. I think to do a program for my method just have a count from 0 to 15 and make it so that when a prisoner gets there for the first time he adds one to the count (or resets it back to 0 if the count is at 15 when he arrives). Then program it so that when a prisoner arrives in the room to see a count that says 4 on n consecutive occasions have him guess that all 100 prisoners have been to the room (make n=4 to start). Then after each guess just see how many total prisoners have been to the room and check to see if he guessed correctly that all 100 prisoners had been to the room at least once.

Also, I think it would be good to make a program for Dej Mar's method so we can compare the strategies to see which is more efficient. The "expected" number of visits is hard to calculate perfectly, so I think just running a program a few times would do the trick.

[Guest]

okay, what i'm trying to figure out is what happens on the second and third entrance under your method.

let's say a prisoner enters once and sees 10. then he enters a second time and sees 15. then he enters a third time and sees 4.

how many prisoners should he guess have been in the room so far under your stategy? under my strategy, he would guess 35. i'm thinking that under your strategy, he only adds 31, and only if greater than or equal to his number on the second run through.

ie. 10 on first enter, 15 on next enter, 4 on next enter, 12 on next enter, you have now passed 10, so count 31.

[Guest]

okay, what i'm trying to figure out is what happens on the second and third entrance under your method.

let's say a prisoner enters once and sees 10. then he enters a second time and sees 15. then he enters a third time and sees 4.

how many prisoners should he guess have been in the room so far under your stategy? under my strategy, he would guess 35. i'm thinking that under your strategy, he only adds 31, and only if greater than or equal to his number on the second run through.

ie. 10 on first enter, 15 on next enter, 4 on next enter, 12 on next enter, you have now passed 10, so count 31.

He enters once and sees 10. Because this is his first time in the room he adds one to the cout making it say 11. Thus, including himself he knows that at least 11 different prisoners have been in the room so he adds 11 to the total number of different prisoners that he knows have definitely entered the room (because it would take 11 prisoners to change the count from 0 to 11). It's possible that 27 prisoners (or 11+16x prisoners where x goes from 0 to 5) have really entered the room, but he can only be certain that that at least 11 different prisoners entered the room.

Then, the second time he enters the room he sees 15. Again, the cycle could have repeated past 11 and ended up on 15, but the prisoner doesn't know this so again he can only add 4 (15-11) to his count. Thus, now his total is at 15.

Let's say the next time he enters the room he sees the count at 4. He now can add 5 new prisoners to his tally list totaling 20 prisoners that he know have definitely entered the room. In reality, 20, 36, 52, 68, 84, or 100 different prisoners may have been to the room, but the prisoner can only be sure of 20. Thus, this is not the way that the prisoner eventually goes about deciding that he will guess that all 100 prisoners will get to the room. It is very very likely that this prisoner or any other prisoner's personal prisoner count will ever get to 100.

Thus, the strategy for guessing that all 100 prisoners have been to the room is when it appears that the count has stopped on count 4. Note that the count WILL stop on the 4th count after all 100 prisoners have gotten to the room, simply because when you start at 0 and add 100 to this count system that is a cycle of 16 counts, the 100th +1 will bring you to the 4th count.

So if you make the "n" value that I was talking about n=100, then after 100 times that a prisoner enters the room and sees the count still at 4, then he will guess that all 100 prisoners have been to the room. Statistically, he is EXTREMELY confident that he is correct, so he is almost guaranteed to guess correctly. However, this is not a very efficient way to win the game. I would think that Dej Mar's method would be a lot more efficient in terms of the number of prisoners who enter the room before the game is won. Thus, we must lower the n value from 100 to something like 4 or 5. Then, after a prisoner sees that the count is at 4 when he enters the room n times (e.g. 4 times), then he can guess with a good amount of confidence statistically, that all 100 prisoners have been to the room.

Did that clear things up? If not, I would be glad to try and it explain it even more.

About your strategy, how could he possibly know that at least 35 different prisoners have entered the room upon seeing those 3 different counts the first 3 times he enters the room? I'm going to clarify that my count system only goes from 0 to 15 (using 4 switches) because we need the 5th switch as a placebo switch. This is because everyone MUST move at least one switch each time they enter the room and thus we must give the people who have already been in the room a switch to move.

[Guest]

use the force, you spend more time explaining how he doesn't do it versus how he does.

i don't need my method explained back to me. i need your method explained better.

okay let's just use 4 switches as an example.

you seem to be using 1 dummy switch. okay.

0000 start.

prisoner 5 enters. he flips the dummy switch and increases the count by 1.

0011

prisoner 21 enters. does the same. he can count 1.

0110

prisoner 80 enters. he can count 2.

0101

prisoner 5 enters again. he can count 3, bringing his total to 4.

1100

prisoner 12 enters. he can count 4.

continue from here, or if your method is different change as necessary.

[Guest]

By the way, what do you use to make your programs?

[Guest]

use the force, you spend more time explaining how he doesn't do it versus how he does.

i don't need my method explained back to me. i need your method explained better.

okay let's just use 4 switches as an example.

you seem to be using 1 dummy switch. okay.

0000 start.

prisoner 5 enters. he flips the dummy switch and increases the count by 1.

0011

prisoner 21 enters. does the same. he can count 1.

0110

prisoner 80 enters. he can count 2.

0101

prisoner 5 enters again. he can count 3, bringing his total to 4.

1100

prisoner 12 enters. he can count 4.

continue from here, or if your method is different change as necessary.

I don't understand your method above. Why do you have the first prisoner to enter the room (#5) flip the dummy switch? All he has to do is increase the count by 1. Also, why do you have prisoner 5 bring his total to 4 when only 3 different prisoners have been to the room (5,21,80)? That's only 3 different prisoners, not 4. I also don't understand how your method ends. When does someone find out that all 100 prisoners have been to the room at least once and how do they find that out?

The simple version of my method is that one switch is used as a dummy switch and the other 4 are made to use as a counting system that acts as a cycle starting at 0 and going to 15. Once it gets to 15, the next +1 brings it to 0 and it continues in a cycle. This is how prisoners behave: The first time a prisoner enters the room he adds 1 to the count. The second, third, fourth, fifth, etc time a prisoner enters the room he flips the dummy switch (and leaves the count alone, but takes note of what the count is at (0-15)). If a prisoner should enter the room n=4 times in a row (say on his 3rd, 4th, 5th, and 6th visits) and sees that the count is at 4 on all n=4 of those visits, then he declares that all 100 prisoners have been to the room. This is a guess, but the greater "n" is, the more confident he can be that he is correct and thus the more confident he is that he will win the game.

Now, my method can be made slightly more complex by making the "n" value unique for each prisoner: Make the "n" value a function of how many times each prisoner has entered the room, how many times in a row he has seen the count say 4, and how many prisoners he knows have reached the room (e.g. "at least 20" or "at least 36"). You can ignore this n-as-a-function thing when you write your program though for simplicity's sake. I don't think it would be a very significant improvement, so just make n a constant (n=4, or maybe n=5).

Edited August 7, 2010 by Use the Force

[Guest]

okay i think i understand now.

i use python. a fairly simple programming language.

after running my simulation, i found n can actually be 1, and still have 100% success!!!

here's my code.

import random

success = 0

#declare array to keep track of number of enters.

enter = [0]*100

#declare counter array (know what count it is on.)

counter = [0]*100

#declare array to keep track of number of times see same number.

same = [0]*100

switch = 0

for i in range(0,100000):

   while True:

      #pick a random inmate

      pick = random.randint(0,99)

      #if enter first time, set "counter" to current number, and increase the switch

      if enter[pick] == 0:

         counter[pick] = switch

         switch += 1

      #if enters again and see same number, increase "same" for declare win

      elif counter[pick] == switch:

         same[pick] += 1

      #if enters more than once and doesn't see same number, then "same" starts over.

      else:

         same[pick] = 0

         counter[pick] = switch

      #cycle the switch around from 15 back to 0.

      if switch == 16:

         switch = 0

      #once "same" hits "n", declare win

      if same[pick] == 1:

         break

      enter[pick] += 1

   #check to see if actually won

   check = True

   for i in range(0,100):

      if enter[pick] == 0:

         check = False

         break

   if check:

      success += 1

   #reset arrays for next sim.

   for i in range(0,100):

      enter[i] = 0

      same[i] = 0

      counter[i] = 0


print(success)

[Guest]

okay i think i understand now.

i use python. a fairly simple programming language.

after running my simulation, i found n can actually be 1, and still have 100% success!!!

here's my code.

import random

success = 0

#declare array to keep track of number of enters.

enter = [0]*100

#declare counter array (know what count it is on.)

counter = [0]*100

#declare array to keep track of number of times see same number.

same = [0]*100

switch = 0

for i in range(0,100000):

   while True:

      #pick a random inmate

      pick = random.randint(0,99)

      #if enter first time, set "counter" to current number, and increase the switch

      if enter[pick] == 0:

         counter[pick] = switch

         switch += 1

      #if enters again and see same number, increase "same" for declare win

      elif counter[pick] == switch:

         same[pick] += 1

      #if enters more than once and doesn't see same number, then "same" starts over.

      else:

         same[pick] = 0

         counter[pick] = switch

      #cycle the switch around from 15 back to 0.

      if switch == 16:

         switch = 0

      #once "same" hits "n", declare win

      if same[pick] == 1:

         break

      enter[pick] += 1

   #check to see if actually won

   check = True

   for i in range(0,100):

      if enter[pick] == 0:

         check = False

         break

   if check:

      success += 1

   #reset arrays for next sim.

   for i in range(0,100):

      enter[i] = 0

      same[i] = 0

      counter[i] = 0


print(success)

This looks pretty good from what I can tell. When you said, "after running my simulation, i found n can actually be 1, and still have 100% success!!!" you lost me for a bit. If n=1 then my method is a guaranteed fail. n=1 means the first time a prisoner enters the room and sees the count at 4 then he declares that all 100 prisoners have entered the room. This guarantees a loss. But, after reading your simulation I think that you interpreted n differently than I did: I would consider your n=1 as an n=2. A prisoner must enter the room twice and see the same count (a count of 4) on both consecutive visits before declaring that all 100 prisoners have entered the room. I believe that this is what you did in your program, but you called it an n=1. I would call it an n=2 because the prisoner visits the room 2 times in a row seeing the same count (a count of 4) both times.

I have a question about your program though. Do you take into account the fact that the count must be at 4 in order to declare a win? You have, "#if enters again and see same number, increase "same" for declare win" in your program. To me this just appears as though if the number is the same as the previous visit then you increase "same," but it should only increase "same" if it is the same count as the previous visit AND the count is at 4. We know the count will end at 4 because if you start at 0 (as the count does) and each of the 100 prisoners add +1 to it, then it will go through the 16-count-cycle 6 full times plus 4 more, bringing it to a count of 4. It is important to include this in the program because it will reduce the chance that a prisoner lands on a count that says 7 (as an example) multiple times in a row and guesses that all 100 prisoners have entered the room, when we know with certainty that it is NOT true that all 100 prisoners have entered the room (the only way that all 100 prisoners can have entered the room under this method is if the count is at 4).

Also, I don't think that n=2 has a 100% win rate. How many times did you run the simulation? N=2 (that you called n=1, but used in your program) doesn't statistically confirm that all 100 prisoners have entered the room. By chance someone could easily be chosen to go into the room for a second time and there is a roughly ~1/16 chance that they will see the same count as last time. This does not necessarily mean that all 100 prisoners have entered the room. This could happen by chance moderately commonly.

For " #check to see if actually won

check = True

for i in range(0,100):

if enter[pick] == 0:

check = False

break

if check:

success += 1

"

Shouldn't i only be i the range (0,99)? You have (0,100), but that seems like 101 prisoners to me.

Also, I don't think you added anything into your program to tell how many total visits there were to the room. I would think that this would be very important so that we can compare the efficiency of this method to Dej Mar's method, etc, to see if it wins in fewer visits.

Note: About the program (Python). Which version are you using? I'm going to try to do some programming with this myself and I'm wondering if it matters if I get Python 2.7 or Python 3.1.2 (the two recommended versions).

[Guest]

I downloaded/installed Python 2.7, but it might take some time for me to learn it.

Edited August 8, 2010 by Use the Force

[Guest]

after reading your simulation I think that you interpreted n differently than I did: I would consider your n=1 as an n=2. A prisoner must enter the room twice and see the same count (a count of 4) on both consecutive visits before declaring that all 100 prisoners have entered the room. I believe that this is what you did in your program, but you called it an n=1. I would call it an n=2 because the prisoner visits the room 2 times in a row seeing the same count (a count of 4) both times.

basically i made it so if a prisoner enters twice, first time, then immediately again second time, he won't call "win" yes. he doesn't read his own increment as the necessary number. if it cycled around again and hit the number he was on, then he would declare win on entering, thus i say n = 1.

Do you take into account the fact that the count must be at 4 in order to declare a win?

the only way that all 100 prisoners can have entered the room under this method is if the count is at 4

no, I didn't, which is weird that i get a 100% success rate.

How many times did you run the simulation?

100,000, any more would take too long to run the program. and i got 100,000 successes.

Shouldn't it only be in the range (0,99)? You have (0,100), but that seems like 101 prisoners to me.

python ends one less than the max number, except with the random function which ends on it.

if it was wrong i would get an array out of bounds error.

Also, I don't think you added anything into your program to tell how many total visits there were to the room.

i didn't print it out, but i could easily use the enter array for this.

Edited August 9, 2010 by phillip1882

[Guest]

i went ahead and added the code for number of enters.

also i corrected a "severe" bug. i have enter[pick] in my for loop rather than enter.

now i get much more sane results. i went ahead and made it such that switch has to be 4 as well.

with n = 2, 95935 out of 100,000 wins, 534 average entrances.

with n = 3, 99732 wins, 591 average entrances.

with n = 4, 99986 wins, 634 average entrances.

[Guest]

i went ahead and added the code for number of enters.

also i corrected a "severe" bug. i have enter[pick] in my for loop rather than enter.

now i get much more sane results. i went ahead and made it such that switch has to be 4 as well.

with n = 2, 95935 out of 100,000 wins, 534 average entrances.

with n = 3, 99732 wins, 591 average entrances.

with n = 4, 99986 wins, 634 average entrances.

Fantastic! Thanks, those results look similar to what I was guessing. So now my question is: If you create a program for Dej Mar's method and do 100,000 simulations, what will be the average number of entrances? I would guess at least 700 and if that is true, wouldn't my method be more efficient? I think a .3% chance of guessing wrongly is worth it if you decrease your average entrances by over 100. That sounds like a great risk to take to me.

If any prisoner can at any point correctly declare that ALL prisoners have been the the room, everyone wins. Otherwise they lose.... What is the optimal strategy to win the game? Optimal means the expected number of visits to win is smallest.

Given that this is the problem we are trying to solve, I would think that it would be okay to get rid of a 100% win rate in exchange for a 99.7% win rate if that also causes the expected number of visits to decrease by 700ish to 591.

So if you could do this last favor for me (make a program for Dej Mar's method... only a slight modification from my n-method) in order to check to see what the average number of entrances is (an approximation of the expected number of entrances) then I would be very content and finished with asking you to use your programming-skills (that I lack) to answer all of these questions for me. Again, thank you for taking the time to do these programs for me. I very much appreciate it.

[Guest]

now maybe you could explain dej mar's method to me. i know he only has 1 tally man, but anything else i should know?

[Guest]

now maybe you could explain dej mar's method to me. i know he only has 1 tally man, but anything else i should know?

The lone tallyman is designated before the game begins. The count starts at 0 and goes to 15.

When a prisoner (other than the tallyman) goes into the room he adds one to the count unless the count is maxed out at 15 (in which case he flips the dummy switch) or if he has already added one to the tally before (in which case he flips the dummy switch).

When the tallyman enters the room he adds whatever the count is at to his personal prisoner tally in his brain. Then he resets the count to 0. Once he is able to enter the room and bring his tally in his brain to 99, then he will know that all 99 other prisoners (plus himself) have entered the room and he will declare that to win the game.

Make sense? If not, I'll be glad to answer any more questions.

Edited August 10, 2010 by Use the Force

[Guest]

sorry dej mar, good news, you get 100% for success rate, bad news you get about 1,211 average entrances.

[Guest]

sorry dej mar, good news, you get 100% for success rate, bad news you get about 1,211 average entrances.

I thought that it would be a lot higher than 700. So I was right, 700 for Dej Mar's strategy is a lot better than average.

591 expected number of entrances @ 99.7% win rate (my method) or 1211 expected number of entrances at 100% success rate (Dej Mar's method)? I guess my strategy is better then. Are you sure your program is right about the 1211 (it sounds about right)? If so, I think I should ask bushindo to change which method he deems the solution to his riddle.

[Guest]

yeah I modified my method a bit after i reread your post, second time through i got closer to 1000.

(orignally i had him only reset switch if it was 15, now he always resets switch.)

Edited August 10, 2010 by phillip1882

[Guest]

yeah I modified my method a bit after i reread your post, second time through i got closer to 1000.

(orignally i had him only reset switch if it was 15, now he always resets switch.)

591 (99.7% win) is still better than 1000. Do you think my method is the best one given yet for this prisoner-problem? If not, what is a better strategy?

[Guest]

i have to agree that seems very well thought out valid method, i don't see how you could do any better in terms of accuracy and efficiency.

[Guest]

i have to agree that seems very well thought out valid method, i don't see how you could do any better in terms of accuracy and efficiency.

Well I think the method could be improved slightly by developing a function to determine an "n" value for each specific prisoner. In this way, "n" wouldn't have to always be 3, but could be less. For example, we said that it was very unlikely that a prisoner's personal prisoner count ever reached 100, but it IS possible as long as a prisoner was luckily chosen to enter the room at the right times (e.g. every time the count says 0 and every time the count says 15 (and then when it is at the 4th count at the end) because this would allow him to count each prisoner before the count resets and he misses his opportunity). Thus, in a rare instance like this, a prisoner might be completely certain that all 100 prisoners have been to the room. And it also might be his only time coming to the room and seeing a count 4. Thus, he would be able to declare a win without seeing a count of 4 n=3 times. There are many other small things like this that would improve the efficiency of this method beyond the simple n=3, but I don't think they are worth putting into your program. All in all though, I do think that this method of a count that acts as a cycle and stops at a certain known count as soon as all 100 prisoners have added 1 to the count is the best method. Too bad bushindo already declared Dej Mar's method the best. I was late on the discussion. Thanks for making the programs for me though, I really appreciate it. Without them I wouldn't have known for sure that my method is more efficient than Dej Mar's.