12
$\begingroup$

Each of an infinite number of wizards is independently assigned a black or white hat based on the outcome of an unbiased coin flip. Each wizard can see everyone's hat but his own.

At the count of three, each wizard must simultaneously either guess his own hat color or abstain from guessing. The wizards collectively win if an infinite number of them guess correctly and none of them guess incorrectly.

Can the wizards devise a strategy so that they usually win?

The wizards can plan and move around before the hats are distributed, but immediately upon hat distribution, a spell is cast so that they are all completely paralyzed up until the moment of their simultaneous guess. No communication is allowed.

$\endgroup$
23
  • 4
    $\begingroup$ Is it relevant that they are wizards? Are they allowed communication? Are the hats pointy? $\endgroup$
    – DrunkWolf
    Commented Jan 18, 2016 at 8:05
  • $\begingroup$ @DrunkWolf Some hats are square, but since they are in limited quantities, we politely asked each wizard to hand us his pointy hat for recoloring. $\endgroup$ Commented Jan 18, 2016 at 10:45
  • 1
    $\begingroup$ How do the wizards collectively guess? If they go one by one, they'll never finish saying their guesses. $\endgroup$
    – BruceWayne
    Commented Jan 18, 2016 at 14:18
  • 1
    $\begingroup$ Does "infinite" here mean "countably infinite," or could it be another infinity? Are we assuming the Axiom of Choice? What about the Continuum Hypothesis? $\endgroup$
    – jwodder
    Commented Jan 18, 2016 at 21:11
  • 2
    $\begingroup$ Hmm...does it matter if there are more than countably infinite wizards? Can't they just choose a countable subset of themselves and have the rest abstain? $\endgroup$
    – dshin
    Commented Jan 18, 2016 at 21:36

11 Answers 11

5
$\begingroup$

This solution is based on the Jose's answer, but it construct a strategy with an arbitrary win chance.

Winning with an arbitrary win chance

xnor showed int this post that a group with $2^i-1$ person can achieve a win chance of $1-\frac{1}{2}^i$.
Or in other words for all $p\in [0,1)$ there exists an group size $n$ so that the group has a win chance of at least $p$.

Now we make infinity many groups numbered from 1 onward. The $i$'th group should have a win chance of at least $p_i = (1-\epsilon)^{\frac{1}{2}^i}$.

To achieve that the groups must have $2^{\lceil log_2(\frac{1}{1-p_i}) \rceil}-1$ member.

The probability that all groups win is at least $$\prod_{i=1}^\infty p_i=\prod_{i=1}^\infty (1-\epsilon)^{\frac{1}{2}^i} =(1-\epsilon)^{\sum_{i=1}^\infty\frac{1}{2}^i} = (1-\epsilon)^1 = 1-\epsilon$$

So for all $\epsilon>0$ there is strategy that has a fail chance at most of $\epsilon$; or in other words: There is a strategy that has a win chance as close to 100% as you want (at least if you want it to be lower than 100%).

$\endgroup$
6
  • $\begingroup$ This is the only submission that is correct. I would like to accept it but feel it can be greatly simplified. Why not simply cite xnor's answer to say that you can partition the wizards into finite groups where the $i$'th group wins with probability $(1-\epsilon)^{2^{-i}}$? $\endgroup$
    – dshin
    Commented Jan 20, 2016 at 1:10
  • $\begingroup$ @dshin I have added that version. But it only shows that such a strategy exists. I think that isn't enough for the wizards; they also want to know what the strategy is. $\endgroup$
    – Etoplay
    Commented Jan 20, 2016 at 11:11
  • $\begingroup$ Nice. You have both shown existence and constructed the strategy through your edit. Now you can delete everything from "Complex constructing version..." onwards. $\endgroup$
    – dshin
    Commented Jan 20, 2016 at 16:33
  • $\begingroup$ To expound on my comment, imagine a solution to a different problem that starts, "Partition the infinite wizards into groups of size 1, 2, 3, 4, 5, ...". That does not just prove existence; it provides construction. Assigning countably infinite elements to finite sets of given size is trivial and needs no further explanation. $\endgroup$
    – dshin
    Commented Jan 20, 2016 at 16:37
  • $\begingroup$ I kept the complex version too because the simple version didn't specify the group sizes. But I realized that the group sizes are easily calculated from the win probabilities. $\endgroup$
    – Etoplay
    Commented Jan 20, 2016 at 18:04
12
$\begingroup$

Create infinite groups of finite size with $$size = (2^k)-1 ; k=2,3,...,infinity$$

Each of the groups will handle themselves as per the optimal strategy in this answer by xnor

Thus each group has a probability of correctly guessing equal to : $$1- \frac{1}{2^k}$$

And the probability that all of the groups guess right is the infinite multiplication of those probabilities, which is at least 56.25%

You may even get a better strategy by starting with k=3 rather than k=2. And the higher k you start with the better your strategy will be.

Demonstration that the infinite multiplication $\ge .5625$

Let $f(k)$ be the result of the multiplication up to the k-th term. Thus :

$$f(2) = 0.75 $$ $$f(k+1) = f(k) * (1- \frac{1}{2^{k+1}}) = f(k) - f(k)*\frac{1}{2^{k+1}}$$

All the terms in the multiplication are greater than 0 and less than 1 thus we know that for all $k \gt 2$ : $f(k+1) \lt f(k)$. So for all k we have $f(k) \le f(2)$. Hence :

$$f(k+1) = f(k) - f(k)*\frac{1}{2^{k+1}} \ge f(k) - f(2)*\frac{1}{2^{k+1}}$$

If we rewrite our infinite multiplication using the previous formula we have an infinite sum which is a lower bound (L) of our infinite multiplication :

$$L = f(2) - f(2)* \sum_{k=2}^\infty \frac{1}{2^{k+1}} = .5625 $$

And we conclude that the strategy here explained has a probability of success at least 56.25%

$\endgroup$
15
  • $\begingroup$ If I understand your solution correctly, this will only produce one correct guess. $\endgroup$
    – dshin
    Commented Jan 18, 2016 at 13:43
  • $\begingroup$ Indeed, you are right. I have reread your answer and just noticed you need infinite answers. So, yes, my answer is wrong. $\endgroup$ Commented Jan 18, 2016 at 13:44
  • $\begingroup$ I have redesigned my solution to give infinite guesses. $\endgroup$ Commented Jan 18, 2016 at 14:10
  • $\begingroup$ Almost, but not quite rigorous. Hint: what if you choose your group sizes so the $k$'th group succeeds with probability $p_k > e^{-c2^{-k}}$? $\endgroup$
    – dshin
    Commented Jan 18, 2016 at 14:30
  • 1
    $\begingroup$ Taking OP's hint, you should change the $k$-th group sizes to $f(k) = \left\lceil\frac{c}{2^k} - \log\left(e^{\frac{c}{2^k}}-1\right)\right\rceil$, which would make the group probability to be $p_k > e^{-\frac{c}{2^k}}$, and overall probability to be $p > e^{-c\cdot\sum_{k=1}^{\infty}\frac{1}{2^k}} = e^{-c}$ and by making $c$ smaller, you can reach any probability as close to 1 as you want. $\endgroup$
    – justhalf
    Commented Jan 19, 2016 at 2:51
6
$\begingroup$

As other answers have shown that any probability of success less than $100\%$ can be achieved, let me show that no strategy can achieve a success rate of $100\%$. The argument is quite simple: Number the wizards as $1,\,2,\,3,\ldots$ and let $p_i$ be the probability that the $i^{th}$ wizard will guess at all (given a random arrangement of hats). Unfortunately, the wizard necessarily guesses wrongly with probability $\frac{p_i}2$ since they must choose their guess based on the other's arrangement of hats, but this knowledge is independent of their hat color. Thus, to achieve no wrong guesses, $p_i=0$. However, if the event of any given wizard guessing almost never happens, the event of infinitely many wizards guessing almost never happens either which is a problem.

This proof, however, does not present a problem to the fact that probabilities less than $100\%$ are obtainable; these essentially work by choosing the individual $p_i$ to be small (but have infinite sum) and choosing them such that the losses are "consolidated" (e.g. everyone guesses wrong if anyone does) but the wins are spread out (e.g. one wizard guessing correctly decreases the probability that others do).


One should note that this argument fails for uncountably many wizards. A strategy for $2^{|\mathbb N|}$ wizards that succeeds with probability $100\%$ (assuming this probability is well defined) is presented below. The strategy given here by xnor can be extended fairly naturally. To summarize the strategy there for $2^{n}-1$ wizards:

The wizards are put into bijection with the non-empty subsets of $\{1,2,\ldots,n\}$. Then, we compute a new set $S$ by letting $s\in S$ if, there are an odd number of wizards who have black hats and whose associated sets include $s$. Any wizard who can guess their own hat color in a way that would make $S$ empty will make the opposite guess.

And the lemmas one might need to show that this strategy is effective would be noting that $S$ can be any subset of $\{1,\ldots,n\}$ with equal probability and that, if it is non-empty, one wizard will make a guess (in particular, the wizard associated with the set $S$).

To extend this, let $W$ be the set of wizards. Choose some bijection $f:W\rightarrow P(\mathbb N)\setminus\{\emptyset\}$. Next, let $E$ be some function $E:P(W)\rightarrow \{0,1\}$ such that, if two sets $S$ and $S'$ differ by one element (i.e. $|(S\setminus S')\cup (S'\setminus S)|=1$) then $E(S)=1-E(S')$. The existence of such an $E$ follows from the axiom of choice (in the finite case, we can just use $E(S)=|S|\text{ mod }2$, which breaks down for infinite $S$). Then, consider the set $S\subseteq \mathbb N$ defined as $$S=\{n\in\mathbb N : E(W_n)=1\}$$ where $W_n$ is the set of wizards $w$ whose hats are black and for which $n\in f(w)$. Each wizard guesses that $S$ is not empty and thus, if one of their choices would make $S$ zero, they do not make the guess. Notice that, if $S$ is not empty, then changing the hat color of the wizard associated with $S$ would make it empty - thus, that wizard is able to deduce the color of their hat if they know $S$ is not empty.

This strategy therefore lets a single wizard guess correctly whenever $S$ isn't empty (and if it is, every wizard guesses incorrectly). Noting that there is a unique arrangement of the hat colors on the wizards associated with the sets $\{1\},\,\{2\},\,\{3\},\ldots$ that makes $S$ empty given the hat colors of everyone else, and this arrangement must be achieved with probability $0$ as it requires infinitely many independent events of probability $\frac{1}2$ to occur. Partitioning the wizards into countably many uncountable groups and applying this strategy gives countably many correct guesses with probability $1$.

(I note "assuming the probability is well defined" because the mathematical formalisms handling probability tend to not play well with those handling the axiom of choice; in particular, it's not obvious that the set of positions for which this strategy wins is measurable, which would mean no probability could be assigned to it. It's possible that such strategies exist for countably many wizards too)

$\endgroup$
5
  • $\begingroup$ Do you know of any measurable sets whose construction require the axiom of choice? $\endgroup$
    – dshin
    Commented Jan 21, 2016 at 5:44
  • $\begingroup$ Answer to my question here. That gives me hope that your set might be measurable. I'm very curious to find out the answer! $\endgroup$
    – dshin
    Commented Jan 21, 2016 at 7:04
  • $\begingroup$ @dshin Really, it's not too hard to use AC to make a measurable set - just make a nasty subset of something which already has measure $0$. It just that AC opens us up to the possibility that sets aren't measurable. Indeed, for any $\varepsilon$, it is possible to choose $E$ such that the set of failures of this strategy is a subset of a set of measure $\varepsilon$. (But we need to show that a fixed $E$ yields that the set of failures is a subset of a set of measure $0$) Unfortunately, this doesn't convince me of anything, because I could always squish a Vitali set into $[0,\varepsilon]$. $\endgroup$ Commented Jan 21, 2016 at 14:35
  • $\begingroup$ This link has some interesting information which might be of help. $\endgroup$
    – dshin
    Commented Jan 24, 2016 at 17:18
  • 1
    $\begingroup$ @dshin The link, unfortunately, takes the measure and space of events to be variable, whereas it is fixed here. (And given that $P(\mathbb R)$ is not an inaccessible cardinal, the result cited there tells us that we cannot have all subsets be measurable - but this can be proven with less machinery). The question of whether this strategy has a measurable set of successes strikes me as a question that could be mathematically interesting on its own. It's certainly beyond me. (To be honest, my money is on "no" after some reflection, since the set $\{n\in P(\mathbb N):E(n)=0\}$ is non-measurable) $\endgroup$ Commented Jan 24, 2016 at 18:56
5
$\begingroup$

Another option of 'sorting' the wizards would be to:

  • Start off with two wizards (put them someplace where there is a lot of room around them).
  • Now a third wizard joins in.
  • He sees that the first two wizards have similar hats (let's say white) so he stands on the left of the both wizards.
  • Now a fourth wizards joins in.
  • He sees that two wizards are wearing white hats and one is wearing a black hat. He goes and stand in between the wizard with the white hat and the wizard with the black hat.

Now, regardless of the fourth wizard's own hat color, he will always be sorted next to his own color (since there are only two possibilities).

W = White hat B = Black hat

  • First two wizards : W W
  • Three wizards : W W B
  • Four wizards : W W W B
  • Five wizards : W W W B B
  • Six wizards : W W W B B B

As long as the room is big enough, this method will sort all the wizards and will (assuming the number really is infinite) tell all the wizards that are in between two of the same colored hats their own colored hat as well. So in the end only the last wizard will have to "guess" (or as stated by DrunkWolf, he can abstain about) which hat he has.

This answer assumes the wizards have no means of communicating with each other.

$\endgroup$
14
  • 3
    $\begingroup$ That is some fast moving wizards... 3 seconds to form an infinite line. $\endgroup$
    – DrunkWolf
    Commented Jan 18, 2016 at 9:16
  • 2
    $\begingroup$ On a more serious note, the last wizard should never guess, since abstaining is allowed. $\endgroup$
    – DrunkWolf
    Commented Jan 18, 2016 at 9:56
  • 5
    $\begingroup$ The wizards are infinite. There is no last wizard. $\endgroup$
    – GOTO 0
    Commented Jan 18, 2016 at 10:10
  • 3
    $\begingroup$ And showing everybody where the middle of the row is (by joining at that place) isn't communication? $\endgroup$
    – Etoplay
    Commented Jan 18, 2016 at 13:01
  • 2
    $\begingroup$ @MarcDiMillo: That was added later as a clarification by the OP to address the issue in this answer. $\endgroup$
    – justhalf
    Commented Jan 19, 2016 at 2:36
3
$\begingroup$

As the number of hat-wizards approaches infinity, the probability of winning approaches 100%

Using a strategy similar to the one given by xnor to solve the case where n=15 (and adding an additional digit each time ceil(log2(n+1)) increases), the wizards' odds of losing will become arbitrarily small as the number of wizards becomes arbitrarily large.

However, that does not extend to infinity itself

The strategy provided there does not work at infinity, as it would require vectors of infinite length, which is beyond even the most learned and magical of wizards.

Furthermore, since the probability of losing remains positive (if very small) for all non-infinite n, the infinite wizards cannot divide themselves into infinitely-many finitely sized subgroups, because, given infinite trials, at least one of those subgroups would lose.

I believe that a solution where infinitely many wizards all guess correctly is impossible

EDIT: As Cruncher points out in a comment, the following is fallacious reasoning. I'm not going to amend this answer, because someone else already arrived at just such a strategy above!

This riddle, as stated, requires that an infinite number of wizards guess correctly - not merely one. Thus, infinitely many wizards must be able to deduce their hat with 100% certainty, and otherwise stay silent. No strategy existing for this puzzle has ever given any wizard 100% certainty of their hat.

If the constraint requiring infinitely many wizards guess right were lifted, the finite solution could be applied, by having a predetermined finite (but very large) subset of wizards use the finite strategy, while all others remain silent.

$\endgroup$
6
  • $\begingroup$ "given infinite trials, at least one of those subgroups would lose" - what exactly do you mean by this? $\endgroup$
    – dshin
    Commented Jan 18, 2016 at 13:52
  • $\begingroup$ If you have a solution for the case where only one wizard has to know his hat with certainty then surely you can divide the Wizards of this problem into an infinite amount of infinite groups for that sub problem and use the solution for each subgroup, resulting in an infinite amount of positives? $\endgroup$
    – DrunkWolf
    Commented Jan 18, 2016 at 14:50
  • $\begingroup$ What if the trials diminish in probability? Like if the probability of failing on the first is 1/4, failing on the second is 1/8, failing on the third is 1/16, etc. etc. you could arrive at some probability of an infinite number of wizards guessing correctly with no failed trials. $\endgroup$
    – Cruncher
    Commented Jan 18, 2016 at 18:19
  • $\begingroup$ @dshin I think he means that no matter the probability of a group guessing correctly, as long as it's not 1, one of the groups will fail out of the infinite number of groups. This of course fails because of the fallacious assumption that all groups must have the same probability of guessing correctly. $\endgroup$
    – Cruncher
    Commented Jan 18, 2016 at 18:27
  • $\begingroup$ @Cruncher Good point! That would, indeed, make this answer completely false. Thank you for the education! $\endgroup$
    – Tim C
    Commented Jan 18, 2016 at 18:40
0
$\begingroup$

If there are infinite number of wizards and wizards can see each other (assuming wizards can see infinite number of wizards) and flipping coin is unbiased, the solution is that every wizard know their hats already since the chance of getting head or tail is exactly 50% if number of wizards goes to infinity.

$\endgroup$
2
  • 2
    $\begingroup$ Nice idea, but unfortunately it doesn't work - since even if exactly 50% of an infinite number of wizards have black hats, then flipping one of the black hats to be white will leave exactly 50% of each colour... $\endgroup$
    – psmears
    Commented Jan 18, 2016 at 13:57
  • $\begingroup$ The chance for each wizard is always 50% black and 50% white regardless of the others. No wizard would ever 'know' from looking at anyone else's hat. Furthermore, a coin does not have to land an equal amount heads and an equal amount tails and your strategy would likely result in more incorrect guesses than correct guesses since the minority would guess correctly and the majority would guess incorrectly... $\endgroup$ Commented Jan 18, 2016 at 23:02
0
$\begingroup$

I'm going to say it's not possible, given these assumptions about the rules are correct:

  1. Each wizard can see every other wizard's hat. Apart from that, no knowledge or information may be imparted to one between getting a hat and making a guess. The wizards aren't able (or allowed) to notice any other details about the other wizards, like for example whose hat they're looking at.

  2. The coin flips (& therefore the hats assigned) truly are completely random & independent.

If these facts are true... each wizard receives absolutely no relevant information about their own hat before making his or her guess. Every wizard who guesses really is guessing, and has a 50% chance of being correct. Any non-infinite number of guesses fails to satisfy the first condition of victory, so [edited replacing my 'infinite number of guesses' bit which dshin responded to]...

The probability of two unrelated events A and B occurring is P(A) * P(B). The accuracy (even if not the contents) of a wizard's guess is not related to that of another wizard's guess. Therefore as the number of wizards approaches infinity, the probability of all their guesses being correct -- P(A Wizard Guesses Correctly) ^ Number of Wizards Guessing -- approaches 0.

Short answer: No. The wizards lose.

EXCEPT I'M A BIG DUMMY AND

i did NOT do my hat-counting puzzle research

also infinity is weird and i forgot to take that into account as well

$\endgroup$
5
  • $\begingroup$ I'm in agreement with everything you write up until the sentence, "An infinite number of guesses are infinitely unlikely to all be correct." That statement does not logically follow from what comes before it. $\endgroup$
    – dshin
    Commented Jan 19, 2016 at 6:10
  • $\begingroup$ Sorry, let me rephrase and be a little more technical. $\endgroup$
    – Droqen
    Commented Jan 19, 2016 at 11:04
  • $\begingroup$ Oops, didn't mean to send that. does pressing ctrl+enter add a line break instead of sending? $\endgroup$
    – Droqen
    Commented Jan 19, 2016 at 11:05
  • $\begingroup$ Nope. Okay. --> The probability that a wizard's guess is correct is 0.5; the probability of two unrelated events occurring -- P(A and B) -- is P(A) * P(B). Sure, the wizards can agree to make certain guesses in certain conditions so their guesses aren't entirely unrelated, but it seems to me that the accuracy of the guesses themselves is. P(a specific wizard's guess is correct)^(a number of wizards approaching infinity) = 0.5^(a number approaching infinity) = a number that approaches 0. I... should probably look up how to do fancy mathy lim formatting. $\endgroup$
    – Droqen
    Commented Jan 19, 2016 at 11:11
  • $\begingroup$ This is wrong (in the finite case too). It is true that any wizard who guesses has a $50\%$ chance of being wrong. The probability of one wizard guessing correctly can be dependent on the event of another wizard guessing incorrectly - even if they exchanged no information. Consider carefully the answer given by xnor here for the finite case, where if any wizard guesses incorrectly, every wizard does, but if any wizard guesses correctly, no other wizard does. This means the events are decidedly not independent, as you claim here. $\endgroup$ Commented Jan 20, 2016 at 1:09
-1
$\begingroup$

The wizards make groups of three, one is appointed "the chosen one". When they all get their hats, the chosen one of each group can either join or not join their group. Joining means that the other two have the same colored hat, not joining means that they have different colors (this can also be done the other way around). The other two can deduce from the action of the chosen one whether their hat color is the same as or opposite from the color of the other. So two thirds of the wizards can "guess" correctly, the chosen one abstains from guessing.

This is slightly cheaty since this is a form of communication, which I presume is not allowed (if it is, simply ask someone the color of your hat).

$\endgroup$
2
  • $\begingroup$ I've added a clarifying sentence to the end of the problem statement regarding communication. $\endgroup$
    – dshin
    Commented Jan 18, 2016 at 13:45
  • $\begingroup$ That's exactly what came to my mind. Groups of three. One selects two others with the same hat color and one of the selected ones tells the first one if he belongs to their group or not. They don't even have to speak as simply dragging around wizzzards and a yes/no gesture would be sufficient. $\endgroup$
    – Aron_dc
    Commented Jan 18, 2016 at 16:19
-1
$\begingroup$

What if they all abstain from guessing? Wouldn't that mean they all won? Nobody guesses incorrectly, and the color of everyone's hat is totally irrelevant. Or did I miss something.

$\endgroup$
1
  • $\begingroup$ That only satisfies half the requirement (that none guess incorrectly); it does not satisfy the first half, that an infinite number guess correctly. $\endgroup$
    – JAB
    Commented Jan 18, 2016 at 20:01
-1
$\begingroup$

Use Magic:

Have each wizard cast a spell on himself/herself that allows himself/herself to "feel" color. To get a sense of what black and white "feel" like touch something black/white before the hats are distributed. Then feel your own hat as it sits on your head and guess from that.

OR

Use some sort of a "Luck" spell/enchantment and guess with the increased luck...

$\endgroup$
1
  • $\begingroup$ upvote for the try :) $\endgroup$ Commented Jan 20, 2016 at 7:33
-1
$\begingroup$

There is only one wizard, but being surounded by cleverly arranged mirrors, it seems like there is an infinity of him. As soon as he get his hat every copy will get the same, and he will win. Any kind of mirrory solution can work.

In the same idea, as wizards, they might use spell to see through their colleagues eyes.

The problem is that as they can't move nor communicate once the hats are on, and as the hats are distributed simultaneously, they can't get any significant hint on what they have, as two neighbours can have black hats as well as whites. So you are stuck with 1/2 per wizard, which will descend to 0 as you reach an infinity of wizard. So they have to cheat one way or another.

$\endgroup$
7
  • $\begingroup$ I don't mind being down voted, but seing as the most voted answer rely on the wizzard moving, which is not possible once the hats are distributed, I'd like to understand why ? $\endgroup$
    – MakorDal
    Commented Jan 19, 2016 at 13:45
  • $\begingroup$ The question is super vague and has been edited many times to counter-act different answers... And apparently suggesting wizards use magic is completely unacceptable... $\endgroup$ Commented Jan 19, 2016 at 17:27
  • $\begingroup$ Everyone's answer is wrong but it seems some people only downvote a couple of the answers. Typical unmoderated community. $\endgroup$ Commented Jan 19, 2016 at 18:24
  • $\begingroup$ @NicolasPierre I will add that the question states the each wizard can see every hat but his own. This could mean that they are not permitted to see their own hat under any circumstance which would make any strategy banking on reflection. $\endgroup$ Commented Jan 19, 2016 at 21:08
  • $\begingroup$ @MarcDiMillo Some are more incorrect than others. The question is looking for an "infinite" number of correct guesses which would mean that not all the wizards could abstain. Whether or not that was edited in after the fact, who knows. And I posted my answer pretty much knowing it would be downvoted. People tend to dislike others who skirt the rules... $\endgroup$ Commented Jan 19, 2016 at 21:13

Not the answer you're looking for? Browse other questions tagged or ask your own question.