KöMaL 2013 B4540

There are $n$ prisoners in a prison. The guards were bored, so they invented the following game: In the courtyard, they place either a red cap or a blue cap on the head of each prisoner. The prisoners are then given some time to look at one another (each prisoner can see all caps but his own), and then each of them has to write down on a sheet of paper what colour he thinks his cap is. Those guessing correctly are allowed to walk in the courtyard the following day, too. What is the largest number $k$ for which the prisoners may follow an appropriate strategy to make it certain that at least $k$ of them are allowed to walk in the courtyard the following day?