A Magic Trick

Logic Level 4

Pete and Zandra are performing a mathematical magic trick. Given a string of $N$ digits (0-9) of an audience member's choice that only Pete can see , Pete will cover up a digit of his choosing, and then Zandra will look at the remaining digits (and which one is covered) and -- without any communication with Pete -- say the digit that Pete covered.

For example, if $N=13,$ the audience member might write 2, 5, 1, 1, 5, 6, 2, 3, 3, 7, 8, 9, 2. Then, Pete decides to cover up the 7. Then, Zandra opens her eyes, looks at the whole list (but can't see the covered number), and then 'guesses' the missing number, 7, correctly. Since that number might have been any digit, this seems like a pretty amazing feat.

What is the smallest $N$ for which this trick is always possible? And how could they pull it off?

Bonus: What if Pete had to cover two adjacent digits?

The answer is 10.

1 solution

Ivan Koswara
May 25, 2016

There are $10^N$ possible digit strings chosen. There are $N \cdot 10^{N-1}$ possible strings with one digit covered ( $N$ ways to choose the covered digit, and $10^{N-1}$ ways to put the digits of the rest). We need to map each digit string to each string with one digit covered, and the mapping must be injective (otherwise we have ambiguities). Thus $N \cdot 10^{N-1} \ge 10^N$ , so $N \ge 10$ .

To show that $N = 10$ is possible, one way to do it is to compute the sum of the digits $s$ , then hide the $(s \mod 10) + 1$ -th digit. For example, $2694153186$ has sum of digits 45, so we hide the $(45 \mod 10) + 1 = 6$ -th digit, giving $26941?3186$ . Figuring out the missing digit is simple; since we can see the position of the hidden digit, we know the sum of the digits modulo 10, and by summing everything else and subtracting from our sum, we get the missing digit.

Thus the answer is $\boxed{10}$ .

Moderator note:

Great explanation.

The lower bound is often an easy counting argument. In coding theory, establishing the minimum can be harder since it's not immediately apparent what approach to take. It is not even clear that such a mapping exists, much less a "nice" mapping as shown above.

Great! How about the 2 digit case?

Eli Ross Staff - 5 years ago

Similar: $10^N \le \binom{N}{2} 10^{N-2}$ , so $N \ge 15$ . It should be possible, too, but I'll leave it for others (read: I'm too lazy to figure out the solution now).

EDIT: Oops, two adjacent digits. Then $10^N \le (N-1) 10^{N-2}$ and so $N \ge 101$ . Easily possible: Add up the digits in odd positions, modulo 10. Add up the digits in even positions, modulo 10. The odds make the tens digit, the evens make the units digit. Approach like above.

Ivan Koswara - 5 years ago

Just to be sure , can you assure that it is possible ? The strategy for the minimal case in this problem should be different for 2 (and especially consecutive as it is stated) numbers which are covered than a strategy for just 1 covered number because the amount of information received from the string of digits such that the two numbers can be deduced speaks about a compound.

A A - 5 years ago

A Magic Trick

The answer is 10.

1 solution

Moderator note:

0 pending reports