[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 a digital calendar set on the month of July.

The rules are as follows

1) The prisoners can set the digital calendar to any of 31 dates in July. 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.

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

3) The initial setting of the clock is July 1st, and is KNOWN by all prisoners.

4) The time between visits is variable.

If any prisoner can at any point 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 (ie. July 1st is considered as OFF, July 2nd is considered as ON), 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 7, 2010 by bushindo

[unreality]

One prisoner designated as counter, with 99 normals.

the numbers 1 through 31 and their binary equivalents: I'm doing this by hand so correct me if I'm wrong:

1   00001

2   00010

3   00011

4   00100

5   00101

6   00110

7   00111

8   01000

9   01001

10  01010

11  01011

12  01100

13  01101

14  01110

15  01111

16  10000

17  10001

18  10010

19  10011

20  10100

21  10101

22  10110

23  10111

24  11000

25  11001

26  11010

27  11011

28  11100

29  11101

30  11110

31  11111

therefore each of the 31 days can store 5 binaries at once, except for All False (00000). You need 32 (2^5) to fully store 5 binaries, so 31 days allows you to store ALMOST.

Okay, so the calendar starts at 00001 (false false false false TRUE). There are four "spaces" open at a time, the first four bits. A prisoner entering for the first time will look for the rightmost zero and set it (ie, make the bit equal to 1). The rightmost bit will always stay 1, so really we're only holding four positions at a time.

When the counter comes in and sees July 31st, he adds 4 to his count and resets it to July 1st. Then those four that marked themselves never mark it again.

it starts at July 1st. If it's your first visit, advance the day by 1. Otherwise leave it. If it's july 31st, then leave it.

When the counter comes in and sees July 31st, he adds 30 to his count and resets it to July 1st.

Once his count hits 90, he only needs to reset when the date gets to July 11th.

same thing as before - if it's your first visit, advance 1 day. Don't advance past July 31st.

The counter then resets it to July 1st EVERY TIME he goes into the room, and adds the count. For example if he goes in and it's at July 8th, he adds 7 to his count and resets it. Then he goes in and it's still at July 1st. He adds zero and leaves. He returns to find it July 31st. He adds 30 and leaves. etc. Until 100

[bushindo]

One prisoner designated as counter, with 99 normals.

the numbers 1 through 31 and their binary equivalents: I'm doing this by hand so correct me if I'm wrong:

1   00001

2   00010

3   00011

4   00100

5   00101

6   00110

7   00111

8   01000

9   01001

10  01010

11  01011

12  01100

13  01101

14  01110

15  01111

16  10000

17  10001

18  10010

19  10011

20  10100

21  10101

22  10110

23  10111

24  11000

25  11001

26  11010

27  11011

28  11100

29  11101

30  11110

31  11111

therefore each of the 31 days can store 5 binaries at once, except for All False (00000). You need 32 (2^5) to fully store 5 binaries, so 31 days allows you to store ALMOST.

Okay, so the calendar starts at 00001 (false false false false TRUE). There are four "spaces" open at a time, the first four bits. A prisoner entering for the first time will look for the rightmost zero and set it (ie, make the bit equal to 1). The rightmost bit will always stay 1, so really we're only holding four positions at a time.

When the counter comes in and sees July 31st, he adds 4 to his count and resets it to July 1st. Then those four that marked themselves never mark it again.

it starts at July 1st. If it's your first visit, advance the day by 1. Otherwise leave it. If it's july 31st, then leave it.

When the counter comes in and sees July 31st, he adds 30 to his count and resets it to July 1st.

Once his count hits 90, he only needs to reset when the date gets to July 11th.

same thing as before - if it's your first visit, advance 1 day. Don't advance past July 31st.

The counter then resets it to July 1st EVERY TIME he goes into the room, and adds the count. For example if he goes in and it's at July 8th, he adds 7 to his count and resets it. Then he goes in and it's still at July 1st. He adds zero and leaves. He returns to find it July 31st. He adds 30 and leaves. etc. Until 100

This is the answer. With the middle method above, my calculation shows that it takes an average of about 900 visits until a win, which is a vast improvement over the 99000 visits needed for the light-switch case. I suspect the improvement at the bottom at the above post can cut the expected number of visits down a couple hundred more. Great work, unreality.

[Guest]

^ How did you come to an average of 900 visits? it is possible that it would take infinity visits...

[bushindo]

^ How did you come to an average of 900 visits? it is possible that it would take infinity visits...

It is possible to take an infinity number of visits, but the chance of that happening approaching 0. Just like the chance of flipping an infinite number of heads in a row with a fair coin, it is possible but the chance of it happening is approaching 0. The average number of visits is how long it would take a typical game to win (not entirely correct definition, but it will do).

The expected number of visits until the calendar goes from July 1st to July 31th for the first time is

100/99 + 100/98 + 100/97 + ... 100/70

Then the expected number of visits until the counter goes in is 100/1

The expected number of visits until the calendar goes from July 1st to July 31th for the second time is

100/69 + 100/98 + 100/97 + ... 100/40

Then the expected number of visits until the counter goes in is 100/1

Repeat twice more, and summing up all the expected times, we get

Expected trips = 100*4 + ( 100/99 + 100/98 + ... 100/2 + 100/1 ) = 917

Edited July 8, 2010 by bushindo

[Guest]

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 a digital calendar set on the month of July.

The rules are as follows

1) The prisoners can set the digital calendar to any of 31 dates in July. 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.

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

3) The initial setting of the clock is July 1st, and is KNOWN by all prisoners.

4) The time between visits is variable.

If any prisoner can at any point 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 (ie. July 1st is considered as OFF, July 2nd is considered as ON), 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.

Prisoner 1 is designated as the "captain"

If a prisoner is taken to the room for the first time and the date is less than July, 31, he changes the date to +1. So if the date is July 5, he changes it to July 6. If the date is July 31, he doesn't do anything and will wait for another opportunity to change the date at a later time. Once a prisoner has changed the date, he is done changing dates.

Anytime the captain enters the room, he notes how many prisoners have changed the date since his last visit and resets the date to July 1. If he enters the room and it reads July 8, he knows 7 new prisoners have changed the date. If on his next visit, the date reads July 31, he knows another 30 prisoners changed the date, thus his new total is 37. Once he gets to 99, everyone has entered the room.

[Guest]

Prisoner 1 is designated as the "captain"

If a prisoner is taken to the room for the first time and the date is less than July, 31, he changes the date to +1. So if the date is July 5, he changes it to July 6. If the date is July 31, he doesn't do anything and will wait for another opportunity to change the date at a later time. Once a prisoner has changed the date, he is done changing dates.

Anytime the captain enters the room, he notes how many prisoners have changed the date since his last visit and resets the date to July 1. If he enters the room and it reads July 8, he knows 7 new prisoners have changed the date. If on his next visit, the date reads July 31, he knows another 30 prisoners changed the date, thus his new total is 37. Once he gets to 99, everyone has entered the room.

Ha ha. Now that I checked unreality's answer, not surprised we came up with the same solution. But odd we used the same examples. I guess 7 is a compelling number.

[Guest]

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 a digital calendar set on the month of July.

The rules are as follows

1) The prisoners can set the digital calendar to any of 31 dates in July. 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.

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

3) The initial setting of the clock is July 1st, and is KNOWN by all prisoners.

4) The time between visits is variable.

If any prisoner can at any point 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 (ie. July 1st is considered as OFF, July 2nd is considered as ON), 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.

After I solved this problem, I started thinking of the obvious next level. How efficient can you be if the starting state of the calendar is not known? It feels like knowing the original state is a pretty big cheat. It's easy to turn it into the switch problem by making 31 "on" and any other number "off." But I think I have a much more efficient solution. Before looking at my spoiler, I suggest try to solve this new twist. It's significantly more difficult.

Prisoner 1 is named captain. Everyone else is a "regular" prisoner.

Strategy for the regular prisoners:

First time you enter the room, just observe the state of the calendar and do nothing

On your second visit or a subsequent visit, if the state of the calendar has changed, you are now "activated." Once activated, you will move the date up 1, if the date is not 31. You will move the date a total of two times, and then will become "deactivated" for the rest of the game.

Strategy for the captain:

Upon your first visit to the room, you will "activate" the regular prisoner by changing the date. It's important to make a note of that original state, as towards the end, you may need to get the date off that state in case there some regular prisoners who are stuck.

You should usually move the date to 1 every time you enter the room, but if the original state is very low, like 5, moving it to 6 each time could be more efficient.

On each subsequent visit, make a note of how many prisoners have moved the date up 1. If you moved the date to 6, for example, and on your next visit, it's on 31, move your total count up 25. Once your count gets up to 197, every regular prisoner has entered the room at least once and you win the game.

This solution will take a significant amount of time longer than the original version, but will be much more efficient than resorting to an "on" "off" strategy.

[Guest]

After I solved this problem, I started thinking of the obvious next level. How efficient can you be if the starting state of the calendar is not known? It feels like knowing the original state is a pretty big cheat. It's easy to turn it into the switch problem by making 31 "on" and any other number "off." But I think I have a much more efficient solution. Before looking at my spoiler, I suggest try to solve this new twist. It's significantly more difficult.

Prisoner 1 is named captain. Everyone else is a "regular" prisoner.

Strategy for the regular prisoners:

First time you enter the room, just observe the state of the calendar and do nothing

On your second visit or a subsequent visit, if the state of the calendar has changed, you are now "activated." Once activated, you will move the date up 1, if the date is not 31. You will move the date a total of two times, and then will become "deactivated" for the rest of the game.

Strategy for the captain:

Upon your first visit to the room, you will "activate" the regular prisoner by changing the date. It's important to make a note of that original state, as towards the end, you may need to get the date off that state in case there some regular prisoners who are stuck.

You should usually move the date to 1 every time you enter the room, but if the original state is very low, like 5, moving it to 6 each time could be more efficient.

On each subsequent visit, make a note of how many prisoners have moved the date up 1. If you moved the date to 6, for example, and on your next visit, it's on 31, move your total count up 25. Once your count gets up to 197, every regular prisoner has entered the room at least once and you win the game.

This solution will take a significant amount of time longer than the original version, but will be much more efficient than resorting to an "on" "off" strategy.

Why does each prisoner have to change it twice? Make it once each and also have the leader move it up one himself if he ever comes in and the calendar hasn't moved since his last visit (maybe best to move it to a date he knows nobody has seen yet if possible).

More efficiency can be squeezed out if the counter is smart about where he moves it to (as you mentioned). Prisoners are most likely to get "stuck" at numbers near the date he sets as "zero" as well as the date he saw when he first visited the room.

[Guest]

i guess i don't see why everyone can't be a captain.

each prisoner advances the date by 1. if 31, go back to 1. once a prisoner enters three times, if each time the date is less than the date before, then he knows the other 99 prisoners have entered.

[Guest]

i guess i don't see why everyone can't be a captain.

each prisoner advances the date by 1. if 31, go back to 1. once a prisoner enters three times, if each time the date is less than the date before, then he knows the other 99 prisoners have entered.

sorry small correction, i should note that it may take more than 3 entries depending on how much less the next entry is.

[Guest]

Why does each prisoner have to change it twice? Make it once each and also have the leader move it up one himself if he ever comes in and the calendar hasn't moved since his last visit (maybe best to move it to a date he knows nobody has seen yet if possible).

More efficiency can be squeezed out if the counter is smart about where he moves it to (as you mentioned). Prisoners are most likely to get "stuck" at numbers near the date he sets as "zero" as well as the date he saw when he first visited the room.

Silly me. The two visits part was a remnant from the switch problem. With your solution, there is very little efficiency lost due to the unknown starting state. Pretty cool.