1
$\begingroup$

In Peter Winkler's Mathematical Puzzles A Connoisseur's Collection, he posed Fitch Cheney's card trick problem as follows.

enter image description here

His solution for the last question concerning the $124$-card, rather than the original $52$-card version is as follows.

enter image description here

However, I find myself puzzled by the solution. What is $k$? Is this a typo which is supposed to be $j$ and presumably $x=c_j$ the card Dorothy pulls out? We know neither $j$ or $k$ nor $c_k$ or $c_j$ or $x$. We need that to position $x$ in one of the modulo of $5$ before we can pick the exact position from amongst the $4!$ possibilities within each modulo class. Can someone explicate the solution?

Note: I understand the original $52$ card solution. Please do not explain that basic version.


I found Michael Kleber's The Best Card Trick. It gives a clear presentation. However, the new numbering system modulo 5 is best explained by the answer of @LonzaLeggiera below. This answer also has some good references on this problem.

$\endgroup$
  • $\begingroup$ Ah! I had seen this in a book of puzzles for the $52$ case in school. $+1$ for the question, and let me tell you I used to be David in school for this one! The kids loved it. $\endgroup$ – астон вілла олоф мэллбэрг Aug 16 '19 at 3:38
  • $\begingroup$ Note the "closing the gap" part... that clear things up for me. $\endgroup$ – user202729 Aug 16 '19 at 4:22
  • $\begingroup$ That sentence can be written as "find a number $x$ such that there exists a $k$ such that $x$ is $c_k$ and $x \equiv -s+k \pmod 5$". $\endgroup$ – user202729 Aug 16 '19 at 4:26
  • $\begingroup$ @user202729: That is clearer. But why does such $k\neq j$ exist and is unique? $\endgroup$ – Hans Aug 16 '19 at 5:11
  • $\begingroup$ I've heard this trick referred to as "communicating the card". $\endgroup$ – Peter Kagey Aug 16 '19 at 19:30
2
$\begingroup$

Apart from the confusing description of what it is that "David needs to find", the trick won't work as described because of an error in the way Winkler indexes the cards chosen by the stranger. If you're going to use a sum mod $5$ as an index, then you need to index the cards as $\ c_0, c_1, \dots, c_4\ $ rather than $\ c_1, c_2, \dots, c_5\ $. If you use the latter indexing, which is what Winkler seems to assume later on in his explanation, then Dorothy has to choose the card $\ c_{j+1}\ $ rather than $\ c_j\ $, and David has to obtain a number $\ x\ $ such that $\ x\equiv -s + k \hspace{-0.3em}\mod 5\ $ and $\ x = c_{k+1}\ $, which is what I'll assume in the rest of this answer.

If $\ b_0<b_1<\dots\ <b_{119}\ $ are the cards remaining in the deck after the four which Dorothy hands to David have been removed from it, and $\ x= c_i\ (i=j+1)\ $ is the face value of the card Dorothy removes from the five chosen by the stranger before handing the remaining four to david, then $\ x=b_{x-i+1}=b_{x-j} $. Then if $\ s\ $ is the mod $5$ sum of the face values of the four cards Dorothy hands to David, $\ \sigma\equiv -s\equiv x-j\hspace{-0.3em}\mod 5\ $, and $\ d\ $ the unique number in the set $\ \left\{0,1,\dots,23\right\}\ $ such that $\ x-j=5d+\sigma\ $, Dorothy rearranges the cards in the order that she has prearranged with David to represent the number $\ d\ $. David can recover $\ d\ $ by inspecting the arrangement of the cards, and $\ \sigma\ $ by calculating the mod $5$ sum of their face values, so he can calculate the value of $\ x-j\ $ and $\ x=b_{x-j}\ $.

$\endgroup$
1
$\begingroup$

So...

(The puzzle omitted to mention that Dorothy is allowed to rearrange the cards. I don't see why this should be assumed if it isn't mentioned. After all it is assumed that David can't see which of the five cards Dorothy removes so that David won't know the value of $j$. The puzzle would be very different if David knew what $j$ was. And there's no reason, according to what the puzzle has stated, that David can't watch Dorothy put the cards in order and watch her remove precisely the $j$th card...)

The way I read this.

Let $j \equiv c_1+c_2+c_3+c_4+c_5 \pmod 5$ and $1 \le j\le 5$. Dorothy removes $c_j$.

Let $s = ( c_1+c_2+c_3+c_4+c_5)- c_j\equiv j-c_j \pmod 5$. David knows the value of $s$.

David has four cards which he will call $A_1 < A_2 < A_3 < A_4$

So the way I see David figures:

If the missing card is $c_k=x$ where he doesn't know what $k$ or what $x$, then $s \equiv k - x\pmod 5$ or $x \equiv k-s \pmod 5$ and $A_{k-1} < x < A_k$ (if $k-1=0$ of $k=5$ just ignore the non-defined $A_{term}$). He tries to solve these for $k = 1,2,3,4,5$.

Now if we relabel the numbers $1....124$ to the numbers $1..... 120$ by omitting $A_1,...,A_4$ the $x$ will get translated to $x'$ and $x'=x$ if $x < A_1$. And $x'=x-1$ if $A_1 < x < A_2$ and $x'=x-2$ if $A_2< x < A_3$ and so on.

So $s \equiv k - x\pmod 5$ or $x \equiv k-s \pmod 5$ and $A_{k-1} < x < A_k$ all be become the equation $s \equiv 1-x'\pmod 5$. where $1 \le x' \le 120$.

There are $24$ possible such $x'$s. And there are $24$ ways to arrange the cards $A_1,A_2,A_3,A_4$. Dorothy rearranges the remaining $4$ cards to indicate the which of the $24$ values $x'$ is.

.......

So for example. Let's say the cards are $21, 27, 86, 110, 114$.

Then $21+27+86+110+114 = \equiv 3\pmod 5$. So Dorothy removes the $3$rd card: $86$. Dorothy does a subtraction of $c_j - (j-1)$, in this case, $86-(3-1) = 84$. And Dorothy figures $s = 21+27+110+114= 272\equiv -3\pmod 5$ and $84 \equiv 1-272\equiv 1+3 \equiv 4\pmod 5$. Furthermore $84 = 16*5 + 4$.

So Dorothy rearranges $2127,110,114$ into the $16$th permuations. The sixteenth permutation is.. lets see... if $abcd$ through $adcb$ are the first six permutations, then $cabd$ through $cdba$ are the thirteenth through eighteenth, And $cabd$ and $cadb$ are the 13th and 14th, $cbad,cbda$ are the 15th and 16th. So we want the permutation $cbda$.

So Dorothy arranges the cards as $110,27,114,21$.

David sees those cards and sees they are arranged in order of $cbda$ and figures they are the $16$th permutation.

He adds $s=110,27,114,21= 272$. $1-272 \equiv 4\pmod 5$. And $16*5 + 4 = 84$. $84 \not < 21$. And $21 \not < 85 \not < 27$. But $27 < 86 < 110$ so David figures the card is $86$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.