For the "find N given all the sums of N-1", you add up the values and divide by N-1, to get the sum of all N. Then subtract each sum of N-1 to get the individual numbers. In your example, 22+24+27+20 = 93, so the sum of all 4 numbers is 93/3 = 31. Your numbers are 31-{22,24,27,20} = {9,7,4,11}. For the 4:2 example, it gets more interesting. First, there are only 4 unknowns, and 6 values given. So there are some constraints on the values. In this case, they must be arrangeable in three pairs that add to the same thing. We can discover the sum of all 4 unknowns by adding and dividing, as before. The sum of the inputs is 117, and the sum of the 4 unknowns is 117/3 = 39. So our groups are 14+25 = 12+27 = 23+16, and the two extra degrees of freedom are happy. If we know which combinations go into each sum, we can reduce to a simpler problem by merely dropping out enough variables to get to a K:K-1 situation and solving as above. So I'll guess that your sums are A+B, A+C, A+D, B+C, B+D, C+D. Dropping the first three, (B+C)+(B+D)+(C+D) = 16+27+25 = 68; B+C+D = 34; B = 9, C = 7, D = 18; then A = 5 works for the first three inputs. If the sums are given in arbitrary order, I'd suspect an NPC puzzle, without any specific evidence. If the set of sums is incomplete, with some inputs omitted, it seems like an ordinary simultaneous linear equations problem. If we go over to non-commutative groups, it could get hard. For example, we might be multiplying unit quaternions (either real or rational coefficients), or elements from a permutation group. Rich -----Original Message----- From: math-fun-bounces@mailman.xmission.com [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of Thane Plambeck Sent: Monday, October 13, 2008 11:30 PM To: math-fun Subject: [math-fun] what's the best way of finding n unknown integers from their sums taken k at a time In WW Rouse Ball's A short account of the history of mathematics he gives the following "characteristic problem from Diophantus": Find four numbers, the sum of every arrangement 3 at a time being given; say 22, 24, 27, 20. What about Find four numbers, the sum of every arrangement two at a time being given, say 14, 12, 23, 16, 27, 25 ? I'm interested in what work might have been done on problems like this. I'm particularly interested in the good algorithms for such problems. Hard, easy, or what? -- Thane Plambeck tplambeck@gmail.com http://www.plambeck.org/ehome.htm _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun