All puzzles

A 1-bit communication puzzle

This is best experienced with good company. Meet with puzzle-minded friends and enter a room code:

Your room

Join room

Are you sure?


This will clear your progress and start a new room.

Prelude#

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.

ImportantAI 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’sBrainmade.

A lightbulb next to 0/1 binary digits

Flavor text#

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.

Say hello to your manager

“Hey, just letting you know the session started 10 minutes ago. We’ve been waiting for you.”

The conference room

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…

Brainrot

“…and zero communication allowed.”

You are ejected back into reality

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.

TL;DR#

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.

ImportantYour 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).

Key

Hints

Your turn

Loading editor…

This editor is readonly.

Show solution?


Are you sure? You haven’t even seen all the hints!

Now try this#

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?

Key

Hints

Now try this

Loading editor…

This editor is readonly.

Show solution?


Are you sure? You haven’t even seen all the hints!

Uniformity#

INFORMATION HAZARD

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:

Key

Hints

Up the ante

Loading editor…

This editor is readonly.

Show solution?


Are you sure? You haven’t even seen all the hints!

And it’s always possible (for any !) if the switch is tri-state, and starts in the first state:

Key

Hints

Triple it

Loading editor…

This editor is readonly.

Show solution?


Are you sure? You haven’t even seen all the hints!

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.

An impossible challenge#

INFORMATION HAZARD

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.

ImportantNote:That last assumption is important! A general strategy does not exist.

Key

Hints

The dark side

Loading editor…

This editor is readonly.

Show solution?


Are you sure? You haven’t even seen all the hints!

Optimization#

INFORMATION HAZARD

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:

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

Key

Hints

Let’s gamble

Loading editor…

This editor is readonly.

Show solution?


Are you sure? You haven’t even seen all the hints!

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!)

LeaderboardLeaderboard

Solution zoo

Parting words#

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.

— Thomas

References#

  1. One hundred prisoners and a lightbulb — logic and computation, by Hans van Ditmarsch, Jan van Eijck, and William Wu.
  2. Mathematical Puzzles: A Connoisseur’s Collection, by Peter Winkler.