This is best experienced with good company. Meet with puzzle-minded friends and enter a room code:
This is a classic puzzle, but I bet it will find fresh ears here. This is also an experiment in creating a problem-solving environment with higher-than-average production value.
AI use:I used AI for proofreading and to speed up webdev. The core content (including like 80% of the total code) remains handcrafted, and the rest is carefully reviewed/tuned by hand excluding tests. It’s
.
You wake up bleary-eyed and brain fogged just in time for lunch. Stumbling out the door, even though your mind is absolutely bricked, you know exactly what’s going to happen. Months of nights spent scrolling reels have unraveled your professional self. Soon, you and other low performers will be put to the test. You arrive for the catered lunch and have just finished refilling your 32oz coffee tumbler when your manager slides by, weakly feigning a smile.
“Hey, just letting you know the session started 10 minutes ago. We’ve been waiting for you.”
You follow him to the meeting room, a glass-walled prison with two glaringly vacant seats. Focused on their desperation, everyone is seated and ponderously silent, not bothering to open their laptops or turn on the lights. You flick them on the way in, hoping it’s enough light to eat away at all the mold in your brain. Your manager clears his throat.
“Good afternoon everyone. As we discussed last week, it’s time for your performance review.”
A pause, then a lonely chuckle.
“Sorry, test. You’ve obviously gone through the review, and due to pressure from above, we can’t keep all of you. So, in case you forgot, you’ll all be completing an assignment today. The faster you finish, the better.”
You’ve had ample time to collude with the other prisoners and devise a plan where everyone announces they’ve finished at the same time. After all, they can’t fire all of you. The manager drones on about the task while your brain drifts back to bed, puny imagination bombarded with a firehose of dumb, fast content…
“…and zero communication allowed.”
The silence sharply cuts off your dopamine supply. Despite his hovering presence, an employer can only do so much to ensure a controlled testing environment. For instance, by flushing or not in the bathroom, you can set one bit of information shared between you and your fellow inmates. Your manager still has control over the order you enter the bathroom, but can’t exclude any one of you forever!
Together, you’ve found a strategy that allows one of you to determine, at some point, that everyone else has completed the project.
In case my word soup made you vomit, here’s the unflavored plaintext:
prisoners are isolated in separate rooms. They are called to a common room with a switch whose state can be observed and flipped by the prisoner in the room. The switch starts off.
The adversary can choose some (possibly adversarial) order for them to enter the room, under the constraint that each prisoner must appear infinitely many times in this sequence. That is, there does not exist a time after which they never enter the room again.
How can at least one prisoner know when all others have visited the room?
Think you’ve got it? Show me. Don’t be ashamed to use hints! It’s far better that you enjoy the process than get stuck, ne’er to return.
Your turn:Write some Python to solve the puzzle in the editor below. A separate instance of this Python module runs for each prisoner, so you can't secretly share information. You can skip these if you want (but imagine my disappointment).
Need a hint?
The prisoners can meet beforehand. How can this help?
Need a hint?
If the prisoners know who they are, how can the switch be used to signal to one another?
Need a hint?
If one prisoner is the “leader,” how can they count the others?
Loading editor…
Have the first prisoner store a counter of the number of prisoners who have visited the room (starting at 1, when they visit). This “leader” will increment their counter whenever the switch is on, and turn the switch off.
Whenever a non-first prisoner visits: the first time they enter the room and the switch is off, they flick the switch on, and otherwise do nothing. Since each prisoner is visited eventually, the next prisoner who hasn’t turned on the switch will get a shot at signaling to the leader. Hence, progress is guaranteed!
Loading editor…
It seems you all are the second session of the day, and the previous examinees have converged on the same idea. But nobody has any idea what state they left the bit of information in! Can you make it work anyways?
Need a hint?
How much can the answer be off by, using your previous strategy?
Need a hint?
What happens when you run your strategy again?
Loading editor…
Just do the original solution twice. While the switch being initially on can add at most 1 to the first count, all prisoners must be visited for the total count to hit .
Loading editor…
This content is spoilered for your safety! But if you think you can take it:
What if we required that all prisoners behave the same? That is, if they have observed the same sequence of lightbulb states when they entered the room, they behave the same way: they should change the switch's state and decide if everyone else has visited identically.
For it takes just a moment to see that the simplest solution still works. For , it’s still possible:
Need a hint?
How can you single out a prisoner?
Need a hint?
How can you ensure the second distinct prisoner to visit the room knows this fact?
Loading editor…
The second distinct prisoner to enter the room is always the leader, and knows this since the switch is on the first time they enter. Everyone else turns the switch on once. I think you can verify the cases work out.
Loading editor…
And it’s always possible (for any !) if the switch is tri-state, and starts in the first state:
Need a hint?
How can you elect a leader?
Need a hint?
How can the other prisoners know they are not the leader, if the leader is the first prisoner to enter the room?
Loading editor…
Simple: the first person to enter flips the first switch from 0 to 1, marking themselves as the leader. The rest proceeds identically to the first puzzle, except off/on map to states 1/2.
Loading editor…
When a friend told me of the original (simple) problem, I interpreted it this way and tried to clarify that prisoners didn’t know who they were. But my friend thought I was asking about whether a prisoner knew if they were the th to be called and I left very confused. After many hours of thought I asked gippity, who immediately pointed me to a StackExchange post (spoilers!), which in turn cited [2], one of Peter Winkler’s puzzle books.
This content is spoilered for your safety! But if you think you can take it:
And, of course, it’s impossible for . To make it feasible to write an adversary, I’ll lend you a few methods that expose the prisoners’ strategy and we’ll keep the state space small (like, at most a few thousand prisoner states).
Your goal is to get a prisoner to incorrectly state that everyone else has visited the room, assuming their strategy requires that one of them will eventually say everyone has visited the room if each prisoner is visited infinitely many times.
Note:That last assumption is important! A general strategy does not exist.
Need a hint?
If you’re wondering how to make sense of the shared strategy, try thinking of it as a state machine (more precisely, a DFA / deterministic finite automaton). This graph has directed edges depending on the observed state of the switch, and a state may be terminal if it signals .
Need a hint?
As the adversary, you can use your predictions to make a prisoner reenter a room until they settle on an outcome or enter a cycle.
Need a hint?
What are the possible inputs/outputs of this process?
Need a hint?
How can you simplify the behavior of each prisoner to (roughly, a bit more than) a single number?
Need a hint?
Remember: you are guaranteed that the prisoners will eventually signal that everyone has visited, as long as you don’t skip out on one forever. What does this imply about their strategy?
Loading editor…
This might be the most cheesable problem in the set. As noted, the statement that they eventually signal (that everyone else has visited) does all the heavy lifting.
There are quite a few implications of this:
I don’t want to trouble you with the next couple messy observations, since the above is enough to implement. Anyways, it turns out that just cycling through the first 2 or 3 prisoners is sufficient:
Loading editor…
This content is spoilered for your safety! But if you think you can take it:
Back to the original question: how long are the prisoners confined for, assuming they are selected randomly to enter the room? If a single leader is elected, let denote the expected number of steps until prisoners have signalled to the leader,
Hence,
where is the harmonic number . This matches a simulation:
Click the to run the simulation.
Can we make this faster? There are a couple tricks that shave off a margin (for instance, letting all prisoners count, even if they can’t reset the bit), but none I’ve seen defy the term. This is an interesting problem in itself, but I think things get even more unpredictable when you re-add the uniformity constraint and allow randomness (each prisoner just happens to have a coin on them).
Need a hint?
How can you use randomness to differentiate the prisoners?
Need a hint?
If each prisoner stores a counter, how can you make sure that, eventually, all the “counts” are concentrated in a single prisoner?
Need a hint?
In the solution to the original puzzle, the leader always “accepts” the state of the switch, incrementing their count and turning off the switch. How can you vary the acceptance criteria?
Need a hint?
Find interesting ways to derive an acceptance probability.
Loading editor…
Instead of having a single leader, I have prisoners receive or donate their counts based on how much they currently have: the rich get richer, and the poor get poorer. Note I also fully saturate the probability at , since at that point we pretty much have a leader.
If you’re looking for a direction to explore, I expect using that prisoners are visited in a random order will prove helpful. The number of prior visits is a proxy for how many times other prisoners have been visited, and therefore contains a lot of information!
Loading editor…
Once you’re done, let’s see how your solution stacks up. The score is just the sum of total steps across all trials (lower is better!)
Solve the problem first.
If, after all this, you’re somehow still interested in this puzzle, the synchronized twist in [1] might interest you.
I know this is the content I would enjoy consuming, even though it does require some effort! But it’s certainly more appealing than one paragraph in a warehouse of puzzles, as is traditional. That austere format feels purer, but lonely and less accessible. Even if you get more out of solving problems without this added “fluff,” if there’s less chance you would have seriously attempted the problem, a glamourized version has to be better. And I hope it has been.