Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 ?

share|improve this question
4  
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. –  David Roberts Jun 7 '13 at 3:57
    
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 –  Gerhard Paseman Jun 7 '13 at 4:23
    
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.) –  Barry Cipra Jun 7 '13 at 15:20
add comment

3 Answers

up vote 4 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
7  
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. –  Chris Stretch Jun 7 '13 at 10:49
add comment

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


share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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