## May 2007 riddle

Chico and Dico were a famous pair of magicians, and the following trick used to be part of their repertoire:

From an untampered standard deck of 52 playing cards, a volunteer from the audience would pick five cards at random. He would give these to Chico. Chico would reorder them and give them back to the volunteer. This would all happen entirely without Dico seeing it. The volunteer would then show Dico the first four cards, according to the order decided by Chico, and Dico would magically be able to divine the identity of the fifth card.

It is not difficult to show that no ESP and no sleight of hand is required to pull this trick off. An agreed strategy between Chico and Dico regarding how the cards should be ordered is all that is really required.

This month's riddle has to do with generalizations over this trick. We will consider decks with an arbitrary number of cards, which we will denote n. (If n is larger than 52, we will of course not be able to use standard playing cards, but one can equally think of cards numbered consecutively one through n or marked in any other way, as long as no two cards are identical.) We will also consider an arbitrary number of cards picked from the deck, k, and an arbitrary number of cards divined by magical intuition, j. The original trick is therefore describable as the special case n=52, k=5, j=1. Note that it doesn't matter, when j>1, whether Dico needs merely to divine the identity of the remaining cards or also the order in which they are placed, as these remaining cards are ordered by Chico, and the two magicians can agree in advance that they will be placed, for example, by order of rising rank.

The riddle this month will be composed of two parts. Answer either or both parts for your name to be mentioned as a solver. A separate list of solvers will be kept for each of the two parts.

#### Part 1:

For what combinations of n, k and j is the trick possible? Prove your answer.
Note that in this part we ask for an exact characterization, and not mere bounds.

#### Part 2:

Consider the special case j=1. Describe a strategy for Chico and Dico to follow, that will allow them to perform the trick with an arbitrary k and with the largest possible associated n (as determined in part 1, above).

Note that in this part of the riddle it is not enough to show that such a strategy exists, nor even to give a recipe that will show how to come up with such a strategy for any k. What we require here is an explicit description of the strategy (which should preferably be simple enough for two magicians to actually be able to perform it on stage...).

### List of solvers:

#### Both parts:

Oded Margalit (7 May 5:00)

#### Part 2 only:

Elegant solutions can be submitted to the puzzlemaster at riddlesbrand.scso.com. Names of solvers will be posted on this page. Notify if you don't want your name to be mentioned.

The solution will be published at the end of the month.

Enjoy!