Guess another's present 2: Generalised

What if in Guess another's present problem introduce more present's colours? Also i would reduce a number of men to number of colours. So the task basically the following:

N clever men receive presents from the president. There are N possible colors of present. Each man knows the color of his own gift only.

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 N.

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 3) prove that there is no other strategy, which can guaranty a bigger amount.

@Mike Earnest gave a quite clear proof that for such a task it is impossible to guarantee more than N/N=1 correct guess. When N=2 it is quite easy to guarantee 1 correct guess: see answer of @The Dark Truth. But already with N=3 i'm failing to figure out a strategy.

Also note that the task is quite similar to well known N logicians wearing hats of N colors problem. The differences are: 1. a man sees only his "hat", not "hats" of all others, 2. a man must guess another person color and he can chose this person, he is not stuck with guessing his own "hat" color.

• tough one for sure, I'm actually leaning towards it not being possible but will be happy if someone proves me wrong. It would be possible ofcourse if you had $N^2$ men or if people didn't know their own gift but were allowed to choose themselves. Dec 22, 2015 at 9:57
• @DrunkWolf, N^2? for N colours? N+1 men should be enough for easy solution. Dec 22, 2015 at 10:30
• it's enough to get 1 correct guess yes, but not to get 1/Nth of guesses correct. Dec 22, 2015 at 10:32

No, a correct guess cannot be guaranteed for any $N\geq 3$.
The key idea, pointed out by Mike Earnest, is that the expected number of correct guesses is the number of people divided by the number of colors, here $1$. So, if ever there are $2$ or more correct guesses, some other state must lead to $0$ incorrect guesses to compensate. Therefore, any winning strategy must always give exactly $1$ correct guess. We can imagine the players simply lose if two or more of them guess right.
Moreover, any two pairs of players that consider each other must have a player in common. Otherwise, both pairs could have a correct guess. This requires that there is a player who considers everyone. It only remains to rule this out for $N \geq 3$.
Note from before that if P considers Q, he must dedicate at least two of his colors to guessing Q. So, any player considers at most half the other players, which for $N\geq 3$ rules out a player who considers everyone.