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.
Answer
Here is a proof that more than 50 is impossible.
No matter what strategy a player uses, they will be wrong exactly half of the time. Why? Let Alice be a particular player. For each present distribution $P$, define a corresponding distribution $f(P)$, where you change the color of the person that Alice is guessing and leave all other colors the same.
Since $f(P)$ doesn't change Alice's color, it doesn't change her guess, which means that $f(f(P))=P$. In addition, $f$ has no fixed points. Therefore, we can break up the set of all $2^{100}$ distributions into pairs $(P,f(P))$. Alice will be correct for exactly one distribution in each pair, so she is correct half the time.
This means that each person gets 0.5 guesses correct on average, so adding these up, the team gets 50 guesses correct on average. This proves that it is impossible to guarantee getting more than 50 (if they always get 51 or more, then the average would be 51 or more).
Put another way: from Alice's perspective, she is guessing the value of a coin flip she has no information about, so she has to be correct with probability 1/2.
No comments:
Post a Comment