Variations on colours and hats

Printable View

June 24th 2009, 06:01 PM
Laurent

Variations on colours and hats

Hi everybody,

Here are a few very nice problems about guessing colors of hats, subject to various constraints. All are very quick to state, and have interesting solutions. They may be well known but a quick search on the forum about "hats" gave few answers. One of these problems was just submitted by godelproof in another thread that kept me happily busy tonight...

1) This is the story of N magicians that have been captured by a cannibal (don't ask me how or why). In order to spice things up, this cannibal decides to have the magicians play a game to determine who will eventually be devoured. He gathers his prisonners and explains to them the following rules:
On the next morning, the magicians will have to stand in a long queue, and each of them will be given a coloured hat, either red or blue (any combination is possible). They will be able to see the hats of the people in front of them, but neither those of the people standing behind, nor their own.
Then, one by one, starting with the magician at the tail, the cannibal will ask them for the colour of the hat they're wearing. They will answer loudly, and unbeknowst to the other magicians they will either be freed or killed depending whether the answer was right or wrong. Thus each magician knows the previous answers, but not if they were correct.
During all night, the magicians may prepare a strategy together.

The question is: how many magicians can be saved surely, and how?

NB: the magicians can't provide more information than the very colour they tell to the cannibal. (No accent, no timing,...)
NB2: even though they are magicians, they don't have any supernatural power.

2) What if there are $R$ different colours of hats instead?

3) Again with 2 colors. Assume N is even. Suppose now that the magicians will stand around a circle instead of a line, so that they will see the colour of every other hat but their own. This may look like an advantage... However, since there is no natural starting point, the cannibal will ask them to tell their colour all at once (which means in particular that they can't use the answer of the others). Again, is it possible to save magicians surely? If yes, how many?

4) What if N is odd, or if there are more than 2 colors? [n.b.: I don't have the answer for these ones by now]

The last one is hyper hard, but hyper cool... (well, actually it depends on your tastes)

5***) Consider the same problem as 1) but with infinitely many magicians in the queue: there is a last one (who sees every one else) but no first one. We assume furthermore that, like in 3), no information is communicated between magicians: they don't know what the previous ones answered or if they were killed. Although this is clearly impossible, you are asked to prove that there exists a strategy to save all but finitely many magicians. What if there are more colors?

About this last one:

Spoiler:

The strategy is not constructive: it uses the Axiom of Choice... And, seriously, don't spend too much time on it, or even any...

Enjoy!

Laurent.
July 7th 2009, 04:31 PM
pomp

If the last one only has a countably infinite number of magicians then I think I have it:

Spoiler:

The need for the axiom of choice suggests to me that we will be needing to pick representatives from certain sets at some point.

Each player has finitely many hats behind him and infinitely many in front of him, this is a clue at how to save all but finitely many magicians.

So, before they get given hats, the magicians should notice that since there are a COUNTABLY finite number of them, that they can set up a bijection from their hats to $\mathbb{N}$ and assign a colouring function $\phi$ which takes a given hat to RED or BLUE.

Here's where the axiom of choice comes in. Any two colouring functions $\phi$ and $\psi$ are equivalent in the sense of an equivalence relation (easily proved) if they differ in only finitely many places. These functions can therefore be partitioned into equivalence classes.

Now, the strategy is then as follows; before given hats, the magicians choose a reprasentative from each equivalence class (a la Axiom of Choice)
When they are given hats, let the actual colour of magician i's hat be $\phi(i)$ , then since each magician has infintely many hats in front of him he can immediatlely (I guess this is where his magician powers come into it, as they would all need to be able to process a lot of info very quickly for this to work) see which equivalence class $\phi$ is in. Suppose they agreed on a representative $\phi_R$ ~ $\phi$ before hand, every magician guesses that their own hat is given by $\phi_R(i)$

Due to the setup, only finitely many of them can be wrong. I think.

I have no idea how to approach different cardinalities, hopefully someone else does. Nice question though.

Cheers,
pomp
July 8th 2009, 02:51 AM
Swlabr

Quote:

Originally Posted by pomp

If the last one only has a countably infinite number of magicians then I think I have it:

Spoiler:

The need for the axiom of choice suggests to me that we will be needing to pick representatives from certain sets at some point.

Each player has finitely many hats behind him and infinitely many in front of him, this is a clue at how to save all but finitely many magicians.

So, before they get given hats, the magicians should notice that since there are a COUNTABLY finite number of them, that they can set up a bijection from their hats to $\mathbb{N}$ and assign a colouring function $\phi$ which takes a given hat to RED or BLUE.

Here's where the axiom of choice comes in. Any two colouring functions $\phi$ and $\psi$ are equivalent in the sense of an equivalence relation (easily proved) if they differ in only finitely many places. These functions can therefore be partitioned into equivalence classes.

Now, the strategy is then as follows; before given hats, the magicians choose a reprasentative from each equivalence class (a la Axiom of Choice)
When they are given hats, let the actual colour of magician i's hat be $\phi(i)$ , then since each magician has infintely many hats in front of him he can immediatlely (I guess this is where his magician powers come into it, as they would all need to be able to process a lot of info very quickly for this to work) see which equivalence class $\phi$ is in. Suppose they agreed on a representative $\phi_R$ ~ $\phi$ before hand, every magician guesses that their own hat is given by $\phi_R(i)$

Due to the setup, only finitely many of them can be wrong. I think.

I have no idea how to approach different cardinalities, hopefully someone else does. Nice question though.

Cheers,
pomp

I don't think you can do it for uncountably many magicians, as I don't thik the problem actually makes sense. If they are standing in a line each saying the colours one after another then you can surely label them with the natural numbers. There must be a first to answer, and a second, and a third, etc.

I may, of course, be wrong.
July 8th 2009, 05:54 AM
pomp

Quote:

Originally Posted by Swlabr

I don't think you can do it for uncountably many magicians, as I don't thik the problem actually makes sense. If they are standing in a line each saying the colours one after another then you can surely label them with the natural numbers. There must be a first to answer, and a second, and a third, etc.

Good point, I think you're right there.
July 8th 2009, 09:56 AM
Jose27

Quote:

Originally Posted by Swlabr

I don't think you can do it for uncountably many magicians, as I don't thik the problem actually makes sense. If they are standing in a line each saying the colours one after another then you can surely label them with the natural numbers. There must be a first to answer, and a second, and a third, etc.

I may, of course, be wrong.

Doesn't the axiom of choice imply a well-ordering of the real numbers?
July 8th 2009, 10:55 AM
Swlabr

Quote:

Originally Posted by Jose27

Doesn't the axiom of choice imply a well-ordering of the real numbers?

Yes, but every time you are just adding 1...every time a magician gives an answer one more magician is giving an answer. This means we must be working over the natural numbers, doesn't it?
July 8th 2009, 11:20 AM
Jose27

Quote:

Originally Posted by Swlabr

Yes, but every time you are just adding 1...every time a magician gives an answer one more magician is giving an answer. This means we must be working over the natural numbers, doesn't it?

But you're just assigning a real number to a magician and the hypothesis only require that there is a last magician in line (first element in your set), so it makes sense (I think), because when the last one says it's hat colour (taking one element from the set), the next one (which exists because your set is well-ordered) says it's hat colour and so on.

Actually doesn't this argument work for a set of any cardinality (which you can build a well-ordering in using the axiom of choice)?
July 8th 2009, 12:20 PM
Laurent

Quote:

Originally Posted by pomp

If the last one only has a countably infinite number of magicians then I think I have it:

I have no idea how to approach different cardinalities, hopefully someone else does. Nice question though.

Cheers,
pomp

Well done! I liked your remark about where the magical power is involved! You certainly are right (Giggle) (and only magicians can use the axiom of choice...)

Actually, the paragraph in your answer about the bijection between hat colours and $\mathbb{N}$ is weird. You don't need that. $\phi$ is just a function from the set of magicians (whatever it is) to $\{{\rm Red, Blue}\}$ .

Like Jose27 says, the problem with more than countably many magicians still makes sense if they are well-ordered (which is always possible using AC): there is always a next smallest element.
Then either all magicians tell their answer all at once, or they tell it one by one but it will take more than infinitely long: first, countably many will answer, then the next one (whose index is an infinite ordinal number) will answer, etc. Highly mystical.

What I find even more flummoxing in this problem is that the solution works exactly the same if the set of colours is, for instance, the set of real numbers!! Imagine: each magician has a real number written on his hat. One by one, they answer a real number without any knowledge of their own hat. Yet, it is "possible" for them to act in such a way that, after some finite number of magicians, all the others will answer their own number!!! :eek:

After that, don't you dare tell me you believe in the axiom of choice. (Nerd)
July 8th 2009, 01:15 PM
Jose27

Quote:

Originally Posted by Laurent

(and only magicians can use the axiom of choice...)

Do you, by any chance, work in Category theory?
July 8th 2009, 01:18 PM
Swlabr

Quote:

Originally Posted by Laurent

Then either all magicians tell their answer all at once, or they tell it one by one but it will take more than infinitely long: first, countably many will answer, then the next one (whose index is an infinite ordinal number) will answer, etc. Highly mystical.

Well-this is what was confusing me (in your first post, you stipulated "one-by-one"). I mean, how can something take "more than infinitely long"...(Thinking)
July 8th 2009, 01:41 PM
Laurent

Quote:

Originally Posted by Swlabr

Well-this is what was confusing me (in your first post, you stipulated "one-by-one"). I mean, how can something take "more than infinitely long"...(Thinking)

For instance, you can understand it using converging series. Imagine the magicians are indexed by $\mathbb{N}\cup\{\omega\}$ . One by one, the magicians number 1, 2, 3,... give their answer. This will take infinitely long so that the last one, with number " $\omega$ " will never answer. Except if the first one uses 1 minute to answer, the second one 1/2 minute, the third one 1/4 minute,... Because all the magicians except the last one will have answered at time 2(= $\sum_{k\geq 0} \frac{1}{2^k}$ ), and the last one can answer afterward.

But this is still a countable case. If magician number $\omega$ answers first, there is no problem.

This idea can be greatly enhanced howver, like: countably many magicians answer (they have numbers 1,2,3,...), then magician $\omega$ answers, then magician $\omega+1$ answers,... (infinitely many),..., then magician $\omega+\omega(=2\omega)$ answers, then magician $2\omega+1$ ,... you see the scheme, it goes on indefinitely. And then magician $\omega \omega=\omega^2$ answers. Then magician $\omega^2+1$ ,... then $\omega^2+\omega$ ,...,... then $\omega^3$ , you see the scheme, it goes on indefinitely. And then magician $\omega^\omega$ answers. After a while, magician $\omega^{\omega^\omega}$ answers. And after a long while, magician $\omega^{\omega^{\cdots}}$ answers. How many exponents? $\omega$ ! So you can go on with the number of exponents being $\omega+1$ , etc. Got vertigo?

I don't know exactly how long my parallel with converging series can be continued. After the one in the first paragraph, you can consider a second converging series but which sums to 1 (instead of 2), then a third one which sums to 1/2, etc. So you have a converging series of converging series: magician $\omega^2$ can answer afterward. Here there are $\mathbb{N}^\mathbb{N}\simeq \mathbb{R}$ magicians answering, which is uncountable.
July 8th 2009, 01:54 PM
Laurent

Quote:

Originally Posted by Jose27

Do you, by any chance, work in Category theory?

I guess I would't have enough magical power to do that!..., is that what you mean? Actually I work in probability theory, and in this context Banach-Tarski paradox advises me to carefully avoid strong versions of the axiom of choice...
July 8th 2009, 03:38 PM
Jose27

Quote:

Originally Posted by Laurent

I guess I would't have enough magical power to do that!..., is that what you mean? Actually I work in probability theory, and in this context Banach-Tarski paradox advises me to carefully avoid strong versions of the axiom of choice...

Just curious. It's just that the people I know that work in Category theory avoid the axiom of choice like the plague.