[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]

The 5th switch will remain untouched, when each prisoner comes into the room, if it's his first time, he'd add 1 to the binaric number of the 4 switches, i.e if it were 0000 he'd make it 0001, if it were 0001 he'd make it 0010, if the switches had reached 1111 the prisoner would just skip his turn, he'd do that by flipping the 5th switch...

A counter is picked, each time the counter comes into the room he'd sum the binary number in the switches and reset them to 0, once he has 99 he'd know that everyone has been to the room

Use the first two switches as a 2-digit binary number and the 3rd and 4th as another separate 2-digit binary number, so instead of having from 0000 (0) to 1111 ((15) you'd have from 00-00 to 11-11 (3-3), it'd go slower but it'll work...

[Guest]

I forgot, the counter is also bounded to the2 switch rule, so I guess maybe they'd use only the first and second switches, and the third and fourth perhaps be another separate number but only used once, or if the counter comes in he resets the larger number and doesn't add the second number to his count...

Edited July 28, 2010 by Anza Power

[Guest]

basically you can use the grey code to solve this one.

00000

00001

00011

00010

00110

00111

00101

00100

01100

01101

etc. only one light switch at a time need be flipped with each prisoner, and each prisoner can tell how many have gone before him by the switches represented. one one prisoner enters there times or more and can tell by the number that 99 have gone before, you're set.

[Guest]

The prisoners choose a tallyman.

Of the 5 switches, the prisoners can assign the first switch as a placebo switch. The other four can then be used for a tally.

The first time a prisoner, other than the tallyman, enters the room without having previously incremented the tally with the switches, increments the tally. He otherwise switches the placebo switch. When the chosen tallyman enters the room he adds the tally to the total and then resets the tally switches back to 0000.

In regard to the tally switches, though they would be used as a binary tally, one could not simply increment or read them as in the base 2 sequence of numbers as only up to two switches may be flipped. Base 2 numbers for 7, 11, 13, 14 and 15 each uses three 1's, as the tallyman would need reset the tally by flipping only one or two switches, these numbers can not be used. Even with skipping 7, the sequence still needs altered to allow only one or two switches to be used each visit. One possible sequence that might be chosen is 1, 2, 3, 6, 5, 4, 8, 9, 10, 12 to represent the sequence 1 to 10.

When the tallyman has totalled a tally of 99, he can then declare that all 100 prisoners have visited the room.

+----+

The minimum number of needed visits to the room by the tallyman: 10.

The minimum number of years required, with an average visit of once every 100 days, for the tallyman to be able to declare with certainty that all 100 prisoners have entered the room.: 3 (~=2.822).

[Guest]

0: 0000

1: 0001

2: 0010

3: 0011

4: 0110

5: 0100

6: 0101

7: 1001

8: 1010

8: 1100

10:1000

I can't think of any way to make them easier to remember, but this way you'd have a system where you can level up one number and reset them every time with only flipping two switches...

[bushindo]

The prisoners choose a tallyman.

Of the 5 switches, the prisoners can assign the first switch as a placebo switch. The other four can then be used for a tally.

The first time a prisoner, other than the tallyman, enters the room without having previously incremented the tally with the switches, increments the tally. He otherwise switches the placebo switch. When the chosen tallyman enters the room he adds the tally to the total and then resets the tally switches back to 0000.

In regard to the tally switches, though they would be used as a binary tally, one could not simply increment or read them as in the base 2 sequence of numbers as only up to two switches may be flipped. Base 2 numbers for 7, 11, 13, 14 and 15 each uses three 1's, as the tallyman would need reset the tally by flipping only one or two switches, these numbers can not be used. Even with skipping 7, the sequence still needs altered to allow only one or two switches to be used each visit. One possible sequence that might be chosen is 1, 2, 3, 6, 5, 4, 8, 9, 10, 12 to represent the sequence 1 to 10.

When the tallyman has totalled a tally of 99, he can then declare that all 100 prisoners have visited the room.

+----+

The minimum number of needed visits to the room by the tallyman: 10.

The minimum number of years required, with an average visit of once every 100 days, for the tallyman to be able to declare with certainty that all 100 prisoners have entered the room.: 3 (~=2.822).

You're very close. It is possible to get more milage out of this methodology. The minimum number of needed visits to the room by the tallyman can be lower than 10.

[Guest]

You're very close. It is possible to get more milage out of this methodology. The minimum number of needed visits to the room by the tallyman can be lower than 10.

Again, let the prisoners choose a tallyman.

Of the five switches, the prisoners assign the first switch as a placebo switch. A switch that will have no effect on the tally that a prisoner can flip. The other four switches are the tally switches.

Other than the tallyman, the first time a prisoner enters the room without having previously incremented the tally, will increment the tally, otherwise he switches the placebo switch. When the tallyman enters the room, he adds the current tally to a total and resets the tally.

It is at this point I veer from my original answer. The tally need not be reset to 0000.

The prisoners, instead, would prearrange the tally to increment by a set pattern such as the one following:

.0 - 1111

.1 - 0011

.2 - 0000 - 0

.3 - 0001 - 1

.4 - 0010 - 2

.5 - 0100 - 3

.6 - 1000 - 4

.7 - 1001 - 5

.8 - 1010 - 6

.9 - 1100 - 7

10 - 0110 - 8

11 - 0101 - 9

12 - 0111 -10

13 - 1011 -11

14 - 1101 -12

15 - 1110 -13

As in the previous submission, only two switches are ever flipped to increment the tally, but this pattern extends the possible range available.

The first time the tallyman visits the room, he will add the value of the tally on the right hand side of the binary representation. If the value of this right hand side is 4 or less, he resets the tally to 0000, else he (re)sets it to 1111. The next time he visits the room, depending on which of the two points he reset the tally, he adds the value of either the binary representation on the left or the right before, again, resetting the tally switches.

+----+

The minimum number of needed visits to the room by the tallyman: 7.

The minimum number of years required, with an average visit of once every 100 days, for the tallyman to be able to declare with certainty that all 100 prisoners have entered the room.: 2 (~=1.674).

[Guest]

i don't understand why my solution isn't more optimal. under your solution the problem may never be solved. under mine it's guaranteed. not sure how long it would take though. worst case scenario I'm guessing would be 100 entrances of each prisoner, but that highly unlikely.

[bushindo]

Again, let the prisoners choose a tallyman.

Of the five switches, the prisoners assign the first switch as a placebo switch. A switch that will have no effect on the tally that a prisoner can flip. The other four switches are the tally switches.

Other than the tallyman, the first time a prisoner enters the room without having previously incremented the tally, will increment the tally, otherwise he switches the placebo switch. When the tallyman enters the room, he adds the current tally to a total and resets the tally.

It is at this point I veer from my original answer. The tally need not be reset to 0000.

The prisoners, instead, would prearrange the tally to increment by a set pattern such as the one following:

.0 - 1111

.1 - 0011

.2 - 0000 - 0

.3 - 0001 - 1

.4 - 0010 - 2

.5 - 0100 - 3

.6 - 1000 - 4

.7 - 1001 - 5

.8 - 1010 - 6

.9 - 1100 - 7

10 - 0110 - 8

11 - 0101 - 9

12 - 0111 -10

13 - 1011 -11

14 - 1101 -12

15 - 1110 -13

As in the previous submission, only two switches are ever flipped to increment the tally, but this pattern extends the possible range available.

The first time the tallyman visits the room, he will add the value of the tally on the right hand side of the binary representation. If the value of this right hand side is 4 or less, he resets the tally to 0000, else he (re)sets it to 1111. The next time he visits the room, depending on which of the two points he reset the tally, he adds the value of either the binary representation on the left or the right before, again, resetting the tally switches.

+----+

The minimum number of needed visits to the room by the tallyman: 7.

The minimum number of years required, with an average visit of once every 100 days, for the tallyman to be able to declare with certainty that all 100 prisoners have entered the room.: 2 (~=1.674).

This is an improvement, but it could be even more optimal.

i don't understand why my solution isn't more optimal. under your solution the problem may never be solved. under mine it's guaranteed. not sure how long it would take though. worst case scenario I'm guessing would be 100 entrances of each prisoner, but that highly unlikely.

It isn't clear from your solution what happens when a prisoner enters the room a second time. He is forced to modify 1 or 2 switches. Wouldn't that screw up the counting system for the next prisoner?

[Guest]

i don't understand why my solution isn't more optimal. under your solution the problem may never be solved. under mine it's guaranteed. not sure how long it would take though. worst case scenario I'm guessing would be 100 entrances of each prisoner, but that highly unlikely.

...your method would be optimal. But as it is, there are 100 prisoners and 99 in binary code is the seven digit palindrome 1100011. This cannot be represented with only the 5 switches given.

If given 7 switches where each prisoner could tally 100 visits, there is still no 100% guarantee that each prisoner would actually visit the room. As you are correct in stating that there guarantee to my method as the selection process is random, but then there is similarily no guarantee in your method either.

Though the selection process does not give a 100% guarantee all prisoners will be selected to enter the room, the probability is more likely each will; and with the probability that each prisoner will be selected to do so 3 times a year (365/100 = 3.65). The method I presented does give the tallyman (thus all prisoners represented by him) a 100% certainty (within the permissible constraints of the puzzle) that upon his nth visit (whenever that will be) of knowing that all prisoners have visited the room.

[Guest]

This is an improvement, but it could be even more optimal.

I'd say we need to use the plyssibo switch for something? cause I don't see an improvement on Dej Mar's solution

Maybe they can use normal binary code, from 0 to 15,when the tallyman comes in if there are two switches on he resets them, if there are more he resets the two from the left (the biggest) and only adds the number he too to his tally (i.e if it were 1011 he'd make it 0001 and add 10 to the tally)

[Guest]

For a more fuller explanation of the method, see my previous posts.

The prisoners prearrange the tally to be in a sequence as the following:

_0 : 0000

_1 : 0011

_2 : 1111

_3 : 1011

_4 : 0111

_5 : 1110

_6 : 1101

_7 : 0101

_8 : 0110

_9 : 1100

10 : 1010

11 : 1001

12 : 1000

13 : 0100

14 : 0010

15 : 0001

When the tallyman visits the room, he will add the value of the tally on the lefthand side of the binary representation (less a possible noted amount from a previous visit). If the value of the binary representation is the left-hand side value 2, 3 or 4, the tally is reset to 0011 and the tallyman will subtract 1 (to a minimum of zero) from the next tally. If the binary representation is 5 or 6, the tally is reset to 1111 and the tallyman will subtract 2 (to a minimum of zero) from the next tally. Otherwise, the tally is reset to 0000.

When the tallyman has tallied 99. He can announce that all prisoners have visited the room.

+----+

The minimum number of needed visits to the room by the tallyman: 7.

The minimum number of years required, with an average visit of once every 100 days, for the tallyman to be able to declare with certainty that all 100 prisoners have entered the room.: 2 (~=1.668) [A small improvement, but an improvement].

[Guest]

I don't know if this is better but:

The numbersystem will be as follows:

0000

0001

0010

0011

0101

0110

0111

0100

1000

1001

1010

1011

1101

1110

1111

1100

When the tally comes he resets it to zero, if he can't then he resets the two digits nearist to the left (worse case is in 14 where he resets to 3) and he adds to his tally the amount he substarcted from the count...

An easy way to remember the number system is that every number that is _100 is pushed 3 numbers ahead, as in 4 and 12 are both placed as 7 and 15

[Guest]

I don't know if this is better but:

The numbersystem will be as follows:

0000

0001

0010

0011

0101

0110

0111

0100

1000

1001

1010

1011

1101

1110

1111

1100

When the tally comes he resets it to zero, if he can't then he resets the two digits nearist to the left (worse case is in 14 where he resets to 3) and he adds to his tally the amount he substarcted from the count...

An easy way to remember the number system is that every number that is _100 is pushed 3 numbers ahead, as in 4 and 12 are both placed as 7 and 15

We both have 11 (re)sets to 0 and 3 resets to 1. In yours, you have 1 reset to 2 and 1 reset to 3; while, in mine, I have 2 resets to 2.

This pattern may be better than my last offering, though.

_0 0000 _0

_1 1100 12

_2 1111 15

_3 1110 14

_4 1101 13

_5 1011 11

_6 0111 _7

_7 0110 _6

_8 0101 _5

_9 0100 _4

10 0001 _1

11 0010 _2

12 0011 _3

13 1010 10

14 1001 _9

15 1000 _8

And, perhaps, a poem like the one following will help the prisoners remember the sequence:

Zero chance was our beginning ... [zero = x'0'; chance begins with C x'C' = 12]

Down the byway, blind in our sinning, ... [by = "bi-" = 2(digit); "blind" = "no see" (x'C')]

But, seven to four, we wait the open door ...

One, two, three - soon to be free...

Ten, nine, eight - we'll be out the gate.

I tried to keep all the numbers represented with three 1's toward the beginning, as I believe (but I may be wrong), that it is more probable the tally will be higher than 6 when the tallyman visits the room. This way, if the tally is higher than 6, it is more likely to be reset to 0 where there are 15 available increments before his next visit.

[bushindo]

We both have 11 (re)sets to 0 and 3 resets to 1. In yours, you have 1 reset to 2 and 1 reset to 3; while, in mine, I have 2 resets to 2.

This pattern may be better than my last offering, though.

_0 0000 _0

_1 1100 12

_2 1111 15

_3 1110 14

_4 1101 13

_5 1011 11

_6 0111 _7

_7 0110 _6

_8 0101 _5

_9 0100 _4

10 0001 _1

11 0010 _2

12 0011 _3

13 1010 10

14 1001 _9

15 1000 _8

And, perhaps, a poem like the one following will help the prisoners remember the sequence:

Zero chance was our beginning ... [zero = x'0'; chance begins with C x'C' = 12]

Down the byway, blind in our sinning, ... [by = "bi-" = 2(digit); "blind" = "no see" (x'C')]

But, seven to four, we wait the open door ...

One, two, three - soon to be free...

Ten, nine, eight - we'll be out the gate.

I tried to keep all the numbers represented with three 1's toward the beginning, as I believe (but I may be wrong), that it is more probable the tally will be higher than 6 when the tallyman visits the room. This way, if the tally is higher than 6, it is more likely to be reset to 0 where there are 15 available increments before his next visit.

Dej Mar has the solution. Extra bonus points for the poem. Great work.

[Guest]

The tallyman is dynamically chosen!

Of the 5 switches, the first switch is designated a "placebo" switch. It has no affect on the tally, and thus maybe switched without inadvertantly affecting the tally. The other four are then used for the tally. As we need to allow only up to two switches to be used in an increment, let the pattern be as follows:

_0 0000 _0

_1 1100 12

_2 1111 15

_3 1110 14

_4 1101 13

_5 1011 11

_6 0111 _7

_7 0110 _6

_8 0101 _5

_9 0100 _4

10 0001 _1

11 0010 _2

12 0011 _3

13 1010 10

14 1001 _9

15 1000 _8

The first column is the tally count. The second column is the binary representation of the Tally count using the four on/off switches. The third column is simply to show the base-2 representation equivalent of the binary numbers.

If it is the second visit to the room by a prisoner before day 16, and the current tally count+1 is equal to the current day count, the prisoner knows he is the designated tallyman. He sets to memory the current tally and resets the tally switches to 0000, 1100 or 1111 (explained later), setting the reset point to memory as well. The first time a prisoner, other than the dynamically designated tallyman, who enters the room without having previously incremented the tally with the tally switches, increments the tally -- unless it is the 16th day. If it is the 16th day, and the current tally count+1 is equal to the current day, the prisoner knows he is the dynamically designated tallyman. As the designated tallyman, he sets to memory the current tally and then resets the tally to 0000, 1100 or 1111 (explained later) - setting the reset point to memory as well. If a tallyman has been designated, and it is a subsequent visit by a prisoner who has already incremented the tally, that prisoner instead switches the "placebo" switch. A prisoner will know a tallyman has already been designated if it is after day 16, or if it is on or before day 16 and the current tally count+1 is less than current day.

When the designated tallyman visits the room, he adds the value of the tally on the lefthand side of the binary representation after subtractng 0, 1 or 2 respective to the last reset and where the current tally switch representation is greater than the last reset. If the value of the binary representation is the left-hand side value 5 or 6 the tally switches are reset to 1111 (tally representation 2). If the left-hand side value is 2, 3 or 4, the tally switches are reset to 1100 (tally representation 1), otherwise the tally switches are reset to 0000 (tally representation 0). If the current tally count can not be reset to a lower count, then as any repeat visitor, he instead switches the "placebo" switch, adding 0 to his tally. When the tallyman has tallied 99. He can announce that all prisoners have visited the room.

Edited July 29, 2010 by Dej Mar

[Guest]

not at all. each prisoner adds one.

lets say a prisoner enters the first time and sees 4. then he knows that at least 4 have gone before, and adds 1 to the count for his own entry. then let's say he enters next time and sees 1. then since its less, he knows that at least 31-3 = 28 prisoners have gone before. the worst case would be if he entered again and saw 5. then he can only count himself.

[Guest]

dej mar, with my code, each prisoner adds 1, and the code starts over when it hits 31.

[Guest]

here it is on code form.

import random

#declare an array for the prisoner's count.

prisoner = [0]*100

#counter for entrance of each prisoner

enter = [0]*100

#counter for switch

count = 0

#tally for compare with previous entrance

tally = [0]*100 

while True:

   pick = random.randint(0,99)

   count += 1

   if tally[pick] < count:

      if enter[pick] == 0:

         prisoner[pick] += count

      else:

         prisoner[pick] += 31 -(count -tally[pick])

   else:

      prisoner[pick] += tally[pick] -count +1

   tally[pick] = count

   enter[pick] += 1

   if prisoner[pick] >= 99:

      break

   if count == 31:

      count = 0

total = 0

for i in range(0,100):

   total += enter[i]

print(total)

[Guest]

i get a max entrance of 5 for any prisoner given the conditions of the puzzle, (that is, random)

and an average of 160 entrances.

[bushindo]

here it is on code form.

import random

#declare an array for the prisoner's count.

prisoner = [0]*100

#counter for entrance of each prisoner

enter = [0]*100

#counter for switch

count = 0

#tally for compare with previous entrance

tally = [0]*100 

while True:

   pick = random.randint(0,99)

   count += 1

   if tally[pick] < count:

      if enter[pick] == 0:

         prisoner[pick] += count

      else:

         prisoner[pick] += 31 -(count -tally[pick])

   else:

      prisoner[pick] += tally[pick] -count +1

   tally[pick] = count

   enter[pick] += 1

   if prisoner[pick] >= 99:

      break

   if count == 31:

      count = 0

total = 0

for i in range(0,100):

   total += enter[i]

print(total)

My impression here is that every prisoner increments the count by 1 during his visit. Every prisoner also keeps track of the count increase since his last visit. If any prisoner has a personal count that exceeds 100, he declares that everyone has been in the game.

The issue that I see here is what if, by chance alone, the game only chooses 2 prisoners to enter the room repeatedly. Eventually one of them would falsely declare that everyone has been in the room.

Edited July 30, 2010 by bushindo

[Guest]

well i see that as a problem under your system as well then. what if the tally man is never chosen?

or what if he is chosen, but only two people have entered the room 99 times?

p.s. i thought the puzzle was for 100 prisoners entering the room, not for each of the 100 prisoners entering the room.

[Guest]

if the puzzle is for each of the 100 prisoners entering the room, then...

everyone would need to act like the tally man, and only advance the number when it hits his particular number.

of course even this is no guarantee, but it would make it much harder for the person declaring to be wrong.

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

I tried to be more efficient than the solution in the spoiler below but with no luck so here goes...

First the group must nominate a "counter." He will keep track of the number of prisoners who enter the room by keeping track of the changing state of the switches.

Since a prisoner must change the state of at least one switch each visit (I assumed this didn't mean he could turn a switch on and then off, effectively not changing anything), one of the switches will be designated a dummy switch. This switch will be used when a prisoner enters the room after his first visit and/or if the switches are at 15. He will simply change the state of the dummy switch and the counter will ignore the state of this switch whenever he enters the room.

So, this leaves 4 active switches. The prisoners can easily devise a counting system, where every number from 0 (all off) to 15 are indicated by a different state for the 4 switches. There are two constraints. It must be possible to get from every number to the next number by changing only 2 or fewer switches. And, 15 must be signified by no more than 2 switches in the on position. That way, when the counter enters the room and the switches are set to 15, he can turn the switches back to 0.

Once they set their counting system and agree on a the dummy switch, it's easy. When a prisoner enters the room for the first time, he will move the switches up 1 in their counting system, unless the switches are set to 15. In that case, he will move the dummy switch and wait for a time he can move the count up 1 on a later visit. The "counter" will look at the state of the four switches each time he enters the room. If it as at 8, he will move his total count up 8, and then change the switches to the lowest number possible. There will be some times where more than 2 switches are on, which won't allow him to move them to 0. But, if he can only move the switches to 3, for example, then on the next visit, he takes that into account when making his tally.

Once he gets to a total count of 99, all the prisoners have entered the room.

[Guest]

The tallyman is dynamically chosen!

Of the 5 switches, the first switch is designated a "placebo" switch. It has no affect on the tally, and thus maybe switched without inadvertantly affecting the tally. The other four are then used for the tally. As we need to allow only up to two switches to be used in an increment, let the pattern be as follows:

_0 0000 _0

_1 1100 12

_2 1111 15

_3 1110 14

_4 1101 13

_5 1011 11

_6 0111 _7

_7 0110 _6

_8 0101 _5

_9 0100 _4

10 0001 _1

11 0010 _2

12 0011 _3

13 1010 10

14 1001 _9

15 1000 _8

The first column is the tally count. The second column is the binary representation of the Tally count using the four on/off switches. The third column is simply to show the base-2 representation equivalent of the binary numbers.

If it is the second visit to the room by a prisoner before day 16, and the current tally count+1 is equal to the current day count, the prisoner knows he is the designated tallyman. He sets to memory the current tally and resets the tally switches to 0000, 1100 or 1111 (explained later), setting the reset point to memory as well. The first time a prisoner, other than the dynamically designated tallyman, who enters the room without having previously incremented the tally with the tally switches, increments the tally -- unless it is the 16th day. If it is the 16th day, and the current tally count+1 is equal to the current day, the prisoner knows he is the dynamically designated tallyman. As the designated tallyman, he sets to memory the current tally and then resets the tally to 0000, 1100 or 1111 (explained later) - setting the reset point to memory as well. If a tallyman has been designated, and it is a subsequent visit by a prisoner who has already incremented the tally, that prisoner instead switches the "placebo" switch. A prisoner will know a tallyman has already been designated if it is after day 16, or if it is on or before day 16 and the current tally count+1 is less than current day.

When the designated tallyman visits the room, he adds the value of the tally on the lefthand side of the binary representation after subtractng 0, 1 or 2 respective to the last reset and where the current tally switch representation is greater than the last reset. If the value of the binary representation is the left-hand side value 5 or 6 the tally switches are reset to 1111 (tally representation 2). If the left-hand side value is 2, 3 or 4, the tally switches are reset to 1100 (tally representation 1), otherwise the tally switches are reset to 0000 (tally representation 0). If the current tally count can not be reset to a lower count, then as any repeat visitor, he instead switches the "placebo" switch, adding 0 to his tally. When the tallyman has tallied 99. He can announce that all prisoners have visited the room.

This improvement doesn't work because the time between visits is variable (it's not a daily event), as bushindo said when stating the problem:

5) The time between visits is variable.

However, I am still unsure that your solution is optimal (note: I later realize that your solution is "optimal" when you want to guarantee a win, but I am quite unsure if it is optimal if you only have to win the game (i.e. guess correctly that all 100 prisoners have entered the room) 99% of the time, or 95% of the time, etc.), (as bushindo seemed to think when he declared your answer to be the solution:

Dej Mar has the solution. Extra bonus points for the poem. Great work.

I am wondering whether phillip1882's idea to have everybody act as a tallyman would work. In this method, when the count reaches its max, the next person who enters the room for their first time and wishes to add a count must reset it (so the count goes in a cycyle). Because everyone is a tallyman, the counting numbers will have to exclude combinations of switches with 3 or 4 1s (because such combinations can't be reset to 0000 by moving only 2 switches). Thus, the count might look like this:

0-0000

01-0001

02-0010

03-0100

04-1000

05-1100

06-0110

07-0011

08-1001

An individual prisoner's thought process might look something like this:

(Note: I'm not going to show the placebo digit for this, because nobody gains any information from it.)

A prisoner enters the room and sees 0000. He adds 1 to the count (making it say 0001). He makes a mental note that 0 more of the other 99 prisoners have entered the room, totaling his personal prisoner count to 0.

The same prisoner enters the room for a second time and sees 0110. Because he had brought the count to 1, and this is the count for 6, he makes a mental note that 6-1=5 more of the other 99 prisoners have entered the room, totaling a personal prisoner count of 5. He then changes the placebo and leaves.

The same prisoner enters the room for a third time and sees 1100 (5). Because he had last seen the count say 0110 (6), and this is the count for 5, he makes a mental note that 8 more of the other 99 prisoners have entered the room (note: the 8 is because you need 8 new prisoners entering the room to change the counter from 6 to 5). He then changes the placebo switch and leaves.

Etc...

Eventually all of the prisoners will get to the room multiple times and find that the count is not changing anymore (or rather, it has not changed in the last n times that the prisoner has gone to the room) and they will likely all have total counts on the number of individuals who they know have entered the room that are less than of 99 (99 is possible, but statistically unlikely because in order for an individual to get a count of 99 he would have to be randomly selected to go into the room at least every 8th new person. Even having 9 new people go in the room after he goes in and before he goes in another time would cause the cycle to repeat and he would miss counting those 9 new individuals). So, how does a prisoner finally decide to GUESS that all 100 prisoners have entered the room? I'll explain shortly

So I now see that this system would not guarantee a win, but I think that there's still a chance that statistically it could win a good percentage of the time (say 90% of the time they are expected to win) in fewer expected prisoner visits than Dej Mar's solution. I don't know how to calculate the probability, so I'm not sure how efficient a 90%-of-the-time-win would be in comparison to the efficiency (in terms of expected number of prisoners to enter the room) of Dej Mar's 100%-of-the-time win.

In order to determine how efficient my method is relative to Dej Mar's, one would have to calculate the expected number of prisoner visits in Dej Mar's solution before the tallyman announces that all 100 prisoners have visited the room (this expected number of visits is somewhere around 700, as Dej Mar said). This would be the easier calculation. The more difficult calculation would be in determining the optimums for my system with the cycle of 9 counts. This would include determining the optimum number of times that an individual should visit the room and see the same count before guessing that everyone had visited the room (such a number would probably be a function of the number of prisoners that that individual knew had visited the room, if you wanted to make my method as efficient as possible).

So anyways, the problem stated:

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.

I think "guarantee a" should be added to the statement: "Optimal means the expected number of visits to guarantee a win is smallest." This would make me agree that Dej Mar's solution seems to be the correct solution (meaning it is the most optimal way (in terms of expected number of visits by prisoners to the room). Right now, I'm not so sure because I'm wondering what the expected number of visits would be for my method of not-100% confidence. For example, if you adjusted my method (specifically if you adjusted) to win in an expected 99% of these prisoner games, what would the expected number of visits to the room be? Would it be greater than or less than the approximate 700 number of visits for Dej Mar's 15-count method that selects a single individual to be a tallyman?

I would argue that if the expected number of visits for my method is less than the expected number of visits for Dej Mar's method (i.e. if the expected number of visits for my method with 99% confidence to win is something like 500 visits instead of Dej Mar's ~700 visits), then my method is likely superior. Wouldn't it be worth the 1% risk that you would guess wrong and lose the game if you were expected to finish the game a significantly large number of visits faster? You didn't specify in the question that one had to guarantee a win, so I think it most certainly would be more optimal to use a strategy that wins a large percentage of the time (e.g. 99% of games) with an expected number of visits that is significant less (e.g. 500 instead of 700) than the 100% method.

So the question I have for you smart people is this: I don't know if my method adjusted to win 99% of games would have an expected number of visits greater than or less than the 700ish expected number of visits in Dej Mar's method. If any of you could write a program that could do a bunch of simulations to test out my method to see how efficient it is (in terms of number of visits and in terms of winning percentage), I would be very very interested to see the results.

To go about doing such a thing, you might write into the program that when a prisoner sees the same count (on the light switches, on n consecutive entries into the room (e.g. sees 0110 on the 4-count-switches on n consecutive times going into the room) (where you might try n out to be 5 or 6, to start), then that prisoner guesses that all 100 prisoners have been to the room. Run the program a few times and then see how many guessed successfully and how many unsuccessfully. If a lot were unsuccessful then try increasing the n from 5 to 6 to 10 or something. On the other hand, if all of the runs were successful then try reducing the n value. Continue to adjust the n value until you find a value that wins a good amount of the time (e.g. 90%). At that point, check to see what the average (an approximation of expected) number of visits to the room is. Is it close to 700? More or less?

I'm very curious to find out about this. I wish I knew how to write the programs myself and I wish I had software for them. If someone else could do this (make a program to test the efficiency of my method (in terms of number of visits (e.g. ~700?) and how often it it wins (e.g. 90%?)) for me I would be very grateful. If you (anybody out there) have any questions about my method I would be glad to answer them and explain it better so that you could do me this huge favor and give me an idea of how efficient this method would be relative to Dej Mar's method. Thank you very much.

Edited August 5, 2010 by Use the Force