Design a magic trick

Question

You are a magician designing a new magic trick, which goes like this. First you are blindfolded. Then your assistant asks 4 members of the audience to write 4 distinct numbers between 1 and N (inclusive) on the back of 4 cards. The numbers are shown to the assistant and the audience. Now the assistant hides a card of their choosing. Your blindfold is taken off. The assistant gives you the remaining 3 cards in some specific order. After some deliberation, you correctly announce the number on the missing 4th card.

In order to make the trick more impressive you want N to be as large as possible. How large can you make it?

Notes:

• You know that all numbers are distinct and are between 1 and N, inclusive.
• There are no tricks like hidden cameras, or extra communication between you and the assistant - this is a pure puzzle in logic / mathematics.
• Cards don't have suits, they are just empty pieces of paper.
• In the previous puzzle we saw that N can be made at least 9.

Answer 1

Assuming you only get the knowledge of which cards are chosen, the answer is

27.

Proof:

Suppose there is a strategy with N cards. Instead of the magician announcing just the hidden card, have them announce all four cards.
For any set of 4 unordered cards, there must be a list of 3 ordered cards that causes the magician to announce that set of 4 cards, so the number of 3-card permutations >= number of 4 card combinations. That means N(N-1)(N-2) >= N(N-1)(N-2)(N-3)/24
24 >= N-3
27 >= N

The bipartite graph between 3-card permutations and 4-card combinations, which links when the three cards are a subset of the four cards, satisfies the conditions for Hall's Marriage Theorem, and therefore a 27 card strategy exists.

To construct a strategy:

Given a set of three cards i, j, k: define card m as being viable iff the index of m among the four cards equals (i+j+k+m) mod 4.
For any set of 3 cards, there are exactly 6 viable cards for them. (Proof: exhaustive search)
For any set of 4 cards, exactly one is viable for the other three. (Proof: take sum mod 4, take the nth smallest of the cards.)
Coder chooses the one viable card as the secret card, then orders the other cards to indicate which of the 6 viable cards it is.
Decoder works out which 6 cards are viable, then chooses one based on the ordering of the 3 cards.

Answer 2

Here is a solution for $N=15$.

Note that the standard method for the Fitch-Cheney card trick involves $5$ cards from a $52$-card deck, where the deck has $4$ suits, each of $13$ ranks. This method can be generalised to $k$ cards from a deck that has $k-1$ suits with $2\cdot(k-2)!+1$ ranks in each suit. For $k=4$ we get a deck of $3$ suits with $5$ ranks, so $N=15$ cards.

I will now describe that method as applied to the numbers $1$ to $15$.

Four numbers are chosen from $1$ to $15$ inclusive. Split that range into three parts, $1$ to $5$, $6$ to $10$, $11$ to $15$. By the pigeonhole principle at least one of those three ranges will have two chosen numbers.

• If the two numbers differ by $1$, retain the highest, and give the other number first, and then the remaining two chosen numbers in increasing order.
• If the two numbers differ by $2$, retain the highest, and give the other number first, and then the remaining two chosen numbers in decreasing order.
• If the two numbers differ by $3$, retain the lowest, and give the other number first, and then the remaining two chosen numbers in decreasing order.
• If the two numbers differ by $4$, retain the lowest, and give the other number first, and then the remaining two chosen numbers in increasing order.

The magician receives the three numbers. If the last two are in increasing order, then add $1$ to the first number, otherwise add $2$. If that addition puts the number into the next $5$-number range (for example from $10$ to $11$, or from $14$ to $16$) then subtract $5$ to bring it back down.

Answer 3

Here is a solution for $N=9$ which can be extended to $N=11$:

As an example, the numbers picked might be {1,4,7,8} as indicated by red dots in the following diagram:

Then the assistant could

arrange the cards in the order 714 and then the magician could deduce that the missing number is 8.

OR the assistant could

arrange the cards in the order 874 and then the magician could deduce that the missing number is 1.

How does the magician decode the assistant’s card order:

The first number in the assistant’s ordering is the base number.
The second and third number tells the magician how far to advance clockwise from the base number to get the hidden number.

If the second number is less than the third number, advance one position. For example if the ordering is 714, the base number is 7 and since 1<4, the magician advances clockwise one position from 7 to get 8 (the hidden number).

If the second number is greater than the third number, advance two positions. For example if the ordering is 874, the base number is 8 and since 7>4, the magician advances clockwise two positions from 8 to get 1 (the hidden number).

How does the assistant determine the card order:

First, the assistant picks one of the audience’s chosen numbers (which will be the base number) such that if you advance one or two positions clockwise from the base number you get to another audience chosen number (which will be the hidden number).

Secondly, the assistant places the base number in the first position, sets aside the hidden number, and arranges the two remaining numbers in the second and third positions to indicate the number of positions to advance.

Will the assistant always be able to follow the above procedure no matter what numbers are chosen by the audience:

Yes!

Let the 4 audience chosen numbers be A,B,C,D such that if you start at A and proceed clockwise the next number will be B then C then D. To advance from A to B you go $P_1$ positions, from B to C $P_2$ positions, from C to D $P_3$ positions and lastly from D back to A $P_4$ positions.

$P_1+P_2+P_3+P_4=9$ (all away around the 9-gon)

At least one $P_n$ must be $\le 2$ because otherwise $P_1+P_2+P_3+P_4 \ge 12$

Therefore, using a $P_n$ value that is $\le 2$, the assistant can always pick a base number and then complete their procedure.

The above method will work even if the range of possible audience chosen numbers is expanded to 1,2,3,...11.

Answer 4

Here is a solution for the more general case, where $K$ numbers are chosen between $0$ and $N-1$ (We will use 0-indexing here). It is actually the same as the solution from @ralphmerridew if we take $K = 4$ but because it is more general and maybe explained in a bit more natural way, I hope it is still a good answer.

It is possible to have $N$ as large as $K-1 + K!$ (so for $K = 4$ we get $N = 27$).

Let's call the chosen numbers $A_0, A_1, ..., A_{k-1}$, sorted in increasing order. The assistant will chose one of them to be the hidden card. The magician can already eliminate the $K-1$ visible cards just by seeing them. The assistant will try to communicate a number between $0$ and $K!-1$, that is the index of the hidden card with the visible cards removed.

Let's call $hidden(A_i)$ the "hidden" index of $A_i$, the number to cummunicate if choose $A_i$ to be hidden. For example if the four chosen cards are $2, 4, 7, 10$, we have $hidden(2) = 2$, $hidden(4) = 3$ because we ignore the visible $2$, $hidden(7) = 5$ because we ignore the visible $2$ and $4$, and $hidden(10) = 7$ because we ignore the visible $2$, $4$ and $7$.
In general we have $hidden(A_i) = A_i - i$

The cool trick is that we can choose to hide $A_i$ such that the sum of the visible numbers and the hidden index is a multiple of $K$ :
$A_0 + ... + A_{i-1} + hidden(A_i) + A_{i+1} + ... + A_{k-1} = 0 \mod K$ $\Leftrightarrow A_0 + ... + A_{i-1} + A_i - i + A_{i+1} + ... + A_{k-1} = 0 \mod K$ $\Leftrightarrow A_0 + ... + A_{i-1} + A_i + A_{i+1} + ... + A_{k-1} = i \mod K$
$\Leftrightarrow i = A_0 + ... + A_{k-1} \mod K$
By choosing $i$ this way, we have $hidden(A_i) = -sum(visible ~numbers) \mod K$, so we already gave a big indication on $hidden(A_i)$, actually there is now only $(K-1)!$ possibilities instead of $K!$.
And that is without any constraint on the ordering of the visible numbers!

Finally, we can choose an ordering of the $K-1$ visible numbers to indicate $num\_perm$, the correct possibility among the $(K-1)!$ remaining.
$hidden(A_i) = K \times num\_perm + (-sum(visible~numbers) \mod K)$ is communicated to the magician, who can deduce $A_i$ and impress the audience!

Answer 5

Here is a solution for $N = 256$, depending on how loose the meaning of "in some specific order" is.

When the assistant presents the cards, each card can be face up or face down, and rotated right way up or right way down. This means each card can contain two bits of data. Three cards can therefore contain six bits of data, or a number between 1 and 64, regardless of what numerical order they're in.

The numerical order of cards can contain 6 possible permutations (eg if the numbers on the three cards were 1,2, and 3, then the 6 possible arrangements would be: 1,2,3; or 3,2,1; or 2,1,3; or 3,1,2; or 1,3,2; or 2,1,3. Other numbers would follow this arrangement with their low, middle, and high values.) The assistant can encode an additional 2 bits of data by using one of the first four permutations.

This means a total of 8 bits of data can be encoded into the orientation and numerical order of the cards, for a number between 1 and 256.

Of course

if orientation of cards is allowed then why don't we use arbitrary rotation to encode even higher values? This being a card trick, we can assume the audience will notice any arrangement that's too out of place.