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?
Guess numbers by knowing their sum and product
Moderators: gmalivuk, Moderators General, Prelates
Re: Guess numbers by knowing their sum and product
{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 (y1)(zx) = (b1)(ac). There is enough freedom to choose the numbers to get them all different.
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 (y1)(zx) = (b1)(ac). There is enough freedom to choose the numbers to get them all different.
Re: Guess numbers by knowing their sum and product
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.
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.
Re: Guess numbers by knowing their sum and product
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.
Re: Guess numbers by knowing their sum and product
{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
(ab)x + (bc)y + (ca)z = 0.
Note also that (ab)+(bc)+(ca) = 0. I somewhat arbitrarily chose a,b,c = 3,2,1. Then the coefficients ab, bc, ca 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.
...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
(ab)x + (bc)y + (ca)z = 0.
Note also that (ab)+(bc)+(ca) = 0. I somewhat arbitrarily chose a,b,c = 3,2,1. Then the coefficients ab, bc, ca 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.
Re: Guess numbers by knowing their sum and product
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 N1 (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?
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 N1 (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?

 Posts: 2
 Joined: Mon Apr 18, 2011 9:27 am UTC
Re: Guess numbers by knowing their sum and product
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.
Re: Guess numbers by knowing their sum and product
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](xa)(xb)(xc)(xd)=x^4s_1x^3+s_2x^2s_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 s_{2} and s_{3} 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<2^{10}, so 10 yes/no questions will reduce to a single remaining alternative.
Or did you have something else in mind ?
[math](xa)(xb)(xc)(xd)=x^4s_1x^3+s_2x^2s_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 s_{2} and s_{3} 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<2^{10}, so 10 yes/no questions will reduce to a single remaining alternative.
Or did you have something else in mind ?
Re: Guess numbers by knowing their sum and product
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.
Re: Guess numbers by knowing their sum and product
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.
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.

 Posts: 2
 Joined: Mon Apr 18, 2011 9:27 am UTC
Re: Guess numbers by knowing their sum and product
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 ...).
Who is online
Users browsing this forum: No registered users and 8 guests