Solution
Two Players, Five Colours
Show the problem again
Alice and Bob agree on a strategy, after which each receives a hat in one of five colours, chosen uniformly and independently. Each sees the other's hat but not their own, and no communication is allowed once the hats are on. Simultaneously, each must name a colour as their guess for their own hat (no passing). The pair wins if at least one guess is correct. What is the largest possible probability of winning? Give a reduced fraction.
Worked solution
The answer is 2/5. Describe a world by the pair (a, b) of Alice's and Bob's colours, 25 equally likely pairs in all. Alice's strategy is a function f giving her guess as a function of Bob's colour b; she is right exactly in the worlds (f(b), b), one for each b, so she is right in exactly 5 of the 25 worlds. The same holds for Bob: his guess depends only on a, and he is right in exactly 5 worlds, one for each a. The pair wins in at most 5 + 5 = 10 worlds, so the winning probability is at most 10/25 = 2/5. This is attainable: Alice guesses that her colour equals Bob's, and Bob guesses that his colour is the next colour after Alice's (in a fixed cyclic order of the five colours). Then Alice is right when a = b, and Bob is right when b = a + 1, two disjoint sets of 5 worlds each, giving 10 winning worlds of 25. (A program searching over all 5^5 strategies for Alice, with Bob's best reply chosen optimally for each, confirms that 10 is the maximum.)
Source: Small case of the classic hat-guessing game with many colours, in wide circulation; no traceable original source. Statement written for AxiomIQ.