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$$
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$– Thomas KahleCommented 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$– user9072Commented Feb 6, 2013 at 9:24
-
$\begingroup$ 7^6 is "smallish" !!!!! anyway i want to solve for n. So, want a general approach $\endgroup$– aaaaaaCommented 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$– user9072Commented 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$– Barry CipraCommented Feb 6, 2013 at 13:28
|
Show 4 more comments
1 Answer
$\begingroup$
$\endgroup$
1
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
-
$\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$– user9072Commented Feb 6, 2013 at 9:47