Guess numbers by knowing their sum and product

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
Kurushimi
Posts: 841
Joined: Thu Oct 02, 2008 12:06 am UTC

Guess numbers by knowing their sum and product

Postby Kurushimi » Sun Apr 17, 2011 9:25 pm UTC

I was playing a game with my friend recently. He would pull out some cards at random, four at a time, and I would have to ask some questions with numerical answers to figure out what all the cards were. I could ask for, say, the largest prime divisor of all the cards (where jack = 11, queen = 12, king = 13). One time I decided to ask for the sum and the product of all the cards, and I found that this was enough to figure out the cards uniquely, at least in this case. I was interested in if knowing the sum and the product of a set of positive natural numbers always determines the set uniquely, but am having trouble proving it.

So, if you are given that there are N positive natural numbers, and you know their sum and their product, can you know what all the numbers are?

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

Re: Guess numbers by knowing their sum and product

Postby jaap » Sun Apr 17, 2011 9:42 pm UTC

{2, 2, 3, 8} and {1, 4, 4, 6} have the same sum and product.
So do {3, 4, 4, 9} and {2, 6, 6, 6}.
Of course these are not sets since they do contain some numbers more than once.

Edit: {1, 6, 7, 10} and {2, 3, 5, 14} is a better example with all of them different.
These examples are easy to find if you start with {x, yz, a, bc} and {xy, z, ab, c} which have the same product. For their sum to be equal, you need (y-1)(z-x) = (b-1)(a-c). There is enough freedom to choose the numbers to get them all different.

Sagekilla
Posts: 382
Joined: Fri Aug 21, 2009 1:02 am UTC
Location: Long Island, NY

Re: Guess numbers by knowing their sum and product

Postby Sagekilla » Sun Apr 17, 2011 10:45 pm UTC

This problem is the same as trying to find the diagonal matrix if you know it's trace and determinant.
For example, given Tr(M) = p, Det(M) = q, find the matrix [imath]M = Diagonal(x_1, x_2, ..., x_n)[/imath]

I actually tried to do this in a systematic manner before, but I didn't get far. I'd be interested in any solutions.
http://en.wikipedia.org/wiki/DSV_Alvin#Sinking wrote:Researchers found a cheese sandwich which exhibited no visible signs of decomposition, and was in fact eaten.

User avatar
Kurushimi
Posts: 841
Joined: Thu Oct 02, 2008 12:06 am UTC

Re: Guess numbers by knowing their sum and product

Postby Kurushimi » Sun Apr 17, 2011 10:59 pm UTC

Aw, I see. When I searched for counterexamples, I tried doing it with just three numbers so it would be easier. I even wrote a program on my calculator to check random examples but didn't find any with multiple solutions.

skullturf
Posts: 556
Joined: Thu Dec 07, 2006 8:37 pm UTC
Location: Chicago
Contact:

Re: Guess numbers by knowing their sum and product

Postby skullturf » Sun Apr 17, 2011 11:35 pm UTC

{2,6,6} and {3,3,8} have the same sum and the same product, but I don't know if you can find an example with no repeated elements.

...and after playing around for a while, I found

{4,9,10} and {5,6,12}.

How I found it: Inspired by jaap, I looked for solutions of the form {ax,by,cz} and {bx,cy,az}. For these to have the same sum, we must have

(a-b)x + (b-c)y + (c-a)z = 0.

Note also that (a-b)+(b-c)+(c-a) = 0. I somewhat arbitrarily chose a,b,c = 3,2,1. Then the coefficients a-b, b-c, c-a are 1, 1, -2. One example of x,y,z that works is 3,5,4.

EDIT: Similarly, another example is {2,7,12} and {3,4,14}. I haven't checked to see whether this is "minimal" in some natural sense.

Yesila
Posts: 221
Joined: Sun Dec 16, 2007 11:38 am UTC

Re: Guess numbers by knowing their sum and product

Postby Yesila » Mon Apr 18, 2011 6:22 am UTC

It should be mentioned somewhere in this thread that for N=1 and N=2 the information given is enough to uniquely determine the numbers.

If your willing to ask additional questions you can pick up the N=3 case by also asking for the sum (or product) of any two of the numbers. This allows you to easily find the 3rd number and then modify the product (or sum) of all three numbers to be that of just the two. Then you solve as in the N=2 case.

This same method can be used to move from knowing how to solve N-1 (with some number of questions) to N by the addition of one extra question. So (as expected) asking N questions is enough to find N unknowns. Can we do better? Since you restrict to natural numbers AND the foreknowledge that there is a solution there is at least some information given... is it enough to reduce at least one question when N is high enough?

joelphillips
Posts: 2
Joined: Mon Apr 18, 2011 9:27 am UTC

Re: Guess numbers by knowing their sum and product

Postby joelphillips » Mon Apr 18, 2011 9:42 am UTC

If you're going to try to generalise this to "asking N questions to find N unknowns", you need to carefully define what the permissible questions are. For example, when N=2, if I'm allowed to ask for x + y + 1/(x * y) then I can do it with just one question.

Jyrki
Posts: 117
Joined: Mon Dec 06, 2010 12:27 pm UTC
Location: Rusko, Finland

Re: Guess numbers by knowing their sum and product

Postby Jyrki » Mon Apr 18, 2011 10:23 am UTC

Well. Without any extraneous information we obviously need 4 questions. If the numbers are a,b,c,d, then knowing these numbers is equivalent to knowing the polynomial
[math](x-a)(x-b)(x-c)(x-d)=x^4-s_1x^3+s_2x^2-s_3x+s_4,[/math]
where the coefficients are the basic symmetric polynomials. Of these we note [imath]s_1=a+b+c+d[/imath] and [imath]s_4=abcd.[/imath] For any choice of s2 and s3 the said polynomial has four zeros (in the complex plane), so we can't guess correctly without knowing them, too.

Of course, the way this question was posed, we may infer that a,b,c,d are integers in the range [1,13]. In that case a single question suffices. Select a base [imath]M>13[/imath] (M=1000 will make the following solution obvious, but a smaller base such as 16 may manage to obfuscate the issue better). Then ask your friend to tell you the mystery number (dun... dunn... dunnn...)
[math]E=a+M*b+M^2*c+M^3*d.[/math]

For example with the choices M=1000, a=7, b=5, c=2, d=13 the answer would be E=13002005007. Somehow I don't think that this `solution' will be received too warmly :(

Yeah, so the point I'm trying to make is that we need a better definition for this problem: What kind of questions are allowed? Any limits on the size of the answer? At the other extreme is the case, where you are only allowed to ask yes/no questions. IOW each answer will give you one bit of information. Here it is easy to see that 10 questions will be enough. There are 13*12*11*10/4*3*2*1=715 possible sets of 4 distinct integers in the range [1,13]. We can list them in some order, for example lexicographically, and start asking yes/no questions in the usual forking manner halving the number of remaining alternatives with each question. Here 715<210, so 10 yes/no questions will reduce to a single remaining alternative.

Or did you have something else in mind :twisted: ?

User avatar
Kurushimi
Posts: 841
Joined: Thu Oct 02, 2008 12:06 am UTC

Re: Guess numbers by knowing their sum and product

Postby Kurushimi » Mon Apr 18, 2011 12:06 pm UTC

Yeah, our game wasn't all that strict. We were just doing it to pass time and I tried to avoid asking questions I felt were "cheap", like converting all the cards to a particular number in base M. And I wasn't really sure how to change the rules to make it better.

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Guess numbers by knowing their sum and product

Postby WarDaft » Mon Apr 18, 2011 1:41 pm UTC

Just having the questions unable to reference any particular card or any particular value should do it.

I'm in the middle of pondering how useful the question "what is the product of the sums of the factors of each number?" is.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

joelphillips
Posts: 2
Joined: Mon Apr 18, 2011 9:27 am UTC

Re: Guess numbers by knowing their sum and product

Postby joelphillips » Mon Apr 18, 2011 3:19 pm UTC

WarDaft wrote:Just having the questions unable to reference any particular card or any particular value should do it.


When N = 2, no. See my example above.

For any N > 2 something evil like:
[math]\sum_{i = 0}^\infty 2^{-i} \text{sgn}((\Pi_{j=1}^N (x_j - i))^2)[/math]
would also give you all the [imath]x_j[/imath] with just one question (I'll leave the question: how? as an exercise ...).


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 8 guests