2
$\begingroup$

Fitch Cheney's card trick is well known. Alice picks five cards from a deck. Bob takes them, gives one back to Alice and arranges the other four in some order. Chuck then enters the room, looks at the four cards and names the fifth. This would work with a deck of 124 cards.

Erich Friedman's Math Magic puzzle for March 2006 asks this question. Alice picks a hand of $n$ cards, and Bob shows $k$ of them in some order to Chuck who deduces the other $n-k$ cards. How big can the deck be?

Suppose a single suit of $13$ cards is used. Alice picks six cards, then Bob selects three of those and arranges them in some order. Can Chuck possibly deduce the other three cards?

I am asking those numbers because there is exactly enough possibilities. Bob shows Chuck three cards in some order, which has $3!{13\choose3}=1716$ ways, and Alice has ${13\choose6}=1716$ possible hands. How can Alice's $1716$ hands be paired $6-1$ with Bob's $286$ triples?

$\endgroup$
  • $\begingroup$ I assume the "possibly" in "can Chuck possibly" means "easily". Otherwise just choose some bijection and have Bob and Chuck memorize it. $\endgroup$ – Ethan Bolker Apr 21 at 16:22
  • $\begingroup$ Can you find a bijection with the triple always a subset of all six? Which of the twenty subsets do you choose? $\endgroup$ – Empy2 Apr 21 at 16:28
  • $\begingroup$ Skip the $6-1$ mapping. Just match each of Alice's $1716$ possible hands with one of the $1716$ sequences Bob could show Chuck. Since you can't remember such a mapping if it's essentially random the trick is to design one that can be easily computed from the input data. $\endgroup$ – Ethan Bolker Apr 21 at 16:39
  • $\begingroup$ Remember Bob has to choose three from Alice's six cards. $\endgroup$ – Empy2 Apr 21 at 16:44
  • $\begingroup$ You're right. Now I understand why it's an interesting question. $\endgroup$ – Ethan Bolker Apr 21 at 16:50
2
$\begingroup$

If you don't need the mapping to be "easy to memorize" then yes the $(13,6,3)$ case can be done.

In fact, this answer is an easy generalization of this which I found in a comment in this related MO post.

We recast the problem as follows: for any $6$-card subset $S$, we need to encode it with a $3$-card sequence $f(S) = (c_1, c_2, c_3)$ where $c_1, c_2, c_3 \in S$. Now consider a bipartite graph with node sets $X, Y$, where $X$ contains the $6$-subsets and $Y$ contains the $3$-sequences. There is an edge from $S\in X$ to $(c_1, c_2, c_3) \in Y$ iff $c_1, c_2, c_3 \in S$. What we want is a matching which covers every $S \in X$.

In fact we can find a perfect matching:

  • Every $S \in X$ connects to $6\times 5 \times 4 = 120$ different $y\in Y$ because that's the number of $3$-sequences with elements in $S.$

  • Every $y \in Y$ connects to ${10 \choose 3} = 10 \times 9 \times 8 / 6 = 120$ different $S \in X$ because there are ${10 \choose 3}$ ways to pick the other $3$ elements of $S.$

  • Therefore, the graph is actually a $120$-regular bipartite graph. A simple application of Hall's marriage theorem shows that a perfect matching exists.

$\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.