Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Think of a Number. How Do Math Magicians Know What It Is?

quantamagazine.org

Post reply on HN
Print view View original

41–50 of 60 posts

Re: Think of a Number. How Do Math Magicians Know What It Is?

#41

Post by thfuran »

at_a_remove wrote: post #38
thfuran wrote: post #37

Earlier quoted context omitted.

The only requirement is that they're both perfect (or at least sufficiently good) logicians and arithmeticians.

In that case, I still don't get it.

Alright, so at each step, they're trying to rule out as many wrong answers as they can until there's only one left, at which point they'll know the right answer. It works because they have different starting information and know the nature of each other's starting information, allowing them to combine information that they already know with the information communicated by the other person still not knowing the answer. Each time they say they don't know, that gives the other person some information—and they know they're giving each other this information. For example, say Sandy was told the sum is 84. When Peter says he doesn't know the answer, Sandy can immediately rule out (83,1) because that's the only pair of numbers with a product of 83. If Peter had been told that the product was 83, he'd have known the answer immediately. And Peter knows that Sandy can rule such pairs out. Every time Sandy says she doesn't know the answer, Peter can rule out from his remaining options the ones that he knows she has enough information to have known, had it been correct. And vice versa, repeating until one of them narrows it down to just one option.

Re: Think of a Number. How Do Math Magicians Know What It Is?

#42

Post by HWR_14 »

at_a_remove wrote: post #36
HWR_14 wrote: post #16

Earlier quoted context omitted.

Think about it like this. There are two numbers, 1-99 choices. So there are 4545 possible pairs (since 2,5 and 5,2 are the same we ignore order). However there are only 197 sums (2-198) and only so many products (I don't want to do the math on that, but obviously a number like 60 is reached by quite a few pairs). Each time one of them says "I don't know", the other considers every sum (or product) and asks if the oth…

I am still not getting this. I think there is an assumption that both parties are ordering their possible choices in an identical manner, but I am unsure.

They aren't ordering it. Let's use a much simpler thing, the pair of numbers is 1-4. That gives us only 10 possible combinations. The product person says they don't know the answer. What do we know?

So if I told you the product of two numbers (positive integers) was 3, you immediately know 3 is prime and therefore the numbers are 1,3. Therefore either they cannot say they don't know if they were told 3. We can go through every combination and find what possibilities they could be.

Well, it cannot be 1,1 or 1,2 or 1,3 because those produce products of 1, 2 and 3 because they don't have any other pair that can generate them. The same is true of 2,3 which is the only way to get six or 2,4 the only way to get 8. And 3,3 or 3,4 which are the only way to get 9 and 12. And lastly 4,4 is the only way to get to 16. You'll note that this is almost all pairs which is easy to iterate over by making the second number greater than or equal to the first. The only pairs left are 1,4 and 2,2 both of which produce a product of 4. So we, as the sun person, now know the product must be four. Given the product and the sum, we can deduce that it's 1,4 because we were told the sun was 5.

When it goes to 100, it's the same process. Except now I have to iteratively eliminate pairs until there is only one solution.

Re: Think of a Number. How Do Math Magicians Know What It Is?

#43

Post by [deleted] »

contingencies wrote: post #5

The Collatz Conjecture or the 3n+1 problem was mentioned last week https://news.ycombinator.com/item?id=31208035 Any positive integer you take, you end up in a 1-4-2-1 loop. It's not proved yet but there's no number found yet that satisfies otherwise. Very interesting. What's the use case of this? Impressing ladies at the bar with your 'deep connection'.

[deleted]

Re: Think of a Number. How Do Math Magicians Know What It Is?

#44

Post by 4jsfgja5aj »

contingencies wrote: post #5

The Collatz Conjecture or the 3n+1 problem was mentioned last week https://news.ycombinator.com/item?id=31208035 Any positive integer you take, you end up in a 1-4-2-1 loop. It's not proved yet but there's no number found yet that satisfies otherwise. Very interesting. What's the use case of this? Impressing ladies at the bar with your 'deep connection'.

Rather than just downvote and otherwise be silent (I didn't up or down vote), I'll provide some direct feedback. First, as a reader, I almost never want to encounter a weird "wink-wink know what I mean?" type of joke out of the blue. Second, your "ladies" comment has a tone drawn from the era where cigarettes, martini lunches, and casual harassment were the norm. My rule is: if I find something that I write really funny, don't send.

Re: Think of a Number. How Do Math Magicians Know What It Is?

#45

Post by 4jsfgja5aj »

dehrmann wrote: post #24

Then there's the time with David Blaine and George W. Bush: https://www.youtube.com/watch?v=0vzuDkjtDOY

That is a great trick. I played along with the number trick, and I also had my number predicted. So this is success on a random independent sample of 2 people, with 1-in-20 odds. I'm sure LLN eventually kicks in, but I'll remember this coincidence for a long time.

Re: Think of a Number. How Do Math Magicians Know What It Is?

#46

Post by alabarbacoa »

jcranmer wrote: post #33
dmitriid wrote: post #11

Earlier quoted context omitted.

Yeah, I read this explanation, and I'm probably being very dense, but I still don't get it :)

There are 4950 possible pairs in the initial problem statement. Sandy gets one of 197 possible sums, and Peter gets one of 2,869 possible products. Of those 2,869 products, 1,765 can be produced with only possible pair of numbers: something like 67 can only be (1, 67), whereas 240 could be (3, 80) or (5, 48) or (4, 60) or 5 other possible pairs. Peter doesn't know the answer, so when he tells that to Sandy, she learn…

I think you are missing one more round. Impossible pairs after each round:

Round #1: ... (many)

Round #2: ... (many)

Round #3: (1,4), (72,92) and (72,98)

Round #4: (2,3), (80,90)

Round #5: (1,6), (75,96)

Round #6: (72,99)

Round #7: (81,88)

Round #8: (70,99)

Round #9: (77,90)

Round #10: (72,95)

Round #11: (76,90)

Round #12: (70,96)

Round #13: (90,84)

Round #14: (66,98)

Round #15: Solution is "77" and "84"

Re: Think of a Number. How Do Math Magicians Know What It Is?

#47

Post by at_a_remove »

kadoban wrote: post #40
at_a_remove wrote: post #38

Earlier quoted context omitted.

In that case, I still don't get it.

Is the basic idea clear? I'd say it's just that the statement "I don't have enough information" is _itself_ information that can be used to eliminate some possibilities. After understanding that idea, the rest is just tedious logic/brute-force-search, I believe. It's also possible that there is ambiguity in the statement or something like that. Hard to say exactly what part isn't connecting with you.

Well, so they brute-force and come up with a set of possible answers, a list of tuples.

I don't have any guarantees that both of them are sorting each list the same. So how does "I don't have enough information" relay which of those list items to eliminate?

Re: Think of a Number. How Do Math Magicians Know What It Is?

#48

Post by ascar »

at_a_remove wrote: post #47
kadoban wrote: post #40

Earlier quoted context omitted.

Is the basic idea clear? I'd say it's just that the statement "I don't have enough information" is _itself_ information that can be used to eliminate some possibilities. After understanding that idea, the rest is just tedious logic/brute-force-search, I believe. It's also possible that there is ambiguity in the statement or something like that. Hard to say exactly what part isn't connecting with you.

Well, so they brute-force and come up with a set of possible answers, a list of tuples. I don't have any guarantees that both of them are sorting each list the same. So how does "I don't have enough information" relay which of those list items to eliminate?

They always eliminate the pairs of products/sums with only one possible pair (think a sum to possible pairs and a product to possible pairs list).

When the person knowing the product says he doesn't know the answer, the sum person now checks the product list for all products with only 1 pair. These pairs can now be removed from the sum and product list. That actually culls the sum list and some entries that previously had 2 or more options now have 1 less. If the entry for the known sum has only 1 pair, he knows the answer. Otherwise he doesn't and now the culling continues with all sums that have only 1 pair. Repeat until you have the solution.

No ordering required. The algorithm can terminate at different rounds depending on the picked number and for some N (like 4) might not have a solution at all! For the given riddle the exact turn the solution was found is given through the conversation.

This is a pretty neat explanation https://alexanderell.is/posts/numbers-game/

Re: Think of a Number. How Do Math Magicians Know What It Is?

#49

Post by vivegi »

ninjinxo wrote: post #3

Reminds me of this problem: Two numbers are chosen randomly, both are positive integers smaller than 100. Sandy is told the sum of the numbers, while Peter is told the product of the numbers. Then, this dialog occurs between Sandy and Peter: Peter: I don't know the numbers. Sandy: I don't know the numbers. Peter: I don't know the numbers. Sandy: I don't know the numbers. Peter: I don't know the numbers. Sandy: I don'…

Peter: I know the product and it is p.q Sandy: I know the sum and it is p + q Peter and Sandy (in unison): Got it!

another variant:

Peter: If I divide by 4, I have remainder x Sandy: If I divide by 4, I have remainder y Peter: If I divide by 25, I have remainder a Sandy: If I divide by 25, I have remainder b Peter and Sandy (in unison): Got it!

Re: Think of a Number. How Do Math Magicians Know What It Is?

#50

Post by dromedariusCase »

ninjinxo wrote: post #3

Reminds me of this problem: Two numbers are chosen randomly, both are positive integers smaller than 100. Sandy is told the sum of the numbers, while Peter is told the product of the numbers. Then, this dialog occurs between Sandy and Peter: Peter: I don't know the numbers. Sandy: I don't know the numbers. Peter: I don't know the numbers. Sandy: I don't know the numbers. Peter: I don't know the numbers. Sandy: I don'…

Cutest problem I've ever seen. If anyone still doesn't understand, it basically comes down to removing "unique" products and sum from the possibility space.

Here is some python code that might be more revealing https://www.online-python.com/c5nAfLoIqr

A code review would be greatly appreciated!

Post reply on HN