Mdthbs

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?

I hope it wasn't asked before...

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.

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.

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.