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 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