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.