# Winning Strategy for the Magician and his Apprentice

There are $$13$$ upside-down opaque cups and $$2$$ balls, a magician and his apprentice and yourself. You decide under which cups to put the balls, and the objective of the magician is to find the two balls with only $$4$$ guesses.

The magic trick works as follows:

1. The magician leaves the room.
2. You put the two balls under two cups while the apprentice observes.
3. The apprentice allows the magician to enter the room.
4. The apprentice lifts one cup which doesn't hide a ball.
5. The magician uses his $$4$$ guesses to reveal the hidden balls.

What strategy the magician and his apprentice can use such that the magician will always find the two balls?

• How does the magician guess? Does he need 2 guesses to find both of the balls? – EKons Jun 3 at 15:17
• Do the cups have to be arranged in a straight line? Or a circle? Or a grid? Or can they be place in any shape/position? – yoozer8 Jun 4 at 19:45
• Current answers all assume the cups can be ordered (implicitly by position or explicitly by marking). Is this a valid assumption? – asgallant Jun 4 at 21:42
• @asgallant It is always possible to order cups by position, since the Pauli exclusion principle prevents them from occupying the same space. – Fax Jun 5 at 10:25
• Just as a note for a real magic show, it doesn't seem like a good illusion to me if the magician takes more than two guesses, the first of which must be a ruse to trick the audience into thinking he doesn't know where it is. Also, for some reason I now have the idea to submit questions which consist of asking how "Fool Us" contestants do their illusions... – Michael Jun 5 at 20:31

Here is a simple strategy of how they could do it

Label the cups $$0,1,2,\ldots,12$$ and the ball positions are $$b_1$$ and $$b_2$$.
The assistant picks cup $$X$$ such $$b_1-X$$ and $$b_2-X$$ are both in the set of residues $$\{1,2,4,10\}$$, modulo $$13$$.
Then the magician picks cups $$X+1, X+2, X+4$$ and $$X+10$$, modulo $$13$$
There will always be an $$X$$ that the assistant can pick such that magician finds both balls

Proof

Each non-zero residue modulo $$13$$ can be expressed as the difference between two numbers in the set $$\{1,2,4,10\}$$

$$1 \equiv 2-1, \mod 13$$
$$2 \equiv 4-2, \mod 13$$
$$3 \equiv 4-1, \mod 13$$
$$4 \equiv 1-10, \mod 13$$
$$5 \equiv 2-10, \mod 13$$
$$6 \equiv 10-4, \mod 13$$
$$7 \equiv 4-10, \mod 13$$
$$8 \equiv 10-2, \mod 13$$
$$9 \equiv 10-1, \mod 13$$
$$10 \equiv 1-4, \mod 13$$
$$11 \equiv 2-4, \mod 13$$
$$12 \equiv 1-2, \mod 13$$

Hence, the assistant can determine $$b_2 - b_1 =x$$, mod $$13$$, choose the equation above with $$x$$ on the left-hand side and pick $$X$$ such that $$b_1$$ and $$b_2$$ are at the appropriate relative positions on the right-hand side.

• +1 for a solution that allows the magician to pick all four balls at once, rather than adapting the choice based on previous results. – user3294068 Jun 3 at 17:43
• This is like a circular/modular version of a complete sparse ruler of length 13 with only 4 marks. The assistant merely shows the magician where to put the ruler. – Jaap Scherphuis Jun 4 at 15:27
• @JaapScherphuis Yes, that is a good description. – hexomino Jun 4 at 17:00

Here's another solution. Unlike the highest-voted answer, it's adaptive. However, it may be easier to put into practice.

Suppose you put the balls in cups $$b_1$$ and $$b_2$$. Without loss of generality we can suppose that $$d=b_2-b_1 \bmod 13 \in \{1,2,3,4,5,6\}$$ (if not, relabel $$b_1$$ as $$b_2$$ and vice versa).

Then the apprentice does the following:

If $$d \in \{1,2,3\}$$, the apprentice lifts up cup $$b_1-1$$. If $$d \in \{4,5\}$$, the apprentice lifts up cup $$b_1-2$$. If $$b_2-b_1=6$$, the apprentice lifts up cup $$b_1-3$$.

And the master does the following:

Now, the master proceeds sequentially from the lifted cup until he finds the first ball. If he finds it immediately, he knows to look in the next three cups for the other ball. If he finds it on his second try, he knows to skip three cups and look in the following two cups. If he finds it on his third try, he only has one guess left, but the location of the other ball is fixed.

• That's the solution I worked out, sans set terms/symbols. For me, it was easier to think about (rot-13) gur phcf orvat va n pvepyr naq ernyvmvat gung gur onyyf jvyy arire or zber guna fvk phcf njnl. Gurersber, gur qvfcynlrq phc arrqf gb or (rt) pbhagrepybpxjvfr sebz gur svefg onyy ol rabhtu fcnprf gb tvir gur zntvpvna rabhtu vasbezngvba gb xabj vagb juvpu tebhc bs phcf gb ybbx. – Van Jun 4 at 13:44
• ...I now see my answer as even more equivalent to Cireo's answer. – Van Jun 4 at 13:50

Thinking completely sideways, the assistant picks a cup (won't matter which one, just the actions)

put hand on cup.
wait n seconds.
lift cup.
wait m seconds.
drop cup.

ball 1 is n cups away, ball 2 is m cups away.

• Yeah, my first thought was that there's a lot of sideband channels the assistant can communicate to the magician with... – Michael Jun 5 at 20:33

Expanding on Omega Krypton's solution:

I decided to form my own "code" assigning 4 possible cups to each potential lifted cup, and you can indeed make a code that will always result in a correct guess.

The first number represents the apprentice's cup, the other 4 are the magician's guesses.

1 - 2,5,8,11
2 - 1,5,6,7
3 - 1,8,9,10
4 - 1,11,12,13
5 - 1,2,3,4
6 - 2,7,10,13
7 - 2,6,9,12
8 - 3,5,9,13
9 - 3,6,10,11
10 - 3,7,8,12
11 - 4,5,10,12
12 - 4,6,8,13
13 - 4,7,9,11

This is a rather ugly and hard to remember combination, though it just exists as a proof of concept, I just went through a greedy algorithm to assign 4 cups to each number such that you never have two overlapping. I'm sure there is a more elegant way to arrange them.

So, first things first.

Combinations of ball locations:

$$(1+12)*12/2 = 78$$

There are 13 cups and four guesses.

If the magician and the apprentice agreed on a code, this can be done.

For example, if the apperentice flipped cup number 1, it means the two balls are in two cups in cup 2,3,4, and 5.

Why this works:

Each combination of 4 cups cover $$3+2+1=6$$ guesses

$$13*6=$$

$$78$$, covering all combinations of ball locations.

Therefore, this strategy works.

• The apprentice only has 11 choices. – JMP Jun 3 at 16:00
• @JonMarkPerry Looking at it from this perspective, the concept still works. Since the apprentice rules out one cup by lifting it, there are actually only 12!/(10!*2!) = 66 possibilities remaining for the magician to have to find. Since a "code" can correspond to 6 arrangements, and 11*6 = 66, this still works. – Michael Moschella Jun 3 at 16:42
• @JMP hexomino's answer is the solution to your question. we have the same concept, and his or her answer is the extension of mine, proving my point – Omega Krypton Jun 3 at 16:52
• This is essentially scratchwork for an existence proof. You don't propose any strategy. The trick is finding the correct selections. Continuing your example: 1 goes to 2,3,4,5; if you say 2 goes to 3,4,5,6 - then you are duplicating (3&4), (3&5), and (4&6). So you've already lost the chance to represent all 78 combinations. – Cireo Jun 4 at 5:52

Haven't heard this one before, though I believe there is a class of similar puzzles. I don't know if they have a name.

Naturally, the puzzle can be solved.

The simplest way, without requiring any special memorization prowess, is as follows:

Consider the 13 positions as numbered from 0-12. Note that this solution doesn't actually require a line with a start and end, as long as there is an order (a circle works as well if we consider clockwise). With two numbers among 13 values, we know they can be at most 6 apart (modulo 13). For example, 1 is 5 away from 6 (2,3,4,5,6), 6 away from 7 (2,3,4,5,6,7) and then back to 5 away from 8 (12,11,10,9,8).

The assistant notes

The ball that is 6 or less away from the other (modulo 13). That is, they would choose the smaller position if the distance is <=6, otherwise the larger one. For example, if the balls are in 7 and 10, they choose 7. If they were in 1 and 10, they would choose 10.

The assistant then considers

The balls to be relabeled as follows: _ _ _ X ? ? ? ? ? ? _ _ _. Where X is the noted ball. By construction, the other ball must be in one of the positions marked with question marks.

Finally, the assistant chooses

One specific ball in one of the three positions before the noted ball, as follows: _ _ A X a a a ~ ~ ~ _ _ _. Selecting A if the second ball is the 1st, 2nd, or 3rd after the noted _ B _ X ~ ~ ~ b b ~ _ _ _. Selecting B if the second ball is the 4th or 5th after the noted C _ _ X ~ ~ ~ ~ ~ c _ _ _. Selecting C if the second ball is the 6th after the noted

The magician then enters, and reverses as follows

Starting with the position after the chosen, they lift up until they find the first ball. If they find it after one lift, they are in scenario A, and can continue lifting with their remaining 3 guesses. If they find it after two lifts, they are in scenario B, and skip ahead 3 before continuing to lift. If they find it after three lifts, they are in scenario C, and skip ahead 5 to find the last ball.

For example:

I choose positions 3 and 10. The assistant notes 10, since 3 is 6 ahead of 10 (3-10 mod 13 ~= -7 ~= 6). The assistant chooses 7 (3 before 10) and is done. The magician chooses 8, 9, finding nothing. The magician chooses 10, and then skips 5 (11, 12, 0, 1, 2), choosing 3.

• This is essentially the same as Micah's answer. – Jaap Scherphuis Jun 4 at 8:26
• @JaapScherphuis - That's very possible. I don't understand Micah's answer; it uses notation that I'm not familiar with. I understand this answer. – AndyT Jun 4 at 9:55

The apprentice arranges the cups such the balls are amongst the first four cups closest to the doorway.

The apprentice allows the magician to enter the room.

The apprentice says, 'Come in and pick the from the four cups closest to you'

This also works for a two guess strategy.

I'm pretty sure this is similar to some other answers, but it's presented in a way that's more practical to the magician and their assistant.

We assume the cups are ordered (perhaps laid out in a line or circle or by prior arrangement between the magician and the assistant) and that when the assistant lifts a cup, they are also indicating a direction along that order. We also assume that order wraps, so that the 1st cup is 'after' the 13th.

When the assistant indicates the cup,

Starting with the next cup, the magician lifts the 1st, 2nd, 5th and 7th cups; consider these cups P (picked by apprentice), A, B, C and D. Due to the assistant's selection, those cups are guaranteed to contain both balls.

The heuristic for the assistant's selection is:

Select a 'first' ball so the balls are 6 or less cups apart. Label cups A, B, C and D so that the balls fall under them with their given distance apart, e.g. if the balls are 6 apart, they go under A and D. If they are adjacent, they go under A and B. All distances from 1-6 are covered by the permutations and are fairly easy to work out in your head. Cup P is always the cup before A to cue the magician and is guaranteed to be empty because the balls fall under ABCD.

To be exhaustive, all the permutations are:

1 = AB, 2 = CD, 3 = BC, 4 = AC, 5 = BD, 6 = AD

Assuming the magician's guesses involve revealing the contents of the cups he guesses, correctly guessing both the cups that hold a ball within four guesses can be accomplished with a rather simple strategy.

The assistant picks a cup that is an equal amount of cups away from both of the cups holding a ball. Thanks to the uneven number of cups, this is always possible by having the cups loop in the distance calculation.

Example: XAXXXOXXXXOXX, where X is an empty cup, O is a cup with a ball and A is the cup chosen by the assistant.

Then the magician simply locates the other ball by guessing cups to the right of the assistant's cup until one ball is found. When the ball is located, the magician can calculate the position of the other ball by going left from the assistant's cup the appropriate amount. In the above example, the two balls would be found with the third guess:
 XAXXXOXXXXOXX 11 22 3 3 
This method takes the largest amount of guesses when the distance from the assistant's cup to the two chosen cups is the highest it can be, which is five cups. However, four guesses are still sufficient, as three guesses can cover six cups, meaning one of the two balls is guaranteed to be found with the first three guesses. Example:
 OXXXXXAXXXXXO 11 22 33 4 4 

As such, the magician can always guess the two correct cups with at least four guesses as long as the contents of all guessed cups are revealed.

• I think the magician is only allowed to reveal the contents of 4 cups, not 4 pairs of cups. – Jaap Scherphuis Jun 5 at 15:09