KöMaL 2013 B4568

There are $n$ prisoners in a prison. Since the guards are bored, they invent the following game: Either a red hat or a blue hat is placed on the head of each prisoner such that no one can see the colour of the hat on their own heads. Then the prisoners are allowed to look at one another (everyone can see everyone else's hat). Finally, each of them guesses the colour of their own hat, and writes it down on a sheet of paper. If all answers are correct, the prisoners may go for a walk in the courtyard. What strategy should they agree on, so that the probability of a walk in the courtyard is a maximum?