And on an intuitive level, it makes sense that that algorithm is slower, because it is conveying more information – not just how many prisoners have visited the room, but their identities too. Certainly in the well-known 100 prisoner variant of this puzzle, that algorithm and versions of it proved to be far slower than the single or multiple leader approaches.
I suppose you could lop off a little time by gathering some information before the leader arrives on the scene by appointing the prisoner chosen the third month as the 'leader" (rather than the first month).
Have the prisoner chosen in month one flick the light on, and the prisoner chosen in month two flick the light off, unless he’s the same prisoner as was already chosen. Then the prisoner chosen in month three will know for certain if he’s been preceded by exactly two or one prisoners (or, rarely, zero), and the tallying goes on from there, with prosoner #3 as the “leader.” So you’re always farther ahead in the tally than you would be if prisoner #1 was the “leader.”
At the beginning someone leaves the light on only every ten months, but after that anyone who has already crossed off prisoner X can leave the light on that month.
If prisoner 2 already crossed off prisoner 5 and is called on month 35, they leave the light on.
I don’t think this method beats the head-start + single-counter method though.
Can the prisoners unscrew the light bulb? That would provide two binary bits. The first person flips off the switch. The second unscrews the light bulb. The third flips the switch back on with the bulb still out. When the leader is selected, he’ll know how many new people have entered the room up to three. You could even change one bit to a base-3 digit by having the light bulb either tight, loose, or completely removed and count up to 5 at once.
…I’m not getting this. Per the rules of the riddle, none of the methods for the prisoners should work:
So how do they designate a leader? How do they coordinate all this stuff? They can’t see/hear/leave marks. Even if we assume all these prisoners are smart enough to do this, how do they set it up to begin with?
It was corrected later that the prisoners did get a chance to meet together once at the very beginning before going to their individual cells.
I’m not getting how the guards aren’t a factor in turning the light off on the way out after they clean up.
Oh, I get it. Interesting. I’m guessing, like you, that this would still be a slower method, but since the information transfer speeds up over time that’s not crystal clear.
I’m guessing “head-start + single-counter method” would take ~110 months, and the “mod 10” method would take ~150 months. That’s just a WAG, so I’m interested if anyone does a Monte Carlo.
The guards will leave the common area untouched except remove any markings and left items. So we can assume that the guards don’t interfere with the switch or the bulb anduse a. Binary counting system with 4 variables which would allow the prisioners to count to 10 pretty quickly. Rules could be:
- When it’s your first visit, add 1
- When it’s your second or successive visit, do nothing
- Remember OBLS (Old Boys Love Soccer) which represents the 4 variables: bulb Out, bulb Broken, bulb Loose, Switch on
- When counting in binary, 1 means Yes (i.e. Switch is on), and 0 means No (i.e. Switch is off)
- If the switch is already on in the very first month (prisoner will know who s/he is, do nothing)
So, we have:
1st person: 0001 Switch On (or leave on)
2nd person: 0010 Loosen bulb and turn Switch off
3rd person: 0011 Turn switch on
4th person: 0100 Break bulb, tighten it, switch off
5th person: 0101 Turn switch on
6th person: 0110 Loosen bulb, switch off
7th person: 0111 Switch on
8th person: 1000 Take bulb out, switch off*
9th person: 1001 Switch on*
The person who finds the broken bulb on the floor with the switch turned on knows s/he’s the 10th visitor and calls the guards…
- Logic fails a little here as it’s not possible to unbreak the bulb but should be otherwise clear to the prisoners…
I was trying to work out a system like that… but you beat me to it!
You can count to 9 with just three binary signals: 000, 001, …, 110, 111, and the 9th prisoner will see 111 when finally called to the room.
And in fact, you can make this work for 10 prisoners – any previously-counted prisoner who finds the switches reset to 000 knows that #9 has visited, and sets the signals to something other than 000. Then the 10th prisoner will increment the count (not realising that he is 10th), and on a later visit the other prisoner (or possibly others who observed the out-of-sequence signals) will see the increment and know that the 10th prisoner has visited. In other words, the other prisoner will become a “leader”, just to count the last guy.
Let me refine that: #9 sees 111 and knows that he is #9. He sets the signals to 000 and waits for #10 to increment them to 001. #10 will not know whether he is #10 or #2, but #9 (and possibly other prisoners) will, and will be able to declare to the warden on his/their next visit.
Rolling the balls down a ramp would work.
I was also thinking of giving each ball a good spin, then stopping it abruptly. The hollow ball will remain motionless, but the fluid in the other ball will remain in motion so the ball will continue spinning slowly after you release it.
I perform this test every time I crack open a boiled egg, just in case some prankster swapped it for a raw egg.
What fluid? The problem just says “low-density substance”, but that could be balsa wood or aerogel or whatever.
No matter the density, the sound will probably be different.