0
$\begingroup$

part (a)

How many ordered quadruples $(a,b,c,d)$ satisfy $$a+b+c+d=18,$$ where $a,b,c,d$ are nonnegative integers?

(part (b) How many ordered quadruples $(a,b,c,d)$ satisfy $$a+b+c+d=18,$$ where $a,b,c,d$ are odd positive integers?

part (c)

How many ordered quadruples $(a,b,c,d)$ satisfy $$a+b+c+d=18,$$ where $a,b,c,d$ are integers such that $|a|,\ |b|,\ |c|,\ |d|$ are each at most $10$?

For part (a) I counted the number of positive quadruples which is 18+4=22 so it would be 21C3 = 1330 ways to do that. But, I'm not sure how to do part (b) or (c).

$\endgroup$
1
  • $\begingroup$ Infinitely many, of course. Let $a; b;c$ be any real number and let $d = 18-(a+b+c)$. If you have stipulations such as $a,b,c,d$ are natural number not equal to $0$ you should state that. I was toungue in cheek about the "any real number" but whether $a,b,c,d$ are allowed to be $0$ or not is a crucial detail that shouldn't be omitted. $\endgroup$
    – fleablood
    Aug 9, 2020 at 1:26

3 Answers 3

5
$\begingroup$

Part (a): read about stars and bars

$\binom{18+4-1}{4-1}$

Part (b)

$a=2p+1 , b=2q+1 , c=2r+1 , d=2s+1$

$p+q+r+s=7$

Stars and bars again

$\binom{7+4-1}{4-1}$

Part (c)

Continuing Brian’s solution, $a+10=w , b+10=x , c+10=y , d+10 = z$

$w+x+y+z=58$ where all four are at most 20.

Quadruples with at least one greater than 20:divide 37 into 4 and then add 21 to one of the four numbers

$\binom{37+4-1}{4-1}\times 4$

Quadruples with two greater than 20: divide 16 into 4 and then add 21 to two of the four numbers

$\binom{16+4-1}{4-1}\times\binom{4}{2}$

Last we use principle of inclusion and exclusion

$\binom{58+4-1}{4-1}-\binom{37+4-1}{4-1}\times 4 + \binom{16+4-1}{4-1}\times\binom{4}{2}$ =$2284$

$\endgroup$
6
  • $\begingroup$ can you explain why we need to subtract this from part (a)? i did 1330-(10 choose 3)*4 = 850 but it was incorrect and im not sure why $\endgroup$
    – user801134
    Aug 9, 2020 at 0:16
  • $\begingroup$ @3bds oh hold on, are the quadruples non negative in part (c) or can they be negative? To answer your question, because $\binom{10}{3}\times 4$ is the number of quadruples in which at least one of them are greater than 10 $\endgroup$
    – acat3
    Aug 9, 2020 at 0:22
  • $\begingroup$ they can be negative because they are integers $\endgroup$
    – qs13
    Aug 9, 2020 at 0:23
  • $\begingroup$ @rezha they can be negative $\endgroup$
    – user801134
    Aug 9, 2020 at 0:28
  • $\begingroup$ @RezhaAdrianTanuharja Glad the method with 58 can be redeemed. I think the key insight is that the count for $58$ and $80-58 = 22$ are the same be replacing $a$ with $20-a$, etc. $\endgroup$ Aug 9, 2020 at 2:09
3
$\begingroup$

I agree with your (a) answer and Rezha's (b) looks good.

For (c), moving everything up by 10 gives you 4 nonnegative numbers with sum 58, but summands over 20 definitely come up a lot. Here's the trick: Move everything down 10 instead, then multiply everything by $-1$: \begin{align} a + b + c + d = 18 & \quad \text{with } -10 \le a, b, c, d \le 10 \\ (a-10) + (b-10) + (c-10) + (d-10) = 18-40 \\ \alpha + \beta + \gamma + \delta = -22 & \quad \text{with } -20 \le \alpha, \beta, \gamma, \delta \le 0 \\ -\alpha - \beta -\gamma - \delta = 22 \\ w + x + y + z = 22 & \quad \text{with } 0 \le w, x, y, z \le 20 \end{align} That is, move the variables down 10 and then negate them. The range of allowed values goes from $[-10,10]$ to $[-20,0]$ to $[0,20]$, so a maximum constraint is still in effect. But the sum went from 18 to $18-40 = -22$ to 22: we'll see that the maximum constraint won't matter much when it's so close to the sum.

Count solutions to $w + x + y + z = 22$ as in (a), I believe you get ${25 \choose 3} = 2300$. Those include some solutions with values over 20, but very few: You could have $(22,0,0,0)$ with 4 ways to assign the 22, and $(21,1,0,0)$ with 12 ways to assign the 21 and 1 (not just ${4 \choose 2}=6$ ways since, e.g., $(0,21,0,1)$ and $(0,1,0,21)$ are distinct solutions). Removing those 16 "bad" solutions leaves 2284 with allowed values.

PS: In the time it takes to think of that and work out the details, you could find a computer algebra system and look up the coefficient of $x^{18}$ in the expansion of $$(x^{-10} + x^{-9} + \cdots + x^{-1} + x^0 + x^1 + \cdots + x^9 + x^{10})^4$$ which is, in fact, 2284.

$\endgroup$
0
$\begingroup$

A reasonable way to approach parts (b,c) is to attempt to reduce them to problems of type (a): "How many ordered quadruples $(a,b,c,d)$ satisfy $a+b+c+d = k$ where $a,b,c,d$ are nonnegative integers?" So heuristically, the goal is to make nonnegative integers out of odd positive integers, and out of integers whose absolute values are at most 10. Can you come up with a way to re-parametrize solutions to parts (b,c) based on ranges of nonnegative integers?

$\endgroup$

You must log in to answer this question.