4
$\begingroup$

I have the following problem:

Find all $a_1,a_2,a_3,....,a_{10} \in\{1,2,3,...,10\}$ satisfying
$\hspace{2cm}\begin{align} a_1+a_2+a_3 &=k\\ a_3+a_4+a_5 &=k\\ a_5+a_6+a_7 &=k\\ a_7+a_8+a_1 &=k \\ a_1+a_9+a_5 &=k \\ a_7+a_{10}+a_3 &=k \end{align} $
where $k$ is a constant positive integer.

I am really stuck on this problem how to solve these $6$ equations to find the ten unknowns.Please help me.

Thanks.

$\endgroup$
  • 1
    $\begingroup$ Could all of the a's = (k/3)? $\endgroup$ – Julian Jefko Feb 7 '15 at 18:10
  • $\begingroup$ @Julian Jefko: Should $k/3\in\{1,2,\cdots,10\}$? $\endgroup$ – supremum Feb 7 '15 at 18:16
3
+100
$\begingroup$

There's 25420 solutions, for various k between 3 and 30. Definitely not the most elegant, but my way is to enumerate them all with a program. Following is a C program that does it.

void enumerate() {
int k, a1, a2, a3, a4, a5, a6, a7, a8, a9, a10;

for (k = 3; k <= 30; k++) {
    for (a1 = 1; a1 <= 10; a1++)
        for (a2 = 1; a2 <= 10; a2++) {
            a3 = k - a2 - a1;
            if (a3 > 0 && a3 <= 10)
                for (a4 = 1; a4 <= 10; a4++) {
                    a5 = k - a3 - a4;
                    if (a5 > 0 && a5 <= 10)
                        for (a6 = 1; a6 <= 10; a6++) {
                            a7 = k - a5 - a6;
                            a8 = k - a7 - a1;
                            a9 = k - a5 - a1;
                            a10 = k - a7 - a3;
                            if ((a7 > 0 && a7 <= 10) && (a8 > 0 && a8 <= 10)
                                    && (a9 > 0 && a9 <= 10)
                                    && (a10 > 0 && a10 <= 10)) {
                                cout << "a1 " << a1 << ", a2 " << a2
                                        << ", a3 " << a3 << ", a4 " << a4
                                        << ", a5 " << a5 << ", ";
                                cout << "a6 " << a6 << ", a7 " << a7
                                        << ", a8 " << a8 << ", a9 " << a9
                                        << ", a10 " << a10 << ", ";
                                cout << "k " << k << endl;
} } } } } }
$\endgroup$
2
$\begingroup$

Since you have ten variables (not counting $k$) and six equations, you can choose $10-6=4$ variables to be your "base" variables, for which you can choose any value, and then you can use one of several techniques to find equations for the other six variables in terms of those four base variables. Choose values for those base variables and the equations will quickly tell you the values of the other variable.

For example, you could use elimination of variables to solve for $a_1,a_2,a_3,a_4,a_5,$ and $a_6$ in terms of $a_7,a_8,a_9,a_{10},$ and $k$.

Here are two examples.

Your fourth equation immediately tells us that

$$a_1=-a_7-a_8+k$$

The first equation minus the fourth then minus the sixth tells us that

$$a_2=2a_7+a_8+a_{10}-k$$

And so on. If you need a systematic way to get the formulas for $a_3$ through $a_6$, use Gauss-Jordan elimination. Or let us know you need more help, after you show that you have done more work on your own.


Here are more details.

What we really care about are the constants and the coefficients of the variables. So we rewrite the equations to show the coefficients of all the variables, including the ones not present in the given equations. For example, we rewrite the first equation to:

$$1\cdot a_1+1\cdot a_2+1\cdot a_3+0\cdot a_4+0\cdot a_5+0\cdot a_6+0\cdot a_7+0\cdot a_8+0\cdot a_9+0\cdot a_{10} =1\cdot k$$

Writing this many times would be tiresome, so we just remove the variables and place the coefficients in an augmented matrix. The matrix will have $6$ rows, one for each equation, and $10$ columns before the augment, one for each variable, and $1$ column after the augment, for the constant term. The matrix will then be:

$$ \left[\begin{array}{rrrrrrrrrr|r} 1& 1& 1& 0& 0& 0& 0& 0& 0& 0& 1\\ 0& 0& 1& 1& 1& 0& 0& 0& 0& 0& 1\\ 0& 0& 0& 0& 1& 1& 1& 0& 0& 0& 1\\ 1& 0& 0& 0& 0& 0& 1& 1& 0& 0& 1\\ 1& 0& 0& 0& 1& 0& 0& 0& 1& 0& 1\\ 0& 0& 1& 0& 0& 0& 1& 0& 0& 1& 1\\ \end{array}\right] $$

We will now use linear elimination to change this matrix to an easy form. We want to end up with equations like

$$a_1=-a_7-a_8+k$$

where the variable $a_1$ is not in any other equation. This means we want the matrix to have a $1$ in an entry where all other entries in that column are $0$.

Now to choose the $6$ variable that will be defined in terms of the base variables. There are two main choices. We could choose the simplest variables out of the $10$ variables. As Joffan pointed out in his answer, we could choose the variables to make the work easier. However, in this case let us do it the "standard" way and choose the first six variables $a_1$ through $a_6$ to be defined in terms of the last four variables $a_7$ through $a_{10}$.

There are several $1$'s in the first column. We choose to use the fourth row to eliminate the other rows since its $1$ is followed by many zeros. (This choice was not necessary but it allows us to do fewer steps.) We can remove another non-zero entry in the same column, say in the n'th row, by multiplying the fourth row by an appropriate number and adding that to the n'th row. In our case, to remove the $1$ in the first row first entry we multiply the fourth row by $-1$ and add that to the first row, leaving the fourth row unchanged. We do the same to the fifth row to remove its leading $1$. That gives us the matrix

$$ \left[\begin{array}{rrrrrrrrrr|r} 0& 1& 1& 0& 0& 0&-1&-1& 0& 0& 0\\ 0& 0& 1& 1& 1& 0& 0& 0& 0& 0& 1\\ 0& 0& 0& 0& 1& 1& 1& 0& 0& 0& 1\\ (1)& 0& 0& 0& 0& 0& 1& 1& 0& 0& 1\\ 0& 0& 0& 0& 1& 0&-1&-1& 1& 0& 1\\ 0& 0& 1& 0& 0& 0& 1& 0& 0& 1& 1\\ \end{array}\right] $$

I marked the fourth row first entry with parentheses to show that it was the "pivot" for this operation. We now have only one $1$ in the first and second columns. We choose one of the $1$'s in the third column to eliminate the others: we choose the $6$th row for its many zeros. We multiply that sixth row by $-1$ and add to the first and second rows, and we get

$$ \left[\begin{array}{rrrrrrrrrr|r} 0& 1& 0& 0& 0& 0&-2&-1& 0&-1&-1\\ 0& 0& 0& 1& 1& 0&-1& 0& 0&-1& 0\\ 0& 0& 0& 0& 1& 1& 1& 0& 0& 0& 1\\ 1& 0& 0& 0& 0& 0& 1& 1& 0& 0& 1\\ 0& 0& 0& 0& 1& 0&-1&-1& 1& 0& 1\\ 0& 0& 1& 0& 0& 0& 1& 0& 0& 1& 1\\ \end{array}\right] $$

The fourth column has only one zero. We choose the fifth row to eliminate the others. Multiplying by $-1$ and adding to the second and third row gives us

$$ \left[\begin{array}{rrrrrrrrrr|r} 0& 1& 0& 0& 0& 0&-2&-1& 0&-1&-1\\ 0& 0& 0& 1& 0& 0& 0& 1&-1&-1& 0\\ 0& 0& 0& 0& 0& 1& 2& 1&-1& 0& 1\\ 1& 0& 0& 0& 0& 0& 1& 1& 0& 0& 1\\ 0& 0& 0& 0& 1& 0&-1&-1& 1& 0& 1\\ 0& 0& 1& 0& 0& 0& 1& 0& 0& 1& 1\\ \end{array}\right] $$

Columns $1$ through $6$ now have one $1$ and those $1$'s are in different rows. That is what we wanted! We now rearrange the rows to get a nice diagonal of $1$'s and add a clarifying vertical line:

$$ \left[\begin{array}{rrrrrr|rrrr|r} 1& 0& 0& 0& 0& 0& 1& 1& 0& 0& 1\\ 0& 1& 0& 0& 0& 0&-2&-1& 0&-1&-1\\ 0& 0& 1& 0& 0& 0& 1& 0& 0& 1& 1\\ 0& 0& 0& 1& 0& 0& 0& 1&-1&-1& 0\\ 0& 0& 0& 0& 1& 0&-1&-1& 1& 0& 1\\ 0& 0& 0& 0& 0& 1& 2& 1&-1& 0& 1\\ \end{array}\right] $$

We now interpret the matrix. The first row means

$$1\cdot a_1+0\cdot a_2+0\cdot a_3+0\cdot a_4+0\cdot a_5+0\cdot a_6+1\cdot a_7+1\cdot a_8+0\cdot a_9+0\cdot a_{10} =1\cdot k$$

Simplifying and rewriting this to define $a_1$ in terms of the others,

$$a_1=-a_7-a_8+k$$

You see the pattern: The $1$ in the first six columns tell us the variable on the left hand side of the equation; we reverse the signs of the entries in the next four columns and put them on the right hand side; the last column is the coefficient of $k$.

Putting this all together, we get the final solution

$$a_1=-a_7-a_8+k$$ $$a_2=2a_7+a_8+a_{10}-k$$ $$a_3=-a_7-a_{10}+k$$ $$a_4=-a_8+a_9+a_{10}$$ $$a_5=a_7+a_8-a_9+k$$ $$a_6=-2a_7-a_8+a_9+k$$

This procedure could fail, and I left out some details, but I think you get the idea.

$\endgroup$
2
$\begingroup$

Note that every one of your equations has a free variable - $a_2, a_4, a_6, a_8, a_9, a_{10}$ each only appear in one equation.

The remaining variables, $a_1, a_3, a_5, a_7$ each appear paired together with every other member of that group, appearing in three equations each.

The possible answers depend on $k$, of course, but it's important that every pairing in the second group allows solution with another variable from the specified numeric range.


Expanding a little on these observations, any choice of $a_1, a_3, a_5, a_7$ leads a number of possible values for $k$ (from zero to ten options), which then determines the values of the other $6$ variables. If we call the values for these four key variables $b,c,e,f,$ with $b\le c\le e\le f$, we can have $(10-((f+e)-(c+b)))$ possible values of $k$, or zero if that is greater. We can also have all four values equal (the only route to $10$ possible values of $k$), three equal, two pairs equal, one pair equal, or all different, which will affect the number of different ways we can allocate any particular $\{b,c,e,f\}$ to $\{a_1,a_3,a_5,a_7\}$.

If now we set $d_1=c-b, d_2=e-c, d_3=f-e$, the "reduction" part of the $(10-((f+e)-(c+b)))$ formula for how many possible $k$s we can have,

$\begin{align}((f+e)-(c+b)) &= (b+d_1+d_2+d_3+b+d_1+d_2) - (b+d_1+b)\\ &=d_1 + 2d_2+d_3 \end{align}$

So a "middle difference", $d_2$, of $5$ or more will give us no values for $k$. $d_2=4$ allows $1$ or $2$ possible values for $k$, etc.

For each possible pattern of $\{d_1,d_2,d_3\}$, $b$ can have values from $1$ to $(10-(d_1+d_2+d_3))$. Special cases for allocation to the base variables are when $d_1=0$ or $d_3-0$ or both. An example of a non-special case might be $d_2=2$, with $d_1+d_3=4$, giving $4-1= 3$ all-positive patterns, $4$ possible values for $b$, giving $3\times 4=12$ options across $(d_1,d_3,b)$ each allocated $4!=24$ ways to the base variables with $10-(2\times2+4) = 2$ values for $k$, for a total of $24\times 12 \times 2 = 576$ possible solutions from this.

So we should be able to make a large table fairly straightforwardly from there - the number of cases for $(d_1,d_3,b,k)$ has some extra work within it though. Here is what I have:

$$\begin{array}{c|c|c} d_2 & \text{max }d_1+d_3 & d_1,d_3\text{ zeros} & \text{cases}(d_1,d_3,b,k) & \frac{\text{allocations}}{\text{case}} & \text{total}\\ \hline 4 & 1 & 1 & 10 & 12 & 120 \\ \hline 4 & 0 & 2 & 12 & 6 & 72 \\ \hline 3 & 3 & 0 & 18 & 24 & 432 \\ \hline 3 & 3 & 1 & 64 & 12 & 768 \\ \hline 3 & 0 & 2 & 28 & 6 & 168 \\ \hline 2 & 5 & 0 & 90 & 24 & 2160 \\ \hline 2 & 5 & 1 & 170 & 12 & 2040 \\ \hline 2 & 0 & 2 & 48 & 6 & 288 \\ \hline 1 & 7 & 0 & 252 & 24 & 6048 \\ \hline 1 & 7 & 1 & 336 & 12 & 4032 \\ \hline 1 & 0 & 2 & 72 & 6 & 432 \\ \hline 0 & 9 & 0 & 540 & 12 & 6480 \\ \hline 0 & 9 & 1 & 570 & 4 & 2280 \\ \hline 0 & 0 & 2 & 100 & 1 & 100 \\ \hline \end{array}$$

giving a total of $25420$ solutions. I have to admit that I don't feel comfortable with the amount of side reckoning I had to do with forming the cases column here and without the semi-brute-force* confirmation which I ran, I would not be confident about this number.

*my confirmation looped through $a_1,a_3,a_5,a_7$ only and calculated the number of options for $k$ for each using the principles further up.

$\endgroup$
  • $\begingroup$ (+1) This is a good answer, supplying something important that I left out of my own answer. I don't know why this hasn't gotten more attention. If I get the time tonight I'll expand my answer and include your idea: with appropriate credit, of course. $\endgroup$ – Rory Daulton Feb 17 '15 at 18:33
  • $\begingroup$ @RoryDaulton thanks, & you're welcome... I'd kind of forgotten about this post so was interested to see how far I could push the analysis. I have a feeling there's something better just out of reach... $\endgroup$ – Joffan Feb 18 '15 at 2:11
0
$\begingroup$

we need to deal with two cases: $k \neq 0$ and $k = 0$. i will first deal with the case $k \neq 0.$ i will set $k = 1.$ once i find a particular solution i will multiply all of them by $k.$ this is the matrix i get when i rrefed. i will indicate the columns $7$ through $11.$ previous $6$ columns is $I_6$

$\pmatrix{1&1&0&0&1\\-1&-1&0&0&0\\1&0&0&1&1\\0&1&-1&-1&0\\-1&-1&1&0&0\\2&1&-1&0&1}$

the variables $a_1, a_2, \cdots, a_6$ are pivot variables and rest are free variables. for a particular solution set all the free variables to zero. the pivot variables are then the negative of column $11.$ a basis for the the homogeneous solution is gotten by e.g. set $a_7 = 1, a_8 = \cdots = a_{10} = 0$ then pivot variables are then the negative of column $7$.

i hope you can take it from here.

$\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.