3
$\begingroup$

How many non-negative integer solutions are there for the equation x + y + z + w = 20, where x>y.

I started by substituting x for a new variable x'=x-y:
x > y
x-y > 0
x'>0

However, this led me to a point from which I didn't know how to make progress:
x'+ 2y + z + w = 20

How should I deal with the 2y?

(the answer provided was 825)

$\endgroup$
  • $\begingroup$ I'm not sure one can apply Stars-and-Bars with such modifications. In general introducing coefficients not equal to one makes the problem (counting non-negative integer solutions) more difficult. Would you entertain an alternative approach? $\endgroup$ – hardmath Apr 26 '19 at 23:53
4
$\begingroup$

By symmetry, the number of solutions with $x>y$ is the same as the number with $x<y$ so the answer is "half the number of solutions where $x\neq y$." I would go about this by subtracting the solutions with $x=y$ from the total number of solutions.

Stars and bars gives the total solutions, so now we need to know the number of solutions to $$2x+w+z=20$$ in nonnegative integers. For a given $x$ this is just $21-2x$ so it's easy to add them up.

$\endgroup$
  • $\begingroup$ Your logic makes perfect sense. Sadly, I feel it comes back to the problem I encountered in my attempt: not knowing how to make progress with Stars-and-Bars when 2 of the variables are the same. $\endgroup$ – pug Apr 27 '19 at 0:13
  • $\begingroup$ @pug - saulspatz is saying this: iterate through $x=0,1,...,10$ and you have $w+z = 20-2x$ which is itself a stars-and-bars problem. however, this problem is so small ($2$ variables) that the no. of solutions is obviously ${20-2x + 2 -1 \choose 2 - 1} = 21 - 2x$ (he has a typo). so now you sum through all $x=0,1,...10$ etc $\endgroup$ – antkam Apr 27 '19 at 3:02
  • $\begingroup$ @antkam Thanks for pointing out the typo. It's fixed. $\endgroup$ – saulspatz Apr 27 '19 at 11:14
2
$\begingroup$

$$x+y+z+w=20\tag{1}$$

Firstly it says $x \gt y$ so $x=y+x'+1$ where $x'\ge 0$.

This gives

$$x'+2y+z+w=19\, .$$

So since $2y$ is always even, $x'+z+w$ must be odd which means either all three variables are odd or just one is.

  1. If all three are odd then say $x'=2x''+1$, $z=2z''+1$, $w=2w''+1$, giving

\begin{align}&& 2(x''+y+z''+w'')&=16\\[1ex] &\implies& x''+y+z''+w''&=8\, ,\end{align}

which has $\binom{8+3}{3}$ non-negative integer solutions by bars and stars.

  1. If just one is odd, say $x'=2x''+1$, then the other two must be even: $z=2z''$, $w=2w''$, this gives

\begin{align}&& 2(x''+y+z''+w'')&=18\\[1ex] &\implies & x''+y+z''+w''&=9\, ,\end{align}

which has $\binom{9+3}{3}$ non-negative integer solutions by bars and stars. However, there are 3 choices for our odd variable so that's $3\binom{9+3}{3}$ total solutions for this case.

Adding both cases together we have a grand total of

$$\binom{8+3}{3}+3\binom{9+3}{3}=825\tag{Answer}$$

non-negative integer solutions to $(1)$ with $x\gt y$.

$\endgroup$
  • 1
    $\begingroup$ A nice approach. However, the equation $x'' + y + z'' + w'' = 8$ has only $\binom{\color{red}{8} + 3}{3}$ solutions in the nonnegative integers. $\endgroup$ – N. F. Taussig Apr 27 '19 at 9:09
  • $\begingroup$ Whoops! Thank you @N.F.Taussig. Where was my head when I wrote that? I don't know. I'll edit. $\endgroup$ – N. Shales Apr 27 '19 at 9:35

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.