An interview puzzle
Brian Pickrell
: is this: given a deck of cards from a standard 52 card deck, you draw 5 random
: cards from the deck. On the (green) table in front of you are 4 card shaped
: boxes in a row (like on a gambling table.) You put 4 cards down on the table
: face-up in the boxes; the 5th card you must keep hidden. Your partner walks
: in the room. Your partner must then be able to deduce what the hidden card is
: from only the information presented in the 4 cards you put down in the boxes.
: You aren't allowed to do anything special to the cards beyond what is described
: here. What method can you and your partner agree on that will work? (This
: method must work no matter what 5 cards you draw.)
This is what I came up with after about 5 minutes--proving that I deserve
my important and high-paying job:
<spoiler>
First of all, it won't work to always put 1 of the 4 cards in each of
the boxes. There are only 4! = 24 ways to do this, and 48 possibilities
for the 5th card.
Anyway. First put the cards in order of rank. Aces low, spades are
the high suit, clubs are low. Also, number the boxes 0-3.
To indicate the suit of the fifth card, put the lowest ranking
of the four cards in
one or another box: 0 for a club, 1 for a diamond, 2 for a heart, 3 for a
spade.
To indicate the rank of the fifth card, convert it to a number:
A=1; J=11; Q=12; K=13 Then convert this number to a 2-digit base 4, i.e.
a 3 is "03" and a Q is "30." Take the highest of the 4 cards and put
it into the box indicated by the first digit, and put the second-highest
into the box indicated by the second digit.
Do whatever you want with the fourth card.
Brian Pickrell
Randall Gee
with which you will solve this puzzle. He then leaves the room. The puzzle
is this: given a deck of cards from a standard 52 card deck, you draw 5 random
cards from the deck. On the (green) table in front of you are 4 card shaped
boxes in a row (like on a gambling table.) You put 4 cards down on the table
face-up in the boxes; the 5th card you must keep hidden. Your partner walks
in the room. Your partner must then be able to deduce what the hidden card is
from only the information presented in the 4 cards you put down in the boxes.
You aren't allowed to do anything special to the cards beyond what is described
here. What method can you and your partner agree on that will work? (This
method must work no matter what 5 cards you draw.)
This puzzle was posed to a friend of a friend of mine (I shall call him Joe,
for that is his name) in Yale. At this place he interviewed for a job,
the "hotshot CS major" who interviewed him gave each interviewee a little
brain-teaser, and if the interviewee answered it in a half an hour without
having heard it beforehand, he got the job. (There was no penalty for not
getting it.) He didn't get the puzzle (I don't know if he got the job) so
he asked people in his dorm about it, who didn't get it, and then he E-mailed
it to his friends here in California, who didn't get it. One of them (whom
I shall call Aaron, because that's his name) sent it to me. I did solve it
in the half-hour (and won a cookie.) Because this passed through all these
people, I'm just curious -- how did you do on this puzzle?
-- Randall M! Gee
(rm...@soda.berkeley.edu)
RVES...@vma.cc.nd.edu
the table, in four card boxes marked on the felt, and from those four, your
friend has to deduce what the fifth card is.
a bunch of blank lines, then a solution...
first, note that there is necessarily a suit which is that of at least
two of the five cards. so the card in the first box tells your partner
the suit of the hidden card.
first card is a implies hidden card is one of
--------------- -----------------------------
2 3,4,5,6,7,8
3 4,5,6,7,8,9
4 5,6,7,8,9,T
5 6,7,8,9,T,J
6 7,8,9,T,J,Q
7 8,9,T,J,Q,K
8 9,T,J,Q,K,A
9 2,T,J,Q,K,A
T 2,3,J,Q,K,A
J 2,3,4,Q,K,A
Q 2,3,4,5,K,A
K 2,3,4,5,6,A
A 2,3,4,5,6,7
it is trivial to check that no matter what the two cards (the first and the
hidden) are, you can choose which is first and which is hidden in one and
only one way according to this scheme.
now define an ordering on the cards, say clubs are lower than diamonds are
lower than hearts are lower than spades, and within the same suit, two is
the lowest, three next, and so on up to ace high.
now, given this ordering, look at the cards in the second, third and fourth
boxes. if they are ordered low, medium, high, then the hidden card is the
first of the six possibilities; low, high, medium -> second; medium, low,
high -> third; medium, high, low -> fourth; high, low, medium -> fifth;
high, medium, low -> sixth.
an example, using cards that i've just drawn:
i've drawn the six of clubs, seven of hearts, queen of spades, jack of
diamonds, and the ten of clubs. there are two spades, so these will be
the first and hidden cards. now to decide which is first and which is
hidden, we look at the entries on the table for six and queen:
6 -> 7,8,9,T,J,Q
Q -> 2,3,4,5,K,A
so 6 -> Q, and Q -/-> 6. therefore, the first card will be the six, and
the hidden card will be the queen. now "queen" is the sixth card on the
list for six, so the remaining three cards must be ordered high, medium,
low, which would be seven of hearts, jack of diamonds, ten of clubs.
so i put the cards down in that order. my partner comes in, sees that the
card in the first box is a spade, and deduces that the hidden card is
therefore a spade. he also sees that the first card is a six, and deduces
that the hidden card is either a seven, eight, nine, ten, jack or queen.
then he looks at the other three cards. the second box has a heart,
the third a diamond, and the fourth a club, so the order is high,
medium, low. this tells him that the hidden card is the sixth of the
six possibilities, and is therefore a queen.
my partner says "queen of spades", and we win a round of beers on the
poor schlep sitting next to us.
this was a fun puzzle. thanks for posting it.
anyone have any other (non-isomorphic) solutions?
bob vesterman.
RVES...@vma.cc.nd.edu
says:
>
>First of all, it won't work to always put 1 of the 4 cards in each of
>the boxes. There are only 4! = 24 ways to do this, and 48 possibilities
>for the 5th card.
note that here you assume that you must put one and only one card in each
of the four boxes. though the problem doesn't state that this is true,
i think it is a good assumption, and implicit in the problem; otherwise,
the problem is trivial. given this assumption, your solution doesn't
work.
>Anyway. First put the cards in order of rank. Aces low, spades are
>the high suit, clubs are low. Also, number the boxes 0-3.
>
>To indicate the suit of the fifth card, put the lowest ranking
>of the four cards in
>one or another box: 0 for a club, 1 for a diamond, 2 for a heart, 3 for a
>spade.
>
>To indicate the rank of the fifth card, convert it to a number:
>A=1; J=11; Q=12; K=13 Then convert this number to a 2-digit base 4, i.e.
>a 3 is "03" and a Q is "30." Take the highest of the 4 cards and put
>it into the box indicated by the first digit, and put the second-highest
>into the box indicated by the second digit.
here's the problem, where you ignore the assumption. what does one do if
the hidden card is a five? in this case, one must put both the highest
card and the second-highest card in box one.
bob vesterman.
David Karr
You can always arrange the cards so that one box has a card of the
same suit as the hidden card, and from 1 to 6 ranks below it (in
modulo-13 arithmetic, where the "2" is 3 ranks above the queen).
Then use one of the six possible arrangements of the other three
cards to indicate exactly how much higher the hidden card is.
>In article <pickrellC...@netcom.com>, pick...@netcom.com (Brian Pickrell)
>says:
>>
>>First of all, it won't work to always put 1 of the 4 cards in each of
>>the boxes. There are only 4! = 24 ways to do this, and 48 possibilities
>>for the 5th card.
This turns out to be a key point in a very similar-sounding puzzle in
the book The Unexpected Hanging, by Martin Gardner. But that puzzle
turns out to have a completely different solution.
In article <94114.1422...@vma.cc.nd.edu> <RVES...@vma.cc.nd.edu> writes:
>note that here you assume that you must put one and only one card in each
>of the four boxes. though the problem doesn't state that this is true,
>i think it is a good assumption, and implicit in the problem; otherwise,
>the problem is trivial.
Well, not *entirely* trivial. If you assume you can put multiple cards in
one box and your confederate can still see all of them, then yes, you can
encode any 4-digit base 4 number, which is a lot more than you need.
That's why Brian Pickerell ended up not even using the fourth card.
My initial reading of the problem was that you could put two cards in
one box, but then your confederate could see only the topmost one.
That cuts down considerably on the number of distinct encodings.
ObPuzzle: How many distinct encodings can you form under this last
set of assumptions?
-- David A. Karr (ka...@cs.cornell.edu)
RVES...@vma.cc.nd.edu
you can code a lot more than just four digit base four numbers this way.
if the two of diamonds and the three of diamonds are in the same box, and
your partner can see both, there is a difference between the two on top
and the three on top.
and yes, *entirely* trivial, even if you assume the person can only see
the top card.
if you define an ordering on the cards, there are twenty-four ways that
four can be arranged in four distinct boxes. there are six ways that
three can be arranged in three, and you can multiply this by four since
you can choose any one of the four boxes to be empty. there are two ways
to arrange two in two; multiply by six since you can choose any two of
the four boxes to be empty. there is one way to arrange one in one;
multiply by four since you can choose any three of the four to be empty.
so the obvious trivial attempt at a solution gives you one, as said
attempt can code up to 64 cards. there are only 52 cards.
and that's if the partner can not only not see the bottom cards, but also
if he can't even tell that they are there. if he can tell that there
are, say, two cards in the third pile, but only what the top card is, even
more than 64 could be trivially coded.
the only way that the problem is non-trivial is if you must put one and
only one card in each box.
>My initial reading of the problem was that you could put two cards in
>one box, but then your confederate could see only the topmost one.
>That cuts down considerably on the number of distinct encodings.
not enough to make the problem non-trivial.
bob vesterman.
jrw
Just a thought. A simpler way to state the puzzle. Deal five cards from a
deck. Rearrange them and replace them on the deck such that after the first
four cards are dealt face up you will know the identity of the fifth card.
Risto Lankinen
>In <94113.2217...@vma.cc.nd.edu> <RVES...@vma.cc.nd.edu> writes:
>] [paraphrasing rm...@soda.berkeley.edu (Randall Gee)
>] in <2pcflh$b...@agate.berkeley.edu>]
>]
>]> you're given five cards from a deck. you can put four of them face up on
>]> the table, in four card boxes marked on the felt, and from those four, your
>]> friend has to deduce what the fifth card is.
>Now consider the general case: M-card deck, choosing (K+1) cards.
>(The above problem is (M,K) = (52,4).)
>
>For given K, what is the largest M for which a solution exists?
> K max_M
> --- -----
> 2 8
> 3 27
> 4 124
>A colleague of mine constructed such a mapping for the (27,3) case and
>conjectures that his procedure will work for the (124,4) and higher cases
>as well. Can the reader find such a mapping?
Hi!
How about this:
The first player gets his K+1 cards, and imagines that their values define
positions of gas stations along a circular track of max_M units. Each gas
station is capable of selling gas for a ride of (max_M+1)/(K+1) , or K!+1
units of length. The track will be travelled in one direction only, and
whenever a vehicle passes a gas station, it always refuels. A journey is
started with an initial fuelling on any gas station.
Next, the first player iterates thru all of the stations, thinking: "If I
removed this station, will this place be reachable with the gas provided by
the other stations only". There will be a station, that cannot be reached
with non-empty tank, no matter where the journey started.
He then removes that station and, starting from location 0, enumerates all
positions of the track, that cannot then be reached. There will be K! units
total, one of which is the location of the removed station, which he encodes
with the arrangement of the K cards.
The guesser similarly thinks of the cards as gas stations and goes thru the
same mental exercise of finding the unreachable parts of the track. He then
uses the information provided by the arrangement of the cards to decide which
of the unreachable parts of the track should've had the gas station, ie. the
hidden card.
This easily generalizes to games of M<max_M , because any such game could be
played with a deck of max_M cards with cards (M+1)...max_M simply ignored.
Thus, this also solves the original problem (although not in half an hour,
and with the help of Mr. James Allen ;-)
terv: Risto L.
--
Risto Lankinen / ris...@xerver.icl.fi - ICL Personal Systems Oy, Finland.
"Rock'n'Roll on laakkeenomainen tuote, jonka tehoa ei ole osoitettu laak-
keilta vaadittavalla tavalla." -- Radio City 96.2 FM, Helsinki, Finland.
David Karr
>My initial reading of the problem was that you could put two cards in
>one box, but then your confederate could see only the topmost one.
>That cuts down considerably on the number of distinct encodings.
>
>ObPuzzle: How many distinct encodings can you form under this last
>set of assumptions?
Bob Vesterman immediately shot back the answer, 64, and he and someone
else complained my interpretation makes the puzzle too easy. Which of
course it does.
So instead, I offer the following puzzles:
Puzzle 1 (still quite easy):
Suppose you have a large number of ordered cards and can put them in n
boxes. You are allowed to put multiple cards per box but then only
one will be visible at all (it will be impossible to tell where the
covered cards are). How many different values can you encode?
(We already know the answer is 64 for n=4.)
Puzzle 2 (not too hard, I hope):
As in the "interview puzzle," your confederate has to guess the suit
and rank of a hidden card using only the information gathered by
looking at the cards you placed in four boxes. And as before, you can
place only one card per box. But this time you start out with only
four cards arbitrarily selected for you, not five; you must choose one
to hide, and so must leave one and only one box empty. How do you
communicate the hidden card's value?
PDP11 Hacker .....
OK, I'm going to make a fool of myself, but can you please tell me what I am
missing :
I'm going to assume :
a) The deck consitsts of 52 all-different cards, with the conventional names.
b) The first 5 cards are selected at random from the deck.
Without that, the problem becomes trivial - if the 5th card is not selected
at random, then we always pick the same 5th card, say the King of Diamonds,
and the first 4 cards tell us nothing
If the first 4 cards are not selected at random, we can ensure that say the
first card matches in value, and the second in suit, or something like that.
Again, the puzzle is trivial
So, with those assumptions...
As far as I can see, we can assign an ordering to the cards in the deck,
something like :
AC<...<KC<AH<...<KH<AS<...<KS<AD<...<KD
When we have turned over the top 4 cards, we can assign each one a rank from 1
to 4, 4 to the highest, 1 to the lowest, according to our ordering. The cards
can be of any values, so I fail to see what other information you can get from
them.
Now, there are 4! = 24 orderings of 4 objects, and therefore the order of the
first 4 cards can send 24 different 'messages'
However, the 5th card is one of the remaining 48 cards in the deck. Therefore
we need to send a final yes/no signal.
What am I missing here?
-tony
Bristol University takes no responsibility for the views expressed in this
posting. They are the personal views of the user concerned.
Dr D F Holt
a...@siva.bris.ac.uk (PDP11 Hacker .....) writes:
>In article <wyatt.87...@chem.nrl.navy.mil>, wy...@chem.nrl.navy.mil (jrw) writes...
>>GREAT PUZZLE
>>
>>Just a thought. A simpler way to state the puzzle. Deal five cards from a
>>deck. Rearrange them and replace them on the deck such that after the first
>>four cards are dealt face up you will know the identity of the fifth card.
>
>OK, I'm going to make a fool of myself, but can you please tell me what I am
>missing :
>
>I'm going to assume :
>a) The deck consitsts of 52 all-different cards, with the conventional names.
>b) The first 5 cards are selected at random from the deck.
>
>As far as I can see, we can assign an ordering to the cards in the deck,
>something like :
>AC<...<KC<AH<...<KH<AS<...<KS<AD<...<KD
>
>When we have turned over the top 4 cards, we can assign each one a rank from 1
>to 4, 4 to the highest, 1 to the lowest, according to our ordering. The cards
>can be of any values, so I fail to see what other information you can get from
>them.
>
>Now, there are 4! = 24 orderings of 4 objects, and therefore the order of the
>first 4 cards can send 24 different 'messages'
>
>However, the 5th card is one of the remaining 48 cards in the deck. Therefore
>we need to send a final yes/no signal.
>
>What am I missing here?
>
>-tony
>
You are missing the fact that you can choose which of the five cards is to
be the 5th card which has to be guessed. So you have 120 choices in all.
This puzzle does have a solution.
Derek Holt.
Ren Maddox
[snip]
>Puzzle 1 (still quite easy):
>Suppose you have a large number of ordered cards and can put them in n
>boxes. You are allowed to put multiple cards per box but then only
>one will be visible at all (it will be impossible to tell where the
>covered cards are). How many different values can you encode?
>(We already know the answer is 64 for n=4.)
too lazy to formulate (but given solution below, 64 is probably too
low for n=4)
>Puzzle 2 (not too hard, I hope):
>As in the "interview puzzle," your confederate has to guess the suit
>and rank of a hidden card using only the information gathered by
>looking at the cards you placed in four boxes. And as before, you can
>place only one card per box. But this time you start out with only
>four cards arbitrarily selected for you, not five; you must choose one
>to hide, and so must leave one and only one box empty. How do you
>communicate the hidden card's value?
Given 3 cards and 4 boxes, we can trivally encode 3!*4 = 24 values.
Add to this the option of placing 1 or more of the cards face down and
we get:
0 face down: 3!*4 = 24 (above)
1 face down: 3!*4 = 24
2 face down: 3*4 = 12
3 face down: 4
----------------------
total: 64 more than enough to encode the 52 possible cards
Ren
--
----------------------------------------------------------------------
Nothing I say really means anything anyway.... Ren Maddox
Email address ---------------------------------------> lhma...@bnr.ca
James Allen
] [paraphrasing rm...@soda.berkeley.edu (Randall Gee)
] in <2pcflh$b...@agate.berkeley.edu>]
]
]> the table, in four card boxes marked on the felt, and from those four, your
]> friend has to deduce what the fifth card is.
Nice puzzle!
]first, note that there is necessarily a suit which is that of at least
]two of the five cards. so the card in the first box tells your partner
]the suit of the hidden card. [rest of solution omitted]
]
]bob vesterman.
Nice solution! Note that 52 is the largest deck-size for which this
particular approach (first card shows which quarter-deck) will work.
Now consider the general case: M-card deck, choosing (K+1) cards.
(The above problem is (M,K) = (52,4).)
For given K, what is the largest M for which a solution exists?
Any strategy can be described as a mapping from the (K+1)-sized
unordered "drawings" (of which there are C(M,K+1) ) to the K-sized
ordered "exposures" (of which there are K! * C(M,K) ).
This immediately gives an upper bound on M:
C(M, K+1) <= K! * C(M, K)
or
M <= K + (K+1)!
or
K max_M
--- -----
2 8
3 27
4 124
The rules also require that the K-sized "drawing" maps to one of its subsets.
To achieve the upper bound it is necessary and sufficient that there be
such a mapping.
For example, the (8,2) problem can be solved with a mapping like:
(0,1,2) --> (0,1)
(0,1,3) --> (1,0)
(0,1,4) --> (0,4)
(0,1,5) --> (0,5)
(0,1,6) --> (0,6)
(0,1,7) --> (0,7)
(0,2,3) --> (0,2)
(0,2,4) --> (2,0)
(0,2,5) --> (5,0)
(0,2,6) --> (6,0)
(0,2,7) --> (7,0)
. . .
in which each of the possible unordered triplets from {0,1,2,3,4,5,6,7}
appears on the left, and the right contains distinct ordered pairs, with
each pair a subset of the corresponding triplet. If no shortcut mnemonic
can be found the players can simply use the above table for their strategy.
A colleague of mine constructed such a mapping for the (27,3) case and
conjectures that his procedure will work for the (124,4) and higher cases
as well. Can the reader find such a mapping? Is this related to a
known combinatorial result?
James D. Allen -- ja...@crc.ricoh.com
David Karr
>In article <1994Apr25....@cs.cornell.edu>,
>David Karr <ka...@cs.cornell.edu> wrote:
>>In article <1994Apr25.0...@cs.cornell.edu> I wrote:
>
>[snip]
>
>>Puzzle 1 (still quite easy):
>>Suppose you have a large number of ordered cards and can put them in n
>
>>Puzzle 2 (not too hard, I hope):
>>As in the "interview puzzle," your confederate has to guess the suit
>
>Given 3 cards and 4 boxes, we can trivally encode 3!*4 = 24 values.
>
>Add to this the option of placing 1 or more of the cards face down and
>we get:
Unfortunately I forgot to save the original posting of the "interview
puzzle," but it specified that the cards should be placed face up.
The same rule applies to both the puzzles I gave. You are not allowed
to put any cards face down. This should make the second puzzle a bit
more interesting, and provides for a quite compact result for the
first problem.
PDP11 Hacker .....
>You are missing the fact that you can choose which of the five cards is to
>be the 5th card which has to be guessed. So you have 120 choices in all.
>This puzzle does have a solution.
Yes, OK, I was being a bit silly, and in fact thinking about a different
puzzle. Still, it's an interesting (?) coincidence that the number fo
arrangements of the 4 cards is exactly half of what you need to indentify one
of the remaining 48 cards, so one final binary signal will do.
I therefore propose the following pseudo-puzzle :
a) Someone picks a card at random (not faked, forced, or anything like that).
b) Remove that card from a standard deck
c) Shuffle the remaining 51 cards, and deal off the top 4
d) Arrange them to encode which out of 24 pairs contains the card picked in
(a).
e) Now for the puzzle. Find a method of communicating the last binary signal
to the guesser. One obvious one is to hand him (assuming that's how he gets the
cards - this is my puzzle, after all) the cards face up or face down. I wonder
how many more subtle ones you can find.
>
>Derek Holt.
David Karr
>The first player gets his K+1 cards, and imagines that their values define
>positions of gas stations along a circular track of max_M units. Each gas
>station is capable of selling gas for a ride of (max_M+1)/(K+1) , or K!+1
I like this approach, but it runs into a bit of trouble right here:
>He then removes that station and, starting from location 0, enumerates all
>positions of the track, that cannot then be reached. There will be K! units
>total, one of which is the location of the removed station, [...]
Let K = 4. Then max_M = 124. Suppose the five cards were numbered
1,2,3,63,64. From station 3 you can get to 3 + 25 = 28 and from 64
you can get to 64 + 25 = 89. The first player must remove either the
1 or the 63, leaving 70 > 4! stations unreachable. That's too many to
distinguish with just 4 cards.
Maybe there's a way to add extra rules so the guesser can still
backtrack and determine that, say, the 1 was removed rather than the
62, but I quickly get lost in special cases when trying this.
Courtenay Footman
>you're given five cards from a deck. you can put four of them face up on
>the table, in four card boxes marked on the felt, and from those four, your
>friend has to deduce what the fifth card is.
>
>a bunch of blank lines, then a solution...
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>anyone have any other (non-isomorphic) solutions?
>
>bob vesterman.
>
there is one other way one can pass information: In a standard deck,
the Aces, threes, fives, sixes, sevens, nines, of spades, hearts and clubs
are asymmetric; one can put one so that the majority of the pips are
facing away from you or towards you. If one has one of these cards,
playing this card gives you twice as much information, and one
can use a simpler scheme than bobs. If one does not have any of the
21 cards listed, then that fact alone will be obvious from the fact
that you do not use one, and again one can use a scheme like Bob's
but with only 31 cards involved.
--
-------------------------------------------------------------------------------
Courtenay Footman I finally got back on the net.
c...@alchemy.ithaca.ny.us Now I will never get anything done
Courtenay Footman
>the table, in four card boxes marked on the felt, and from those four, your
>friend has to deduce what the fifth card is.
>
>a bunch of blank lines, then a solution...
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
cards; obviously there are only 18. It still helps.
Stein Kulseth
[Upper bounds for the size of a deck in the general case of using K
cards to code hidden K+1th card] :
|> --- -----
|> 2 8
|> 3 27
|> 4 124
|>
|> The rules also require that the K-sized "drawing" maps to one of its subsets.
|> To achieve the upper bound it is necessary and sufficient that there be
|> such a mapping.
|> A colleague of mine constructed such a mapping for the (27,3) case and
|> conjectures that his procedure will work for the (124,4) and higher cases
|> as well. Can the reader find such a mapping?
I don't think this has been answered yet, so here goes:
Deck size max_M = K + (K+1)!
After drawing K+1 cards, add their values modulo K+1. Hide the indicated card
(0 means lowest card .. K-1 means highest). Seeing the remaining cards,
one can see that only every K+1th of the (K+1)! undisclosed cards (including
the now hidden card) may have been the hidden card, that is we have
a target set of (K+1)!/(K+1) = K! possible hidden cards. Code these by
the K! possible codings of the K visible cards.
Concluding note and hint to a variant:
Didn't I say only yesterday that a deck of more than 30 was possible
using 3 cards in 3 boxes to code 4th card?
Yes, I did, but that was using a standard deck, not a general case ...
--
stein....@tf.tele.no [X.400] stein....@nta.no [internet]
'When murders are committed by mathematics, they can be solved by
mathematics. Most of them aren't, and this one wasn't'
- Nick Charles (Dashiell Hammett's "The Thin Man")
Pertsel Vladimir
In article <1994Apr25.0...@cs.cornell.edu>, ka...@cs.cornell.edu (David Karr) writes:
|> You can always arrange the cards so that one box has a card of the
|> same suit as the hidden card
|> In article <pickrellC...@netcom.com>, pick...@netcom.com (Brian Pickrell) says:
|> There are only 4! = 24 ways to do this, and 48 possibilities
|> for the 5th card.
....But You choose the 5-th card YOURSELF from the 5 drawn ones, so there is
no necessity to encode 48 cards!
|> In article <94114.1422...@vma.cc.nd.edu> <RVES...@vma.cc.nd.edu> writes:
|> >note that here you assume that you must put one and only one card in each
|> >of the four boxes. though the problem doesn't state that this is true,
|> >i think it is a good assumption, and implicit in the problem; otherwise,
|> >the problem is trivial.
|>
|> Well, not *entirely* trivial. If you assume you can put multiple cards in
|> one box and your confederate can still see all of them, then yes, you can
|> encode any 4-digit base 4 number, which is a lot more than you need.
|> That's why Brian Pickerell ended up not even using the fourth card.
|>
|> My initial reading of the problem was that you could put two cards in
|> one box, but then your confederate could see only the topmost one.
|> That cuts down considerably on the number of distinct encodings.
.....Four cards in four boxes give us 24 cards, Three cards and one
.....free plase -- 24 in addition, Two cards and two free places -- 12 more --
ENOUGH!
--
____/|
\ o.O| Vladimir A. Pertsel
=(_)= E-mail: vold...@wisdom.weizmann.ac.il
U Disclaimer: This posting represents the poster's views only.
David Karr
>Hi!
>
>ka...@cs.cornell.edu (David Karr) writes:
>>Let K = 4. Then max_M = 124. Suppose the five cards were numbered
>>1,2,3,63,64. From station 3 you can get to 3 + 25 = 28 and from 64
>>you can get to 64 + 25 = 89. The first player must remove either the
>>1 or the 63, leaving 70 > 4! stations unreachable. That's too many to
>>distinguish with just 4 cards.
>
>'3'. I never said that your tank will hold just 25 units; I said that each
>station only vends 25 units at a time, [...]
Never mind. I think I must have gotten this method confused with the
"Desert Fox" puzzle, where the limit *is* the capacity of the vehicle.
Indeed in Risto Lankinen's formulation, it's obvious that each station
contributes K!+1 units of fuel that must each be spent in a place
distinct from every other unit of fuel. So yes, with just one station
removed there will be just exactly K! places where fuel doesn't get
spent---these are the "unreachable" locations.
So I'm convinced now, though I'd like to have a similarly simple proof
that there's always at least one station unreachable from the others
(I believe it, I just haven't come upon an argument that makes it
sufficiently obvious.)
James Allen
ris...@xerver.icl.fi (Risto Lankinen) writes:
]>] [paraphrasing rm...@soda.berkeley.edu (Randall Gee)
]>] in <2pcflh$b...@agate.berkeley.edu>]
]>]
]>]> you're given five cards from a deck. you can put four of them face up on
]>]> the table, in four card boxes marked on the felt, and from those four, your
]>]> friend has to deduce what the fifth card is.
]>Now consider the general case: M-card deck, choosing (K+1) cards.
]>(The above problem is (M,K) = (52,4).)
]>
]>For given K, what is the largest M for which a solution exists?
]> --- -----
]> 4 124
]
]>A colleague of mine constructed such a mapping for the (27,3) case and
]>conjectures that his procedure will work for the (124,4) and higher cases
]>as well. Can the reader find such a mapping?
]
]Hi!
]
]How about this:
]
]The first player gets his K+1 cards, and imagines that their values define
]positions of gas stations along a circular track of max_M units. Each gas
]station is capable of selling gas for a ride of (max_M+1)/(K+1) , or K!+1
]units of length. The track will be travelled in one direction only, and
]whenever a vehicle passes a gas station, it always refuels. A journey is
]started with an initial fuelling on any gas station.
]
]Next, the first player iterates thru all of the stations, thinking: "If I
]removed this station, will this place be reachable with the gas provided by
]the other stations only". There will be a station, that cannot be reached
]with non-empty tank, no matter where the journey started.
]
]He then removes that station and, starting from location 0, enumerates all
]positions of the track, that cannot then be reached. There will be K! units
]total, one of which is the location of the removed station, which he encodes
]with the arrangement of the K cards.
]
]The guesser similarly thinks of the cards as gas stations and goes thru the
]same mental exercise of finding the unreachable parts of the track. He then
]uses the information provided by the arrangement of the cards to decide which
]of the unreachable parts of the track should've had the gas station, ie. the
]hidden card.
In <1994Apr26....@cs.cornell.edu>
ka...@cs.cornell.edu (David Karr) writes:
>Let K = 4. Then max_M = 124. Suppose the five cards were numbered
>1,2,3,63,64. From station 3 you can get to 3 + 25 = 28 and from 64
>you can get to 64 + 25 = 89. The first player must remove either the
>1 or the 63, leaving 70 > 4! stations unreachable. That's too many to
>distinguish with just 4 cards.
As I interpret Risto's method, from station 3 you can only get to
3 + 25 - 1 = 27 but from station 1 you can get to 1 + 25*3 - 1 = 75 and
he's looking for a station unreachable from *any* of the other stations.
Here that is station 1. From (2,3,63,64) you can get to
2 + 25*2 -1 = 51 or 63 + 25*2 - 1 = 112 so the unreachable points are now
( 0, 1, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61,
62,113,114,115,116,117,118,119,120,121,122,123)
Exactly 24 unreachable points!
I had to read Risto's posting more than once to understand it and
convince myself it would work. :-)
In an effort to be helpful I will try to flesh out parts of the proof.
Let's rephrase Risto's model to have K gas stations, each issuing (R+1) units
of petrol with a track of length
M = KR + K + R
For Theorems 1 and 2, we assume the track has this length. (We don't need
the relation R = K! )
Theorem 1: There are exactly R points unreachable from any of the K stations.
Proof: Easy for K=1; assume for K-1; proceed by induction.
Somewhere there will be one station followed by R empty points.
These R+1 points have no effect on the rest of the track (the station
provides just enough petrol for the R+1 points). Removing them
will leave a K' = K-1, M' = K'R + K' + R configuration which has
exactly R unreachable points by the inductive hypothesis. Q.E.D.
This theorem shows that the required mapping exists; we must now show it
is one-to-one. Since
C(KR+K+R, K) * R = C(KR+K+R, K+1)
the pigeonhole principle will then mean it is also onto.
Risto asks that we select (and remove) the gas station that is unreachable
from any other gas station. If we can establish that there is at most one
such station, there will be exactly one by the pigeonhole principle.
Theorem 2: At most one station is unreachable from all the other stations.
Proof: Let the distances between consecutive stations be z,y,...,c,b,a.
Wlog let the first station be unreachable; this implies
y+ ... +c+b+a >= KR + K
. . .
c+b+a >= 3R + 3
b+a >= 2R + 2
a >= R + 1
Since z+y+...+c+b+a = M + KR + K + R, these can be rewritten as
z < R + 1
y+z < 2R + 2
. . .
b+c+...+y+z < KR + K
These inequalities show that all the other stations can be reached
from the unreachable station. Q.E.D.
This is *not* the solution conjectured by my colleague. I'll post that
later if the puzzle continues to attract attention.
]terv: Risto L.
]--
]Risto Lankinen / ris...@xerver.icl.fi - ICL Personal Systems Oy, Finland.
James D. Allen -- ja...@crc.ricoh.com
]"Rock'n'Roll on laakkeenomainen tuote, jonka tehoa ei ole osoitettu laak-
] keilta vaadittavalla tavalla." -- Radio City 96.2 FM, Helsinki, Finland.
If this was the Obligatory Puzzle, I didn't get it....
Risto Lankinen
ka...@cs.cornell.edu (David Karr) writes:
>In article <2pj5i7$8...@louhi.to.icl.fi> ris...@xerver.icl.fi (Risto Lankinen)
>writes:
>>The first player gets his K+1 cards, and imagines that their values define
>>positions of gas stations along a circular track of max_M units. Each gas
>>station is capable of selling gas for a ride of (max_M+1)/(K+1) , or K!+1
>>units of length. [...]
>>He then removes that station and, starting from location 0, enumerates all
>>positions of the track, that cannot then be reached. There will be K! units
>>total, one of which is the location of the removed station, [...]
>Let K = 4. Then max_M = 124. Suppose the five cards were numbered
>1,2,3,63,64. From station 3 you can get to 3 + 25 = 28 and from 64
>you can get to 64 + 25 = 89. The first player must remove either the
>1 or the 63, leaving 70 > 4! stations unreachable. That's too many to
>distinguish with just 4 cards.
Not at all! To get past '28' you fill up at '2', then refuel when you pass
'3'. I never said that your tank will hold just 25 units; I said that each
station only vends 25 units at a time, and there's a big difference. Think
about it.
In your example, card '1' cannot be reached with the fuel provided by '63'
and '64' (these combined will only take you to 113 or so). On the other
hand, you can't arrive '63' with the gas of '2' and '3', much less have any
extra gas in the tank to be able to go from 113 to 1 (=125) . Therefore,
'1' is the card to hide, and, assuming '0'-based deck, it is the second
card that *cannot* be reached, so you'll encode it with the second possible
arrangement of 4 cards, or (in this order) 2,3,64,63 .
Why '63' was not be removed? Well, fill up in '1' to find out that it can
be easily reached with the gas of '1','2' and '3'.
>Maybe there's a way to add extra rules so the guesser can still
>backtrack and determine that, say, the 1 was removed rather than the
>62, but I quickly get lost in special cases when trying this.
There is no need to add any extra rules for any special cases.
The guesser could think: There is total 25*4 units of potential energy
stored in the cards, which will leave 24 cards of the deck of 124 out of
reach. Which one of the 24, is encoded in the order of the visible cards.
Try to analyze the guesser's strategy well, and the constructor's strategy
will become evident.
Stein Kulseth
|> Puzzle 2 (not too hard, I hope):
|> in four boxes]
Call suits 1 2 3 4, fi. by going by bridge hierarchy, (and circularily).
Then four cards have one of the following possible suit distributions,
not counting rotations around the suit hierarchy:
1234, 1123, 1124, 1134, 1122, 1133, 1112, 1113, 1114, 1111
(note: 1144 equals 1122)
We also have five different three card distributions that might be used in
coding,
123, 112, 113, 114, 111
Not all 4-card distributions cannot be coded by all 3-card distributions
(obviously), some may have a choice, others must use a specified one.
Each of the 3-card distributions have 24 codings (4 possible empty boxes
times 6 possible orderings).
In general we need 13 different codings to specify the value of the
hidden card, but whenever there is a card in the 3-card set of the
same suit as the hidden card, we only need 6 codings to specify the
value as the highest same-suited card in the 3-card set + 1..6 (mod 13)
... this was explained by Bob Vesterman earlier.
Thus, a matrix showing the needed no of codings of a 4-card set, using
the given 3-card set:
123 112 113 114 111
1234 13* x x x x
1123 6* 13 13 x x
1124 6 13* x 13 x
1134 6 x 13* 13 x
1122 x 6 x 6* x
1133 x x 6* x x
1112 x 6* x x 13
1113 x x 6 x 13*
1114 x x x 6* 13
1111 x x x x 6*
One solution is to use the starmarked entries and set up a coding
scheme allocating a given target card to each coding (leaving
some left over). A 'best' coding scheme would involve finding
'the most intuitive' coding.
Yet a variant,
You shall draw four random cards from a reduced standard deck,
and communicate a hidden card of your choice, by placing the
other three face up in three boxes. How many cards could
the deck maximally contain?
More than 30 is possible...
DENNIS M. CROCKER
binary code to represent all thirteen cards in a suit. E.G.
0010 = 2 1011 = 11 or Jack
0011 = 3 1100 = 12 or Queen
0100 = 4 1101 = 13 or King
0101 = 5 1110 = 14 or Ace
0110 = 6
0111 = 7
1000 = 8
1001 = 9
1010 = 10
Then just put a card in each box corresponding to the 1 and leave the
box empty that holds a 0. Put the fifth card in front of the box that
corresponds to the suit of the card: Spades, Hearts, Diamonds, Clubs.
Your friend simply "reads" the binary, and observes where the card is.
Dennis Crocker
Joe Keane
extra bit, say whether a disk is white or black. Is there a way to always do
this? If not, what percentage of the time can you get it right?
--
Joe Keane, amateur mathematician
j...@netcom.com
Bram Cohen
PDP11 Hacker ..... <a...@siva.bris.ac.uk> wrote:
>e) Now for the puzzle. Find a method of communicating the last binary signal
>to the guesser. One obvious one is to hand him (assuming that's how he gets
>the cards - this is my puzzle, after all) the cards face up or face down. I
>wonder how many more subtle ones you can find.
Hand him the cards with your left or right hand.
--
___ ___ / \____ ############################
/ \_/ \ \_ __ \ # Bram Cohen #
/ \_/ / \/ # bco...@acsu.buffalo.edu #
/\ ___/ # Just trying to be myself #
DENNIS M. CROCKER
> is hidden" doesn't mean that the card is face down. Ok, no
> problem. Put the 5th card in a locked box. Use the left most
> box, that has a card in it, to indicate to your friend the suit
> of the card. Then use the following binary scheme to represent
> the rest of the card.
>
> 0010 = 2 1011 = 11 or Jack
> 0011 = 3 1100 = 12 or Queen
> 0100 = 4 1101 = 13 or King
> 0101 = 5 1110 = 14 or Ace
> 0110 = 6
> 0111 = 7
> 1000 = 8
> 1001 = 9
> 1010 = 10
Does the original puzzle say I cannot put all four cards in one box?
Is not the puzzle solved?
Dennis Crocker
Robert Orenstein
> ...then he looks at the other three cards. the second box has a heart,
> the third a diamond, and the fourth a club, so the order is high,
> medium, low. this tells him that the hidden card is the sixth of the
> six possibilities, and is therefore a queen.
Bob, your solution makes a nifty program. I've already implemented
it in HyperCard and have amazed a few people with it... they pick the cards,
I choose the hidden card and impose your suggested order on the cards,
then they type the four remaining cards into the program and are told
by the program what the hidden card is.
So far, the first try baffles everyone, but by the second try they figure
out at least the part about the suit being in position 1. I'm going to change
it so that the suit cycles through positions 1,2,3,4, or perhaps put a
cleverly disguised indicator in the screen that lets my program choose
the next position the suit is expected in.
This is the best puzzle I've seen in a long time! Thanks for posting
it, Randall.
Robert Orenstein
RVES...@vma.cc.nd.edu
again, the problem is entirely trivial unless you assume that you must
put one and only one card in each box. otherwise, no thought is required
to solve it.
bob vesterman.
Mark Brader
of information which could be used in the agreed code. In a "standard
52 card deck", 16 of the cards are have asymmetrical designs of pips --
namely, the 7 of diamonds and the A3579 of the other three suits.
The code could contain the feature that if all four exposed cards are
symmetrical ones, then the concealed card is also a symmetrical one,
and therefore must be identified from only 32 possibilities rather
than 48; if one or more exposed cards is/are asymmetrical, then the
orientation is made significant and helps identify the concealed card
from the 48 possibilities.
This thought suggests various extended forms of the problem using larger
decks, where (a) more of the cards are asymmetrical, or (b) the back
design is asymmetrical and the decoding player is allowed to peek at
the backs to see the orientation of every card, or (c) the coding player
is allowed to place the cards face up or down and the decoding player
can turn them over after observing the orientation. In the last case
the backs could be symmetrical or not.
--
Mark Brader | ...the scariest words of the afternoon:
m...@sq.com | "Hey, don't worry, I've read all about
SoftQuad Inc., Toronto | doing this sort of thing!" -- Vernor Vinge
This article is in the public domain.
Mark Brader
> While it isn't needed to solve this problem, there is a further piece
> of information which could be used in the agreed code. In a "standard
> 52 card deck", 16 of the cards are have asymmetrical designs of pips --
> namely, the 7 of diamonds and the A3579 of the other three suits.
That should, of course, be 22 asymmetrical cards: the 7 of diamonds and
the A356789 of the other three suits. I should know better than to post
from a place where I don't have a deck of cards at hand to check.
My other comments stand, with the appropriate numerical changes.
--
Mark Brader, m...@sq.com | "I'm not going to post a revision: even USENET
SoftQuad Inc., Toronto | readers can divide by 100." -- Brian Reid
DENNIS M. CROCKER
> In article <1994Apr29....@news.unomaha.edu>, dcro...@cwis.unomaha.edu
> (DENNIS M. CROCKER) says:
> >I think you are all trying too hard. With four boxes, I can use
> Again, the problem is entirely trivial unless you assume that you must
> put one and only one card in each box. otherwise, no thought is required
> to solve it.
>
> bob vesterman.
I strongly disagree with this. Let me explain. The original puzzle did
NOT specify that you must put a card in each box. Why is that important?
Because the premise is that we are applying for a job, and we have been
given 30 minutes to come up with a workable solution, within the given
parameters. Too often employees will overlook good solutions in favor of
more complex and difficult ones because of paradym paralysis. In
quality management class we we given puzzles to solve together, and one
in particular, required that we examine the instructions very carefully
to extract exactly what is required and what is "assumed", such as your
requirement to have a non trivial solution. In the puzzle in class, it was
impossible to solve in the time limit if you stuck with the assumed
limitations.
I agree there are more
elegant solutions, but 30 minutes is not alot of time, and I would not
look favorably on potential employees who rejected workable solutions
because they felt it was trivial, and ended up requesting more time.
Think about this from the employers point of view and let me know
which you would want. Finally, you overestimate your competition. Most
people wouldn't come up with even the trivial solution in 30 minutes.
Opinions?
Dennis Crocker
David Karr
>I agree there are more
>elegant solutions, but 30 minutes is not alot of time, and I would not
>look favorably on potential employees who rejected workable solutions
>because they felt it was trivial, and ended up requesting more time.
I have been on the giving *and* receiving ends of many of these
problem-solving exercises in interview situations. While the original
presentation of the question made it sound like the interviewer handed
his victim a pencil and paper and put him in a room for 30 minutes,
none of the interviews I've participated in was even remotely like
that. The purpose of the exercise is to investigate the person's
thinking and communications skills by interacting with them. It is a
discussion between two people, in which the interviewee may propose
several different approaches, not necessarily completing any of them
in the 30 minutes.
The best such questions have many intermediate results and are really
open-ended, so there is no way for the interviewee to know when
they're "done", and there is no concept of getting an "extension" on
the time limit. (If you're working out the decimal representation of
pi, for example, there's no point in asking for "more time" so that
you can "finish".)
If I were using the five-card puzzle as an interview question, I'd
certainly want to entertain solutions using various "cheats" that make
the problem "trivial". And then I might encourage using the rest of
the interview to look for harder versions that can still be solved.
Randall Gee
DENNIS M. CROCKER <dcro...@cwis.unomaha.edu> wrote:
><RVES...@vma.cc.nd.edu> writes:
>> In article <1994Apr29....@news.unomaha.edu>, dcro...@cwis.unomaha.edu
>> (DENNIS M. CROCKER) says:
>> >I think you are all trying too hard. With four boxes, I can use
>> >binary code to represent all thirteen cards in a suit. E.G...
>
>> Again, the problem is entirely trivial unless you assume that you must
>> put one and only one card in each box. otherwise, no thought is required
>> to solve it.
>>
>> bob vesterman.
>
>I strongly disagree with this. Let me explain. The original puzzle did
>NOT specify that you must put a card in each box. Why is that important?
>Because the premise is that we are applying for a job, and we have been
>given 30 minutes to come up with a workable solution, within the given
>parameters.
Actually, the puzzle was just a puzzle. It did in fact come from a job
interview situation, but I wasn't there, so I couldn't tell you the
original wording anyways. I reworded the puzzle, actually.
> Too often employees will overlook good solutions in favor of
>more complex and difficult ones because of paradym paralysis. In
>quality management class we we given puzzles to solve together, and one
>in particular, required that we examine the instructions very carefully
>to extract exactly what is required and what is "assumed", such as your
>requirement to have a non trivial solution.
It is, of course, necessary to extract what is "required" and abandon any
untenable assumptions. But it is also necessary to adapt to changing
condititions. In a "real" situation, it may be that your solution satisfies
all the requirements "given," but later analysis reveals that more conditions
should b imposed. In this case, you may have to adapt your solution, or
some up with a different one entirely.
The puzzle, as it came to me, actually specified that you were to make
a sequence of 4 cards out of the 5 you had. I didn't want to say the
word "sequence" (I was afraid it would give too much away) so I reworked
it to include the boxes on a gambling table. As also explicitly said that
your friend wasn't there when you laid down the cards. The 1st solution
that my friend Aaron (who gave me the puzzle) came up with had the order
in which you laid down the cards as well as the position in which you laid
down the card be significant. I don't actually know how the orginal
puzzle was presented.
Of course, most of the people who posted came up with the idea of sequences
anyway, so I guess it didn't matter. I like another poster's idea of dealing
4 cards off the deck. (Although in that case, if you are the dealer, you could
convey information by how you dealt the cards.)
In any case, there were a lot of conditions I didn't put on the problem,
without which the problem becomes trivial. You could put mulitple cards in
the boxes and leave some empty. You could arrange the cards funny in
each of the boxes. You could fold some of the cards before you put them
down, marking it permanently. There's a lot of things I didn't rule out
because it would make the problem statement clumsy and inelegant. Also,
I was actually wondering what kind of dodges people would come up with.
Some people were led to stop considering the problem after they worked
they're way around the dodge. Others recognized how trivial it made the
problem and continued looking for better solutions. (Comments?)
I don't think your solution is wrong, necessarily, but there are problems
with it. To say the puzzle is now "solved" or that we're "all working to
hard" is an overstatement.
> In the puzzle in class, it was
>impossible to solve in the time limit if you stuck with the assumed
>limitations.
>I agree there are more
>elegant solutions, but 30 minutes is not alot of time, and I would not
>look favorably on potential employees who rejected workable solutions
>because they felt it was trivial, and ended up requesting more time.
>Think about this from the employers point of view and let me know
>which you would want.
I don't even know if Joe got the job or not. Anyway, coming up with a
solution that turns out not to work and stubbornly sticking to it
isn't such a desirable trait either.
> Finally, you overestimate your competition. Most
>people wouldn't come up with even the trivial solution in 30 minutes.
I believe that many people could come up with a trivial solution in 30 minutes,
but I don't know. I was kind of wondering how long it took people who did
solve this to solve it -- I wanted to know if it was a "fair" interview
question.
-- Randall M! Gee
(rm...@soda.berkeley.edu)