I was reading this post: https://mathoverflow.net/questions/9754 ... 1656#31656
But I'm a bit confused what the apparent "strategy" is. Can anyone explain how the mathematicians can figure out what number it is?
I think it may be related to another puzzle here: https://puzzling.stackexchange.com/ques ... ematicians
sum and product of natural number
Moderators: gmalivuk, Moderators General, Prelates
Re: sum and product of natural number
I don't 'know' the answer, but I'll think aloud (in spoilers in case it's the right idea).
Spoiler:
Re: sum and product of natural number
That there never comes a time where the reason one doesn't know the numbers becomes ambiguous, and therefore which numbers to exclude becomes impossible to guess, would require careful proof.

 Posts: 31
 Joined: Sun Apr 13, 2014 3:35 pm UTC
Re: sum and product of natural number
Dopefish wrote:snip
Spoiler:
Re: sum and product of natural number
Killerofsheep wrote:Dopefish wrote:snipSpoiler:
Spoiler:
Re: sum and product of natural number
Spoiler:
Edit: was too slow
Re: sum and product of natural number
I understand it a bit more now  though thinking about it hurts my brain. I was hoping to compute the pair as a function of the number of times the mathematicians ask each other but that seems out of the question now.
Re: sum and product of natural number
This problem is similar to an old problem in this other thread.
Edit: most of my logic is based off of neither number being one. Hard to edit on mobile device. Easy to add text, though.
If both need to find the number, then it is impossible: (3,3) and (2,4) are indistinguishable for the sumguy (S),but P knows them in both cases only true in the a,b neq 1 version.
My thoughts on this problem:
If natural numbers include zero, then you have  P: I only know one number; S: I know the numbers.
If the product is prime or one , P knows the numbers. After that, S knows the numbers.
If the product is semiprime or a primesquare or a primecube, then P knows the numbers.
: wrote edit above. Also added second part of post below.
It is hard to think about S in abstract. I also forgot much of what I was going to say.
The first case I wrote above has P have an infinite number of possible numbers to choose. S, of course, will then know the numbers.
The second case gives P a single possibility. P clearly knows the numbers.
The third case gives P two possibilities. Narrowing this down will require more concrete information. P just needs to get one but of information, which might be hard.
P has always starts with more information (less possibilities).
Proof:
The number of possibilities for a product is the number of divisors over two rounded up. This is less than the geometric mean of the two numbers (aka sqrt of product) which is, of course, less than the arithmetic mean of the two numbers.
The number of possibilities for a sum is the number over two rounded up. That is, the arithmetic mean.
P clearly has more information at the start. I think that means P should give the first message.
The first level of indirection (I (don't) know that you (don't) know the numbers) is hard to think about without concrete examples.
Edit: most of my logic is based off of neither number being one. Hard to edit on mobile device. Easy to add text, though.
If both need to find the number, then it is impossible: (3,3) and (2,4) are indistinguishable for the sumguy (S),
My thoughts on this problem:
If natural numbers include zero, then you have  P: I only know one number; S: I know the numbers.
If the product is prime or one , P knows the numbers. After that, S knows the numbers.
If the product is semiprime or a primesquare or a primecube, then P knows the numbers.
: wrote edit above. Also added second part of post below.
It is hard to think about S in abstract. I also forgot much of what I was going to say.
The first case I wrote above has P have an infinite number of possible numbers to choose. S, of course, will then know the numbers.
The second case gives P a single possibility. P clearly knows the numbers.
The third case gives P two possibilities. Narrowing this down will require more concrete information. P just needs to get one but of information, which might be hard.
P has always starts with more information (less possibilities).
Proof:
The number of possibilities for a product is the number of divisors over two rounded up. This is less than the geometric mean of the two numbers (aka sqrt of product) which is, of course, less than the arithmetic mean of the two numbers.
The number of possibilities for a sum is the number over two rounded up. That is, the arithmetic mean.
P clearly has more information at the start. I think that means P should give the first message.
The first level of indirection (I (don't) know that you (don't) know the numbers) is hard to think about without concrete examples.
 mathmannix
 Posts: 1453
 Joined: Fri Jul 06, 2012 2:12 pm UTC
 Location: Washington, DC
Re: sum and product of natural number
I'm trying to work it out and struggling even with simple cases like (2,3) or (3,3). But it seems to be like the xkcd hardest logic puzzle in the world, where you have a chain of "I know that he knows that I know..." that eventually collapses? Somehow?
I hear velociraptor tastes like chicken.

 Posts: 481
 Joined: Wed Sep 21, 2011 3:44 am UTC
Re: sum and product of natural number
I'm pretty sure it's impossible as written, even excluding the use of 0. Product guy ("P") knows the numbers directly if he is given a prime or 1. Sum guy ("S") knows the numbers directly if he is given 2 or 3, which are both prime anyway, so we can focus of the condition where P directly knows the number.
Both P and S can speculate about all possible pairs that work given their knowledge, and then about all the pairs that every possible version of their counterpart would consider, and then about all the pairs considered by the possible counterparts considered by the possible counterparts, and so on. In this way they might hope to gain knowledge about how many layers of metaknowledge there are before some hypothetical version of P knows the answers. But as phrased, S only gets to ask P whether P knows the numbers, not whether P knows whether S knows whether P knows the numbers, and so on. They only get that information if it happens to be equivalent to knowing the numbers at a certain stage, which is only the case when there's only one way for them not to know the numbers.
Given this, they can know (1,1) and (1,2) trivially. If P is given 3, then P knows it's (1,3). If S is given 4 and P doesn't know, that rules out (1,3) and S knows it's (2,2). If P is given 4, and S doesn't know even after learning that P doesn't know, that rules out (2,2) and P knows it's (1,4). If S is given 5, and P doesn't know even after learning that S doesn't know even after learning that P doesn't know, that rules out (1,4) and S knows it's (2,3). Finally, by similar logic, if P is given 6, he can eventually rule out (2,3) and know that it's (1,6). But that's the end of the line. If S is given 7, he can eventually rule out (1,6), but there are still two options left: (2,5) and (3,4). For all primes higher than 3, ruling out (1,p) still leaves S with at least two remaining options. At that point, knowing that S doesn't know the numbers isn't the same as knowing that S doesn't know whether P knows whether S knows...
But if they are instead allowed to directly ask about metaknowledge, then it should be possible. Make a tree of versions of P and S connected by whether each sees the other as a possible counterpart, find yourself, find the shortest path along the tree to a version of P that knows the answers, and ask an appropriate metaknowledge question that tells you whether your counterpart also sees the path of that same length. This should be able to eliminate one possible counterpart per question and eventually give you the answer.
Both P and S can speculate about all possible pairs that work given their knowledge, and then about all the pairs that every possible version of their counterpart would consider, and then about all the pairs considered by the possible counterparts considered by the possible counterparts, and so on. In this way they might hope to gain knowledge about how many layers of metaknowledge there are before some hypothetical version of P knows the answers. But as phrased, S only gets to ask P whether P knows the numbers, not whether P knows whether S knows whether P knows the numbers, and so on. They only get that information if it happens to be equivalent to knowing the numbers at a certain stage, which is only the case when there's only one way for them not to know the numbers.
Given this, they can know (1,1) and (1,2) trivially. If P is given 3, then P knows it's (1,3). If S is given 4 and P doesn't know, that rules out (1,3) and S knows it's (2,2). If P is given 4, and S doesn't know even after learning that P doesn't know, that rules out (2,2) and P knows it's (1,4). If S is given 5, and P doesn't know even after learning that S doesn't know even after learning that P doesn't know, that rules out (1,4) and S knows it's (2,3). Finally, by similar logic, if P is given 6, he can eventually rule out (2,3) and know that it's (1,6). But that's the end of the line. If S is given 7, he can eventually rule out (1,6), but there are still two options left: (2,5) and (3,4). For all primes higher than 3, ruling out (1,p) still leaves S with at least two remaining options. At that point, knowing that S doesn't know the numbers isn't the same as knowing that S doesn't know whether P knows whether S knows...
But if they are instead allowed to directly ask about metaknowledge, then it should be possible. Make a tree of versions of P and S connected by whether each sees the other as a possible counterpart, find yourself, find the shortest path along the tree to a version of P that knows the answers, and ask an appropriate metaknowledge question that tells you whether your counterpart also sees the path of that same length. This should be able to eliminate one possible counterpart per question and eventually give you the answer.
Who is online
Users browsing this forum: Bing [Bot] and 8 guests