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 [131.144.56.12]) 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 ([131.198.33.233]) 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: rhaney@olivia.cedar-rapids.ia.us
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 scotty@olivia.cedar-rapids.ia.us
rhaney@cacd.rockwell.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: spj1@acpub.duke.edu
From: gumiro@mbox.vol.it
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 [128.200.200.200]) 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: hahnk@ipcsrq010.ipc.com
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
speck@ac.grin.edu
Sender: tomm@amd.com
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 (tom.maciukenas@amd.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.