0
$\begingroup$

How to find the exact number of non-negative integer solutions of the following set of equations :

$$x_1 + x_2 + x_3 + x_4 + x_5 + x_6=6 $$ $$ 2x_1 + x_2 + x_3 = 4$$ $$ x_2 + 2x_4 + x_5 = 4$$ $$ x_3 + x_5 +2x_6 =4$$

$\endgroup$
9
  • $\begingroup$ This is counting lattice points in polytopes. You can google for this beautiful theory. Concrete instances such as the one you are giving can be solved with the software Latte: math.ucdavis.edu/~latte $\endgroup$ Feb 6, 2013 at 9:17
  • 4
    $\begingroup$ Could you please provide some motivation for this particular problem. I mean this one is a bit smallish, so I do not see what should be the problem about solving this particular one. Even the simplest of all ideas (use 1. to find 0<= xi <=6 and check the 7^6 possibilities by brute force) is perfectly feasible. So if this is not an instance of a general problem or has a clear research motivation it is offtopic. You could ask it on math.stackeexchange.com though. $\endgroup$
    – user9072
    Feb 6, 2013 at 9:24
  • $\begingroup$ 7^6 is "smallish" !!!!! anyway i want to solve for n. So, want a general approach $\endgroup$
    – aaaaaa
    Feb 6, 2013 at 10:46
  • $\begingroup$ It's about 10^5 that's really very smallish (for a computer). But, even to solve it by hand in an ad-hoc way seems feasible (by slightly intelligent brute force). But more immportantly what do you mean by "you want to solve for n"? Is 3n and 2n instead of 6 and 4 (and perhaps n for 2 or not), or n variables, in which form precisely, or still something different. Please formulate a precise question. $\endgroup$
    – user9072
    Feb 6, 2013 at 10:56
  • $\begingroup$ Note that the first equation can be ignored. It is the sum of the other three, divided by 2. $\endgroup$ Feb 6, 2013 at 13:28

1 Answer 1

3
$\begingroup$

This is going to be closed, but I'll answer anyway: Here's how to solve your problem using 'zsolve' from 4ti2 (according to the manual www.4ti2.de/4ti2_manual.pdf)

To solve a linear system $Ax = b$ under nonnegativity $x\in\mathbb{N}_0^n$ create a file A.mat with the matrix:

4 6
1 1 1 1 1 1
2 1 1 0 0 0
0 1 0 2 1 0
0 0 1 0 1 2

The first two rows are the dimensions. Then create A.rhs to save the right hand side (as a row vector):

1 4
6 4 4 4

Finally, create A.sign to encode non-negativity (there are other choices too...)

1 6 
1 1 1 1 1 1

Now run

zsolve A

Voilà, the file A.zinhom contains your 15 points:

15 6

2  0  0  0  4  0
1  0  2  1  2  0
2  0  0  2  0  2
0  4  0  0  0  2
0  3  1  0  1  1
0  2  2  1  0  1
0  2  2  0  2  0
0  1  3  1  1  0
0  0  4  2  0  0
1  1  1  0  3  0
1  0  2  2  0  1
1  1  1  1  1  1
2  0  0  1  2  1
1  2  0  1  0  2
1  2  0  0  2  1
$\endgroup$
1
  • $\begingroup$ Interesting to see +1. I had heard of that software but to see an example is somehow nice. (If only OP had asked a slightly more general question...) $\endgroup$
    – user9072
    Feb 6, 2013 at 9:47

Not the answer you're looking for? Browse other questions tagged or ask your own question.