The Three Grenades and the Four Noble Truths

CMU game connected to error coding theory
computer-science, personal
2008-11-242017-02-08 finished certainty: unlikely importance: 7


Some years ago my fam­ily was in Pitts­burgh, where we were vis­it­ing my sis­ter for East­er. At the time she was a stu­dent at Carnegie Mel­lon Uni­ver­si­ty.

Sinister rites

CMU has long hosted an ensem­ble of thor­oughly geeky mal­con­tents who pass them­selves off as a club called the KGB, whom my sis­ter had fallen in among. Now, the KGB had a cus­tom of every semes­ter hold­ing evening rev­els cen­ter­ing around an autochtho­nous amuse­ment called ‘Cap­ture the Flag with Stuff’ (CTFWS).

CTFWS would thrill the heart of any true geek as it appeals to their pas­sion of tak­ing a con­ven­tional recre­ation and ren­der­ing it more com­plex and absurd. In CTFWS, approx­i­mately 200 peo­ple divide them­selves into the two teams of Red and Yel­low. Each team is assigned one half of a truly enor­mous build­ing on the CMU cam­pus; the build­ing is so large that by admin­is­tra­tive fiat it is listed as the two build­ings of Wean Hall and Doherty Hall, and a player could long range among its 10 floors and foot­ball fields of length with­out ever see­ing another play­er.

The object if the game is sim­ple: per the name of the game, whichever team first steals the 5 or so flags belong­ing to the other team, wins. The flags, how­ev­er, will have been cun­ningly strewn all across the build­ing, and guards set. These guards will likely be armed, which leads to the sec­ond half of the name—‘with Stuff’. The guards could well be inhu­man: the teams are issued sev­eral glyphs (posters) which are held to have magic pow­ers on that team’s ter­ri­to­ry. One poster, for exam­ple, is ‘dis­gust­ing’: should it be placed on a door, an oppo­nent will be utterly repelled by it and unable to pro­ceed through. This poster is fre­quently used to secure the mul­ti­ple doors of a lob­by. Another poster is the alarm bel­l—when an oppo­nent comes into eye­shot, a vol­u­ble alarm will sound and alert the defend­ers. (As posters lack any vocal cords or speak­ers, it is under­stood that the oppos­ing play­ers will do yeo­man’s ser­vice in this stead.) A final poster sim­ply par­a­lyzes for a minute any ene­mies who see it.

If the guards are indeed human, then they will likely be armed with any of a vari­ety of wands (foam stick­s). A red wand may be dis­charged at an oppo­nen­t—in his own ter­ri­to­ry, and the result is that they are auto­mat­i­cally cap­tured and must go to the POW camp. (For­tu­nate­ly, their immure­ment need not be per­ma­nent as the rules pro­vide for a prison break every quar­ter of an hour.) How­ev­er, it may only be employed once and then must be dis­card­ed. The blue wand func­tions sim­i­lar­ly, but is less desir­able as it merely par­a­lyzes for a time, and in the bus­tle of events the vic­tim may well escape before being offi­cially tagged and cap­tured. The green wand is of par­tic­u­lar note as its sole abil­ity is to neu­tral­ize the effects of the belt items.

The belt items are unique arti­facts that one cinches around one’s waist and invokes. They are very pow­er­ful and use­ful items. One belt is like an ambu­la­tory ver­sion of the poster which stuns all ene­mies in sight; another belt waives the restric­tion that a player may cap­ture only one ene­my, and allows 4 cap­tives. A com­mon tac­tic is for mul­ti­ple play­ers to link arms with the wearer (the effect is con­ta­gious), and set off into enemy ter­ri­to­ry. Once there, the bearer and con­fr­eres begin skip­ping along and singing loudly ‘Yan­kee Doo­dle Dandy’. So long as they skip and sing, the group is immune to all tag­ging, grenades, belt items, and attacks in gen­er­al. Such a cohort will, skip­ping, sys­tem­at­i­cally scour a story for signs of the flags. Even­tu­ally they will encounter a defender wield­ing a green wand. Presently a shout goes up, they leave off singing and skip­ping, and all flee pel­l-mell for safety with their pre­cious intel­li­gence.

Already I have alluded to the remain­ing items: the three kinds of grenades. These are the most plen­ti­ful items and argal, most apt to be employed. The blue grenade is a stun grenade. It par­a­lyzes for 15 sec­onds but it is only effec­tive if the enemy will­ingly grasps it. This ren­ders it rather ineffec­tive. The red grenade is the ‘Ninja Potion’ grenade. It is employed on enemy grounds, where one hurls it to the ground (dis­card­ing it), shouts “Poof! I’m a nin­ja!” where­upon all ene­mies in sight are briefly par­a­lyzed and one pre­sum­ably effects one’s escape. The green grenade is used either when a cap­tive or a pris­on­er, and it removes both con­di­tions.

Not infre­quently it hap­pens that one is tagged/captured while still in pos­ses­sion of items. If the cap­tor sees them, then he may demand that they be ren­dered up. But sup­pose a grenade is con­cealed? (They are the size of a foos­bal­l.) Then if the cap­tor knows for sure the item is con­cealed, he may demand it regard­less. But sup­pose the cap­tor sus­pects that the cap­tive is con­ceal­ing an item, but does not know it for sure? He can­not demand it.

At some point the two play­ers will pass into the depths of his home ter­ri­to­ry, and arrive at the POW camp. At the begin­ning of the game, one player was appointed War­den and given the power of ‘truth serum’: once a pris­on-break cycle, he may select a pris­oner and ask the pris­oner 6 yes-no ques­tions. The pris­oner may lie once, but all other responses are con­strained to truth.

Now, the prob­lem arises like this. That evening the KGB had obtained the build­ing for the entire night. 3 games were played. As each game lasts some­where around 2hours, and involve a great deal of run­ning and shout­ing up stairs and down halls, the play­ers are uni­formly fagged by the con­clu­sion of game 3. Assem­bling in the audi­to­rium where we had early been instructed at great length on CTFWS, all and sundry began swap­ping tales of nar­row escapes, great vic­to­ries, dire set­backs, and pecu­liar encoun­ters, or deci­sions of the peri­patetic judges.

The Player’s Tale

I hap­pened to over­hear one such con­ver­sa­tion. The player recounted to his friend about his role in the rout of a minor incur­sion on the 7th floor. He escorted his pris­oner back to the POW camp and there had the War­den inter­ro­gate him, as it was felt he had con­cealed a grenade. The War­den, the player said, had asked but 4 ques­tions:

  1. Was the grenade he had red?

    No.

  2. Was the grenade green, then?

    No.

  3. Then surely the grenade was blue?

    No.

The War­den repeated the last ques­tion, and this time the pris­oner answered Yes. The War­den deduced that the con­tra­dic­tion proved that either ques­tion 3 or 4 was the lie. If #4, then the pris­oner had no grenade. But if the lie was #3, then the true answer was #4: the pris­on­er’s grenade was blue. The War­den pro­ceeded to demand that the pris­oner ren­der up the blue grenade. The dis­grun­tled pris­oner did so, and the player ended his anec­dote one grenade rich­er.

I could­n’t help but feel that the War­den’s ques­tions were art­less and inel­e­gant. My read­ing of William Pound­stone and Ray­mond Smullyan’s books has incul­cated in me an appre­ci­a­tion of logic puz­zles and I decided to treat this as one:

“Your inter­locu­tor has a ball which is one of 3 col­ors. What is the least num­ber of yes-no ques­tions you need to ask, and what are they, to ascer­tain the color of the ball? Remem­ber that he may lie once.”

My first step was to con­sider the ques­tion from a pro­gram­mer’s view, con­sid­er­ing this from an infor­ma­tion the­o­retic view. If we can prove how many ques­tions we need at most, then it will be that much eas­ier to for­mu­late the (pos­si­bly tricky) ques­tions.

Now, each ques­tion is Yes or No. That is, they are bina­ry. Each ques­tion can yield at most 1 bit of infor­ma­tion: a bit of infor­ma­tion is, pace Shan­non, a unit of reduced uncer­tain­ty, of cer­tain­ty. Intu­itive­ly, you can think of it as let­ting you choose between pos­si­bil­i­ties, to uniquely spec­ify one item out of a bunch. Sup­pose we are igno­rant of which of 2 states to choose. Then we need 1 bit. Sup­pose it’s 4 states; we divide it into 2 groups of 2, and we need 1 bit to choose between the first and sec­ond group, and then we need another bit to choose within the group. So 2 bits can choose between 4 items. 8 items become divis­i­ble into 2 groups (of groups of 2)—the first bit chooses between group­s-of-groups, the sec­ond between groups, and the third bit between 2 choic­es. So 3 bits can choose between 8 items. The pat­tern is obvi­ous by this point: if you have n bits, they can uniquely iden­tify one item out of 2n.

Let’s tackle a sim­pli­fied form of the prob­lem, a ver­sion with­out any lying. Sup­pose the ball in this case is either red, or it does­n’t exist at all. You are informed he has a ball. How many ques­tions do you need to ask? Obvi­ously there’s exactly one pos­si­bil­i­ty; it’s a log­i­cal cer­tainty that the ball is red. It takes 0 bits to spec­ify 1 item out of a group with only 1 item. You already know what the answer is, so there­fore you need 0 ques­tions.

Sup­pose now that the ball is either red or blue. Now there’s two pos­si­bil­i­ties, but still only 1 can be true. We said ear­lier that 1 bit spec­i­fies out of 2 pos­si­bil­i­ties, so by that rea­son­ing you need ask only 1 ques­tion. Let’s con­vince our­selves that this is true. We can’t get away with ask­ing 0 ques­tion­s—it could be either. We could guess and per­haps be right, but no mat­ter how often our inter­locu­tor chooses red, we could never be absolutely sure. So 0 ques­tions is right out. We could try ask­ing 2 ques­tions, such as ‘Is it red?’ ‘Is it blue?’. This would work, sure­ly. But one can’t help but notice that every Yes will be fol­lowed by a No, and vice ver­sa; indeed, this fol­lows from the law of the excluded mid­dle—the ball can’t be both red and blue, nor nei­ther red or blue. So one of the ques­tions is redun­dant. Which leaves us ask­ing exactly one ques­tion: ‘Is it red?’ If Yes, then that’s the answer; if No, then it must be blue. One ques­tion suffices, just like expect­ed.

Let’s go up a pow­er. 2 bits spec­ify 4 pos­si­bil­i­ties (22 = 4). So if the ball was of 4 col­ors, we could ask ‘Is it red or blue?’ A Yes answer reduces it to the pre­vi­ous 2-color prob­lem, and we know only 1 ques­tion is needed to solve the 2-color prob­lem, so 4 col­ors requires just 2 questions/bits. Our actual prob­lem is 3 col­ors, not 4. Yet we can solve it just like 4; a for­tiori, 2 ques­tions will work. Cer­tain­ly, we can use the ‘excess’ to reduce the amount of think­ing we need to do—­for exam­ple, if we have only 3 col­ors, we can ele­gantly ask ‘Is it red or blue? Blue or green?’ Then YY = blue, YN = red, and NY = green. Note that NN is miss­ing; it does not cor­re­spond to any color (that’s the wastage).

My response to the two play­ers fol­lowed this approach. Assume the pris­oner lies. That means one of the ques­tions, one bit, must be dis­card­ed. Then we need to cover 3 pos­si­bil­i­ties with n+1 bits; 2 bits cover 4 pos­si­bil­i­ties, so 2 bits cover 3 pos­si­bil­i­ties as well, and 2+1 = 3. So 3 ques­tions suffice.

What are the 3 ques­tions? well, let’s fol­low our mod­el. The key is over­lap­ping dis­junc­tions which sum to Truth. The sim­pli­fied 3-color prob­lem had 2 ques­tions of (r or b), (b or g). The liar ver­sion must scrap a ques­tion. So our 3 ques­tions look like: (r or b), (b or g), (g or r).

Let’s give that a try. The pris­oner has a red grenade and does­n’t lie: YNY. ‘r’ is the com­mon fac­tor, and so the grenade must be red. Sup­pose he lies on the first ques­tion: you dis­card to get NY, then it is nei­ther b or g, but g or r. Again, ‘r’ falls out as the only con­sis­tent answer. And this rea­son­ing is sym­met­ri­cal, so it does­n’t mat­ter which ques­tion he lies on: either way, we can fig­ure out the answer in 3 ques­tions, exactly as our infor­mal infor­ma­tion-the­o­ret­i­cal argu­ment says.

I sug­gested this to the two play­ers and after some thought, they assent­ed: those three ques­tions did the trick. I thought it was an inter­est­ing prob­lem, and con­tin­ued until I’d con­vinced myself by the fore­go­ing chain of rea­son­ing that 3 was the min­i­mum, that there was just not enough infor­ma­tion in even the most con­trived set of 2 ques­tions.

After that inci­dent at CMU, I occa­sion­ally brought this prob­lem up in con­ver­sa­tion as a nice logic puz­zle found in the real world. But one day dis­cussing my solu­tion with a Haskell pro­gram­mer, he kindly informed that my solu­tion was incom­plete. 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 inde­ter­mi­nate; all one could deduce was that there was a lie in there. I was thun­der­struck, and my attempts to sal­vage my 3 ques­tions in some man­ner all foundered.

After fur­ther dis­cus­sion, I real­ized that my pre­vi­ous proofs had been naive and their lack of rigor directly led to my fatal mis­take: in my argu­ments, I had smug­gled in illicit infor­ma­tion; specifi­cal­ly, I had assumed one just some­how knew which reply was the lie (if any) and that one could then dis­card it, and solve the no-ly­ing prob­lem. Of course, one does­n’t know which reply is the lie! That’s fur­ther infor­ma­tion one needs to obtain!

Infor­ma­tion the­ory had served me well, and had done as I had asked—but I had­n’t real­ized that my proof did­n’t apply. A bet­ter anal­ogy was need­ed. I found the anal­ogy in another area of com­puter sci­ence: in cod­ing the­o­ry. In this case, I mean by cod­ing the­ory the study of how to detect and cor­rect mis­takes in a stream of bits, what ‘error cor­rec­tion codes’ are, and how they can be devised. With cod­ing the­o­ry, we are con­cep­tu­ally sent a stream of bits and noth­ing else. Some­times one of the bits will be cor­rupted (flipped). We know we can add fur­ther bits to detect errors: for exam­ple, sup­pose we know a stream will have at most 1 cor­rupted bit. Then we can tack on a num­ber which says ‘the pre­vi­ous 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 check­sum is cor­rupt­ed, then the cor­rect stream won’t it either, and we’ll still know some­thing went wrong).

Some­times we don’t need an explicit check­sum or ECC bits, since a bit-stream might have con­straints or a known struc­ture. (For exam­ple, one knows an ASCII file is sup­posed to have a new­line ter­mi­na­tor, and that bytes gen­er­ally don’t have the high­-bit set.) Sim­i­lar­ly, our 3 ques­tions only have 3 valid streams: YYN, YNY, and NYY. (Each color is present in 2 ques­tions, and absent from one ques­tion.) The 3 valid streams have an impor­tant prop­er­ty: if we get them, then we know that the entire sequence is truth­ful. Were one not truth­ful, then either a true N would be turned into a Y (in which case our answer must be the degen­er­ate YYY) or a Y would be N (in which case the obvi­ously lying NNY, or a per­mu­ta­tion); either leads to con­tra­dic­tions. So if we’re given a valid stream, we can rea­son that there is no lie and then we can deduce the color of the ball. Even more impor­tant is the con­se­quence: in the case of a NNY, or a YYY, we now know that the lie has been used up. The pris­oner only gets one lie and that’s it. The next answers must be truth­ful.

Let’s con­sider NNY. We know the Y must be true, since the pris­oner 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 impos­si­ble result that NNN is com­pletely true1. So there are only two pos­si­bil­i­ties as to the lying reply: N and N. For­tu­nate­ly, one ques­tion suffices to dis­tin­guish. ‘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 com­mon fac­tor between 1 and 3 is ‘r’—the ball is red. Be the answer ‘No’. then the sec­ond N was the lie, and so it is (b or g) and (g or r); the ball is green.

Thus 4 ques­tions suffice for all pos­si­bil­i­ties other than YYY. Can we solve that too? We know that one answer is a lie. But we can­not use the same strat­egy as before! Sup­pose 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 pos­si­ble, either is con­sis­tent. One ques­tion can’t dis­tin­guish between 3 pos­si­bil­i­ties. ‘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 ques­tion about the last two pos­si­bil­i­ties, but what a defeat this feels like! To go from just 3 ques­tions to 5!

Can we be more clever than 5 ques­tions? It takes 2 ques­tions, we know, to decide the col­or. That is because there are 3 col­ors. But the lie bol­lixes things. Per­haps we can han­dle the lie in 2 ques­tions as well. Does this work from an infor­ma­tion-the­o­ret­i­cal view? Well, aren’t there 4 pos­si­bil­i­ties here as well? Either the pris­oner does­n’t lie at all, he lies on the 1st ques­tion, the 2nd, or the 3rd. This is an exhaus­tive list­ing. We need to pick out the cor­rect item. So we need a total of 4 bits to solve this ques­tion. But this assumes that there’s no ineffi­cien­cy, that we are wring­ing a full bit out of each ques­tion. Pre­vi­ously I men­tioned that the triply-en­tan­gled ques­tions were ineffi­cient, in a sense. So we need a new set of ques­tions.

Our intu­ition here about ‘sequences that can­not be trans­formed into each other’ can be for­mal­ized a bit more. (I am indebted to this gen­eral approach to the lovely book .)

Imag­ine one of those tin­ker-toy sets, or one of those chem­istry mod­els with the balls and sticks. A stick and a ball can rep­re­sent 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 sim­ple enough; no bits cor­re­spond to a lonely ball with no stick to slide on; one bit is a rod with 2 end­points for the ball to be at. (This should start sound­ing famil­iar.) What then is 2 bits? Why, a square of course! If a line has 2 end­points, then the next step is a square with 4 cor­ners. Let’s label them: the one clos­est to us is 00, the one to our left is 10, the one to our right is 01, and the fur­thest one is 11. Now here’s the inter­est­ing bit: our bit stream of 2 bits, in its entire­ty, is just the ball we push from cor­ner to cor­ner. We did­n’t notice this iden­tity in the case of the line and bit—we could think that it was just a coin­ci­dence. But what’s a lie, or error, in this model then? A lie is our oppo­nent being able to push the ball one posi­tion (with­out us see­ing). So sup­pose the ball is sit­ting at 00; with one push, our oppo­nent could push it left to 10, or right to 01. But he could­n’t push it to 11, since he’d have to push it to 10 or 01, and then push it round the cor­ner a sec­ond time. So 11 is right out. The next step up is 3 bits, with 8 cor­ners; this is a 3D cube, which is much the same—one push of the ball can’t move it all the way to another cor­ner, etc. With 4 bits, we reach 16 but that means a hyper­cube and those are a lit­tle hard to visu­al­ize, so let’s stop there.

Let’s go back to the orig­i­nal prob­lem. How does this way of think­ing help us? Well, our three ques­tions were erro­neous. Why? Because in our hyper­cube, our valid answers were all posi­tioned just one point sep­a­rat­ing them from each oth­er. So a lie could move the ball 1 up and then we could­n’t fig­ure out which way the ball came from. What we need is to put 2 points between each of our valid points. This rea­son­ing tells us we do need a fourth ques­tion: we can’t arrange 8 points such that there are 2 points in between each valid point. (Think of it as a cir­cle: 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 require­ments: we must use up 4 ques­tions, and each valid sequence has to be cor­rupt­ible by 2 lies (but not 1). The lat­ter implies we ask about 2 of the col­ors twice and let the third take care of itself. This approach will lead us to the answer.

Again, our prob­lem stems from the fact that each valid answer can be turned into the lying YYY sequence by a sin­gle lie. Just given YYY, we don’t know which ‘true’ sequence the pris­oner started from. If we could some­how make each valid sequence be con­vert­ible into a differ­ent lying sequence then the other 2, then we could rea­son back­wards from the lying sequence to the valid sequence, and from thence solve the prob­lem. With 4 ques­tions and 4 replies how do we do that?

One’s first impulse is prob­a­bly to try to sim­plify things again. With 4 ques­tions, can’t we ask “Is it red? Is it red? Is it blue? Is it blue?” Obvi­ously with all truth­ful answers, we can know what color it is; bet­ter, we know that there were no lies here, since it’s all con­sis­tent. And it even seems to work if the grenade is red or blue. But unfor­tu­nate­ly, these 4 ques­tions can be defeat­ed: sup­pose the answers are NNNY. Clearly one of the two last ques­tions 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 tin­gling: there feels like there’s some­thing waste­ful about these 4 ques­tions. Our last 2 ques­tions are doing yeo­man’s ser­vice in expos­ing the vicious con­temptible lie of the pris­on­er, but the first 2 are not really doing any­thing use­ful. How can we make them do more work?

We can do that by mak­ing the ques­tions even fur­ther entan­gled. Con­sider the 4 ques­tions: ‘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 ques­tion, where pre­vi­ously each color only appeared twice. This sequence has the prop­erty we seek. There are 3 valid sequences of replies: YYNN, NNYY, and YYYY. No mat­ter which reply is a lie, it does­n’t get turned into a lying sequence which is reach­able from one of the oth­ers. The pos­si­ble lying sequences are YYYN, YNNN, YNYY and so on. We can sat­isfy our­selves of this by exhaus­tively list­ing out the 15 pos­si­ble responses (4 bits have 16 pos­si­ble val­ues, but a NNNN is the sole impos­si­ble sequence, so there’s just 15 pos­si­ble sequences).

And that’s that. we have learned that while the War­den was cor­rect in using 4 ques­tions, his par­tic­u­lar set of 4 only worked because the pris­oner chose the sub­op­ti­mal strat­egy of deny­ing every­thing. After sev­eral false detours, much inter­est­ing think­ing, and a per­haps sur­pris­ing amount of com­puter sci­ence, we have found the answer to this decep­tively sim­ple prob­lem. The prob­lem can be solved by just 4 ques­tions, that lead to 4 truths.

"And thus do we of wis­dom and of reach,

With wind­lasses and with assays of bias,

By indi­rec­tions find direc­tions out."

Boxo’s Tale

Haskeller Boxo (he of the deci­sion the­ory monad) offers the fol­low­ing twisty exam­i­na­tion of a very sim­i­lar prob­lem to the pre­ced­ing where one can learn the truth in just 2 ques­tions:

Sup­pose you want to know whether p and there is a per­son that knows whether p, but they may lie depend­ing on arbi­trary cir­cum­stances, includ­ing what ques­tion 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 ques­tion would you answer yes?”

  1. 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”

  2. 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”

  3. 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”

  4. not p and askee lies: “no”

    not p and and askee’s choice is lying, so they would answer “yes”, but since their choice is lying they answer “no”

So they will tell you the truth about p.

The 2 Ques­tions

Now, to find out the color of the ball, just ask the two ques­tions you would ask of an hon­est per­son, name­ly:

“Is it green or blue”?

and if the answer is yes, “Is it green?”

But replace them with the propo­si­tions “It is green or blue” and “It is green” and ask them in the place of p in the ques­tion:

“If I asked you whether p and your choice of lying or truth-telling was the same as in the case of this ques­tion would you answer yes?”

The askee will always answer with the truth, and you will find out the truth in at most two ques­tions.

The 1 Model

Here I’ll explain my tech­nique in com­ing up with the answer.

In my mod­el, a per­son chooses whether to lie or tell the truth, not whether to say “yes” or “no”. More pre­cise­ly—an answerer has access to a func­tion eval­u­ate of type (Proposition -> Bool) such that (evaluate p) = True iff p, and for every pair of answerer and cir­cum­stances there is a func­tion 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 cur­rent cir­cum­stances your func­tion 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 equiv­a­lent to (f (f (evaluate p))) since—ie., for liars and truth-tellers, (not (not (evaluate p))) and (id (id (evaluate p))) respec­tive­ly, which both reduce to (evaluate p).

The Null Case

But con­sider answer­ers who have decided to either answer­ing “yes” or answer­ing “no” to your ques­tion.

In this case, f = (const True) or f = (const False) respec­tive­ly. You may see the prob­lem: no clever ques­tion will help you if in the end a is applied to the answer. The solu­tion pre­sented above fails in the pres­ence of “con­stant answer­ers”.

The One True Ques­tion

Here’s a way to arguably get the answer with just one ques­tion in the absence of con­stant answer­ers & allow­ing non-an­swer­ing3. Con­sider this propo­si­tion:

“The ball is green or it is the case that the ball is blue and this propo­si­tion is false.”

It’s true if the ball is green, false if the ball is red, and unde­fined if the ball is blue.

Now just plug this propo­si­tion into our liar-rec­ti­fy­ing ques­tion like so:

“If I asked you whether the ball is green or it is the case that the ball is blue and this propo­si­tion is false; and your choice of lying or truth-telling was the same as in the case of this ques­tion, would you answer yes?”

Now ask the above ques­tion. If they answer “yes”, the ball is green. If they answer “no”, the ball is red. If they answer noth­ing, or if they answer “mu”, or if their head explodes, the ball is blue.

Mestroyer’s tale

Mestroyer offers this graph­i­cal take on the prob­lem:

Your essay “The 3 Grenades” is wrong (as a few com­menters have pointed out). Pre­clud­ing self­-ref­er­en­tial ques­tions like Boxo comes up with, 4 ques­tions are not enough when the per­son does­n’t have to lie. How­ev­er, if out of 4 ques­tions, they are forced to lie exactly once, it can be done in 4 ques­tions. If they have to lie exactly once, you can actu­ally pick from among 4 col­ors in 4 ques­tions.

(There’s another assump­tion I did­n’t real­ize I was mak­ing: you don’t change future ques­tions based on what answers you get.) But here goes: If every ques­tion is depen­dent only on the col­ors of the grenades, and you have 4 ques­tions, then if you draw out a grid like this:

Ini­tial empty grid

Then each square rep­re­sents a set of four answers, one for each of ques­tions Q1, Q2, Q3, and Q4. The col­umn 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 num­bered in grey code, which means that mov­ing one square in any direc­tion is equiv­a­lent to flip­ping one Y/N answer. Because there are 4 answers to flip, and 4 direc­tions to move in (you can move left on the left­most square to end up on the right­most, same with top and bot­tom. Like the Aster­oids video game), every answer-flip is rep­re­sented by a move of one square in a par­tic­u­lar direc­tion.

So for each pos­si­ble grenade col­or, answer­ing the ques­tions truth­fully would spec­ify a square in the grid. Answer­ing one incor­rectly will move the set of answers one square in one direc­tion. 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 per­son 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 deter­mine the ball col­or, we have to arrange 3 of these shapes on the grid so that they don’t over­lap. If they do over­lap, then they could have answered that way if the ball was one of two or more differ­ent col­ors.

Because this grid wraps like the aster­oids game, it does­n’t mat­ter where you put the first “+”. Men­tally plac­ing a sec­ond plus makes it obvi­ous that there is nowhere to put the last , no mat­ter 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 deter­mine the grenade color if 4 col­ors are pos­si­ble in 4 ques­tions, if in 4 ques­tions they must lie, just pick the ques­tions so that if the grenade is red, the cor­rect 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 basi­cally the same.)

When you get your answers, look up a square in the grid, and what­ever color it is, is the color of the ball.

See Also


  1. Remem­ber, we’re assum­ing that he does have a ball and the prob­lem is fig­ur­ing out its col­or.↩︎

  2. id is the iden­tity func­tion, defined as f x = x.↩︎

  3. In some respects, this is smug­gling in addi­tional infor­ma­tion; there are con­nec­tions to deno­ta­tive seman­tics in com­puter sci­ence and the .↩︎