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 en­sem­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 se­mes­ter hold­ing evening rev­els cen­ter­ing around an au­tochtho­nous amuse­ment called ‘Cap­ture the Flag with Stuff’ (CTFWS).

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

The ob­ject if the game is sim­ple: per the name of the game, whichever team first steals the 5 or so flags be­long­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 in­hu­man: the teams are is­sued sev­eral glyphs (posters) which are held to have magic pow­ers on that team’s ter­ri­to­ry. One poster, for ex­am­ple, is ‘dis­gust­ing’: should it be placed on a door, an op­po­nent will be ut­terly re­pelled by it and un­able to pro­ceed through. This poster is fre­quently used to se­cure the mul­ti­ple doors of a lob­by. An­other poster is the alarm bel­l—when an op­po­nent comes into eye­shot, a vol­u­ble alarm will sound and alert the de­fend­ers. (As posters lack any vo­cal cords or speak­ers, it is un­der­stood that the op­pos­ing play­ers will do yeo­man’s ser­vice in this stead.) A fi­nal poster sim­ply par­a­lyzes for a minute any en­e­mies who see it.

If the guards are in­deed hu­man, then they will likely be armed with any of a va­ri­ety of wands (foam stick­s). A red wand may be dis­charged at an op­po­nen­t—in his own ter­ri­to­ry, and the re­sult is that they are au­to­mat­i­cally cap­tured and must go to the POW camp. (For­tu­nate­ly, their im­mure­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 em­ployed once and then must be dis­card­ed. The blue wand func­tions sim­i­lar­ly, but is less de­sir­able as it merely par­a­lyzes for a time, and in the bus­tle of events the vic­tim may well es­cape be­fore be­ing 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 ar­ti­facts that one cinches around one’s waist and in­vokes. They are very pow­er­ful and use­ful items. One belt is like an am­bu­la­tory ver­sion of the poster which stuns all en­e­mies in sight; an­other belt waives the re­stric­tion that a player may cap­ture only one en­e­my, and al­lows 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 en­emy ter­ri­to­ry. Once there, the bearer and con­fr­eres be­gin skip­ping along and singing loudly ‘Yan­kee Doo­dle Dandy’. So long as they skip and sing, the group is im­mune to all tag­ging, grenades, belt items, and at­tacks in gen­er­al. Such a co­hort will, skip­ping, sys­tem­at­i­cally scour a story for signs of the flags. Even­tu­ally they will en­counter a de­fender 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 in­tel­li­gence.

Al­ready I have al­luded to the re­main­ing items: the three kinds of grenades. These are the most plen­ti­ful items and ar­gal, most apt to be em­ployed. The blue grenade is a stun grenade. It par­a­lyzes for 15 sec­onds but it is only effec­tive if the en­emy will­ingly grasps it. This ren­ders it rather in­effec­tive. The red grenade is the ‘Ninja Po­tion’ grenade. It is em­ployed on en­emy grounds, where one hurls it to the ground (dis­card­ing it), shouts “Poof! I’m a nin­ja!” where­upon all en­e­mies in sight are briefly par­a­lyzed and one pre­sum­ably effects one’s es­cape. The green grenade is used ei­ther when a cap­tive or a pris­on­er, and it re­moves both con­di­tions.

Not in­fre­quently it hap­pens that one is tagged/­cap­tured while still in pos­ses­sion of items. If the cap­tor sees them, then he may de­mand 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 de­mand it re­gard­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 de­mand it.

At some point the two play­ers will pass into the depths of his home ter­ri­to­ry, and ar­rive at the POW camp. At the be­gin­ning of the game, one player was ap­pointed War­den and given the power of ‘truth serum’: once a pris­on-break cy­cle, he may se­lect a pris­oner and ask the pris­oner 6 yes-no ques­tions. The pris­oner may lie on­ce, but all other re­sponses are con­strained to truth.

Now, the prob­lem arises like this. That evening the KGB had ob­tained the build­ing for the en­tire night. 3 games were played. As each game lasts some­where around 2hours, and in­volve 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. As­sem­bling in the au­di­to­rium where we had early been in­structed at great length on CTFWS, all and sundry be­gan swap­ping tales of nar­row es­capes, great vic­to­ries, dire set­backs, and pe­cu­liar en­coun­ters, or de­ci­sions of the peri­patetic judges.

The Player’s Tale

I hap­pened to over­hear one such con­ver­sa­tion. The player re­counted to his friend about his role in the rout of a mi­nor in­cur­sion on the 7th floor. He es­corted his pris­oner back to the POW camp and there had the War­den in­ter­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 re­peated the last ques­tion, and this time the pris­oner an­swered Yes. The War­den de­duced that the con­tra­dic­tion proved that ei­ther 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 an­swer was #4: the pris­on­er’s grenade was blue. The War­den pro­ceeded to de­mand 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 in­el­e­gant. My read­ing of William Pound­stone and Ray­mond Smullyan’s books has in­cul­cated in me an ap­pre­ci­a­tion of logic puz­zles and I de­cided to treat this as one:

“Your in­ter­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 as­cer­tain the color of the ball? Re­mem­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 in­for­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 bi­na­ry. Each ques­tion can yield at most 1 bit of in­for­ma­tion: a bit of in­for­ma­tion is, pace Shan­non, a unit of re­duced un­cer­tain­ty, of cer­tain­ty. In­tu­itive­ly, you can think of it as let­ting you choose be­tween pos­si­bil­i­ties, to uniquely spec­ify one item out of a bunch. Sup­pose we are ig­no­rant of which of 2 states to choose. Then we need 1 bit. Sup­pose it’s 4 states; we di­vide it into 2 groups of 2, and we need 1 bit to choose be­tween the first and sec­ond group, and then we need an­other bit to choose within the group. So 2 bits can choose be­tween 4 items. 8 items be­come di­vis­i­ble into 2 groups (of groups of 2)—the first bit chooses be­tween group­s-of-groups, the sec­ond be­tween groups, and the third bit be­tween 2 choic­es. So 3 bits can choose be­tween 8 items. The pat­tern is ob­vi­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 ly­ing. Sup­pose the ball in this case is ei­ther red, or it does­n’t ex­ist at all. You are in­formed he has a ball. How many ques­tions do you need to ask? Ob­vi­ously there’s ex­actly 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 al­ready know what the an­swer is, so there­fore you need 0 ques­tions.

Sup­pose now that the ball is ei­ther 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 ei­ther. We could guess and per­haps be right, but no mat­ter how often our in­ter­locu­tor chooses red, we could never be ab­solutely 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 no­tice that every Yes will be fol­lowed by a No, and vice ver­sa; in­deed, this fol­lows from the law of the ex­cluded mid­dle—the ball can’t be both red and blue, nor nei­ther red or blue. So one of the ques­tions is re­dun­dant. Which leaves us ask­ing ex­actly one ques­tion: ‘Is it red?’ If Yes, then that’s the an­swer; if No, then it must be blue. One ques­tion suffices, just like ex­pect­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 an­swer re­duces 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 re­quires just 2 ques­tion­s/bits. Our ac­tual 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 ‘ex­cess’ to re­duce the amount of think­ing we need to do—­for ex­am­ple, if we have only 3 col­ors, we can el­e­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 re­sponse to the two play­ers fol­lowed this ap­proach. As­sume 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 an­swer. And this rea­son­ing is sym­met­ri­cal, so it does­n’t mat­ter which ques­tion he lies on: ei­ther way, we can fig­ure out the an­swer in 3 ques­tions, ex­actly as our in­for­mal in­for­ma­tion-the­o­ret­i­cal ar­gu­ment says.

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

After that in­ci­dent at CMU, I oc­ca­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 so­lu­tion with a Haskell pro­gram­mer, he kindly in­formed that my so­lu­tion was in­com­plete. As proof, he asked me to de­duce the color if the re­sponse was YYY. I froze. Any of the replies could be the lie. The true an­swer was in­de­ter­mi­nate; all one could de­duce was that there was a lie in there. I was thun­der­struck, and my at­tempts to sal­vage my 3 ques­tions in some man­ner all foundered.

After fur­ther dis­cus­sion, I re­al­ized that my pre­vi­ous proofs had been naive and their lack of rigor di­rectly led to my fa­tal mis­take: in my ar­gu­ments, I had smug­gled in il­licit in­for­ma­tion; specifi­cal­ly, I had as­sumed one just some­how knew which re­ply 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 re­ply is the lie! That’s fur­ther in­for­ma­tion one needs to ob­tain!

In­for­ma­tion the­ory had served me well, and had done as I had asked—but I had­n’t re­al­ized that my proof did­n’t ap­ply. A bet­ter anal­ogy was need­ed. I found the anal­ogy in an­other 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 de­tect and cor­rect mis­takes in a stream of bits, what ‘er­ror cor­rec­tion codes’ are, and how they can be de­vised. 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 de­tect er­rors: for ex­am­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 ze­ros in it’; then if a 1 is flipped to 0, or a 0 to 1, we can add up the ze­ros and see that they don’t match (if the added check­sum is cor­rupt­ed, then the cor­rect stream won’t it ei­ther, and we’ll still know some­thing went wrong).

Some­times we don’t need an ex­plicit check­sum or ECC bits, since a bit-stream might have con­straints or a known struc­ture. (For ex­am­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 ab­sent from one ques­tion.) The 3 valid streams have an im­por­tant prop­er­ty: if we get them, then we know that the en­tire se­quence is truth­ful. Were one not truth­ful, then ei­ther a true N would be turned into a Y (in which case our an­swer must be the de­gen­er­ate YYY) or a Y would be N (in which case the ob­vi­ously ly­ing NNY, or a per­mu­ta­tion); ei­ther 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 de­duce the color of the ball. Even more im­por­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 an­swers 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 as­sume the Y is a lie, then we get the im­pos­si­ble re­sult that NNN is com­pletely true1. So there are only two pos­si­bil­i­ties as to the ly­ing re­ply: 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 be­tween 1 and 3 is ‘r’—the ball is red. Be the an­swer ‘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 an­swer is a lie. But we can­not use the same strat­egy as be­fore! Sup­pose we asked if 1 is the lie, and we are told ‘No’. This ‘No’ is true, as we al­ready know. So was it 2 or 3 that was the lie? Ei­ther is pos­si­ble, ei­ther is con­sis­tent. One ques­tion can’t dis­tin­guish be­tween 3 pos­si­bil­i­ties. ‘Was 1 or 2 the lie’? ‘Yes’. Then we still have to choose be­tween 1 and 2. We can clearly patch things up with a fifth and fi­nal ques­tion about the last two pos­si­bil­i­ties, but what a de­feat 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 de­cide the col­or. That is be­cause 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 in­for­ma­tion-the­o­ret­i­cal view? Well, aren’t there 4 pos­si­bil­i­ties here as well? Ei­ther the pris­oner does­n’t lie at all, he lies on the 1st ques­tion, the 2nd, or the 3rd. This is an ex­haus­tive list­ing. We need to pick out the cor­rect item. So we need a to­tal of 4 bits to solve this ques­tion. But this as­sumes that there’s no in­effi­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 in­effi­cient, in a sense. So we need a new set of ques­tions.

Our in­tu­ition here about ‘se­quences that can­not be trans­formed into each other’ can be for­mal­ized a bit more. (I am in­debted to this gen­eral ap­proach 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 fa­mil­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 la­bel 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 in­ter­est­ing bit: our bit stream of 2 bits, in its en­tire­ty, is just the ball we push from cor­ner to cor­ner. We did­n’t no­tice this iden­tity in the case of the line and bit—we could think that it was just a co­in­ci­dence. But what’s a lie, or er­ror, in this model then? A lie is our op­po­nent be­ing able to push the ball one po­si­tion (with­out us see­ing). So sup­pose the ball is sit­ting at 00; with one push, our op­po­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 an­other cor­ner, etc. With 4 bits, we reach 16 but that means a hy­per­cube and those are a lit­tle hard to vi­su­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 er­ro­neous. Why? Be­cause in our hy­per­cube, our valid an­swers were all po­si­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 be­tween 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 be­tween 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 to­tal, which is more than we get.) So we have more re­quire­ments: we must use up 4 ques­tions, and each valid se­quence has to be cor­rupt­ible by 2 lies (but not 1). The lat­ter im­plies we ask about 2 of the col­ors twice and let the third take care of it­self. This ap­proach will lead us to the an­swer.

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

One’s first im­pulse 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?” Ob­vi­ously with all truth­ful an­swers, 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 un­for­tu­nate­ly, these 4 ques­tions can be de­feat­ed: sup­pose the an­swers 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 se­quence fails. But it does seem to be on the right track­—it al­most 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 do­ing yeo­man’s ser­vice in ex­pos­ing the vi­cious con­temptible lie of the pris­on­er, but the first 2 are not re­ally do­ing 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 en­tan­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 ap­pears in every ques­tion, where pre­vi­ously each color only ap­peared twice. This se­quence has the prop­erty we seek. There are 3 valid se­quences of replies: YYNN, NNYY, and YYYY. No mat­ter which re­ply is a lie, it does­n’t get turned into a ly­ing se­quence which is reach­able from one of the oth­ers. The pos­si­ble ly­ing se­quences are YYYN, YNNN, YNYY and so on. We can sat­isfy our­selves of this by ex­haus­tively list­ing out the 15 pos­si­ble re­sponses (4 bits have 16 pos­si­ble val­ues, but a NNNN is the sole im­pos­si­ble se­quence, so there’s just 15 pos­si­ble se­quences).

And that’s that. we have learned that while the War­den was cor­rect in us­ing 4 ques­tions, his par­tic­u­lar set of 4 only worked be­cause the pris­oner chose the sub­op­ti­mal strat­egy of deny­ing every­thing. After sev­eral false de­tours, much in­ter­est­ing think­ing, and a per­haps sur­pris­ing amount of com­puter sci­ence, we have found the an­swer to this de­cep­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 as­says of bi­as,

By in­di­rec­tions find di­rec­tions out."

Boxo’s Tale

Haskeller Boxo (he of the de­ci­sion the­ory monad) offers the fol­low­ing twisty ex­am­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 de­pend­ing on ar­bi­trary cir­cum­stances, in­clud­ing what ques­tion they’re asked.

Ask them this:

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

  1. p and as­kee truth-tells:

    p and as­kee’s choice is truth-telling, so they would an­swer “yes”, and since they’re truth-telling, they an­swer “yes”

  2. not p and as­kee truth-tells: “no”

    not p and as­kee’s choice is truth-telling, so they would an­swer “no”, and since they’re truth-telling, they an­swer “no”

  3. p and as­kee lies: “yes”

    p and as­kee’s choice is ly­ing, so they would an­swer “no”, but since their choice is ly­ing they an­swer “yes”

  4. not p and as­kee lies: “no”

    not p and and as­kee’s choice is ly­ing, so they would an­swer “yes”, but since their choice is ly­ing they an­swer “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 an­swer is yes, “Is it green?”

But re­place 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 ly­ing or truth-telling was the same as in the case of this ques­tion would you an­swer yes?”

The as­kee will al­ways an­swer with the truth, and you will find out the truth in at most two ques­tions.

The 1 Model

Here I’ll ex­plain my tech­nique in com­ing up with the an­swer.

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 an­swerer has ac­cess to a func­tion eval­u­ate of type (Proposition -> Bool) such that (evaluate p) = True iff p, and for every pair of an­swerer and cir­cum­stances there is a func­tion f of type (Bool -> Bool) such that when you ask of them “p?”, they an­swer with (f (evaluate p)). In the case of an an­swerer who has de­cided 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 an­swer, 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))) re­spec­tive­ly, which both re­duce to (evaluate p).

The Null Case

But con­sider an­swer­ers who have de­cided to ei­ther an­swer­ing “yes” or an­swer­ing “no” to your ques­tion.

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

The One True Ques­tion

Here’s a way to ar­guably get the an­swer with just one ques­tion in the ab­sence of con­stant an­swer­ers & al­low­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 un­de­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 ly­ing or truth-telling was the same as in the case of this ques­tion, would you an­swer yes?”

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

Mestroyer’s tale

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

Your es­say “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 ex­actly on­ce, it can be done in 4 ques­tions. If they have to lie ex­actly on­ce, you can ac­tu­ally pick from among 4 col­ors in 4 ques­tions.

(There’s an­other as­sump­tion I did­n’t re­al­ize I was mak­ing: you don’t change fu­ture ques­tions based on what an­swers you get.) But here goes: If every ques­tion is de­pen­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 an­swers, one for each of ques­tions Q1, Q2, Q3, and Q4. The col­umn de­cides the an­swers to Q1 and Q2. The row de­cides the an­swers to Q3 and Q4. I’m us­ing “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 di­rec­tion is equiv­a­lent to flip­ping one Y/N an­swer. Be­cause there are 4 an­swers to flip, and 4 di­rec­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 As­ter­oids video game), every an­swer-flip is rep­re­sented by a move of one square in a par­tic­u­lar di­rec­tion.

So for each pos­si­ble grenade col­or, an­swer­ing the ques­tions truth­fully would spec­ify a square in the grid. An­swer­ing one in­cor­rectly will move the set of an­swers one square in one di­rec­tion. So if when the grenade is re­ally red, the true an­swers are 0101 (No to Q1, yes to Q2, no to Q3, yes to Q4), the sets of an­swers the per­son can give are the ones filled in be­low:

Grid up­dated 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 al­ways de­ter­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 an­swered that way if the ball was one of two or more differ­ent col­ors.

Be­cause this grid wraps like the as­ter­oids game, it does­n’t mat­ter where you put the first “+”. Men­tally plac­ing a sec­ond plus makes it ob­vi­ous that there is nowhere to put the last , no mat­ter where you put it.

But, if they have to lie, then the an­swers they can give look like this:

Grid if ly­ing

And you can fit 4 of this shape on the grid:

Filled in grid

So to de­ter­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 an­swers 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 ba­si­cally the same.)

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

See Also


  1. Re­mem­ber, we’re as­sum­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, de­fined as f x = x.↩︎

  3. In some re­spects, this is smug­gling in ad­di­tional in­for­ma­tion; there are con­nec­tions to de­no­ta­tive se­man­tics in com­puter sci­ence and the .↩︎