The Hidden Card #2

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 the dealer. The dealer 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

Preliminaries

We first define the possible face-down cards your partner may guess when they see 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$

The strategy

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, they can see $\cal U$, the set of face-up cards. From the order those cards are in, they can derive the $n$ you used. They calculate the $n$th lowest possibility for $\cal U$ and guess that card.