0
$\begingroup$

So I want to solve for a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r which satisfy the following system of equations: ( I only need positive integer (or 0) solution)

a g + c h + b i + g j + i k + h l == 2,

b g + a h + c i + h j + g k + i l == 2,

c g + b h + a i + i j + h k + g l == 2,

d g + f h + e i + j^2 + 2 k l == 4,

e g + d h + f i + 2 j k + l^2 == 3,

f g + e h + d i + k^2 + 2 j l == 3,

a^2 + 2 b c + d g + f h + e i == 4,

2 a b + c^2 + e g + d h + f i == 3,

a d + c e + b f + d j + f k + e l == 2,

b d + a e + c f + e j + d k + f l == 2,

c d + b e + a f + f j + e k + d l == 2,

g m + i n + h o + m p + o q + n r == 2,

h m + g n + i o + n p + m q + o r == 2,

i m + h n + g o + o p + n q + m r == 2,

j m + l n + k o + p^2 + 2 q r == 4,

k m + j n + l o + 2 p q + r^2 == 3,

l m + k n + j o + q^2 + 2 p r == 3,

a + b + c + d + e + f == 4,

g + h + i + j + k + l == 4,

m + n + o + p + q + r == 4

I know that there is a solution (1,1,1,1,0,0,1,0,0,1,1,1,1,1,1,1,0,0). Now I want to find all integer solutions to see if this is unique. I tried to use Mathematica to find solutions, but it takes forever to run it, and it never gave me answer. ( I guess it is because I don't know how to put constraint as conditions ). I wonder if there is anyway to prove the solution is unique without relying on software ?

$\endgroup$
3
  • 4
    $\begingroup$ This question looks like an unreadable soup of letters. If you want any serious consideration, please format this nicely, e.g. using LaTeX commands or in a code environment. This is a necessary condition, but not sufficient, to get an answer here. $\endgroup$
    – David Roberts
    Jun 7, 2013 at 3:57
  • $\begingroup$ I recommend picking one variable, setting it to 0, and see how that affects the system. Perhaps after picking three such variables, Mathematica might handle the rest. Gerhard "Ask Me About System Design" Paseman, 2013.06.06 $\endgroup$ Jun 7, 2013 at 4:23
  • 1
    $\begingroup$ Why is the equation 2ac + b^2 + fg + eh + di = 3 not included? (I'm mainly asking on the off chance it was unintentionally omitted.) $\endgroup$ Jun 7, 2013 at 15:20

3 Answers 3

5
$\begingroup$

You should try to break things down a little rather than simply attempt to use Solve on the full system (which will never finish). For instance, we observe that equations 1 through 11, 18, and 19 involve only the variables a-l. So one should first look at them separately. Next we can eliminate a-c from equations 1-3 and d-f from equations 4-6. Each time we have to assume a determinant is not zero, which leaves the case when it is zero for separate investigation. We can also eliminate l from equation 19. Now insert the result into equations 7-11 and 18. You find that equation 18 is satisfied identically, and all the equations 7-11 reduce to (-3+g+h+i)(-1+g+h+i)=0.

I have not spent the time to pursue things further, but this should get you started.

$\endgroup$
7
$\begingroup$

The last equation gives (9 choose 4) = 126 possibilities for $(m,n,o,p,q,r)$, and similarly the preceding two give 126 possibilities each for $(g,h,i,j,k,l)$ and $(a,b,c,d,e,f)$. That gives just over two million possibilities for $(a,\dotsc,r)$.

To cut this down further, equation 4 gives $j^2\leq 4$ and so $j\leq 2$. Similarly, other equations involving squares give upper bounds of $1$ or $2$ for many other variables. After exploiting that you can just ask Mathematica to search through the remaining possibilities.

Also, you can note that $n^2=n\pmod{2}$ for all $n$, so equation 4 gives $j=dg+fh+ei\pmod{2}$. This approach will enable you to eliminate many variables when solving the equations mod $2$. When you have the solution mod $2$ plus bounds as above, it should not be hard to recover the integral solution.

$\endgroup$
1
  • 8
    $\begingroup$ A gp program ran through the 126^3 possibilities in 27 seconds and produced 10 solutions: (11:44) gp > mo18() found 100111111100100111 found 111001010111111100 found 111010001111111100 found 111100100111002011 found 111100100111011011 found 111100100111020011 found 111100100111101011 found 111100100111110011 found 111100100111111100 found 111100100111200011 time = 26,922 ms. $\endgroup$ Jun 7, 2013 at 10:49
6
$\begingroup$

The following c++ program gives the 10 solutions within 0.2 second on my pc.

// File e18.cc

#include

int main(){

int NumberSolution =0;

for(int a = 0; a<=4; a++)

for(int b = 0; b<=4-a; b++)

for(int c = 0; c<=4-a-b; c++)

for(int d = 0; d<=4-a-b-c; d++)

for(int e = 0; e<=4-a-b-c-d; e++)

for(int g = 0; g<=4; g++)

for(int h = 0; h<=4-g; h++)

for(int i = 0; i<=4-g-h; i++)

for(int j = 0; j<=4-g-h-i; j++)

for(int k = 0; k<=4-g-h-i-j; k++)

for(int m = 0; m<=4; m++)

for(int n = 0; n<=4-m; n++)

for(int o = 0; o<=4-m-n; o++)

for(int p = 0; p<=4-m-n-o; p++)

for(int q = 0; q<=4-m-n-o-p; q++){

int f = 4-a-b-c-d-e;

int r = 4-m-n-o-p-q;

int l = 4-g-h-i-j-k;

// 2,176,782,336

if(a*g + c*h + b*i + g*j + i*k + h*l != 2)continue; //1,541,820

if(b*g + a*h + c*i + h*j + g*k + i*l != 2)continue; //422,730

if(c*g + b*h + a*i + i*j + h*k + g*l != 2)continue; //150,570

if(d*g + f*h + e*i + j*j + 2*k*l != 4)continue; //22,680

if(e*g + d*h + f*i + 2*j*k + l*l != 3)continue; // 10,080

if(f*g + e*h + d*i + k*k + 2*j*l != 3)continue; //8,820

if(a*a + 2*b*c + d*g + f*h + e*i != 4)continue; //2,730

if(2*a*b + c*c + e*g + d*h + f*i != 3)continue; //2,730

if(a*d + c*e + b*f + d*j + f*k + e*l != 2)continue; //1,260

if(b*d + a*e + c*f + e*j + d*k + f*l != 2)continue; //840

if(c*d + b*e + a*f + f*j + e*k + d*l != 2)continue; //840

if(g*m + i*n + h*o + m*p + o*q + n*r != 2)continue; //192

if(h*m + g*n + i*o + n*p + m*q + o*r != 2)continue; //63

if(i*m + h*n + g*o + o*p + n*q + m*r != 2)continue; //36

if(j*m + l*n + k*o + p*p + 2*q*r != 4)continue; // 10

if(k*m + j*n + l*o + 2*p*q + r*r != 3)continue; //10

if(l*m + k*n + j*o + q*q + 2*p*r != 3)continue; // 10

NumberSolution++;

printf("%d   %d %d %d %d %d %d  %d %d %d %d %d %d  %d %d %d %d %d %d \n", 

   NumberSolution, a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r);

}

return 0;

}


$ g++ e18.cc -o e18

$ time e18

1 1 0 0 1 1 1 1 1 1 1 0 0 1 0 0 1 1 1

2 1 1 1 0 0 1 0 1 0 1 1 1 1 1 1 1 0 0

3 1 1 1 0 1 0 0 0 1 1 1 1 1 1 1 1 0 0

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

5 1 1 1 1 0 0 1 0 0 1 1 1 0 1 1 0 1 1

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

7 1 1 1 1 0 0 1 0 0 1 1 1 1 0 1 0 1 1

8 1 1 1 1 0 0 1 0 0 1 1 1 1 1 0 0 1 1

9 1 1 1 1 0 0 1 0 0 1 1 1 1 1 1 1 0 0

10 1 1 1 1 0 0 1 0 0 1 1 1 2 0 0 0 1 1

real 0m0.178s

user 0m0.108s

sys 0m0.046s


$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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