[HN Gopher] Think of a Number. How Do Math Magicians Know What I...
___________________________________________________________________
Think of a Number. How Do Math Magicians Know What It Is?
Author : nsoonhui
Score : 61 points
Date : 2022-05-05 05:04 UTC (2 days ago)
(HTM) web link (www.quantamagazine.org)
(TXT) w3m dump (www.quantamagazine.org)
| thatjoeoverthr wrote:
| If it involves operations in steps, your "code" is manipulating
| the digits. Easy example. Suppose I ask you to think of a
| positive integer. Then I ask you to double it. Now, give me the
| last digit. It's either zero, two, four, six or eight. With a few
| more steps I can probably get any number I like.
| FPGAhacker wrote:
| Well, they can know the number, but not how fast you are thinking
| it.
| magicseth wrote:
| Well.... If they know how fast, they might be able to know the
| number :-)
|
| https://web.archive.org/web/20121228075545/http://devblog.bu...
| motohagiography wrote:
| I've been working on something related for fair salary
| negotiations, where the two parties think of their honest salary
| proposal, exchange random numbers and exponents with each other,
| perform some arithmetic using the random number and their own
| secret honest salary number, and then decide whether the result
| is acceptable to both.
|
| I started hacking on this protocol using a pencil and paper
| variation of Diffie-Hellman where instead of a secret key
| agreement you arrive at the same salary number (as a function of
| the difference in your secret numbers), but realized you can do a
| one-sided version of this where the potential employee says to
| the recruiter "think of your max budget for this role" using a
| variation the second puzzle in article, though unfortunately the
| recruiter would likely feel tricked, so I've gone back to working
| on a DH-like protocol ahead of time because it would be fairer.
|
| Of course I would have liked to have made a blog post out of it,
| but this article is so close and mine is still half-baked, so if
| someone beats me to it and wants to leverage the power of being
| wrong on the internet in this comment thread, we could create a
| fair protocol that improves the lives of all parties involved in
| the hiring process.
| [deleted]
| oh_sigh wrote:
| Sounds like yaos millionaire problem
| motohagiography wrote:
| Very closely related, thank you!
|
| https://en.wikipedia.org/wiki/Yao%27s_Millionaires%27_proble.
| ..
| debdut wrote:
| How about testing these puzzles on GPT3 or upcoming transformers?
| magicseth wrote:
| One of my favorite versions of this trick was invented by Martin
| Gardner and actually uses a timing attack... on your brain! [0]
| Without apparently telling the magician anything, you end up
| giving enough information to uniquely identify your number!
|
| [0]
| https://web.archive.org/web/20121228075545/http://devblog.bu...
| ninjinxo wrote:
| 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'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'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't know the numbers.
|
| Peter: I do know the numbers.
|
| What are the numbers?
|
| Source:
| https://www.reddit.com/r/math/comments/32opae/next_level_che...
| quickthrower2 wrote:
| A smaller variant if that puzzle is in the article.
| CPLX wrote:
| dmitriid wrote:
| I still don't get it :D
| codetrotter wrote:
| This comment from the linked Reddit thread explains how:
|
| > Each sentence is extra data given to the other person.
|
| > When Peter says "I don't know the numbers", means that he
| doesn't have enough information. For example, if the product
| of the numbers is 10, it could be (1,10) or (2,5). But if the
| product is 9801, then Peter would know the answer (99,99).
| Therefore, his first sentence reveals to Sandy that (99,99)
| isn't a possible answer. But even this extra data isn't
| enough for Sandy to know the answer, and she says so. Again,
| this is extra data for Peter, but , again, is not enough.
| This go back and forth until suddenly Peter gains enough
| information to find the answer.
| dmitriid wrote:
| Yeah, I read this explanation, and I'm probably being very
| dense, but I still don't get it :)
| yayachiken wrote:
| Tip: A simpler variant of essentially the same puzzle
| principle is the xkcd "Blue Eyes" puzzle.
|
| https://xkcd.com/blue_eyes.html
| hashingroll wrote:
| Love this! Took a while to find the solution :)
| ninjinxo wrote:
| Since Peter is given the product of the two numbers, he
| should instantly know the pair if both numbers are prime,
| but since he doesn't it rules out pairs like (7x11) = 77
| and (2x53) = 106.
|
| Sandy knows the sum and has now been told that Peter
| doesn't know the pair. If the sum had been 6, the
| following pairs are possible: (1+5) (3+3) (4+2), Peter
| has just ruled out (1x5) and (3x3), so Sandy would be
| able to narrow it down to (1,5) if the sum had been 6.
|
| So when she tells Peter she can't narrow it down, it
| tells him that the pair isn't (4,2) either (among many
| others).
|
| And if Peter's number were 8: (1x8) or (2x4) he'd be able
| to solve it, but he doesn't so Sandy then knows that
| (1,8) isn't the solution either.
| informal007 wrote:
| >since he doesn't it rules out pairs like (7x11) = 77 and
| (2x53) = 106.
|
| I think pair (7x11)=77 can't be rule out, because pair
| (1x77) is also equal 77.
|
| still don't got it...
|
| Can you explain the situation for 3 turns before Peter
| knows, Sincere thanks.
| indecisive_user wrote:
| It's easier if you think about a smaller range.
|
| Let's think about picking two numbers between 1-9.
|
| Peter is given the product 24. He knows there are two
| possible pairs of numbers between 1-9 which produce a
| product of 24, (3,8) and (4,6), so he says "I don't know
| the numbers"
|
| Sandy is given the sum 10. There are many pairs of
| numbers that produce a sum of 10, [(1,9), (2,8)...]. But
| she also knows that Peter did not immediately know the
| answer. If the pair of numbers was (5,5), that would have
| produced a product of 25. If Peter was given a product of
| 25, he would have immediately known the answer, since
| there's only 1 pair of numbers that produces that
| product.
|
| So Sandy knows the answer isn't (5,5). Similarly, she
| knows it's not (2,8) or (3,7). The answer could be (1,9)
| though, since the product of (1,9) is 9, and there's
| another pair that can produce that product (3,3). If
| Peter was given the product 9 he wouldn't have
| immediately known the answer. The answer could also be
| (4,6), since the product of those is 24, and that can
| also be achieved with the pair (3,8). So there's only 2
| pairs of numbers that add up to 10, and which Peter would
| not have immediately known based on their product. Sandy
| knows the answer must be either (1,9) or (4,6). Sandy
| says "I don't know the numbers".
|
| Peter knows the solution must be either (3,8) or (4,6),
| and he knows that Sandy did not immediately know the
| answer. If Sandy had been given the sum 11 though, she
| should have immediately known the answer. There is only 1
| pair of numbers that produces 11, but which does not have
| a unique product. Yes, the pair (2,9) sums to 11, but the
| product is unique, and if Peter had been given the
| product 18 to begin with, he would have immediately known
| the answer. So because he didn't immediately know the
| answer, and because that was not enough information for
| Sandy to say that the pair is (3,8), then Peter knows
| that the summation of the numbers must not be 11. The
| only other choice then is (4,6), and so Peter says "I do
| know the numbers".
| herendin wrote:
| Probably easier if you imagine it with a much smaller
| range of numbers, like 1-9, or even 1-3
| LodeOfCode wrote:
| >he should instantly know the pair if both numbers are
| prime
|
| That should actually be "if the product of their
| respective smallest prime factors is over 100". 7x11
| can't be ruled out since 1x77 also produces 77, whereas
| 49x17 and Nx53 can be ruled out.
|
| You can also rule out some of the larger squares, e.g.
| 25x25 and 64x64, so there's probably still a better
| phrasing for that
|
| Edit: Can also rule out 1xPrime
| ninjinxo wrote:
| Oh whoops, good pickup; I'd like to say I tried to
| simplify it for the explanation and brevity, but I
| completely overloooked that 1xn = n.
| jcranmer wrote:
| 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 learns that it can't be
| (1, 67) but it still could be (3, 80) or the like.
|
| Before Peter told Sandy he didn't know, only 4 sums could
| have been caused by a unique pair (198, 3, 2, and 197).
| Peter telling Sandy he doesn't know lets her rule out
| lots of pairs, and after doing so, there are 9 sums that
| would have a single pair remaining that hadn't been ruled
| out. For example, were the sum 165, Sandy could have
| concluded that the only possible pairing would be 69 and
| 96, since the other pairs that add up to that number
| (e.g., 74 and 91, 80 and 85, etc.) would have unique
| products that Peter would have known about. That she
| doesn't know the answer yet therefore tells Peter that 69
| and 96 is not a possible pair. Were the product 6624,
| Peter would now know that the only possible remaining
| pair was 72 and 92, and he would know the answer. But
| since he didn't know the answer, now Sandy knows that it
| can't have been 72 and 92 either.
|
| This crossing out continues until Peter realizes that 70
| and 96 was not a viable pair, which lets him realize that
| the only other way to get 6720 was to have the numbers be
| 80 and 84, and he declares he knew the answer. [Assuming
| I got the correct number of rounds]
| HWR_14 wrote:
| 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 other person has received enough
| information that that sum or product they know has one
| unique unelimiated pair that generates it. For some pairs
| (1,1) both players will have a unique answer right away.
| Otherwise, both players eliminate from the set of
| possible answers any pair that would compute an answer
| that no other non-eliminated pair would compute. That
| means the next time the player says "I don't know" they
| were doing so with a more constrained set of pairs. Which
| provides more information. Until eventually they
| eliminate all other possibilities to calculate their
| product/sum.
| at_a_remove wrote:
| 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.
| thfuran wrote:
| The only requirement is that they're both perfect (or at
| least sufficiently good) logicians and arithmeticians.
| at_a_remove wrote:
| In that case, I still don't get it.
| kadoban wrote:
| 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.
| jancsika wrote:
| CVE-2022-123456: The specification doesn't require each new
| round to be dependent on the input from the previous round.
| This can allow unprivileged users to send arbitrary commands to
| the accelerator and breaking system.
| richardfey wrote:
| It's arithmetic, at most.
| bell-cot wrote:
| My immediate reaction to "Think of a number...Magicians...": The
| tricks probably require that their targets think of only natural
| numbers - {1, 2, 3, 4, ...}. And assume that most folks will pick
| small, dull natural numbers. (Vs., say, 2^24-1. Which is the
| maximum unsigned mediumint value in MySQL. Or, if you've ever
| been stuck doing low-level stuff with a 80286 CPU...)
|
| It'd be interesting to see if any of the tricks worked for, say,
| -7p + ei.
| SAI_Peregrinus wrote:
| More precise phrasings of the questions are needed for them to
| work. Even just allowing the rationals makes most (all that
| I've seen) of these sorts of tricks fail. It could be an
| interesting problem to find such tricks in the Surreal numbers,
| since that's the most general form of number (ordered field).
| unholiness wrote:
| Some obvious ones are the "I can guess your number" tricks,
| where you do hard math on a secret number and tell the magician
| the result, who then does easy math to tell you your number.
|
| Such a loop of operations containing only multiplication,
| addition, and subtraction would work on activity complex
| numbers. Square roots would not.
| contingencies wrote:
| _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'._
| dehrmann wrote:
| Then there's the time with David Blaine and George W. Bush:
|
| https://www.youtube.com/watch?v=0vzuDkjtDOY
| unholiness wrote:
| Unless I'm misunderstanding, I think problem 3 has many
| solutions.
|
| Spoilers:
|
| First note that, below 16, 11 is the only sum which explains S's
| first statement: all possible pairs of numbers adding to 11 have
| non-unique products, accounting for S knowing P would not know
| the numbers.
|
| Then note that for 18 (9x2), 24 (8x3), and 28 (7x4), all other
| factor pairs for that product add to a non-11 number below 16.
| Those non-11 sums are ruled out by S's first statement, so P will
| know the sum is 11 by her second statement.
|
| Therefore (9,2), (8,3), and (7,4) all look like valid solutions,
| and it seems likely there are more.
|
| What am I missing?
| unholiness wrote:
| To answer my own question: I'm missing the last statement, that
| S now also knows the solution. It does not follow trivially
| from the others like in the previous problem, for exactly the
| reasons I describe. S would not know the solution in this case
| because there are 3 possibilities.
| riffraff wrote:
| Hey this doesn't mention the simplest trick of all: get them to
| do a bunch of useless operations, then multiply by 3, add all the
| digits, and you'll know the final number.
___________________________________________________________________
(page generated 2022-05-07 23:02 UTC)