Someone walks into your room and dumps a huge bag of quarters all over the floor. They spread them out so no quarters are on top of any other quarters. a robot then comes into the room and is programmed such that if it sees a head, it flips it to tails. If it sees a tail, it throws it in the air. the robot moves around randomly forever. Will there be a convergence in distribution of heads vs. tails?
Soultion
Hmmm. I made a little math trick out of it. If the ‘bot finds a head, it flips. If the bot finds a tail, there’s a fifty percent chance this will become a head, as well.
(P_h = #heads/#coins, P_t = #tails/#coins)
So, delta h = -P_h + .5 P_t
= -(1 – P_t) + .5 P_t
= 1.5 P_t -1
Which is zero when P_t is 2/3. It’s important to remember that a flip to a tail results in no change to the number of tails — this threw me off for a second.
2026 Update: Reachability and State Space Analysis
Coin-flipping puzzles where you must determine whether a target state is reachable from an initial state test state space analysis — a foundational technique in formal verification, model checking, and distributed systems protocol design.
The invariant approach: Instead of trying all possible operation sequences, identify an invariant (a property preserved by all operations) that rules out the target state. If the target violates the invariant, it is unreachable.
Modern equivalents:
- Distributed systems: Can a protocol reach a deadlock state? Invariant analysis (safety properties) proves it cannot
- Database transactions: Which final balance states are reachable from initial balances via valid transfers?
- Formal verification: TLA+ specifications model exactly this — what states are reachable from the initial state via the allowed transitions?
BFS solution for small state spaces:
from collections import deque
def can_reach_target(initial, target, operations):
"""
BFS over all reachable states from initial state.
State: tuple of coin values (0=tails, 1=heads).
operations: list of functions (state -> new_state or None)
"""
visited = {initial}
queue = deque([initial])
while queue:
state = queue.popleft()
if state == target:
return True
for op in operations:
new_state = op(state)
if new_state and new_state not in visited:
visited.add(new_state)
queue.append(new_state)
return False