Ten prisoners and hats of ten colors
Asked at Jane Street, Citadel
Ten prisoners are each given a hat in one of 10 colors (numbered –); colors may repeat, chosen adversarially. As before they stand in a line: each sees all hats in front but not their own or those behind. In order from the back, each announces a guessed color number (–). A prisoner is freed if the guess equals their own hat's number.
They strategize in advance.
Guarantee that at least nine prisoners go free.
Show a hint
Parity worked for two colors by using sums mod 2. Generalize: work modulo 10.
Your answer
This one is open-ended. Work it through, then check your reasoning against the full solution.