12 Responses to “Prisoners with Bit Sequences”

1. R. Says:
   May 28th, 2010 at 11:12 pm

   There are three types of hard riddles:
   - those which require recursive logic reasoning (e.g., pirates sharing a treasure)
   - those which require an awesome trick, usually a potential function (e.g., the peg solitaire one)
   - those which require the axiom of choice (e.g., this one)

2. Nadav Says:
   May 29th, 2010 at 4:13 pm

   Yaniv, you’ve just ruined the riddle.
   Rule number 1 of every riddle: There must be a funny story! Otherwise, it’s terribly boring.

   Three terrorists plan a terror attack on a power plant.
   During the attack, they all got arrested, leaving a bomb with a timer at the crime scene.
   They all got sent to lifetime in prison after not telling where the bomb is.
   Since electricity is expensive nowadays, the prison can only afford turning the light on in 2 cells every night, leaving one prisoner in the darkness.
   If the bomb will go off one day, electricity should become even more expensive, and the prison will afford only to turn one light on every night.

   Infinite years later, the three terrorists met god. God said that if at least two of them will know what happen to the bomb, all three terrorists will earn their 72 virgins in heaven. However, if two or more will give a wrong answer, all three will suffer in hell for eternity.

   Help the terrorists.

3. rouli Says:
   May 29th, 2010 at 7:23 pm

   hmm…are the prisoners allowed to read only a finite (though unbounded) number of bits from their sequence?

4. Dan Says:
   June 28th, 2010 at 12:38 am

   Maybe it’s time to post some solutions.

   Interestingly enough, I know of two solutions so far, each based on a rather high-end concept involving the axiom of choice. One solution I came up with on my own, the other I heard as an immediate response from at least two people (though the immediate part was only the main idea, and not the complete solution – actually, I’m not sure if it really works any more, read and find out).

   First solution (warning: heavy set theory!):
   This is a rather axiomatic approach, based on making some reasonable assumptions about the strategy and then living up to them. First, because of symmetry, it seems reasonable that each of them will have the same deterministic strategy, i.e. a function F from all infinite sequences of bits to the set {0,1} where output is the guess about the majority of the sequences in infinity. Now for some desired properties of F:
   (a) F({a_n}) = c if {a_n} is the constant sequence a_n=c, for both c in {0,1} (reasonable)
   (b) If sequences a_n and b_n differ only in finitely many places, then F({a_n})=F({b_n}). This is reasonable as what happens up to a finite time shouldn’t matter, as it might differ from the behaviour at infinity.
   (c) If sequences a_n and b_n complement each other, i.e. a_n+b_n=1 for all n (or for all but finitely many n, by (b)), then F({a_n})+F({b_n})=1, that is, they also complement. This is not only reasonable but necessary: Suppose the first person got sequence a_n, and the second got b_n. Now it could still be possible for the sum of the sequences to be constantly 1 or 2, the third person will just get the appropriate constant function. Hence for at least two people to guess the correct sum in both cases, the person who got {a_n} must guess differently from the person who got {b_n}.
   (d) If a_n <= b_n for all n, then F({a_n}) 1/2 (else the total sum is > 1) and the other two guess correctly; if the sum is 2, then at most one can have F less than 1/2 (else the sum is less than 2), and again the other two guess correctly.

   It can be seen that the only cases where we do not clearly win is if the values of F are (1,1/2,1/2) or (0,1/2,1/2). As before, in such a case we must have the two people guess differently. Because there are three people, it can be seen that this is not doable by having different people react differently to the value 1/2, and so we must decide for each bit sequence with F = 1/2 whether to guess 0 or 1, in such a way that any two complementary sequences (or more accurately – complementary up to a sequence with F=0) are assigned different guesses.

   I had thought earlier that this could be done easily, but now I realize that it might not be so, and I’m not really sure if this can be finished with something simpler than the first proof. In any case it will most likely require AoC again, but of course, even the Hahn-Banach theorem requires some weaker form of the AoC to hold.

   Anyway, I really liked this riddle. Fun and rewarding. I’ll be glad to hear of any solutions simpler than ultrafilters or Hahn-Banach, as well as a finishing statement for the second proof, if there are any

5. Dan Says:
   June 28th, 2010 at 12:44 am

   Argh. Thought I got rid of all the less-thans, forgot to search up :\
   If the above was less than clear, that is of course due to it being cut off just after the start of line (d), and joined five paragraphs down… Here are the solutions again, with the first and last paragraphs repeated from the last post:

   First solution (warning: heavy set theory!):
   This is a rather axiomatic approach, based on making some reasonable assumptions about the strategy and then living up to them. First, because of symmetry, it seems reasonable that each of them will have the same deterministic strategy, i.e. a function F from all infinite sequences of bits to the set {0,1} where output is the guess about the majority of the sequences in infinity. Now for some desired properties of F:
   (a) F({a_n}) = c if {a_n} is the constant sequence a_n=c, for both c in {0,1} (reasonable)
   (b) If sequences a_n and b_n differ only in finitely many places, then F({a_n})=F({b_n}). This is reasonable as what happens up to a finite time shouldn’t matter, as it might differ from the behaviour at infinity.
   (c) If sequences a_n and b_n complement each other, i.e. a_n+b_n=1 for all n (or for all but finitely many n, by (b)), then F({a_n})+F({b_n})=1, that is, they also complement. This is not only reasonable but necessary: Suppose the first person got sequence a_n, and the second got b_n. Now it could still be possible for the sum of the sequences to be constantly 1 or 2, the third person will just get the appropriate constant function. Hence for at least two people to guess the correct sum in both cases, the person who got {a_n} must guess differently from the person who got {b_n}.
   (d) If b_n >= a_n for all n, then F({a_n}) >= F({b_n}). This is reasonable, as it does not make sense that seeing strictly more 1′s in {b_n} than in {a_n} will make us guess that the majority was 1 for {a_n}, but 0 for {b_n}.

   Now, note that any such function F:{0,1}^N → {0,1} could equivalently be considered as the indicator function of some subset (which by abusing notation we shall also call F) of the power set P(N), i.e. for any subset A of N, F(A)=1 if and only if A is in F. In this language the properties translate to:
   (a) N is in F, the empty set is not in F
   (b) If A and B differ by finitely many elements, then A is in F if and only if B is in F
   (c) A is in F if and only if its complement is not in F.
   (d) If A is a subset of B, and A is in F, then B is also in F.

   At this stage someone who is familiar with the concept might see that such a set F could be, for example, any free ultrafilter: A filter is a set F which satisfies (a),(d) and (e): If A,B are in F, then so is their intersection. Adding property (c) makes it an ultrafilter, and property (b) is then equivalent to the “free” property, which is that no singleton {x} is in F. Proving the existence of a free ultrafilter on N is non-trivial and requires the Axiom of Choice (or some weaker form of it). I recommend looking it up in Wikipedia. It might be simpler just to show that a set satisfying (a-d) exists, though.

   Now let us show that any set F satisfying (a-d) will yield a working strategy: To show that at least two people out of three guess correctly is equivalent to showing that out of each two, at least one will guess correctly. Suppose that at infinity, the sum was 1. Then at no time did both people get 1 simultaneously. Hence their sets, A and B, are disjoint, i.e. A is contained in the complement of B and vice versa. Thus is F(A)=1 then by (d) F(B^c)=1 and by (c) F(B)=0, and similarly if F(B)=1 then F(A)=0. Then at least one of them will guess ’0′, which is the correct response. If the sum at infinity was 2, then it can be similarly shown (using property (b) as well) that either F(A)=1 or F(B)=1, which again means at least one of the two guesses correctly.

   (And that’s all!)

   Second solution(?) (warning: heavy analysis!):
   It seems to me that many people, upon encountering this problem, try the following direction: “If each of the sequences has a density at infinity, then it is very simple: If it is less than half, I will guess 0, if it is more than half, I will guess 1″. A good idea, and true, although dependent on two big ifs: If there is a density (and in general of course there isn’t), and if it isn’t exactly 1/2 (where the above algorithm isn’t defined). The big problem here of course is the existence of the density. Fortunately there exists a common (yet sophisticated and advanced) tool that solves it: The Hahn-Banach theorem. Basically, it allows us to extend any bounded linear functional on a subspace of the vector space of bounded sequences into a bounded linear functional on the entire space. For example, if we use it to extend the limit functional defined on the space of convergent sequences, we will get a functional F on all bounded sequences, which is bounded by the supremum, extends the notion of density, and will attain only values in [0,1] the bit sequences.

   Now given the sequence of bits, we apply F on it, and if it less than 1/2 we guess 0, and if it is more than 1/2 we guess 1. As the sum a_n+b_n+c_n is constantly 1 or 2 at infinity, so is the sum F({a_n})+F({b_n})+F({c_n}) be 1 or 2, by the linearity of F and by the fact that it extends the limit functional. If the sum is 1 then at most one person can have F > 1/2 (else the total sum is > 1) and the other two guess correctly; if the sum is 2, then at most one can have F less than 1/2 (else the sum is less than 2), and again the other two guess correctly.

   It can be seen that the only cases where we do not clearly win is if the values of F are (1,1/2,1/2) or (0,1/2,1/2). As before, in such a case we must have the two people guess differently. Because there are three people, it can be seen that this is not doable by having different people react differently to the value 1/2, and so we must decide for each bit sequence with F = 1/2 whether to guess 0 or 1, in such a way that any two complementary sequences (or more accurately – complementary up to a sequence with F=0) are assigned different guesses.

   I had thought earlier that this could be done easily, but now I realize that it might not be so, and I’m not really sure if this can be finished with something simpler than the first proof. In any case it will most likely require AoC again, but of course, even the Hahn-Banach theorem requires some weaker form of the AoC to hold.

6. yaniv Says:
   June 29th, 2010 at 3:59 am

   Hi,

   Well, my solution is essentially the second one Dan describes (with the correct treatment for 1/2). Actually, the construction itself (modifying the proof of the Hahn-Banach theorem) is also very similar to the use of a filter.

   For simplicity, I will start from the beginning (Dan – I must say that I really like your filter solution, Oded Badt solved it like this as well).

   So, take the vector space of all bounded sequences (with the sup norm). Take the subspace of all converging sequences. On it, the limit linear functional is defined. Now, using Hahn-Banach we can indeed extend it to the entire space. The only problem is indeed with the value 1/2.

   The correction for the value 1/2 is actually really simple, we will build our extension such that all binary sequences will get whole number values (we can even enforce that any sequence that is composed of whole numbers receives whole values).
   How do we do it? Well, let’s recall how the Hahn-Banach proof works: we have the set of pairs Fi,Hi of functionals Fi and subspaces Hi. What happens if we consider only ones which satisfy our requirement? Well, everything still works! Every chain still has an upper bound and the maximal element is our entire space! (BTW – it is enough to define it on the subspace spanned by all the sequences composed of whole numbers, which I think is equal to that spanned by all binary sequences but STRICTLY smaller than the entire space – comments?).

   Anyway, the problem can also be solved by standard transfinite induction (i.e. our modified Hahn-Banach theorem can be proved with it). Which is kind of similar to the filter idea (without explicitly using it). I.e., take the next binary sequence not yet assigned, assign it 0, expand the functional, rinse and repeat.

7. yaniv Says:
   June 29th, 2010 at 4:06 am

   Oh, and regarding rouli’s comment, I forgot to say that I think that the riddle cannot be proved by looking at only finitely many bits (even if unbounded).
   Not sure how to prove that though.

   And finally, I thanked Haran for the riddle, but I should have also thanked Nadav for being a proxy
   So thanks Nadav! Cool riddle!

8. Arie Says:
   September 28th, 2010 at 9:19 pm

   I’m sorry to say I didn’t find the puzzle nearly as enjoyable as you have indicated, mainly because it became quite quickly clear what the necessary and sufficient conditions were, and then the first (and I’d say fairly obvious) tool that came to mind established the solution. I’m posting my solution here because it’s different (at least superficially) from the two that have already been suggested.

   Being a meagre computer scientist I don’t know much set theory, nor much analysis. Here’s my solution, based on a bit of propositional logic. (I won’t be surprised if there is an underlying connection to the other solutions. I’m not familiar enough with the concepts used in them, though, so I can’t tell.)

   First, a bit of an analysis of the problem a-la Dan.
   Let’s assume a solution exists. Let’s call the players p, q, r, and their strategies f_p, f_q, f_r, respectively. Also, let’s define that the answer is 1 in the case of all 1s and 2 in the other case. Denote by 0* the all-0s vector, and by 1* the all-1s vector.

   1. Suppose f_p(x)=1 for some input x given to p. Let y be the complement of x. Then if q gets y and r gets 1*, then the correct answer is 2. Thus f_q(y)=2.
   2. Suppose f_p(x)=2 for some x given to p. Again, let y be the complement of x. Then if q gets y and r gets 0*, then the correct answer is 1. Thus f_q(y)=1.

   So we can conclude that f_q(\bar{x}) = \bar{f_p(x)} for all x, where \bar{“something”} is the opposite of “something”. (In the case of a bit vector it is the complement; in the case of an answer it is 3 minus that answer.) Thus once f_p is determined, so is f_q.

   Now, q is just a name of one of the non-p participants. So by symmetry, f_q=f_r. Similarly, p is just a name, so we conclude that f_p=f_q=f_r.
   Thus:
   (A) All three participants must use the same strategy. Let’s call it f.
   (B) f(\bar{x}) = \bar{f(x)} for all x.

   Let us now introduce some more notation. Denote by z_i the ith bit of vector z. For two bit vectors x, y we denote by x \leq’ y (x<'y) the statement:
   There exists n such that x_i \leq y_i for all i \geq n (and there exists at least one j \geq n such that x_i < y_i).

   Let y be such that f(y)=1 and let x be such that x <' y. Then f(\bar{y})=2. Now, if p gets \bar{y} and q gets x, r can get a vector such that the sum of all three is 1*. In this case p answers 2, so the two others must answer 1. It follows that f(x)=1.
   Thus:
   (C) x \leq' y implies f(x) \leq f(y) for all x and y.

   All we've done so far is develop some necessary conditions. (Of course, they are not needed in order to solve the puzzle, but it's a fun analysis.) To solve the puzzle we need sufficient conditions. We claim that (A)-(C) are just such conditions.

   To prove this, suppose the three participants use a strategy f satisfying (B) and (C). Consider an instance of the puzzle.
   Case 1: the correct answer is 1. Suppose one of the participants gets x such that f(x)=2. Because the correct answer is 1, it must be the case that the other two participants have vectors y and z that sum to \bar{x}. It follows that y \leq' \bar{x} and z \leq' \bar{x}. Since f(\bar{x})=1 by virtue of (B), we have f(y)=f(z)=1, by (C).
   Case 2: the correct answer is 2. Suppose one of the participants gets x such that f(x)=1. Because the correct answer is 2, it must be the case that the other two participants have vectors y and z such that for some n, x_i=0 implies y_i=z_i=1 for all i \geq n. Thus \bar{x} \leq' y and \bar{x} \leq' z. Since f(\bar{x})=2 by virtue of (B), we have f(y)=f(z)=2, by (C).

   Does there exist such an f? Clearly, if the adversary can only choose from some finite collection of 1-2 vectors then there is a maximum point k at which the transition from 1 to 2 may occur. The simple strategy f(x)=1 iff x_k=0 is easily seen to work. Also, conditions (B)-(C) are satisfied by this strategy if we replace \leq' in condition (C) with a bounded version \leq'k defined by: "There exists n \leq k such that …"

   Of course the problem is that the adversary is not limited to a finite collection of instances. We need to somehow go from all finite subcases to the infinite general case. The first thing that comes to mind (well, at least to my mind) is the notion of compactness. Indeed, in this case we can employ the compactness theorem of propositional logic to get the desired result.

   Define propositional variables {V_x | x is an infinite bit vector}. The intended semantics is: V_x=false means f(x)=1, and V_x=true means f(x)=2.

   Now encode (B) and (C) by the following sets of formulae.
   B: For all vectors x
   V_{\bar{x}} \rightleftarrow \not V_x.
   C: For all vectors x and y such that x \leq' y
   \not V_x \vee V_y

   Clearly there is a bijective correspondence between satisfying assignments and strategies satisfying (B)-(C). By the argumentation above every finite subset of formulae is satisfiable. Thus by the compactness theorem the entire set of formulae is satisfiable.

   Remark: Of course the set of variables is uncountable so we need Zorn's lemma (i.e., AC) to support the compactness theorem.

   Rant: Why is everybody so obsessed with the axiom of choice? Yes, it's formal statement seems significantly more complicated than the ZF axioms (even if informally—"can form a set by choosing one element from each set"—it's just as basic as the other axioms, at least to my mind). I can see that its independence of ZF is interesting within set theory, but for general math, what's the big deal? Why do we always need to point out that we are using it? Unlike, say, non-euclidean geometry, there is no great deal of interesting math to be gained by rejecting it (at least to my knowledge; someone please correct me if I'm wrong), and there is a much to gain. So if you're doing foundations-of-mathematics, by all means go ahead and point out the reliance on AC (or lack thereof), but otherwise why not just give it a rest. Oh, and as long as I'm on the topic of geometry, when was the last time anyone saw a proof requiring the Postulate of Parallels bothering to point that out?

   Finally, to answer rouli's suggestion, suppose each participant can only examine a finite number of bits. Consider an instance of the problem where the correct answer is 1. Let k be the maximum index of a bit observed by any participant. If we change the inputs to the participants such that they remain the same up to bit k, and thereafter are all-1s, all-1s and all-0s, the correct answer changes to 2, but the participants will clearly not change their guesses.

9. Arie Says:
   October 3rd, 2010 at 3:29 pm

   I thought about it some more and realized the solution can be based directly on Zorn’s lemma, without appealing to the compactness theorem. I think it would be interesting to contemplate whether there is a solution relying (reasonably straightforwardly) directly on the axiom of choice.

   Define: A set X of bit vectors is \emph{consistent} if:
   1. 0* \in X; and
   2. x \in X implies y \in X for all y \leq’ x; and
   3. x \in X implies \bar{x} \not \in X.

   Define a poset: the elements are all consistent sets of vectors; the partial order is the set containment relation.

   It is easy to see that, for every chain, the union of elements in the chain is a consistent set of vectors and is therefore an upper bound.

   Thus by Zorn’s lemma there is a maximal element T.

   For every bit vector x, either T contains a vector z=\bar{y} for some y \leq’ x, in which case \bar{x} \in T (because \bar{x} \leq’ z), or else T \cup { y | y \leq’ x } is consistent, in which case x \in T (by T’s maximality). Also, it is not possible that both x and \bar{x} are in T (by consistency). In other words, for each x, exactly one of x and \bar{x} is in T.

   The strategy f(x)=1 iff x \in T therefore satisfies (B)-(C).

10. Dan Says:
    October 9th, 2010 at 12:19 am

    Hi Arie,

    Your formulation of the solution with the compactness theorem is nice! I will say that it is different, although of course all of these solutions are very intrinsically linked. There is a nice connection between ultrafilters and the compactness theorem: ultrafilters – and specifically ultraproducts, which rely on them – offer what is probably the most elegant proof for the compactness theorem (Although this bears absolutely no relation to your proof, where you use the compactness to prove the existence of the ultrafilter-like set). For more on this, see the Wikipedia articles “Ultraproducts” and “Compactness theorem”.

    About your rant, there are some nice results to be gained by rejecting AC: wouldn’t you like to have all sets of real numbers measurable, instead of having monsters that can be compressed to any size (and thus with measure at most zero), yet that can cover the real numbers with only countably many copies (thus not of measure zero – thus not measurable)? But indeed there are less such results than there are to be gained by accepting AC. The problem with those is that many of them are unintuitive, maybe even “too strong”, and of course not one of them can be constructive – good examples (in my opinion) are the Well Ordering Principle and the Hahn-Banach theorem. This is of course very much unlike the results of (and reasons for) accepting or rejecting the parallel postulate (at least to modern minds familiar with spherical and hyperbolic geometry). Furthermore, there are many cases where the necessity of the axiom of choice is surprising (as might be argued for this riddle, for example), and it is noteworthy to point out when you are using a powerful and non-trivial tool, especially for something superficially simple.

    Finally, and somewhat off topic, does your browser parse the TeX in your above posts as images, or does it leave all the slashes in? I, for one, am not fluent in TeX, and it’s not much fun to read text filled with \leq and \bar. So if your browser displays it nicely, I’d be happy to hear how (I tried googling for appropriate firefox extensions, unsuccessfully)

11. Arie Says:
    October 18th, 2010 at 5:33 pm

    Dan,

    I’m still unconvinced on the issue of AC. The fact that something superficially (or not superficially) simple needs AC is just a reflection of the fact that AC itself is nearly as simple as you can get (“I can form a set by picking one element from each set in my collection” – isn’t it obvious that I should always be able to do that?). If you get perplexing and counter-intuitive results from AC, then that’s just beautiful mathematics, not a reason to reject it. Fundamentally, it’s obviously true. To illustrate what I mean, consider again the postulate of parallels. Nobody pondering ordinary 2d (or 3D) geometry would ever consider POP to be false (which is why mathematicians had tried to prove it for millenia – I don’t think anyone ever tried to disprove it). Can you imagine someone saying “well, I can prove this or that relation between the faces of those two buildings right there, but only if there exist parallel straight lines?” Only when you decide that “point” and “straight line” can meaning something other than everyday points and straights lines (or indeed, that they need not correspond to anything at all in the real world) do you find that rejecting the POP can be useful. Similarly, as long as we think of a “set” as a collection of things, each of which may either “belong” or not to any given set, I would say that AC is certainly something you’d expect to hold. If somebody comes up with a different interpretation of “set” and “belongs” then I’d expect rejection of AC to be worthwhile, but only in that context. I still think people are overly obsessed with pointing out where AC is being used.

    Regarding Tex (or, if you will, LaTex), alas, I know of no plugin or such that displays it. The only reason I used it is that I know of no other way to reasonably express mathematics in ASCII text. (In fact I was using some sort of pidgin LaTex, not strictly correct syntactically.) I’m guessing it could be done in html, but I barely now html. Sorry about that.

    Finally, two remark on my second solution (the using Zorn’s lemma directly).
    1. Condition 1 in the definition of consistent is of course superfluous. Not only is it subsumed by condition 2 (when considering nonempty sets), it is also not used anywhere in the sequel.
    2. I forgot to point out that the poset is not empty. It contains as a member the set of all bit vectors with a finite number of 1s.

12. yaniv Says:
    October 19th, 2010 at 2:26 am

    Hi Arie,

    Interesting comments.
    You can find my response (which admittedly, I wrote before your comment ) in the post on the axiom of choice: http://yaniv.leviathanonline.com/blog/math/set-it-straight/

Leave a Reply

Name (required)

Mail (will not be published) (required)

Website

Notify me of followup comments via e-mail