100 clever men receive presents from the president. Each man gets either a red or blue present, and only knows the color of his own gift.
Then each man must guess a colour of a gift of some man: he must chose a man (besides himself) and a colour, write these down on a piece of paper and give this paper to an organiser. Once all this is done the organiser counts amount of correct guesses out of 100.
The men know all the described procedure in advance and have time to develop a strategy, before receiving any presents. Once they receive the presents, they will be unable to communicate with each other.
Their task is to guarantee maximum amount of correct guesses. Your task is to say 1) what is this maximum amount, 2) what can be a strategy of the men and, the most important: 3) prove that there is no other strategy, which can guaranty a bigger amount.
P.S. "Guarantee" - means that this amount should be achieved independently of luck and what presents are. It can be that all 100 presents are blue, or all red, or a mix, distribution between men also is arbitrary.
P.P.S. It feels like 50 is right answer, it is easy to figure out a strategy to do this, but it is really hard to prove that this is the best result. Note that 1. several men can guess about one present, 2. man can chose who he is guessing about After he got his present.