0
$\begingroup$

If I have a solution to say $$4x_1+3x_2+3x_3+3x_4...+3x_n=4y$$ where $x_i ,y$ are non negative integers can I generate other solutions from my initial solution? And if I can would all solutions follow from this initial one?

$\endgroup$
  • $\begingroup$ what I am really trying to get at is if my initial solution contains all even integers then would solutions generated contain at least one even integer because the coefficient in front of $x_1$ is even $\endgroup$ – argamon May 15 at 0:40
  • $\begingroup$ Is it a linear equation you are interested in? If yes, you sould find more solution by finding integer vectors in the "kernel" of this system. Here, it is the space orthogonal to $(4, 3, 3, \dotsc, 3)$ or more precisely the integer lattice living in this orthogonal. $\endgroup$ – KeiOh May 15 at 2:15
  • $\begingroup$ For your comment, I am not sure it works: take $n=5$, and consider $u=(-3,1,1,1,1)$. Then $4u_1 + 3u_2 +\dotsb + 3u_5 = 0$. Now look at the equation $4x_1 + 3x_2 + \dotsb + 3x_5 = 8$. Then $x = (2, 0, \dotsc, 0)$ is a solution, but then so is $x+u$, isn't it? But $x+u$ as all odd coordinates. $\endgroup$ – KeiOh May 15 at 2:19
1
$\begingroup$

I'm not sure what exactly are you asking for, but I observed the following properties.


I'm assuming you want solutions for $(x_1,\dots,x_n)$ given $y$. Let $z=y-x_1$, then $$3(x_2+x_3+x_4\dots+x_n)=4z$$

Hence, $z$ must be a multiple of $3$, so we write $3k=y-x_1\implies x_1=y-3k$ for $0\le k\le\left\lfloor\frac{y}{3}\right\rfloor$.

If $x_1=y-3k$ for some $0\le k\le\left\lfloor\frac{y}{3}\right\rfloor$, then $x_2,\dots,x_n$ are a solution $\iff\sum_{i=2}^n x_i = 4k$.

Now to get all solutions, simply iterate all $k$, and for each, all $x_2,\dots,x_n$ s.t. $\sum_{i=2}^n x_i = 4k$.

That is, you can generate a solution form some other in two ways ("one two-case operation"):

  1. (We redistribute the sum condition:) You can decrease (increase) some component $x_i,i\ge 2$ by $1$ as long as you increase (decrease) some other component $x_{j},j\ge 2$.

  2. (We change the case of $k$:) You can decrease (increase) $x_1$ by $3$, as long as you increase (decrease) up to four other components $x_i,x_j,x_t,x_l$ for $2\le i \le j \le t \le l$ by $1$.

The set of all solutions is closed relative to this "two-case operation", so by repeating these two cases on any solution and all subsequently generated solutions, you can eventually reach all solutions.

| cite | improve this answer | |
$\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.