2
$\begingroup$

$$M = \left(\begin{smallmatrix} a_1 & a_2 & a_3 & a_4\\ b_1 & b_2 & b_3 & b_4\\ a_1 & c_2 & b_2 & c_4\\ a_4 & d_2 & b_3 & c_4\\ b_1 & c_2 & a_2 & e_4\\ b_4 & d_2 & a_3 & e_4\end{smallmatrix}\right)$$ All of the equations equal to 26; augmented, the matrix would then have have "26" to the right of each row.

This is basically the "Star of David" that another user posted:

http://i.stack.imgur.com/mVHwZ.jpg

but I don't think anyone has solved it like this.

$\endgroup$
  • 1
    $\begingroup$ The figure has 2 axes of symmetry. $\endgroup$ – BPP Sep 20 '13 at 13:16
3
$\begingroup$

You have forgotten the very important condition that all integers between 1 and 12 must be used exactly once.

Though the equations themselves are linear and contain only 0 and 1 as coefficients, the constraint is very tough. I don't think you could find an easy solution without integer programming, which is, like you may have known, NP-Hard and thus we have by now only exponential solutions, which are not better than brute force for such a small problem.

$\endgroup$
  • $\begingroup$ There are only twelve variables. $\endgroup$ – Don Larynx Sep 20 '13 at 13:55
  • $\begingroup$ @Jossie That's true. So...what's your point? $\endgroup$ – ftfish Sep 20 '13 at 13:58
2
$\begingroup$

As I see, there are $960$ solutions ($80$ different solutions, ignoring rotation and mirror-transformation).

For example, $2$ of them:

enter image description here

enter image description here

Way of solving: "try-and-check".

enter image description here

A). Consider any values $a,h$. For example, $a=5,h=6$.

Then possible values for $i,c$ are:
- $3,12$;
- $4,11$;
- $7,8$;
- $8,7$;
- $11,4$;
- $12,3$.

For these values you'll get system of $5$ equations for $8$ variables. Reduction of system. Sometimes such system will have no solutions.

B). Consider $3$ any values for cells $a,c,e$. Choose values for $b,d,f$, such that $a+c+e=b+d+f$.

When we'll have values for $a,b,c,d,e,f$, we'll get system of $6$ equations for $6$ variables ($g,h,i,j,k,l$).

But such system can have no solutions.


If you'll use brute computer search, then there is not so much permutations of $12$ numbers: $12! = 479~001~600$ (a few seconds of computer work).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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