The puzzle
Three smokers each hold an infinite supply of one ingredient: tobacco, paper, or matches. An agent repeatedly places two different random ingredients on the table. The smoker holding the third ingredient must take both, roll, and smoke. The constraint is that the agent code cannot be modified.
Why it is hard
A naive smoker waiting on a semaphore for each ingredient will grab one ingredient and then block, even though no single smoker should react to a single ingredient. The matching must be on the pair that was placed, not on individual items, and you may not change the agent.
The pusher solution
Introduce three helper threads called pushers, one per ingredient. Each pusher waits for its ingredient and records that it is present under a mutex. When a pusher sees that another ingredient is already on the table it signals the smoker who needs the remaining one. The pushers translate raw ingredient signals into the correct combined event.
This demonstrates building a higher level synchronisation primitive on top of fixed lower level signals.
Key idea
The cigarette smokers problem shows how pusher threads compose individual ingredient signals into a pair match, building a new primitive without touching the fixed agent.