Hi,
This is a solution to problem 2 in the the latest Tech review puzzle
corner. It was a nice problem; for a
while I could not come up with a better winning probability than 1/2
even demanding just *at least 1*
correct guess and no incorrect guesses, much less the real problem
which requires an infinite number
of correct guesses.
The justification of the solution may be a bit long; the solution
itself comprises just the first 2 paragraphs.
Regards,
Mark Fischler
---
Problem 2 (Wizards in Hats)
Assign numbers 1, 2, ... to some (countably infinite) set of the
wizards. Now let's define
a sequence of "cabals", where cabal number N is a sequence of length
L= 10*2^N-1 starting
at wizard k, obeying the following rules:
a) The hats on wizards k-3, k-2, k-1 are black, black white
respectively, and on wizards
k+10*2^N-1 through k+10*2^N+1 are white, black black.
b) At most one hat among the wizards in cabal N is black.
c) Cabal N occurs after cabal N-1 (except for number 1, which is the
first sequence of 19 hats,
at most one of which is white, surrounded by the required BBW
... WBB hats).
Most wizards will be able to determine that they are not part of any
cabal; others will be
unsure (they may be part of a cabal if their own hat is white, but not
if it is black); yet others
will know for sure that they are part of a cabal. For example, if
hats 1 through 25 are
BBW ... WBB there the ... stands for 19 hats at least 18 of which are
white, then any wizard among
those 19 who can see 18 other white hats will know she is in cabal 1.
The agreed plan is
that any wizard who knows he is in a cabal will guess his hat is
black, and all others will abstain.
This plan guarantees (shown below) an infinite number of guesses, and
a total probability of any
wrong guess of less than ten percent.
Let's see what happens when this plan is followed. First, there will
be an infinite number of cabals,
since if there were no cabal after cabal N-1, that would mean that
some specific finite sequence
of hats *never* will occur after the end of cabal N-1, which is
impossible given an infinite sequence
of randome hat assignments. Second, each cabal will contain at least
one wizard who is sure
she is in that cabal, because at least one will see the other 10*2^N-2
white hats. Thus there
will be an infinite number of wizards guessing their hat color.
Now let's define a cabal as "evil" if any wizard in that cabal will
guess incorrectly -- if any
cabal is evil, the the wizards lose their contest. Let's look at the
expected number of evil
cabals (which must, of course, be greater than or equal to the
probability of one or more cabals
being evil). The probability of cabal 1 being evil is 1/20 -- there
are 19 configurations of one black and 18 white hats, and only one
with all white hats. Similarly, the probability of cabal N being evil
is 1/(10*2^N). The expected number of evil cabals is thus 1/20 + 1/40
+ 1/80 + ... = 1/10, and the
probability of at least one wrong guess is less than that. So this
plan solves the puzzle.
Note that the expected number of wrong guesses is still infinite: If
one member of a cabal
guesses wrong, it will be because the entire cabal has white hats, so
all the members will
guess wrong. Thus the expected number of wrong guesses is 19/20 +
39/40 + 79/80...,
which of course diverges. The agreed plan has so strongly grouped
the cases of multiple wrong
guesses, that the probability of no wrong guesses at all is left
non-zero, and in fact above 90%.