1
$\begingroup$

I have a set of equations as follow,

  • $a_1\cdot x_1 + a_2\cdot x_2 + a_3\cdot x_3 + a_4\cdot x_4 + \dots + a_{11} \cdot x_{12} + a_{12}\cdot x_{12} = 6000$
  • $x_1 + x_2 + x_3 + x_4 + \dots x_{11} + x_{12} = 100 $
  • $\{a_1,a_2,a_3, \dots , a_{11}, a_{12}\} \leq 60$

How can I find the values for all $a_i, \text{ and } x_i$,not all values of $a_i$ can be equal to $60$ also if possible integer, else the general solution.

  • How the question get affected if I change the constrain on $a_i$ to some $X$, say $0 < a_i \leq X$,
  • Also if the constrain on $a_i$ is , say $a_i>0$.

If solvable in Matlab please show the code also .


If not solvable please mention why.


What I tried is $$ \begin{bmatrix} a_1&a_2 & a_3 &\dots & a_{11} & a_{12} \\ 1 & 1 & 1& \dots & 1 & 1 \end{bmatrix}\begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ \vdots\\ x_{11} \\ x_{12} \end{bmatrix} = \begin{bmatrix} 6000 \\ 100 \end{bmatrix} $$

The rank will be almost $2$ so atmost I can get $10$ free variables. but since the values for $a_i$'s are also unknown I don't know how to proceed.

$\endgroup$
  • $\begingroup$ If each $x_i$ is positive, the only solution is $a_i = 60$ for every $i$. Must all $a_i, x_i$ be positive? $\endgroup$ – player3236 Oct 31 '20 at 9:03
  • $\begingroup$ yes everything should be positive. $\endgroup$ – Lawliet Oct 31 '20 at 9:05
0
$\begingroup$

Assume that $\exists i\in \{1, 2, ..., 12\}: a_i < 60$, then $$6000 = a_1 x_1 + ... + a_{12} x_{12} < 60x_1 + ...+ 60x_{12} = 60(x_1 + ...+x_{12}) = 6000 $$ is contradiction. So $\forall i \in \{1, 2, ..., 12\}: a_i \geq 60$, so $a_1 = a_2 = ... = a_{12} = 60$

$\endgroup$
  • $\begingroup$ What if I change the the constrain $a_i < 100$ $\endgroup$ – Lawliet Oct 31 '20 at 9:11
  • $\begingroup$ @Lawliet Indeterminate $\endgroup$ – Youngwoon Cheong Oct 31 '20 at 9:12
  • $\begingroup$ Can you just give the proof of this also , like if the constrain on a is relaxed or changed the problem will become indeterminate . $\endgroup$ – Lawliet Oct 31 '20 at 9:14
  • $\begingroup$ I'm not 100% sure what relaxed constrain means. Can you state it more specifically? $\endgroup$ – Youngwoon Cheong Oct 31 '20 at 9:19
  • $\begingroup$ like changing$a_i$ to $a_i>0$ $\endgroup$ – Lawliet Oct 31 '20 at 9:42
0
$\begingroup$

So we have $$ \left\{ \matrix{ 0 \le a_{\,k} \le 60\quad \left| {\,1 \le k \le 12} \right. \hfill \cr 0 \le x_{\,k} \le 100\quad \left| {\,1 \le k \le 12} \right. \hfill \cr x_{\,1} + x_{\,2} + \cdots + x_{\,12} = 100 \hfill \cr {\bf a} \cdot {\bf x} = 6000 \hfill \cr} \right. $$

If we put $b_k = 60 -a_k$ then $$ \left\{ \matrix{ b_{\,k} = 60 - a_{\,k} \quad \left| {\,1 \le k \le 12} \right. \hfill \cr u_{\,k} = 1\quad \left| {\,1 \le k \le 12} \right. \hfill \cr 0 \le x_{\,k} \le 100 \hfill \cr 0 \le b_{\,k} \le 60\quad \left| {\,1 \le k \le 12} \right. \hfill \cr {\bf u} \cdot {\bf x} = 100 \hfill \cr 6000 = {\bf a} \cdot {\bf x} = \left( {60\,{\bf u} - {\bf b}} \right) \cdot {\bf x} = \hfill \cr = 6000 - {\bf b} \cdot {\bf x}\quad \Rightarrow \quad {\bf b} \cdot {\bf x} = 0 \hfill \cr} \right. $$

and clearly, with ${\bf b}, \, {\bf x}$ having non-negative components we must have $$ \left\{ \matrix{ {\bf b} = {\bf 0}\; \Rightarrow \;{\bf a} = 60\,{\bf u} \hfill \cr 0 \le x_{\,k} \le 100 \hfill \cr {\bf u} \cdot {\bf x} = 100 \hfill \cr} \right. $$

That is, $\bf x$ are the vectors lying on the diagonal plane of a 12-D hypercube of side $[0,100]$.

There are $101^{12} \approx 10^{24}$ points inside that cube, and those on the diagonal plane are exactly the number of weak compositions of $100$ into $12$ parts , i.e. $\binom {100+12-1}{11} \approx 2.8 \cdot 10^{14}$.

So your first care should be how to manage such a huge amount of data, if you want to list all the solutions.

You can somewhat reduce the size by taking advantage of the permutation invariance.
If $(x_1,x_2, \cdots)$ is a solution, then any permutation of the twelve components will be.
So you can limit to list the solutions in order, e.g. non-decreasing.
The number in this case will be reduced to that of the partitions of $100$ into up to twelve parts (because the components may be null), which is $ \approx 1.7 \, \cdot 10^7$.

$\endgroup$
  • $\begingroup$ Can you just tell me any one solution for these set of equations ? $\endgroup$ – Lawliet Oct 31 '20 at 19:23
  • $\begingroup$ Well, they are ${\bf a} =(60,60, \cdot, 60)$ and ${\bf x} = (100,0, \cdots), \; (99,1,0,\cdots),\; (98,2,0,\cdots), \; (98,1,1,0,\cdots), \; \cdots \; , (10,10, \cdots,10)$ when listed in non-decreasing order, $\times$ all the permutations (net of repetitions) thereto. $\endgroup$ – G Cab Oct 31 '20 at 19:50

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.