0
$\begingroup$

We've been stumped by a much larger version of this problem, but we have simplified it down to a simple example:

| A | B | 3 --------- | C | D | 7 ---------   4   6  

The constraints are simple:

  • The numbers are the sums of the variables in the line (A+B=3, C+D=7, A+C=4, B+D=6)
  • The variables will be positive numbers
  • This is obviously a very easy example, but we're trying to apply it to huge grids so brute force isn't an option

So can somebody help us solve this, or give us an example of a similar problem?

2 Answers 2

4

The system doesn’t have a unique solution, even in integers. Both $a=1,b=2,c=3,d=4$ and $a=2,b=1,c=2,d=5$ are solutions. The same is true of larger systems.

  • 1
    @Travis: In general you’re going to have $2n-1$ independent equations in $n^2$ variables. For large $n$ that’s going to allow an enormous amount of freedom. But at this point I’m not even really sure what you’re trying to do; are you looking for an algorithm to find at least one solution? At least one **integer** solution?2012-08-17
1

Pick one variable arbitrarily, say $A$. Then using 3 of the four equations to get $B = 3 - A$, $C = 4 - A$ and $D = 6 - B = 6 - (3 - A) = 3 + A$. Check if these values satisfy the other equation: $C + D = (4 - A) + (3 + A) = 7$. We see that all four equations are satisfied by $(A, B, C, D) = (A, 3 - A, 4 - A, 3 + A)$ for any $A$. This is the complete set of solutions.

  • 0
    You have to be a little more careful than that in order to ensure that the solution is positive. And if n>2, you’ll have to fix more than one of the variables.2012-08-17