Four puzzle solutions reveal different ways to divine someone’s hidden number with impossibly little information.
In our most recent Insights puzzle, I challenged readers to figure out how certain magic tricks work. The tricks in question were of the sort where the magician somehow divines the identity of your hidden numbers or playing cards. But how does the magician correctly deduce what’s in your mind based on seemingly no information? As we’ll see below, the secret is to extract just enough information to unravel the mystery through the inexorable logic of mathematics.
Our first puzzle was an elementary arithmetic trick suitable for captivating a child:
Ask the child to think of a three-digit number without telling you what it is. Then tell them that you will reveal the number by producing two copies of it side by side! First ask the child to multiply their number by 7. Then ask them to multiply the answer by 11. Finally — and at this point you can add feigned concentration and appropriate magical phrases — ask them to multiply the second answer by 13.
If the child has done this right, you might find a smile start to light up their face. The question for you, or for an older child, is — why does this work?
The reason, as many readers correctly pointed out, is that 7 × 11 × 13 = 1,001, which is the number that you are effectively asking the child to multiply by. That this will produce a copy of the original three-digit number (say, 457) is obvious when you write down the multiplication in the conventional way.
The information that makes the trick work is the fact that the number has three digits. As George commented, for a four-digit number you’d have to multiply by 73 and 137.
There are two unknown numbers between 2 and 9. The two numbers can include 2 or 9 and they can both be the same number. S and P are two mathematicians with perfect logic. S is given only the sum of the two numbers, and P is given only the product. Both S and P know everything we’ve just specified. Here is their subsequent conversation.
S: I cannot deduce what the two numbers are.
P: Neither can I.
S: Aha! Now I know what the two numbers are!
P: So do I!
This seems like magical mind reading at first glance — where could they be getting the new information to solve the problem? Can you figure out the two numbers (there are two possible answers)? Can you explain how S and P did this?
First, we tabulate all the possible sums and products. The best way to do so is to create an 8-by-8 table with the numbers 2 to 9 on both axes. Within each cell we can put both the sum and the product separated by a comma, as first described by Dabed. As shown below, we only need to consider one triangular half of this table since the order of the numbers doesn’t matter. All of the number pairs that have the same sum line up along the same diagonal line, as shown by the arrows.
Next, let’s look at each statement.
1. When S says that she cannot deduce what the numbers are, she means that the sum she has obtained can be generated in more than one way from the given range of numbers. There are four numbers in our list that can form their sum in only one way: 4 (2 + 2), 5 (2 + 3), 17 (8 + 9) and 18 (9 + 9). These can be eliminated from our list and are grayed out in the figure.
2. When P says he cannot deduce them either, it means that the product he was given can be obtained in more than one way from the given range of numbers. There are only five numbers in the list of products that can be generated in more than one way: 12 (2 × 6, 3 × 4), 16 (2 × 8, 4 × 4), 18 (2 × 9, 3 × 6), 24 (3 × 8, 4 × 6) and 36 (4 × 9, 6 × 6). These products are shown in red. We can reject all the others.
3. Now S can deduce the product. This means that among all the products that are associated with her sum, only one is still possible. So, we have to look at each of our sum diagonals and accept only the ones that have a single product that’s red. This is true of the diagonals for the sums equaling 7, 9, 12 and 13 (shown with red arrows) having acceptable products 12, 18, 36 and 36 respectively.
4. And now P can deduce the sum. This can only happen if his product has a single sum associated with it. This is not true of 36, which could have a sum of 12 or 13. So the only acceptable sum-product pairs are (7, 12) and (9, 18) which correspond to the pairs of original numbers (3, 4) and (3, 6).
Note that although this requires us to do quite a bit of work, things are a lot easier for S and P. For the first solution of (3, 4), S is given a sum of 7. She realizes at once that she cannot be sure of the solution because it could be (2, 5) or (3, 4). So, she says so in her first statement. Now, P has a product of 12, so he too cannot be certain if the original pair is (3, 4) or (2, 6). At this point S is sure that the pair is (3, 4) as P would have been able to tell if it was (2, 5) because it has a unique product of 10. And this enables P to figure it out too, because (2, 6) is on an unacceptable diagonal which has two red products. So when S and P are given the sum and product, respectively, of one of the solutions, they can deduce the unique pair of numbers. We, on the other hand, are only able to deduce the complete set of possible solutions that will work, without being able to specify which particular one S and P actually have.
The answers (3, 4) and (3, 6) both satisfy the problem statements and are correct. Reader Damion Zandrews, however, expressed the opinion that there is only one correct answer (3, 4). While that’s technically incorrect, a case can be made that (3, 4) is the best answer. As we’ll see in the next puzzle, the answers in these kinds of puzzles may change if the upper limit of the range is increased. This turns out to be the case here. If we just increase the upper limit of the range from 9 to 10, then (3, 4) remains a solution, (3, 6) ceases to be one, and a completely new solution emerges. So we can think of (3, 4) as a stable solution to our original problem. Solutions like (3, 6) which appear and disappear as you change the range of numbers are called “phantom solutions.”
Again, there are two unknown numbers that could be equal, but now they are between 2 and 70. Again S is given only the sum of the two numbers, and P is given only the product. Here’s how their conversation goes this time.
P: I cannot deduce what the two numbers are.
S: I could have told you that, even though I can’t deduce the numbers either.
P: Aha! Now I know what the two numbers are!
S: So do I!
Again, find the two numbers and explain how P and S did this. Using number theory principles, what’s the smallest number of cases (sums and products) that you have to examine manually after judicious exclusion?
This time the range is far too large for us to find the solution easily using the method described for puzzle 2. However, S’s first statement gives us an additional clue that enables us to reduce the number of possible cases that need to be examined. Let’s call the sum s and the product p and systematically exclude possibilities for s with the following rules.
1. Since P cannot deduce the two numbers, p cannot be the product of two prime numbers. Therefore, s cannot be the sum of two primes. Here we encounter the Goldbach conjecture, perhaps the most famous unproved conjecture in number theory. The conjecture states that all even numbers above 2 can be expressed as the sum of two primes. Even though this famous conjecture has not yet been conclusively proved, it has been verified to be true for all even numbers up to 4 × 1018. Since our range is far lower than that, we can safely state that s cannot be even.
2. One aspect of rule 1, which I’ll call rule 2, is that s cannot be the sum of an odd prime and 2 since 2 is a prime number. For instance, s could not be 9, which is a sum of 7, a prime, and 2 which is also a prime, because their product 14 can only be factored in a single way, as 2 × 7. In that case, P would have known at once what the two numbers were.
3. Finally, s cannot be equal to or greater than 2 plus the smallest prime greater than half of the upper limit of the range. With an upper limit of 70, the smallest prime greater than half of 70 (35) is 37. By this rule, s cannot be 39 or greater. Why is this so? We can prove this by starting at 39 and working our way up. First, by our rule 2, s cannot be 39 which is 37 + 2 (both primes). Similarly, s cannot be the next odd number 41, because that is 37 + 4 giving the product 37 × 4 =148. The only other way to factor 148 is 74 × 2, but 74 is greater than our upper limit 70, because it is twice a number that’s greater than half of 70. This is true of the next odd number, which can be written 37 + 6, and the next, which is 37 + 8, and so on … all the way up to 70. To generalize, any odd number greater than 39 can be expressed as 37 + x where x is even, and such a number can only be factored as 37 × x if we are to restrict ourselves to numbers less than 70.
Using the above restrictions, we can reduce the possible candidates for s to 11, 17, 23, 27, 29, 35 and 37 using the first three statements made by S and P. This is good, but we can do better! The key is that for S to make statement 4, there must be a single unique product p that gives sum s. Now look at s = 11, which can be expressed as 3 + 8 or 3 + 23 and also as 7 + 4 or 7 + 22. If P has concluded that s is 11, he could have done so with a p of 24, reasoning: “The numbers could be 3 and 8, giving 11, which is permissible, or 2 and 12, giving 14, which is even and disqualified by rule 1, or 4 and 6, giving 10, which is also even and therefore disqualified”; or he could have had a p of 28 and reasoned: “The numbers could be 7 and 4, giving 11, which is permissible, or 2 and 14, giving 16, which is even and disqualified.” So when s = 11 there is no way for S to determine whether p is 24 or 28. This gives us a fourth rule: The sum s must not be expressible as y + 2n, where y is an odd prime, in more than one way.
Looking at our candidates for s, 11 is already disqualified above. So are 23 (19 + 4 and 7 + 16), 27 (23 + 4, 19 + 8 and 11 + 16), 35 (31 + 4, 19 + 16 and 3 + 32) and 37 (29 + 8 and 5 + 32). We are only left with 17 and 29 as possible sums with just 20 products to examine manually. Doing this, we can eliminate 29 because 13 + 16 is a possible solution and so is 25 + 4, and there must only be one solution for S to make her second statement.
The possibilities for an s of 17 are listed in the table below. The first column has the candidate pair of numbers, and the second column has the product p that P would have been given. Based on this P would have come up with possible alternative pairs other than the candidate pair. These are shown in column 3. Then in columns 4 and 5, we have P checking if the sum for these alternative pairs is permissible as determined above (that is, it must be one of 11, 17, 23, 27, 29, 35 and 37). If even one of the alternative pairs gets a Y in column 5, P cannot say he knows the numbers (column 6) because, along with the pair in column 1, that would make two permissible pairs. As shown, there is only one pair, 4 and 13, that has no other “Y” in column 5, and this is the unique solution to the puzzle.
In the original statement of this puzzle, the upper limit was incorrectly set to 50 and there was no solution. Dabed, Jeff L, toma&co., Fabien Friedli and Rob Corlett all pointed this out. We might ask: Why was 4 and 13 not a solution in that case? The answer is that, as we saw in rule 3 above, 35 and 37 are not on the permissible list for s for a range of 50, because they are greater than 31 (the sum of 2 and 29, the smallest prime greater than 25). So both (6, 11) and (7, 10) will have no Y in column 4. Therefore, there will be more than one solution for an s of 17, and S will not be able to say that she knows the numbers.
Readers Dabed, Rob Corlett, Fabien Friedli and George provided a full solution to this puzzle. Corlett, Friedli and George also remarked on its connection to the Goldbach conjecture. This puzzle is called the Freudenthal problem after the German-born Dutch mathematician Hans Freudenthal, who published the first such puzzle in 1969. Martin Gardner popularized it as the “impossible puzzle” because at first glance it seems to have too little information to allow us to solve it. After it was published in Quanta, I received an email from a Boeing engineer, Matthew Thomas, who designs fighter aircraft and uses this puzzle to teach early-career engineers the value in thinking through problems in seemingly extreme circumstances — often a necessity in his field!
A “mathemagician” prepares a deck of 32 cards by throwing away the 2s through 6s. She arranges the remaining cards in a certain order and then places the deck, face down, on a table. Five people are randomly selected to go to the table. Each of them cuts the deck, one after another. Then the first person takes the top card and passes the deck to the second person, who takes the current top card, and so on, in order. Once each one has a card, the last person puts the deck back on the table face down, and they all return to their seats.
Now the performer asks the five people to beam her their card telepathically. A frown of concentration crosses her face. Finally, she shakes her head in a resigned manner. “It’s getting harder these days,” she says. “The expansion of the universe is causing a redshift that’s interfering with the colors I am receiving. Will the people who have red cards please stand up?”
The second and fifth participants stand up. A relieved look crosses the mathemagician’s face. “Now it’s clear,” she says. “You have the 10 of hearts, and you have the king of diamonds.” They do, indeed. She proceeds to correctly guess the cards of the other three people as well.
How did she do it? Hint: Consider the sequence 00010111. It contains, cyclically, all eight possible triplets formed from zero and 1: 000, 001, 010, 101, 011, 111, 110 and 100. What happens if you “cut” it, as you would a card deck?
Was the performer’s stage banter mere theater, or was it essential to the trick?
Here is the solution as described by George:
The sequence 00010111 is called a de Bruijn sequence of order 3 on 0 and 1. Cutting it like a deck of cards is equivalent to cycling it around some number of times, and it retains the property that it contains all possible triplets of 0s and 1s. We can construct a similar sequence for all possible groups of 5 Bs and Rs — for example BBBBBRBBBRRBBRBRBBRRRBRBRRBRRRRR and it will be 25 = 32 digits long which is the same as the number of cards we have — and arrange the cards so that each B in the de Bruijn sequence corresponds to a black card, and each R to a red one. Each arrangement of Bs and Rs occurs exactly once, so once you know where the reds are (in the example 2nd and 5th) you know the whole sequence of five cards (BRBBR). Then simply (!) remember the order of the cards until you find the five that form this run, and you have the answer. The banter is necessary to find the red positions and fix which set of five cards have been drawn (although obviously you could reveal the black cards instead).
As for the order of the cards, you can use any order that is easy for you to memorize. Here is a YouTube video of this card trick using a de Bruijn sequence of order 4 using 16 cards.
This puzzle is one of many mathematics-based card tricks in the book Magical Mathematics: The Mathematical Ideas That Animate Great Magic Tricks by the famous magician-mathematicians Persi Diaconis and Ron Graham. Readers Dabed, Fabien Friedli, Rob Corlett and George gave solutions to this trick, and the last three recognized its dependence on the de Bruijn sequence, which was named after another Dutch mathematician, Nicolaas de Bruijn.
The de Bruijn sequence is widely used in various types of coding, as you can imagine, and amazingly, or perhaps inevitably, it’s finding an application in efforts to build genetic assemblies using the DNA genetic code.
Thank you to everyone who contributed to these intriguing puzzles. There were some very high-quality contributions, and at least four deserving puzzle solvers. But only one prize can be given, and it goes to Dabed, who was the first to draw attention to the fact that puzzle 3 as stated did not have a solution, and who illustrated the “diagonal method” for solving Freudenthal-type puzzles.
See you next time for new Insights!
Written by Pradeep Mutalik
This is our RSS Feed and this story was found here by our Project ADA. Make sure to visit the site and original post!