1
$\begingroup$

How can I solve the diophantine equation

$$x_1 +x_2 + x_3 + x_4 + x_5 + x_6 + x_7 = 30,$$

where $x_1, x_2, x_3, x_4, x_5, x_6, x_7$ can take the values $0,2,3,4,5$?

I am having problems in solving this one. The expansion is getting very big.

I need the number of solutions of this equation.

Thanks

$\endgroup$
  • 1
    $\begingroup$ Do you need all the solutions, or one solution? $\endgroup$ – Jimmy R. Feb 19 '14 at 8:50
  • $\begingroup$ I need number of solutions. $\endgroup$ – AJ_ Feb 19 '14 at 8:53
  • $\begingroup$ As you need the number of solutions, this is about combinatorics, not about diophantine equations. $\endgroup$ – Marc van Leeuwen Feb 19 '14 at 9:05
  • $\begingroup$ @MarcvanLeeuwen, Oops, that was my edit. Thanks for revising that! $\endgroup$ – Christoph Feb 19 '14 at 9:15
3
$\begingroup$

By setting $x_i=5-y_i$, we can instead solve $$(5-y_1)+(5-y_2)+\cdots+(5-y_7)=30$$ for $y_1,\ldots,y_7 \in \{0,1,2,3,5\}$. This is equivalent to $$y_1+y_2+\cdots+y_7=5.$$

From here, the possible multisets of $y$-values are:

  • $\{5,0,0,0,0,0,0\}$, enumerated by $\binom{7}{1,6}=7$,
  • $\{3,2,0,0,0,0,0\}$, enumerated by $\binom{7}{1,1,5}=42$,
  • $\{3,1,1,0,0,0,0\}$, enumerated by $\binom{7}{1,2,4}=105$,
  • $\{2,2,1,0,0,0,0\}$, enumerated by $\binom{7}{2,1,4}=105$,
  • $\{2,1,1,1,0,0,0\}$, enumerated by $\binom{7}{1,3,3}=140$,
  • $\{1,1,1,1,1,0,0\}$, enumerated by $\binom{7}{5,2}=21$.

This gives $420$ possibilities.

$\endgroup$
1
$\begingroup$

Assume none of the $x_i, i=1,\ldots,7$ is equal to $5$. Then the highest you can achieve is $7\times4=28$ which is $2$ less than the desired. So you need at least two $5$'s. Without loss of generality let $x_6=x_7=5$ (you can choose whichever 2 $x_i$ you want). Then the above equation reduces to $$x_1+x_2+x_3+x_4+x_5=20,$$ with $x_i \in {0,2,3,4,5}$. No you can treat different cases based on the minimum (or maximum) of the $x_i$ as @Rebecca's treatment (which is by the way much more elegant). For example

1.Case: $x_1=x_2=0$. No such solution possible.

2.Case: $x_1=0$.Then $x_2=x_3=x_4=x_5=5$. So the first solution is: $6$ fives and $1$ zero. You have $7$ such solutions (permutations).

3.Case: $x_1=2$. Then you have that $$x_2+x_3+x_4+x_5=18,$$ and you have one possibility to solve, which is $x_2=3, x_3=x_4=x_5=5$. So the solution consists of $5$ fives, $1$ three and $1$ two. You have $7\times6=42$ such solutions. There are no other solutions in which 2 appears.

4.Case: $x_1=3$. Then you have that $$x_2+x_3+x_4+x_5=17$$ and you have two possibilities to solve. The first is three fives and a two (but you already had it, so it is rejected. Remember that we take cases according to minimum and 2 as minimum is already treated above) and the other is $3$ fours and $1$ five. So the solution consists of $3$ fives, $3$ fours and $1$ three. You have $7\times \dbinom{6}{3}=140$. (choose one $x$ to be equal to 3 (you have $7$ such possibilities and choose $3$ out of the remaining $6$ to be equal to $5$ (you have $\dbinom{6}{3}=20$ such possibilities).

5.Case: $x_1=x_2=3$.Then you have that $$x_3+x_4+x_5=14$$ and you have one possibility to solve which is $x_3=4,x_4=x_5=5$. So the solution consists of $4$ fives, $2$ fours and $2$ threes. There are $\dbinom{7}{2}\times\dbinom{5}{2}=210$ such solutions. (choose two $x_i$ to be equal to 3 (you have $\dbinom{7}{2}=21$ such possibilities and choose $2$ out of the remaining $5$ to be equal to $4$ (you have $\dbinom{5}{2}=10$ such possibilities. set the remaining two to be equal to 5).

6.Case: $x_1=x_2=x_3=3$.Then you have that $$x_4+x_5=11$$ which is impossible. So no more cases where a $3$ appears are possible.

7.Case: $x_1=4$. Then you have that $$x_2+x_3+x_4+x_5=16$$ and all the $x_i$ must be greater or equal than $4$. So the only possible solution is $x_2=x_3=x_4=x_5=4$. So the solution consists of $2$ fives and $5$ fours. You have (in the same manner as above) $\dbinom{7}{2}$ such solutions.

So to sum up. List of possible solutions (ordered vector and number of such vectors)

  1. $(0,5,5,5,5,5,5)$. $7$ such solutions

  2. $(2,3,5,5,5,5,5)$. $42$ such solutions

  3. $(3,4,4,4,5,5,5)$. $140$ such solutions

  4. $(3,3,4,5,5,5,5)$. $210$ such solutions

  5. $(4,4,4,4,4,5,5)$. $21$ such solutions

which gives 420 solutions.

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