The answer is $\lfloor n/2\lceil$. At least $\lfloor n/2\lceil$: Pair the players up (ignore one player if $n$ is odd). In each pair, one player guesses that both have the same color and the other player guesses that their colors are different. At most $\lfloor n/2\lceil$: Over all possible color distributions, a strategy for a single player will give at most $50$ percent correct guesses. Hence the expected number of correct guesses is $n/2$, and there exists at least one distribution (= one point in the underlying probability space) for which the number of correct guesses is at most $n/2$.

I've seen a similar problem on AoPS before. The "at most" part is the same. For the lower bound, represent black as $0\in\mathbb F_2$ and white as $1\in\mathbb F_2$. Make every person compute the sum of the others' values (in $\mathbb F_2$). Then make $\lfloor 0.5n\rfloor$ say the hat color associated with the value they computed, and the rest say the hat color associated with one minus the value they computed. Depending on the sum of all values in the circle, either everyone in the first group or everyone in the second group will guess the correct color. (This solution is not originally mine)

Unfortunately these solutions are not correct because this problem has a twist from the classical one: the players are all required to follow the same strategy (I made the same mistake myself of thinking this was the classical problem...)

rsa365 wrote: Unfortunately these solutions are not correct because this problem has a twist from the classical one: the players are all required to follow the same strategy (I did the same mistake myself of thinking this was the classical one...) One must then define "same." For example, is it not the "same" strategy if she says "if you are south of <line of latitude> then do <thing> and else do <other thing>?"

The problem does leave this issue open, but I would define it as the strategy must have a "circular symmetry", meaning that if you rotate the players in the circle you will get the same answers from each of them. If you think about it for a while it does start to feel as a well-defined problem...

Hmm so to be rigorous we could say a "strategy" is a (perhaps nonlinear) map $f:\mathbb F_2^{\times n-1}\to \mathbb F_2$? The reasoning for the above definition is 1.) invariance wrt external data (position, planet, day of the week, etc...) and 2.) preservation of "handedness" (the order of the entries matter).

Yeah, I think that is an even better way to formalize what is meant by an strategy (and hence what is meant by everyone having the same strategy)

$0$ for $n=2$ and $1$ for $n=3,4$. (I have yet to prove anything). Edit: an example of a map that guaranteed at least $1$ correct guess for $n=3$ is $f:[0,0]\mapsto 0,\ [1,0]\mapsto 1,\ [0,1]\mapsto 0,\ [1,1]\mapsto 1$.

For odd $n$, one can reach at least $1$ correct guess by "always guessing the color of the left neighbor".

We generalize the above approach; in fact, if $n$ is divisible by an odd prime $p$, one may get a score of $\frac{n}{p}$ by doing "guess the hat of the person $p$ to the left." This breaks the group into $\frac np$ chains, each of which is guaranteed at least one correct answer. However if $n$ is a power of two I am not sure of what to do.

It seems that this strategy guarantees something like $n/3$ correct answers: if more than $2/3$ of the hats you see are black say black, otherwise say white

rsa365 wrote: It seems that this strategy guarantees something like $n/3$ correct answers: if more than $2/3$ of the hats you see are black say black, otherwise say white What if you have $20$ black hats and $10$ white hats. All the white hats will guess black and all the black hats will guess white, giving $0$ correct guesses.

Indeed this doesn't work - for a moment I thought this strategy did not have the same problem as it has for 1/2 but it does

We claim that the answer is $\left\lfloor\frac{n-1}{2}\right\rfloor$.

DVDthe1st wrote: We claim that the answer is $\left\lfloor\frac{n-1}{2}\right\rfloor$.

The strategy has to be the same for everyone.

@above, "same for everyone" is a vacuous statment. The method proposed by DVDthe1st adheres to both definitions of "sameness" in posts 6 and 7. (If you have a different definition, then outline it.)

I think, "the same strategy" means that the answer of $i$-th person is $f(x_{i+1},x_{i+2},\dots,x_{i-1})$, where $f$ is a function from $\{B,W\}^{n-1}$ to $\{B,W\}$, $x_m$ is the colour of $m$-th person ($i$-th person knows $x_{i+1},\dots,x_{i-1}$, so may evaluate the value of $f$).

Fedor Petrov wrote: I think, "the same strategy" means that the answer of $i$-th person is $f(x_{i+1},x_{i+2},\dots,x_{i-1})$, where $f$ is a function from $\{B,W\}^{n-1}$ to $\{B,W\}$, $x_m$ is the colour of $m$-th person ($i$-th person knows $x_{i+1},\dots,x_{i-1}$, so may evaluate the value of $f$). If I'm not mistaken, the solution in post 15 satisfies this criterion as well. (This was the definition I was trying to get at in post 7, but I can see why it is not clear from what I wrote.)

Could someone explain me the solution in post 15? I don't understand Ana's strategy so much and also the solution assumes that $n$ is even.

math90 wrote: Could someone explain me the solution in post 15? I don't understand Ana's strategy so much and also the solution assumes that $n$ is even. Below is a rephrasing of the solution given by DVDthe1st, with the minor modification that the "random choice" step was eliminated in favor of simply guessing "black" in order to meet the deterministic aspect of Fedor Petrov's "sameness" criterion. The reader is highly encouraged to draw along; this is meant to be an interactive post Pretend you are a person in the circle, and WLOG you are facing the center. Observe your $n-1$ compatriots and note the color of their hats. Draw a map of the situation superimposed on the complex plane so that you stand at $1\in\mathbb C$, and moving from right to left, your fellows stand at $e^{\frac{2i\pi}{n}},e^{2\cdot\frac{2i\pi}{n}},\dots,e^{(n-1)\cdot\frac{2i\pi}{n}}$. Associate each person to the complex number upon which they stand. Let $W$ be the set of complex numbers whose corresponding individuals you observe to wear a white hat. Compute $z=\sum_{\omega\in W}\omega$. There are precisely three cases: I. If $\Im(z)=0$, then guess "white" as the color of your hat if $z=-1$, and guess "black" otherwise. II. If $\Im(z)>0$, then guess "white" as the color of your hat if you see an odd number of people with white hats, and "black" otherwise. III. If $\Im(z)<0$, then guess "white" as the color of your hat if you see an even number of people with white hats, and "black" otherwise. To see why this strategy works, suppose Ana is standing above the circle. She chooses a "best friend" from the $n$ people in the circle, and copies his map, so that she retains the person-number associations. Because Ana sees everyone, she can write down the set $W'$ who consists of all individuals wearing a white hat, and thus can compute $z'=\sum_{\omega\in W'}\omega$. The idea is that the maps drawn by all the players are really just rotations of Ana's "master map," and furthermore if $z'\neq 0$, then the set of people who compute $\Im(z)>0$ geometrically lie on one side of $\{rz'|r\in\mathbb R\}$ on Ana's map, and visa versa. This is because $\Im(1+z)>0\iff \Im(z)>0$ (and again visa versa). Explicitly, there are three mutually exclusive cases: I. $z'=0$, in which case everyone has computed the correct hat color. (check that this is indeed the case) II. There is an integer $k$ with $\frac{e^{k\cdot\frac{2i\pi}{n}}}{z'}\in\mathbb R$, in which case, the person corresponding to $e^{k\cdot\frac{2i\pi}{n}}$ potentially guesses incorrectly, while the $n-1$ remaining act as in case III. (below) III. If none of the above is true, then the strategy reduces to that in post #3 (roughly half of the players assume the total number of white hats is even, and the rest assume said number is odd.)

Here is a non-constructive solution using Hall's marriage theorem, that (almost) solves the generalised problem where Bob has $k$ colours to choose from. The probabilistic argument presented above gives an upper bound of $\left \lfloor \frac{n-1}{k} \right \rfloor$ correct guesses in the worst case. We will reach this bound when $n$ is odd (or $k$ even), but for even $n$ we will only get $\left \lfloor \frac{n-2}{k} \right \rfloor$ guesses right. I don't know if this can be fixed.