sum and product of natural number

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

>-)
Posts: 510
Joined: Tue Apr 24, 2012 1:10 am UTC

sum and product of natural number

Postby >-) » Fri Jul 17, 2015 11:42 pm UTC

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

User avatar
Dopefish
Posts: 854
Joined: Sun Sep 20, 2009 5:46 am UTC
Location: The Well of Wishes

Re: sum and product of natural number

Postby Dopefish » Sat Jul 18, 2015 2:53 am UTC

I don't 'know' the answer, but I'll think aloud (in spoilers in case it's the right idea).

Spoiler:
Call the two natural number a and b. A knows a+b, B knows a*b at first.

If A asks if B knows the numbers and B says yes, then it must mean that a*b=1=a=b or that a*b=p where p is a prime, implying the numbers are 1 and p since they're constrained to natural numbers (which I'm considering to be {1, 2, 3, ...} not {0, 1, 2...,} although the logic would be similar either way). The negative response gives A the knowledge that the numbers are not (1,1), and not of the form (1,p).

B then asks A if they know the numbers, and if they say yes, then it must mean that a+b=4, which implies the numbers are (2,2) since (1,3) is excluded based on the negative response to the first question. The negative response give B the knowledge that the numbers are not (2,2).

A asks B if they know, and if they say yes, it means that a*b=4, which means the numbers are (1,4) since (2,2) is excluded based on the previous negative. The negative response gives A the new knowledge the numbers are not (1,4).

I imagine one could carry on in this manner of slowly gaining knowledge by considering the meta knowledge gained each time the question was asked, but it seems to me that it heavily relies on perfect mathematicians and would quickly get to be a pain to keep straight if a pair of people tried to do it in practice. (I'm also assuming that the sort of reasoning above does keep providing new information that would eventually exclude all the possibilities up to the actual pair of numbers, but it's possible that there's some pairs of numbers of a certain form that wouldn't be excluded based only on the reasoning above [that probably would be excluded if one knew about <insert number theory factoid here>]).

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: sum and product of natural number

Postby quintopia » Sat Jul 18, 2015 1:50 pm UTC

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.

Killerofsheep
Posts: 31
Joined: Sun Apr 13, 2014 3:35 pm UTC

Re: sum and product of natural number

Postby Killerofsheep » Sat Jul 18, 2015 9:45 pm UTC

Dopefish wrote:snip

Spoiler:
If B says yes to the first question, doesn't that mean it could be any number with only two divisors?

If B says no then that excludes a=b=1; all a=p, b=1; a=p1, b=p2. Where p, p1, p2 are prime and p1=!p2

User avatar
jaap
Posts: 2071
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: sum and product of natural number

Postby jaap » Sat Jul 18, 2015 9:53 pm UTC

Killerofsheep wrote:
Dopefish wrote:snip

Spoiler:
If B says yes to the first question, doesn't that mean it could be any number with only two divisors?

If B says no then that excludes a=b=1; all a=p, b=1; a=p1, b=p2. Where p, p1, p2 are prime and p1=!p2

Spoiler:
The number p1*p2 has four divisors, namely 1, p1, p2, and p1*p2 - there are two ways to write it as a product if you ignore the order, namely p1*p2 and (1)*(p1*p2).

User avatar
PeteP
What the peck?
Posts: 1451
Joined: Tue Aug 23, 2011 4:51 pm UTC

Re: sum and product of natural number

Postby PeteP » Sat Jul 18, 2015 9:57 pm UTC

Spoiler:
And two primes wouldn't lead to knowing the numbers in the first step, it still could be a=pi*p2, b=1.

And for 1 and p the other one has the sum if it's p and 1 they just have to subtract 1 from the sum to get p.

Edit: was too slow

>-)
Posts: 510
Joined: Tue Apr 24, 2012 1:10 am UTC

Re: sum and product of natural number

Postby >-) » Sun Jul 19, 2015 12:55 am UTC

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.

Elmach
Posts: 155
Joined: Sun Mar 13, 2011 7:47 am UTC

Re: sum and product of natural number

Postby Elmach » Sun Jul 19, 2015 11:42 am UTC

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 sum-guy (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 prime-square or a prime-cube, 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.

User avatar
mathmannix
Posts: 1401
Joined: Fri Jul 06, 2012 2:12 pm UTC
Location: Washington, DC

Re: sum and product of natural number

Postby mathmannix » Mon Jul 27, 2015 2:47 pm UTC

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.

arbiteroftruth
Posts: 367
Joined: Wed Sep 21, 2011 3:44 am UTC

Re: sum and product of natural number

Postby arbiteroftruth » Mon Jul 27, 2015 6:58 pm UTC

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 meta-knowledge 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 meta-knowledge, 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.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 6 guests