The New Challenge:
One night at Zeno's, Maggie and Charles were discussing the importance of questions, perhaps out of respect for their mutual hero, Socrates. At some point in their conversation, Maggie removed from her purse three sealed envolopes, and explained that one contained two one-dollar bills, one contained two five-dollar bills, and another contained one one-dollar bill and one five-dollar bill. She declined to identify which contained which.
Maggie then asked three waiters---John, Jim and Joe---to participate in an experiment, to which they agreed. She then gave them each an envelope.
"I want each of you of open privately your envelope, and to tell Charles what is inside---but I want you to lie about the contents!," instructed Maggie.
They agreed, as Charles watched on.
John reported that he had two one-dollar bills.
Jim reported that he had two five-dollar bills.
Joe reported that he had one one-dollar bill and one five-dollar bill.
"Now Charles," pressed Maggie, "I want you to come up with a procedure, using the fewest possible questions, whereby you ask a waiter to pull out one bill he is holding and show it, until you can deduce who is holding the envelope with the two different bills."
OK, Zeno's patrons, give Charles a helping hand: What is the fewest possible number of questions he needs to ask to make his deduction, and to whom should he direct his first question??
Robert Rorschach's solution, which appears below, is repeated here. It is succinct, and right on the mark. Thanks to all you Zeno's patrons! Keep it up!
One question is enough. Joe said his envelope had a one and a five. Therefore it must either have two ones or two fives (he lied). Ask him to show a bill from his envelope. It will be a one or a five. If it's a one, Joe's envelope must have two ones; therefore Jim's envelope must have a one and a five: it cannot have two one's because Joe's does and it cannot have two five's because that's what Jim claimed it had and that claim was a lie. Similarly, if Joe shows a five, then his envelope has two five's, so John's cannot have two fives. Since John's claim that his envelope has two ones is a lie, John's envelope must have a one and a five.
ZENO's Patrons' Responses:
From: Mark Young
One question, directed to Joe. We know Joe isn't holding a five and a one ('cause he said he was). Thus he's holding either two ones or two fives. If Joe pulls out a one, he's holding two ones. Thus Jim isn't holding two ones, which together with the information that he isn't holding two fives, means he's holding a one and a five. Thus John is holding the two fives. If Joe pulls out a five, he's holding two fives. Thus John isn't holding two fives, nor two ones, so John has the one and the five, leaving the two ones for Jim. ...mark young From: "William R. Wagenseller" Organization: Heald Colleges 3 queries: (1) To Joe - Whatever he shows means he is holding the other of the same demoniation since he originally LIED about having the odd set. (2) Ask the next TWO questions to the same person (it makes no difference whether it is John or Jim as long as the same person is asked twice) - Either of the other two can show you the type of bill other than the one Joe showed after the 1st question. However, after asking the question the second time of the same person, they will either (a) reveal a matching bill - Hence the odd man out has the 2 different denomiations; or (b) reveal a different bill - Hence showing himself to be the holder of the different denomiations. This could be done in 2 queries, but only if the second person asked showed you a bill identical to the one Joe showed. Hence, you would know HE was the one with the two different bills since Joe already revealed he had the matching pair of that particular denomiation. THIS WAS FUN. THX bill From: "Robert F. Rorschach" One question is enough. Joe said his envelope had a one and a five. Therefore it must either have two ones or two fives (he lied). Ask him to show a bill from his envelope. It will be a one or a five. If it's a one, Joe's envelope must have two ones; therefore Jim's envelope must have a one and a five: it cannot have two one's because Joe's does and it cannot have two five's because that's what Jim claimed it had and that claim was a lie. Similarly, if Joe shows a five, then his envelope has two five's, so John's cannot have two fives. Since John's claim that his envelope has two ones is a lie, John's envelope must have a one and a five. From: Beth Ask Joe to show one of his bills. Received: from rdrunner.dalton.PeachNet.EDU (rdrunner.Dalton.PeachNet.EDU [184.108.40.206]) by grits.valdosta.peachnet.edu (8.6.10/8.6.9) with ESMTP id KAA03813 for ; Wed, 24 Apr 1996 10:11:14 -0400 Ask Joe to pull out one bill. This rest is obvious. If he bulls out a $5 he has 2 $5s since he does not have one of each. Thus John has a $1 and a $5 and Jim has 2 $1s. If He pulls out a $1 you reverse the process. Hi Ron! My wife is the Belly Dancer. From: Rob Meredith If the waiters are clever enough, then Charles will never find out which holds the envelope with the two different notes. If each pulls out the same note every time Charles asks them, Charles will never know, no matter how many questions he asks, or who he asks first. Rob Meredith. Received: from vireo.cacd.rockwell.com ([220.127.116.11]) by grits.valdosta.peachnet.edu (8.6.10/8.6.9) with ESMTP id NAA09660 for ; Tue, 30 Apr 1996 13:35:21 -0400 Sender: email@example.com ask joe to show a bill. If it is a one, then Jim has differing bills. Otherwise, John has differing bills. (Joe cannot...because he said he did, and he lied.) -- Scott Haney firstname.lastname@example.org email@example.com From: "Sharleen \"Sahrlan\" Johnson" Organization: Duke University One question: Ask Joe to show one of his bills... since he claims to have one of each, and he is lying, he must have two of the same. If he has two fives, then John has one of each, and Jim has two ones. (John claims to have two ones, but is lying, and therefore can only be in possession of one of each since Joe already has the pair of fives.) If Joe has two ones, then Jon has two fives and Jim has one of each. Regards, Sharleen http://www.duke.edu/~spj1 email: firstname.lastname@example.org From: email@example.com Subject: Sesto quesito - John, Jim e Joe Il primo (ed unico) cui chiedere di mostrare un biglietto dalla propria b= usta =E9 Joe: per le regole del gioco, Egli deve aver mentito e non pu=F2= possedere due biglietti diversi, come dichiara. Pertanto se Joe mostra un biglietto da un milione, deve possederne anche = l'altro; in tal caso, sempre per le regole del gioco, poich=E8 Jim non pu= =F2 possedere i due biglietti da 5 milioni, sar=E0 Egli a possedere i due= biglietti diversi (1 e 5 milioni). = Per il medesimo ragionamento, se Joe mostrasse il biglietto da 5 milioni = (e ne deve possedere anche l'altro), allora sarebbe John ad avere i due b= iglietti diversi, non potendo possedere i due biglietti uguali da 1 milio= ne come dichiara. Dunque basta una domanda a Joe per definire la situazione. From: Lonster Monster X-Personal_name: Lon Kelley I've hit Ctrl-G so many times I'm not gonna bother to fix my email, 'cause I got it this time. you only gotta ask ONE question. Ask Joe. Here's a picture: Joe: 1 and 1 5 and 5 John: 5 and 5 1 and 5 Jim: 1 and 5 1 and 1 Since Joe lied, he either has two 1s or two 5s. If he shows you a 1$, Jim must have it, since Jim claimed to have 5's (which he can't have, since he lied) and we know Joe has the 1's, so Jim must have the envelope with the two different bills. Following the same line of reasoning, if Joe shows you a 5$ bill, John must have the desired envelope, since John cannot have the 1s and we know he does not have the 5s. For the record, I've got a 3x5 notecard with scribbles and at least 5 cancelled comments. Lonster! From: Paul Fahn Organization: Stanford University Answer to the new challenge: Charles should ask Joe to show one bill. This one question will suffice to determine who has the two different bills. If Joe shows a one-dollar bill, then Jim has the different bills; If Joe shows a five-dollar bill, then John has the two different bills. Why? Suppose Joe shows a one-dollar bill. Then Joe must have two one-dollar bills, since he's lying and can't have different bills. Then what does Jim have? He can't have two fives, since he's lying, and he can't have two ones, because Joe has two ones. Thus Jim must have one one-dollar bill and one five-dollar bill. Paul Received: from mta1.nts.uci.edu (mta1.nts.uci.edu [18.104.22.168]) by grits.valdosta.peachnet.edu (8.6.10/8.6.9) with SMTP id QAA12120 for ; Wed, 8 May 1996 16:11:11 -0400 From: Randy Black Was reading your great web page but notice the latest puzzle seems incomplete. Still . . . If we're allowed to *pick* which waiter shows a bill, it seems straightforward: Ask Joe to show one of his bills. Because Joe is lying and says he is the waiter with two different bills, his bills must match. So if Joe shows a dollar, then he has the two dollar bills. Jim cannot have the two fives [he lied] so must have the only remaining possibility: the mixed pair, and that leaves the two fives for John. However, if Joe shows a five, then he must have two fives (his bills must match). John must have a five and a one (because he cannot have the two ones he lied about), leaving Jim with the two ones. Of course, I'm second guessing the instructions. But if you can't pick Joe to show a bill, it doesn't seem real easy. Sender: firstname.lastname@example.org From: Karl Hahn In the words of Humpty Dumpty, "What tremendously easy riddles you ask." One question is all that is necessary. Ask Joe to reveal one bill. If it is a five, then he has both fives, John has the mixed lot, and Jim has the two ones. Likewise, if is a one, then he has both ones, Jim has the mixed lot, and John has the fives. Clearly, if Joe is lying when he says he has the mixed lot, he must have a matched lot. So when he reveals just one bill, you know them both. You know that the other matched lot is with one of the other two guys. You also know which matched lot it is. Since they both lied as well, you know that the one who does say he has that matched lot doesn't, and hence the remaining guy does. Later, Karl From: SPECK@AC.GRIN.EDU All Charles has to do is ask Joe to show one of his bills. Because: We know the following: John said he has 1 1, so he either has 1 5 or 5 5. Jim said he has 5 5, so he either has 1 5 or 1 1. Joe said he has 1 5, so he either has 5 5 or 1 1. So, we ask Joe. If he shows us a 1, then we know the following: Joe has 1 1. Thus, since Jim had 1 5 or 1 1, he must have the 1 5. If Joe shows us a 5-- John has 1 5 or 5 5 Joe must have 5 5. so, John has the 1 5. All that has to be done is to ask Jim one question. Jason Speck email@example.com Sender: firstname.lastname@example.org From: Tom Maciukenas Because all three lied about the contents, Charles knows these facts: John does not have the $1/$1 envelope. Jim does not have the $5/$5 envelope. Joe does not have the $1/$5 envelope. So either John or Jim has the $1/$5 envelope. So, Charles asks John to show a bill. If John shows a $1, Charles knows he has the $1/$5 envelope because John does not have the $1/$1 envelope. If John shows a $5, ask him to show the other bill. If the second bill is a $1, John has the $1/$5 envelope, otherwise Jim has it. That's it, only two questions (at the most). -Tom Maciukenas (email@example.com) From: "E. HURLEY" Organization: University of Leeds Ask each waiter to take out the lowest bill in their envelope if one is larger than the other.