Two switches, unknown start, prove everyone visited
Asked at Jane Street, Citadel, Optiver
20 prisoners are in solitary. Each day the warden marches one prisoner, chosen at random (with repetition), into a room that holds two switches, A and B, each either up or down. Rule: on every visit the prisoner must flip exactly one switch (leaving both untouched is not allowed), then leaves. No other contact is possible.
At any time a prisoner may declare "all 20 of us have now visited this room." If true, everyone goes free; if false, everyone is executed. The catch: the switches start in an unknown position (nobody knows if A began up or down). They plan beforehand.
Design a strategy guaranteed to eventually free them.
Your answer
This one is open-ended. Work it through, then check your reasoning against the full solution.