CMU has long hosted an ensemble of thoroughly geeky malcontents who pass themselves off as a club called the KGB, whom my sister had fallen in among. Now, the KGB had a custom of every semester holding evening revels centering around an autochthonous amusement called ‘Capture the Flag with Stuff’ (CTFWS).
CTFWS would thrill the heart of any true geek as it appeals to their passion of taking a conventional recreation and rendering it more complex and absurd. In CTFWS, approximately 200 people divide themselves into the two teams of Red and Yellow. Each team is assigned one half of a truly enormous building on the CMU campus; the building is so large that by administrative fiat it is listed as the two buildings of Wean Hall and Doherty Hall, and a player could long range among its 10 floors and football fields of length without ever seeing another player.
The object if the game is simple: per the name of the game, whichever team first steals the 5 or so flags belonging to the other team, wins. The flags, however, will have been cunningly strewn all across the building, and guards set. These guards will likely be armed, which leads to the second half of the name—‘with Stuff’. The guards could well be inhuman: the teams are issued several glyphs (posters) which are held to have magic powers on that team’s territory. One poster, for example, is ‘disgusting’: should it be placed on a door, an opponent will be utterly repelled by it and unable to proceed through. This poster is frequently used to secure the multiple doors of a lobby. Another poster is the alarm bell—when an opponent comes into eyeshot, a voluble alarm will sound and alert the defenders. (As posters lack any vocal cords or speakers, it is understood that the opposing players will do yeoman’s service in this stead.) A final poster simply paralyzes for a minute any enemies who see it.
If the guards are indeed human, then they will likely be armed with any of a variety of wands (foam sticks). A red wand may be discharged at an opponent—in his own territory, and the result is that they are automatically captured and must go to the POW camp. (Fortunately, their immurement need not be permanent as the rules provide for a prison break every quarter of an hour.) However, it may only be employed once and then must be discarded. The blue wand functions similarly, but is less desirable as it merely paralyzes for a time, and in the bustle of events the victim may well escape before being officially tagged and captured. The green wand is of particular note as its sole ability is to neutralize the effects of the belt items.
The belt items are unique artifacts that one cinches around one’s waist and invokes. They are very powerful and useful items. One belt is like an ambulatory version of the poster which stuns all enemies in sight; another belt waives the restriction that a player may capture only one enemy, and allows 4 captives. A common tactic is for multiple players to link arms with the wearer (the effect is contagious), and set off into enemy territory. Once there, the bearer and confreres begin skipping along and singing loudly ‘Yankee Doodle Dandy’. So long as they skip and sing, the group is immune to all tagging, grenades, belt items, and attacks in general. Such a cohort will, skipping, systematically scour a story for signs of the flags. Eventually they will encounter a defender wielding a green wand. Presently a shout goes up, they leave off singing and skipping, and all flee pell-mell for safety with their precious intelligence.
Already I have alluded to the remaining items: the three kinds of grenades. These are the most plentiful items and argal, most apt to be employed. The blue grenade is a stun grenade. It paralyzes for 15 seconds but it is only effective if the enemy willingly grasps it. This renders it rather ineffective. The red grenade is the ‘Ninja Potion’ grenade. It is employed on enemy grounds, where one hurls it to the ground (discarding it), shouts “Poof! I’m a ninja!” whereupon all enemies in sight are briefly paralyzed and one presumably effects one’s escape. The green grenade is used either when a captive or a prisoner, and it removes both conditions.
Not infrequently it happens that one is tagged/captured while still in possession of items. If the captor sees them, then he may demand that they be rendered up. But suppose a grenade is concealed? (They are the size of a foosball.) Then if the captor knows for sure the item is concealed, he may demand it regardless. But suppose the captor suspects that the captive is concealing an item, but does not know it for sure? He cannot demand it.
At some point the two players will pass into the depths of his home territory, and arrive at the POW camp. At the beginning of the game, one player was appointed Warden and given the power of ‘truth serum’: once a prison-break cycle, he may select a prisoner and ask the prisoner 6 yes-no questions. The prisoner may lie once, but all other responses are constrained to truth.
Now, the problem arises like this. That evening the KGB had obtained the building for the entire night. 3 games were played. As each game lasts somewhere around 2hours, and involve a great deal of running and shouting up stairs and down halls, the players are uniformly fagged by the conclusion of game 3. Assembling in the auditorium where we had early been instructed at great length on CTFWS, all and sundry began swapping tales of narrow escapes, great victories, dire setbacks, and peculiar encounters, or decisions of the peripatetic judges.
I happened to overhear one such conversation. The player recounted to his friend about his role in the rout of a minor incursion on the 7th floor. He escorted his prisoner back to the POW camp and there had the Warden interrogate him, as it was felt he had concealed a grenade. The Warden, the player said, had asked but 4 questions:
Was the grenade he had red?
No.
Was the grenade green, then?
No.
Then surely the grenade was blue?
No.
The Warden repeated the last question, and this time the prisoner answered Yes. The Warden deduced that the contradiction proved that either question 3 or 4 was the lie. If #4, then the prisoner had no grenade. But if the lie was #3, then the true answer was #4: the prisoner’s grenade was blue. The Warden proceeded to demand that the prisoner render up the blue grenade. The disgruntled prisoner did so, and the player ended his anecdote one grenade richer.
I couldn’t help but feel that the Warden’s questions were artless and inelegant. My reading of William Poundstone and Raymond Smullyan’s books has inculcated in me an appreciation of logic puzzles and I decided to treat this as one:
“Your interlocutor has a ball which is one of 3 colors. What is the least number of yes-no questions you need to ask, and what are they, to ascertain the color of the ball? Remember that he may lie once.”
My first step was to consider the question from a programmer’s view, considering this from an information theoretic view. If we can prove how many questions we need at most, then it will be that much easier to formulate the (possibly tricky) questions.
Now, each question is Yes or No. That is, they are binary. Each question can yield at most 1 bit of information: a bit of information is, pace Shannon, a unit of reduced uncertainty, of certainty. Intuitively, you can think of it as letting you choose between possibilities, to uniquely specify one item out of a bunch. Suppose we are ignorant of which of 2 states to choose. Then we need 1 bit. Suppose it’s 4 states; we divide it into 2 groups of 2, and we need 1 bit to choose between the first and second group, and then we need another bit to choose within the group. So 2 bits can choose between 4 items. 8 items become divisible into 2 groups (of groups of 2)—the first bit chooses between groups-of-groups, the second between groups, and the third bit between 2 choices. So 3 bits can choose between 8 items. The pattern is obvious by this point: if you have n bits, they can uniquely identify one item out of 2n.
Let’s tackle a simplified form of the problem, a version without any lying. Suppose the ball in this case is either red, or it doesn’t exist at all. You are informed he has a ball. How many questions do you need to ask? Obviously there’s exactly one possibility; it’s a logical certainty that the ball is red. It takes 0 bits to specify 1 item out of a group with only 1 item. You already know what the answer is, so therefore you need 0 questions.
Suppose now that the ball is either red or blue. Now there’s two possibilities, but still only 1 can be true. We said earlier that 1 bit specifies out of 2 possibilities, so by that reasoning you need ask only 1 question. Let’s convince ourselves that this is true. We can’t get away with asking 0 questions—it could be either. We could guess and perhaps be right, but no matter how often our interlocutor chooses red, we could never be absolutely sure. So 0 questions is right out. We could try asking 2 questions, such as ‘Is it red?’ ‘Is it blue?’. This would work, surely. But one can’t help but notice that every Yes will be followed by a No, and vice versa; indeed, this follows from the law of the excluded middle—the ball can’t be both red and blue, nor neither red or blue. So one of the questions is redundant. Which leaves us asking exactly one question: ‘Is it red?’ If Yes, then that’s the answer; if No, then it must be blue. One question suffices, just like expected.
Let’s go up a power. 2 bits specify 4 possibilities (22 = 4). So if the ball was of 4 colors, we could ask ‘Is it red or blue?’ A Yes answer reduces it to the previous 2-color problem, and we know only 1 question is needed to solve the 2-color problem, so 4 colors requires just 2 questions/bits. Our actual problem is 3 colors, not 4. Yet we can solve it just like 4; a fortiori, 2 questions will work. Certainly, we can use the ‘excess’ to reduce the amount of thinking we need to do—for example, if we have only 3 colors, we can elegantly ask ‘Is it red or blue? Blue or green?’ Then YY = blue, YN = red, and NY = green. Note that NN is missing; it does not correspond to any color (that’s the wastage).
My response to the two players followed this approach. Assume the prisoner lies. That means one of the questions, one bit, must be discarded. Then we need to cover 3 possibilities with n+1 bits; 2 bits cover 4 possibilities, so 2 bits cover 3 possibilities as well, and 2+1 = 3. So 3 questions suffice.
What are the 3 questions? well, let’s follow our model. The key is overlapping disjunctions which sum to Truth. The simplified 3-color problem had 2 questions of (r or b), (b or g). The liar version must scrap a question. So our 3 questions look like: (r or b), (b or g), (g or r).
Let’s give that a try. The prisoner has a red grenade and doesn’t lie: YNY. ‘r’ is the common factor, and so the grenade must be red. Suppose he lies on the first question: you discard to get NY, then it is neither b or g, but g or r. Again, ‘r’ falls out as the only consistent answer. And this reasoning is symmetrical, so it doesn’t matter which question he lies on: either way, we can figure out the answer in 3 questions, exactly as our informal information-theoretical argument says.
I suggested this to the two players and after some thought, they assented: those three questions did the trick. I thought it was an interesting problem, and continued until I’d convinced myself by the foregoing chain of reasoning that 3 was the minimum, that there was just not enough information in even the most contrived set of 2 questions.
After that incident at CMU, I occasionally brought this problem up in conversation as a nice logic puzzle found in the real world. But one day discussing my solution with a Haskell programmer, he kindly informed that my solution was incomplete. As proof, he asked me to deduce the color if the response was YYY. I froze. Any of the replies could be the lie. The true answer was indeterminate; all one could deduce was that there was a lie in there. I was thunderstruck, and my attempts to salvage my 3 questions in some manner all foundered.
After further discussion, I realized that my previous proofs had been naive and their lack of rigor directly led to my fatal mistake: in my arguments, I had smuggled in illicit information; specifically, I had assumed one just somehow knew which reply was the lie (if any) and that one could then discard it, and solve the no-lying problem. Of course, one doesn’t know which reply is the lie! That’s further information one needs to obtain!
Information theory had served me well, and had done as I had asked—but I hadn’t realized that my proof didn’t apply. A better analogy was needed. I found the analogy in another area of computer science: in coding theory. In this case, I mean by coding theory the study of how to detect and correct mistakes in a stream of bits, what ‘error correction codes’ are, and how they can be devised. With coding theory, we are conceptually sent a stream of bits and nothing else. Sometimes one of the bits will be corrupted (flipped). We know we can add further bits to detect errors: for example, suppose we know a stream will have at most 1 corrupted bit. Then we can tack on a number which says ‘the previous stream had 10 zeros in it’; then if a 1 is flipped to 0, or a 0 to 1, we can add up the zeros and see that they don’t match (if the added checksum is corrupted, then the correct stream won’t it either, and we’ll still know something went wrong).
Sometimes we don’t need an explicit checksum or ECC bits, since a bit-stream might have constraints or a known structure. (For example, one knows an ASCII file is supposed to have a newline terminator, and that bytes generally don’t have the high-bit set.) Similarly, our 3 questions only have 3 valid streams: YYN, YNY, and NYY. (Each color is present in 2 questions, and absent from one question.) The 3 valid streams have an important property: if we get them, then we know that the entire sequence is truthful. Were one not truthful, then either a true N would be turned into a Y (in which case our answer must be the degenerate YYY) or a Y would be N (in which case the obviously lying NNY, or a permutation); either leads to contradictions. So if we’re given a valid stream, we can reason that there is no lie and then we can deduce the color of the ball. Even more important is the consequence: in the case of a NNY, or a YYY, we now know that the lie has been used up. The prisoner only gets one lie and that’s it. The next answers must be truthful.
Let’s consider NNY. We know the Y must be true, since the prisoner only has one lie: he could not flip a Y to N and also a N to Y. If we assume the Y is a lie, then we get the impossible result that NNN is completely true1. So there are only two possibilities as to the lying reply: N and N. Fortunately, one question suffices to distinguish. ‘Is the first N a lie?’ ‘Yes’. So (r or b) is True, (b or g) is False, and (g or r) is True. The common factor between 1 and 3 is ‘r’—the ball is red. Be the answer ‘No’. then the second N was the lie, and so it is (b or g) and (g or r); the ball is green.
Thus 4 questions suffice for all possibilities other than YYY. Can we solve that too? We know that one answer is a lie. But we cannot use the same strategy as before! Suppose we asked if 1 is the lie, and we are told ‘No’. This ‘No’ is true, as we already know. So was it 2 or 3 that was the lie? Either is possible, either is consistent. One question can’t distinguish between 3 possibilities. ‘Was 1 or 2 the lie’? ‘Yes’. Then we still have to choose between 1 and 2. We can clearly patch things up with a fifth and final question about the last two possibilities, but what a defeat this feels like! To go from just 3 questions to 5!
Can we be more clever than 5 questions? It takes 2 questions, we know, to decide the color. That is because there are 3 colors. But the lie bollixes things. Perhaps we can handle the lie in 2 questions as well. Does this work from an information-theoretical view? Well, aren’t there 4 possibilities here as well? Either the prisoner doesn’t lie at all, he lies on the 1st question, the 2nd, or the 3rd. This is an exhaustive listing. We need to pick out the correct item. So we need a total of 4 bits to solve this question. But this assumes that there’s no inefficiency, that we are wringing a full bit out of each question. Previously I mentioned that the triply-entangled questions were inefficient, in a sense. So we need a new set of questions.
Our intuition here about ‘sequences that cannot be transformed into each other’ can be formalized a bit more. (I am indebted to this general approach to the lovely book Flatterland.)
Imagine one of those tinker-toy sets, or one of those chemistry models with the balls and sticks. A stick and a ball can represent a bit. If we stick a ball on the left, then it is a 1; if we stick it on the right, a 0. We slide the ball down the left—now the 0 has been flipped to a 1. This is simple enough; no bits correspond to a lonely ball with no stick to slide on; one bit is a rod with 2 endpoints for the ball to be at. (This should start sounding familiar.) What then is 2 bits? Why, a square of course! If a line has 2 endpoints, then the next step is a square with 4 corners. Let’s label them: the one closest to us is 00, the one to our left is 10, the one to our right is 01, and the furthest one is 11. Now here’s the interesting bit: our bit stream of 2 bits, in its entirety, is just the ball we push from corner to corner. We didn’t notice this identity in the case of the line and bit—we could think that it was just a coincidence. But what’s a lie, or error, in this model then? A lie is our opponent being able to push the ball one position (without us seeing). So suppose the ball is sitting at 00; with one push, our opponent could push it left to 10, or right to 01. But he couldn’t push it to 11, since he’d have to push it to 10 or 01, and then push it round the corner a second time. So 11 is right out. The next step up is 3 bits, with 8 corners; this is a 3D cube, which is much the same—one push of the ball can’t move it all the way to another corner, etc. With 4 bits, we reach 16 but that means a hypercube and those are a little hard to visualize, so let’s stop there.
Let’s go back to the original problem. How does this way of thinking help us? Well, our three questions were erroneous. Why? Because in our hypercube, our valid answers were all positioned just one point separating them from each other. So a lie could move the ball 1 up and then we couldn’t figure out which way the ball came from. What we need is to put 2 points between each of our valid points. This reasoning tells us we do need a fourth question: we can’t arrange 8 points such that there are 2 points in between each valid point. (Think of it as a circle: 2 points, point, 2 points, point, 2 points, point—all adds up to 9 points total, which is more than we get.) So we have more requirements: we must use up 4 questions, and each valid sequence has to be corruptible by 2 lies (but not 1). The latter implies we ask about 2 of the colors twice and let the third take care of itself. This approach will lead us to the answer.
Again, our problem stems from the fact that each valid answer can be turned into the lying YYY sequence by a single lie. Just given YYY, we don’t know which ‘true’ sequence the prisoner started from. If we could somehow make each valid sequence be convertible into a different lying sequence then the other 2, then we could reason backwards from the lying sequence to the valid sequence, and from thence solve the problem. With 4 questions and 4 replies how do we do that?
One’s first impulse is probably to try to simplify things again. With 4 questions, can’t we ask “Is it red? Is it red? Is it blue? Is it blue?” Obviously with all truthful answers, we can know what color it is; better, we know that there were no lies here, since it’s all consistent. And it even seems to work if the grenade is red or blue. But unfortunately, these 4 questions can be defeated: suppose the answers are NNNY. Clearly one of the two last questions is a lie. But which one? It could be #3, in which case the grenade is blue. But it could just as well be #4, which makes the grenade green. We don’t know which. So this sequence fails. But it does seem to be on the right track—it almost works. And our spidey-senses should be tingling: there feels like there’s something wasteful about these 4 questions. Our last 2 questions are doing yeoman’s service in exposing the vicious contemptible lie of the prisoner, but the first 2 are not really doing anything useful. How can we make them do more work?
We can do that by making the questions even further entangled. Consider the 4 questions: ‘Is it blue or red?’ ‘Is it blue or red?’ ‘Is it blue or green?’ ‘Is it blue or green?’ Note how blue now appears in every question, where previously each color only appeared twice. This sequence has the property we seek. There are 3 valid sequences of replies: YYNN, NNYY, and YYYY. No matter which reply is a lie, it doesn’t get turned into a lying sequence which is reachable from one of the others. The possible lying sequences are YYYN, YNNN, YNYY and so on. We can satisfy ourselves of this by exhaustively listing out the 15 possible responses (4 bits have 16 possible values, but a NNNN is the sole impossible sequence, so there’s just 15 possible sequences).
And that’s that. we have learned that while the Warden was correct in using 4 questions, his particular set of 4 only worked because the prisoner chose the suboptimal strategy of denying everything. After several false detours, much interesting thinking, and a perhaps surprising amount of computer science, we have found the answer to this deceptively simple problem. The problem can be solved by just 4 questions, that lead to 4 truths.
“And thus do we of wisdom and of reach,
With windlasses and with assays of bias,
By indirections find directions out.”
Haskeller Boxo (he of the decision theory monad) offers the following twisty examination of a very similar problem to the preceding where one can learn the truth in just 2 questions:
Suppose you want to know whether p and there is a person that knows whether p, but they may lie depending on arbitrary circumstances, including what question they’re asked.
Ask them this:
“If I asked you whether p and your choice of lying or truth-telling was the same as in the case of this question would you answer yes?”
p and askee truth-tells:
p and askee’s choice is truth-telling, so they would answer “yes”, and since they’re truth-telling, they answer “yes”
not p and askee truth-tells: “no”
not p and askee’s choice is truth-telling, so they would answer “no”, and since they’re truth-telling, they answer “no”
p and askee lies: “yes”
p and askee’s choice is lying, so they would answer “no”, but since their choice is lying they answer “yes”
not p and askee lies: “no”
not p and askee’s choice is lying, so they would answer “yes”, but since their choice is lying they answer “no”
Here I’ll explain my technique in coming up with the answer.
In my model, a person chooses whether to lie or tell the truth, not whether to say “yes” or “no”. More precisely—an answerer has access to a function evaluate of type (Proposition -> Bool) such that (evaluate p) = True iff p, and for every pair of answerer and circumstances there is a function f of type (Bool -> Bool) such that when you ask of them “p?”, they answer with (f (evaluate p)). In the case of an answerer who has decided to lie, f=not. In the case of a truth-telling, f = id.2
Now, you just ask “given that in the current circumstances your function is f, is it the case that (f (evaluate p)) = True?”. As an answer, you’ll get (f (evaluate [(f (evaluate p)) = True])), which is equivalent to (f (f (evaluate p))) since—ie. for liars and truth-tellers, (not (not (evaluate p))) and (id (id (evaluate p))) respectively, which both reduce to (evaluate p).
But consider answerers who have decided to either answering “yes” or answering “no” to your question.
In this case, f = (const True) or f = (const False) respectively. You may see the problem: no clever question will help you if in the end a constant function is applied to the answer. The solution presented above fails in the presence of “constant answerers”.
Here’s a way to arguably get the answer with just one question in the absence of constant answerers & allowing non-answering3. Consider this proposition:
“The ball is green or it is the case that the ball is blue and this proposition is false.”
It’s true if the ball is green, false if the ball is red, and undefined if the ball is blue.
Now just plug this proposition into our liar-rectifying question like so:
“If I asked you whether the ball is green or it is the case that the ball is blue and this proposition is false; and your choice of lying or truth-telling was the same as in the case of this question, would you answer yes?”
Now ask the above question. If they answer “yes”, the ball is green. If they answer “no”, the ball is red. If they answer nothing, or if they answer “mu”, or if their head explodes, the ball is blue.
Mestroyer offers this graphical take on the problem:
Your essay “The 3 Grenades” is wrong (as a few commenters have pointed out). Precluding self-referential questions like Boxo comes up with, 4 questions are not enough when the person doesn’t have to lie. However, if out of 4 questions, they are forced to lie exactly once, it can be done in 4 questions. If they have to lie exactly once, you can actually pick from among 4 colors in 4 questions.
(There’s another assumption I didn’t realize I was making: you don’t change future questions based on what answers you get.) But here goes: If every question is dependent only on the colors of the grenades, and you have 4 questions, then if you draw out a grid like this:
Initial empty grid
Then each square represents a set of four answers, one for each of questions Q1, Q2, Q3, and Q4. The column decides the answers to Q1 and Q2. The row decides the answers to Q3 and Q4. I’m using “1” for “yes” and “0” for “no.” The columns and rows are numbered in grey code, which means that moving one square in any direction is equivalent to flipping one Y/N answer. Because there are 4 answers to flip, and 4 directions to move in (you can move left on the leftmost square to end up on the rightmost, same with top and bottom. Like the Asteroids video game), every answer-flip is represented by a move of one square in a particular direction.
So for each possible grenade color, answering the questions truthfully would specify a square in the grid. Answering one incorrectly will move the set of answers one square in one direction. So if when the grenade is really red, the true answers are 0101 (No to Q1, yes to Q2, no to Q3, yes to Q4), the sets of answers the person can give are the ones filled in below:
Grid updated with red
The light red one is if they don’t lie, and the dark red ones are if they lie once. To make it so we can always determine the ball color, we have to arrange 3 of these shapes on the grid so that they don’t overlap. If they do overlap, then they could have answered that way if the ball was one of two or more different colors.
Because this grid wraps like the asteroids game, it doesn’t matter where you put the first “+”. Mentally placing a second plus makes it obvious that there is nowhere to put the last , no matter where you put it.
But, if they have to lie, then the answers they can give look like this:
Grid if lying
And you can fit 4 of this shape on the grid:
Filled in grid
So to determine the grenade color if 4 colors are possible in 4 questions, if in 4 questions they must lie, just pick the questions so that if the grenade is red, the correct answers are 0101, if blue, 1101, if green, 1010, if pink, 0010. This means Q1 should be “Is the ball blue or green,” Q2 should be “Is it red or blue,” Q3: “Is it green or pink”, Q4: “is it red or blue” (Yes, the last three are basically the same.)
When you get your answers, look up a square in the grid, and whatever color it is, is the color of the ball.
Remember, we’re assuming that he does have a ball and the problem is figuring out its color.↩︎
id is the identity function, defined as f x = x.↩︎
In some respects, this is smuggling in additional information; there are connections to denotative semantics in computer science and the bottom type.↩︎
