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.
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.
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.
That's an elegant way to do it. For a brief moment I considered solving this by hand using basically the same idea, but that gets incredibly painful before I even got started.
I mean, obviously the extremes get eliminated right away, and then the primes, but then I have to track 10,000 number combinations.
I originally also thought about doing this (sort of) by hand, but once you realize that the possibility space is too large, programming it really helps you see what kinda pairs you are actually eliminating.
You can actually WLOG away all pairs where the second element is larger than the first.
Also, the most common kind of pair I eliminated was actually due to the size constraint (ie, 98 * 99) or pairs of (1, prime) which I didn't actually realize would be a thing until I coded it up.
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!
That's the point, Sandy doesn't tell Peter her sum, nor vice versa. Sandy only knows the sum, Peter only knows the product, and they both know that the other doesn't (yet) know the answer. It allows them (in turns) to eliminate all the pairs that produce unique sums/products, until Peter ends up with one single pair.
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.
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]
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.
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.
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.
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.
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.
>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
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".
> 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.
pair (2,9) and pair (3,6) can produce a product of 18, so Peter can't immediately know the answer if he had been given the product 18 to begin with, so the problem can't beed solved.
I think this problem would Caught in an unresolved cycle after unique product and unique sum has been ruled out.
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!
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.
My pleasure - I think officially your problem would be the Socialist millionaires problem, but that is mostly only known as a derived form of yao's millionaires problem, which has a much stronger cachet.
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.
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.
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, -7π + ei.
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).
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.
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.
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.
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.
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.
Err, OK keyboard warrior. I think you read way too much in to this. This is PC gone nuts. If I were to have said "impressing handsome men with your magic force" would it have been offensive to you? I think you need go grow up. To spell it out for you, the amusement is not from the closing scenario (whichever pronouns and adjectives are selected) but the reduction of grand theory to the relative triviality of human relations. Enjoy your zealous mission... whatever your point was.
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...