Basic problem:
$2$ prisoners are in a room, they are allowed to chat and come up with a plan for the riddle they are about to face. After their chat, they are separated and assigned one hat each, which they can see. Hats can be black or white. If at least one of the prisoners can guess who has which color, then they are both released.
The answer is here:
Let p1 be prisoner 1 and p2 be prisoner 2. The plan they make before being separated is this: prisoner 1 will claim p1 and p2 both have whatever color p1 gets. p2 claims p1 has a different color from whatever p2 gets. This way if they both have black or both white, then p1's answer will be correct. And if they have different colors p2's answer will be correct. So they have a winning strategy according to the rules, which allow them to make a mistake.
Now the generalized problem:
There are $k$ people and $n$ hat colors. All $k$ people can chat, just like before, and then they are all separated into individual cells, and given one colored hat each. If at least one person can "guess" what color everybody has then they are all freed.
According to the rules they can make at most $g-1:=k-1$ wrong guesses ($g:=$total number of allowed guesses. Here they get exactly one guess per person), but we could seek to minimize that number. In the end I want to know what is the minimal number of guesses they need to ensure a victory, and for what values of $n$ and $k$ is $g\le k$.
What I found for now:
Let $x_i\in\{0,\dots,k\}$ be the number of people that receive a hat of color $i$, with $i\in\{1,\dots,n\}$. Since $x_1+\dots+x_n = k $, the total number of possible hat distributions is the same as the number of ways to distribute $k$ coins of value $1$ among $n$ people (now totally different people, it's kind of a dual situation. You can think of this new set of people as hat merchants, one merchant per hat color.). And that number is $n+k-1 \choose n-1$. But the guesser knows his own color, so each guesser has to be assigned (during their chat) a predetermined claim which concerns the other people's colors (the number of such guesses is $n+k-2\choose n-1$ (*)[explanation]), and he will just shout the concatenation of his color and whatever the people agreed he would shout for all the other people's colors.
(*): Now given the guesser's own color, the number of possible distributions is calculated in a similar way as in the situation where he doesn't know his color. The only difference is that given he has color $j$, we will have $x_j\ge 1$. So this corresponds to the number of ways to distribute $k$ coins to $n$ people such that the $j$'th color has $\ge1$ people with a $j$-hat, this is the same as the number of ways to distribute $k-1$ coins among $n$ people (because you give one to the $j$-hat merchant and distribute the remaining $k-1$ coins to ensure $x_{j}\ge 1$).
Therefore people need at least $n+k-2\choose n-1$ guesses. Does this seem correct?