Source

This is a generalization of a problem I got from Rustan Leino, who learned about it from Lyle Ramshaw. See also puzzles 19 and 20 on the following large collection of mathematical puzzles.

I solved it and wrote up my solution.

Problem

In this problem, you and a partner are to come up with a scheme for communicating the value of a hidden card. The game you'll play involves a deck of $N! + N - 1$ cards, where $N$ is a positive integer you're given; the cards are numbered 1 through $N! + N - 1$. The game is played as follows:

- Once you and your partner have finished strategizing, your partner is sent out of the room.
- The dealer hands you $N$ cards from the deck.
- You look at the cards and hand them back to the dealer, one by one, in whatever order you choose.
- The dealer lays them in a row in the order you gave them to her. She puts the first card face-down and the rest face-up. Thus, while you control the order of the cards, you have no control over their orientations. So, you can't use orientation to transmit information to your partner.
- You leave the room and your partner enters the room.
- Your partner looks at the cards and the order in which they lie and, from that information (and your previously-agreed-upon game plan), guesses the face-down card. If the guess is correct, you win.

What scheme can you and your partner use to always win?

Solution
Reveal

We first define the possible face-down cards your partner may guess when she
sees a certain set of face-up cards $\cal U$.
We call $p$ a *possibility* for face-up card set $\cal U$ if
both $p \notin {\cal U}$ and
$\mathsf{NumSmaller}({\cal U}, p) = [p + \mathsf{Sum}({\cal U})] \bmod N.$
Here, $\mathsf{NumSmaller}({\cal U}, p)$ means the number
of cards in $\cal U$ smaller than $p$, and $\mathsf{Sum}({\cal U})$
means the sum of the cards in $\cal U$.

First, we'll prove that it's always possible to select one face-down card that's a possibility for the remaining cards.

**Lemma 1.** If $|{\cal S}| = N$, $r = \mathsf{Sum}(S) \bmod N$,
and $d$ is the $(r+1)$th lowest card in $\cal S$, then $d$ is a
possibility for ${\cal S} \setminus \{d\}.$

*Proof.* Let ${\cal U} = {\cal S} \setminus \{d\}$. Clearly,
$d \notin {\cal U}$. Also, there are $r$ lower cards in ${\cal S}$
than $d$, so $\mathsf{NumSmaller}({\cal U}, d) = r$.
Finally, $d + \mathsf{Sum}({\cal U}) = \mathsf{Sum}({\cal S})$,
so we have $\mathsf{NumSmaller}({\cal U}, d) = [d + \mathsf{Sum}({\cal
U})] \bmod N$. Thus, $d$ satisfies all the requirements to be
a possibility for $\cal U.$ $\Box$

Next, we'll prove that there are only a limited number of possibilities for your partner to consider, so that you can convey which possibility is the right one with the order of the face-up cards. For this, we'll start with the following lemma.

**Lemma 2.** If $|{\cal U}| = N-1$, $p < q$, and both $p$ and $q$
are possibilities for $\cal U$,
then there are at least $N-1$ cards that
fall strictly between $p$ and $q$
and are not in $\cal U.$

*Proof.* Let $l$ be the number of elements of $\cal U$
less than $p$, and let $b$ be the number of elements of $\cal U$ between
$p$ and $q.$
Thus, there are $l+b$ elements of $\cal U$ less than $q$.
Since $p$ is a possibility for $\cal U$, we have
$l = \mathsf{NumSmaller}({\cal U}, p) = [p + \mathsf{Sum}({\cal U})] \bmod N.$
Since $q$ is a possibility for $\cal U$, we have
$l + b = \mathsf{NumSmaller}({\cal U}, q) = [q + \mathsf{Sum}({\cal U})] \bmod N.$
Subtracting these equations modulo $N$ shows that $p + b \equiv q \pmod N$.
Thus, the number of cards between $p$ and $q$, which is $q - p - 1$,
is congruent to $b-1$ modulo $N.$

The number of cards between $p$ and $q$ cannot be $b-1$ or less because there are $b$ cards in $\cal U$ between them. Thus, the number of cards between $p$ and $q$ must be at least $b-1+N$. Of these, $b$ are in $\cal U$, so there are at least $N-1$ cards between $p$ and $q$ that are not in $\cal U$. $\Box$

We'll now use that lemma to prove that there are a limited number of possibilities.

**Lemma 3.** For any card set $\cal U$ where $|{\cal U}| = N-1$,
the number of possibilities for $\cal U$ is $\leq (N-1)!.$

*Proof.* Suppose the number of possibilities for $\cal U$ exceeds
$(N-1)!.$ Then, we can find a list of distinct, ordered possibilities
$p_1, p_2, \ldots, p_{(N-1)!+1}.$ For each consecutive pair of these
possibilities, $p_i$ and $p_{i+1}$, we apply Lemma 2 and find at least
$N-1$ cards between $p_i$ and $p_{i+1}$ that are not in $\cal U$. Since
there are $(N-1)!$ such consecutive pairs, and none of their intervals
overlap, this gives us at least $(N-1) \cdot (N-1)!$ cards that aren't
among the $p_i$ and aren't in $\cal U$. Since possibilities for $\cal U$
also can't be in $\cal U,$ we have the following bunch of distinct cards:
these $(N-1) \cdot (N-1)!$ cards, the $(N-1)!+1$ possibilities $p_i$, and
the $N-1$ cards in $\cal U.$ Adding these together, we get $N! + N$
distinct cards, which is more than the deck contains. This contradiction
proves that our supposition was wrong, and the number of possibilities for
$\cal U$ cannot exceed $(N-1)!.$ $\Box$

When you're handed the $N$ cards, compute their sum modulo $N$ and call it $r$. Choose the $(r+1)$st lowest card and hand it to the dealer. Call that card $d$ and the remaining $N-1$ cards $\cal U$. By Lemma 1, $d$ is a possibility for $\cal U$. Thus, you can find an $n$ such that $d$ is the $n$th lowest possibility for $\cal U$. By Lemma 3, this $n$ is between 1 and $(N-1)!.$ There are only $(N-1)!$ possible permutations of $\cal U$, so you can compute the $n$th lowest permutation lexicographically among those permutations. Hand the cards in $\cal U$ to the dealer in the order given by that permutation.

When your partner enters the room, she can see $\cal U$, the set of face-up cards. From the order those cards are in, she can derive the $n$ you used. She now calculates the $n$th lowest possibility for $\cal U$ and guesses that card.