This is a magic trick performed by two magicians, Alice and Bob, with one shuffled deck of N unique cards. (Nothing is mentioned about suits; you may consider these cards to be simply enumerated from 1 to N.)

Alice asks a member of the audience, Carol, to randomly select 5 cards out of a deck. Carol then returns her chosen 5 cards to Alice. After looking at the 5 cards, Alice picks one of the 5 cards and gives it back to Carol.

Alice then arranges the other four cards in some way, and gives them to Bob in a neat, face-down pile. Bob examines these 4 cards and determines what card is in Carol's hand (the missing 5th card). Carol is astonished!

What is the largest number of cards N that the deck can contain before the trick is no longer performable? Prove it.

How specifically do you execute the trick on a deck of maximal size N?

*See also ***"5 Cards Magic Trick"**.

---------------------------------------------------------------

Note: There's no secretive message communication in the solution, like encoded speech or ninja hand signals or ESP or whatever ... the only communication between the two magicians is in the logic of the 4 cards transferred from A to B. Think of these magicians as mathematicians.

In general, if C cards are drawn (C=5 in this case), then the maximum N equals C!+C-1

Alice's first act is to arrange the cards in ascending order and calculate their sum mod C, call this R. The (R+1)th ranked card is the card Bob will need to deduce.

Alice will then consider the descending ordered list of the C! cards that Bob will not see, split into (C-1)! blocks of size C. She will arrange the C-1 cards Bob can see to indicate which of the (C-1)! blocks that the desired card falls in.

Bob comes out and notes which block is indicated by the order of the cards. Then he calculates the sum of the C-1 cards he can see mod C, call this R'. Then the (R'+1)th card in the block is the card Bob will call out.

A specific example with C=4, which implies N=27:

Carol chooses cards 2, 7, 15, 21.

Alice calculates (2+7+15+21) mod 4 = 1. The second card, 7, is the card Bob will find.

The descending ordered list partitioned into blocks is (the three visible cards 2, 15, 21 are removed):

27 26 25 24 | 23 22 20 19 | 18 17 16 14 | 13 12 11 10 | 9 8 7 6 | 5 4 3 1

7 is in the fifth block, so Alice arranges the 2, 15, 21 cards according to the fifth of the six permuations of three items (1:123, 2:132, 3:213, 4:231, 5:312, 6:321) -> 21, 2, 15.

Bob comes out and determines the block he needs is 9 8 7 6.

Bob calculates (15+2+21) mod 4 = 2. The third card in this block is 7, so Bob calls out that the hidden card is 7.