2
$\begingroup$

Recently, I have found this problem:

Given two natural numbers $\Phi_1$ and $\Phi_2$ ($\Phi_1,\Phi_2>1$), determine all possible natural integer solutions to the follwing system in the unkown $x_1,x_2,\cdots,x_k$: $$\left\{\begin{matrix} x_1+x_2+x_3+\cdots+x_k=\Phi_1 \\ x_1+2x_2+3x_3+\cdots+kx_k=\Phi_2 \end{matrix}\right.$$ where $k$ is a positive costant so that $k>2$.

To solve this, I have, first of all, shown that it must be $\Phi_2\geq \Phi_1$, because if I substarct the second the equation from the first, I obtain: $$0x_1-x_2-2x_3-\cdots-(k-1)x_k=\Phi_1-\Phi_2 \leftrightarrow x_2+2x_3+3x_4+\cdots+(k-1)x_k=\Phi_2-\Phi_1$$ And so, I must have $\Phi_2\geq\Phi_1$ because $x_1,x_2,\cdots,x_k\geq0$.

When $k=2$, the system can be solved with substitution or Gauss's method; what happens when $k>2$?

For example, let $M$ the matrix associated to the system: $$M=\begin{bmatrix} 1 & 1 & 1 & \cdots & 1 & \Phi_1\\ 1 & 2 & 3 & \cdots & k & \Phi_2 \end{bmatrix}$$

Can $M$ be used to find $(x_1,x_2,\cdots,x_k)$? Or are there any other methods?

$\endgroup$
  • $\begingroup$ We have $2$ equations, any time when $k>2$, we will have infinite number of solutions. $\endgroup$ – mathreadler Mar 10 '20 at 12:05
  • $\begingroup$ Infinite many positive integer solutions? $\endgroup$ – Matteo Mar 10 '20 at 12:07
  • $\begingroup$ Ah, I did not see the integer constraint. $\endgroup$ – mathreadler Mar 10 '20 at 12:08
2
$\begingroup$

You're asking for the partitions of $\Phi_2$ into $\Phi_1$ parts. See e.g. this Wikipedia section for a recurrence relation for their count. There’s an algorithm to generate all of them in Knuth’s The Art of Computer Programming, Volume $4$, Section $7.2.1.4$, Algorithm $H$ on p. $392$. As a general purpose method to solve this sort of system of linear equations with the variables restricted to certain ranges of integers, you could consider integer programming.

$\endgroup$
0
$\begingroup$

One thing which might help at least partially (but is too large for a comment) is to take the triangular matrix with ones

$${\bf T} = \begin{bmatrix}1&0&0\\1&1&0\\1&1&1\end{bmatrix}^T$$ Now, with $\bf I$ being identity matrix and ${\bf x}^T = [x_1,\cdots,x_k]$ $$[{\bf I_2} \otimes {{\bf 1}}^T] {\bf \begin{bmatrix}\bf I\\\bf T\end{bmatrix}x}=\begin{bmatrix}\Phi_1\\\Phi_2\end{bmatrix}$$

This does not utilize any number theoretic knowledge of the problem, only linear algebra.

For computational purposes we might want to do substitution $$\cases {t_k = x_{k+1}-x_{k}\\t_1=x_1}$$ This allows us to express the above using $\bf D$ matrix instead which for large $k$ will be much sparser:

$${\bf D} = \begin{bmatrix}1&0&0\\-1&1&0\\0&-1&1\end{bmatrix}$$

Only two non-zero diagonals.

$\endgroup$
0
$\begingroup$

As you noted:

$$ x_2 + 2 x_3 + \ldots + (k-1) x_k = \Phi_2 - \Phi_1 \tag{1}$$ Subtract from the first equation, obtaining $$ x_1 - x_3 - 2 x_4 - \ldots -(k-2) x_k = 2 \Phi_1 - \Phi_2 \tag{2}$$

Given integers $\Phi_1, \Phi_2, x_3, \ldots, x_k$, equations (1) and (2) determine integers $x_1$ and $x_2$. Now if you want the $x_i \ge 0$, you need $$ \eqalign{\Phi_2 - \Phi_1 - 2 x_3 - 3 x_4 - \ldots - (k-1) x_k &\ge 0\cr 2 \Phi_1 - \Phi_2 + x_3 + 2 x_4 + \ldots + (k-2) x_k &\ge 0\cr} \tag{3}$$ which can be rearranged as bounds for $x_3$: $$\frac{\Phi_2 - \Phi_1 - 3 x_4 - \ldots - (k-1) x_k}{2} \ge x_3\ge -2 \Phi_1 + \Phi_2 - 2 x_4 - \ldots - (k-2) x_k \tag{4}$$

The condition for the upper bound to be greater than or equal to the lower is: $$ 3 \Phi_1 - \Phi_2 + x_4 + 2 x_5 + \ldots + (k-3) x_k \ge 0 \tag{5}$$

Let $x_4, \ldots, x_k$ be any natural numbers such that (5) is true. Then $x_3$ can be any natural number satisfying (4), and $x_1$ and $x_2$ are obtained from (2) and (1).

However, you want $x_3 \ge 0$, so that imposes a requirement

$$ \Phi_2 - \Phi_1 - 3 x_4 - \ldots - (k-1) x_k \ge 0 \tag{6}$$

And (5) and (6) translate to lower and upper bounds on $x_4$. And so on...

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