Red and Blue Hats Puzzle
From
"Aaronson, Scott. Quantum Computing Since Democritus. Cambridge university press, 2013"
\(n\) people sit in a circle.
Each person wears either a red hat or a blue hat,
chosen independently and uniformly at random.
Each person can see the hats of all the other
people, but not his/her own hat.
Based only upon what they see,
each person votes on whether or
not the total number of red hats is odd.
Is there a scheme by which the outcome of the
vote is correct with probability greater than \(\frac{1}{2}\)?
Solution
Each person decides his/her vote as follows: if the
number of visible blue hats is larger than the number of visible red
hats, then vote according to the parity of the number of visible red
hats. Otherwise, vote the opposite of the parity of the number of
visible red hats. If the number of red hats differs from the number
of blue hats by at least 2, then this scheme succeeds with certainty.
Otherwise, the scheme might fail. However, the probability that the
number of red hats differs from the number of blue hats by less than
2 is small – \(O(\frac{1}{\sqrt N})\).
:- use_module(library(mcintyre)).
:- mc.
:- begin_lpad.
red(N,R):binomial(R,N,0.5).
blu(N,B):-
red(N,R),B is N-R.
odd(N):-
red(N,R),
1 =:= R mod 2.
vote_odd(N):-
vote_odd_blu(N,VB),
vote_odd_red(N,VR),
V is VB+VR,
V > N/2.
correct(N):-
odd(N),
vote_odd(N).
correct(N):-
\+ odd(N),
\+ vote_odd(N).
vote_odd_blu(N,B):-
red(N,R),
blu(N,B),
VisibleBlu is B-1,
VisibleBlu>R,
1 =:= R mod 2.
vote_odd_blu(N,0):-
red(N,R),
blu(N,B),
VisibleBlu is B-1,
VisibleBlu>R,
0 =:= R mod 2.
vote_odd_blu(N,0):-
red(N,R),
blu(N,B),
VisibleBlu is B-1,
VisibleBlu =< R,
1 =:= R mod 2.
vote_odd_blu(N,B):-
red(N,R),
blu(N,B),
VisibleBlu is B-1,
VisibleBlu =< R,
0 =:= R mod 2.
vote_odd_red(N,R):-
red(N,R),
blu(N,B),
VisibleRed is R-1,
B>VisibleRed,
1 =:= VisibleRed mod 2.
vote_odd_red(N,0):-
red(N,R),
blu(N,B),
VisibleRed is R-1,
B>VisibleRed,
0 =:= VisibleRed mod 2.
vote_odd_red(N,0):-
red(N,R),
blu(N,B),
VisibleRed is R-1,
B =< VisibleRed,
1 =:= VisibleRed mod 2.
vote_odd_red(N,R):-
red(N,R),
blu(N,B),
VisibleRed is R-1,
B =< VisibleRed,
0 =:= VisibleRed mod 2.
:- end_lpad.
What is the probability that the scheme returns the correct result when there are 10 people?
mc_sample(correct(10),1000,Prob).