If the last one only has a countably infinite number of magicians then I think I have it:
Spoiler:
I have no idea how to approach different cardinalities, hopefully someone else does. Nice question though.
Cheers,
pomp
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 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:
Enjoy!
Laurent.
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.
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)?
Well done! I liked your remark about where the magical power is involved! You certainly are right (and only magicians can use the axiom of choice...)
Actually, the paragraph in your answer about the bijection between hat colours and is weird. You don't need that. is just a function from the set of magicians (whatever it is) to .
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!!!
After that, don't you dare tell me you believe in the axiom of choice.
For instance, you can understand it using converging series. Imagine the magicians are indexed by . One by one, the magicians number 1, 2, 3,... give their answer. This will take infinitely long so that the last one, with number " " 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(= ), and the last one can answer afterward.
But this is still a countable case. If magician number 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 answers, then magician answers,... (infinitely many),..., then magician answers, then magician ,... you see the scheme, it goes on indefinitely. And then magician answers. Then magician ,... then ,...,... then , you see the scheme, it goes on indefinitely. And then magician answers. After a while, magician answers. And after a long while, magician answers. How many exponents? ! So you can go on with the number of exponents being , 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 can answer afterward. Here there are magicians answering, which is uncountable.