34
$\begingroup$

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?

Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ How does the magician guess? Does he need 2 guesses to find both of the balls? $\endgroup$
    – EKons
    Jun 3, 2019 at 15:17
  • $\begingroup$ 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? $\endgroup$
    – yoozer8
    Jun 4, 2019 at 19:45
  • $\begingroup$ Current answers all assume the cups can be ordered (implicitly by position or explicitly by marking). Is this a valid assumption? $\endgroup$
    – asgallant
    Jun 4, 2019 at 21:42
  • $\begingroup$ @asgallant It is always possible to order cups by position, since the Pauli exclusion principle prevents them from occupying the same space. $\endgroup$
    – Fax
    Jun 5, 2019 at 10:25
  • 1
    $\begingroup$ 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... $\endgroup$
    – Michael
    Jun 5, 2019 at 20:31

10 Answers 10

Reset to default
27
$\begingroup$

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.

Improve this answer
$\endgroup$
10
  • 1
    $\begingroup$ +1 for a solution that allows the magician to pick all four balls at once, rather than adapting the choice based on previous results. $\endgroup$
    – user3294068
    Jun 3, 2019 at 17:43
  • 7
    $\begingroup$ 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. $\endgroup$
    – Jaap Scherphuis
    Jun 4, 2019 at 15:27
  • 2
    $\begingroup$ @JaapScherphuis Yes, that is a good description. $\endgroup$
    – hexomino
    Jun 4, 2019 at 17:00
  • $\begingroup$ @hexomino , request you or someone else who is willing to, to give an example. Let us say that b1 is 3 and b2 is 5. Then what will be the value of X ? I am unable to understand the meaning of this statement , "The assistant picks cup X such b1−X and b2−X are both in the set of residues {1,2,4,10}, modulo 13." $\endgroup$
    – Hemant Agarwal
    Oct 9, 2020 at 14:17
  • $\begingroup$ @HemantAgarwal Are you familiar at all with modular arithmetic? If b1 is 3 and b2 is 5 then X will be 1 (because 3-1=2 and 5-1=4 are both in {1,2,4,10}) $\endgroup$
    – hexomino
    Oct 9, 2020 at 14:52
13
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Van
    Jun 4, 2019 at 13:44
  • $\begingroup$ ...I now see my answer as even more equivalent to Cireo's answer. $\endgroup$
    – Van
    Jun 4, 2019 at 13:50
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Yeah, my first thought was that there's a lot of sideband channels the assistant can communicate to the magician with... $\endgroup$
    – Michael
    Jun 5, 2019 at 20:33
3
$\begingroup$

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.

Improve this answer
$\endgroup$
3
$\begingroup$

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

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ The apprentice only has 11 choices. $\endgroup$
    – JMP
    Jun 3, 2019 at 16:00
  • $\begingroup$ @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. $\endgroup$
    – Michael Moschella
    Jun 3, 2019 at 16:42
  • $\begingroup$ @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 $\endgroup$
    – Omega Krypton
    Jun 3, 2019 at 16:52
  • 1
    $\begingroup$ 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. $\endgroup$
    – Cireo
    Jun 4, 2019 at 5:52
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ This is essentially the same as Micah's answer. $\endgroup$
    – Jaap Scherphuis
    Jun 4, 2019 at 8:26
  • $\begingroup$ @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. $\endgroup$
    – AndyT
    Jun 4, 2019 at 9:55
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I think the magician is only allowed to reveal the contents of 4 cups, not 4 pairs of cups. $\endgroup$
    – Jaap Scherphuis
    Jun 5, 2019 at 15:09
0
$\begingroup$

Following is a partial answer and I am hoping that someone can help me prove that it works.

Let us label the cups from 1 to 13.

Before the game begins, the magician and the apprentice write down all the (13*12)/2 = 78 combinations that I can choose, on a blackboard.

To number 1, they allocate, any arbitrary 4 numbers: a,b,c and d. The only things they make sure are that none of a, b, c or d = 1 and ab, ac, ad, bc, bd and cd are all present on the board.

They, then erase these 6 numbers and then to the number 2, allocate another 4 arbitrary numbers, a', b', c' and d' . Again, the only conditions while choosing these 4 numbers are that none of a', b' , c' and d' = 2 and all their 6 combinations (a'b', a'c', a'd', b'c', b'd' and c'd') are present on the board. They then erase these 6 numbers ( a'b', a'c', a'd', b'c', b'd' and c'd') from the board and move on to to allocating numbers to 3, and so on.

The idea is that if the apprentice calls out 1, then the magician will guess a, b, c and d. If the apprentice calls out 2, then the magician will guess a', b', c' and d', etc.

The thing I am unable to prove though is that the magician and his apprentice will always be able to allocate 4 numbers to all the 13 numbers using this strategy and will never come to a point where they can no longer find 4 numbers to allocate to a number.

For example, let's say that they manage to find 4 numbers for 1 to 6. Then they come to 7 and find that no 4 numbers e,f, g, h exist such that ef, eg, eh, fg, fh and gh exist such that are all present on the board .

Intuitively, I feel strongly that this strategy of theirs will work but am unable to prove it.

Improve this answer
$\endgroup$
8
  • $\begingroup$ If I understand correctly, you can just use the number assignments that I've set up in my answer and that will work,e.g, cup 1 assigned to (2,3,5,11), cup 2 assigned to (3,4,6,12), cup 3 assigned to (4,5,7,13), cup 4 assigned to (5,6,8,1), cup 5 assigned to (6,7,9,2)...... $\endgroup$
    – hexomino
    Apr 15, 2021 at 15:41
  • $\begingroup$ @hexomino , I understand your answer . I also realise that there are a total of 78 different combinations . I can also see how your method assigns 6 combinations to each number, thus, covering all the 78 combinations with these 13 numbers . What I am wondering is, can we still solve the problem by the greedy approach that I have mentioned . My approach is basically this : While allocating 4 numbers to, say the 8th cup, take any combination of 4 numbers such that the exact combination hasn't been used before and assign it to the 8th cup . Do this for all the cups . $\endgroup$
    – Hemant Agarwal
    Apr 15, 2021 at 16:06
  • $\begingroup$ Oh, I see. No, it won't work arbitrarily. Consider the following assignments for the first 4 cups: Cup 1 - (13,4,5,6), Cup 2 - (13,7,8,9), Cup 3 - (13,10,11,12), Cup 4 - (1,2,3,5) But now you are in trouble because 13 can only appear with 1,2 and 3 but those three cannot appear together so you won't be able to finish. $\endgroup$
    – hexomino
    Apr 15, 2021 at 16:13
  • 1
    $\begingroup$ Yes, but when you use, for example, (1,13) you have to use two other numbers with it so what numbers are left to choose? $\endgroup$
    – hexomino
    Apr 15, 2021 at 18:24
  • 1
    $\begingroup$ Now you're asking a tricky combinatorics question to which I don't know the answer. Such rules may be difficult to pin down. $\endgroup$
    – hexomino
    Apr 16, 2021 at 9:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.