TransWikia.com

How many solutions are there to $x_1 + x_2 + x_3 + x_4 = 30$ s.t. $x_1 + x_2 le 20$ and $x_3 ge 7$?

Mathematics Asked by Lucas Peres on January 11, 2021

Here is the original question from the book:

How many ways are there to distribute $30$ green balls to $4$ persons if Alice and Eve together get no more than $20$ and Lucky gets at least $7$?

I rewrote the problem as the title of this post, i.e. how many solutions are there to $x_1 + x_2 + x_3 + x_4 = 30$ such that $x_1 + x_2 le 20$ (Alice and Eve together get no more than $20$) and $x_3 ge 7$ (Lucky gets at least $7$).

First, I "eliminated" the second restriction. Give Lucky $7$ balls and distribute the remaining $23$. Thus, we have

$$
x_1 + x_2 + (x_3 + 7) + x_4 = 30 \
x_1 + x_2 + x_3 + x_4 = 23
$$

Then, since the other restriction left me with doubts, I counted the number of solutions to the equation above, which is $23+3 choose 3$, and tried counting the solutions that violate $x_1 + x_2 le 20$ to subtract from $23+3 choose 3$.

Let $k = x_1 + x_2 le 20$. The solutions that violate this are those where $k ge 21$. Hence

$$
(k + 21) + x_3 + x_4 = 23 \
k + x_3 + x_4 = 2
$$

which has $2+2 choose 2$ solutions. Therefore, my solutions was ${23+3 choose 3}-{2+2 choose 2} = 2600 – 6 = 2594$.

However, the book provides the following solution:

Suppose Alice and Eve together get $k$ balls. This can be done in $k + 1$ ways. That leaves $30 – k$ balls for the other $2$ persons, but Lucky must get at least $7$ of these. So, there are $30 – k – 7$ additional balls to distribute to Lucky and the fourth person. This can be done in $(30 – k – 7) + 1$ ways. Hence, our answer is $sum_{k=0}^{20}(k+1)(24-k)$.

That gives $2464$. Forgive me if I didn’t get some "obvious" detail, but what the heck does that summation mean? I was getting everything until it appeared, although I do see what the summands are. Could you point out where is the mistake in my solution? If you think the answer provided is simpler, please do explain.

Thank you very much for any clarifications!

One Answer

Your calculation of the number of solutions that violate the condition that $x_1+x_2le 20$ fails to take into account that if $x_1+x_2=m$, say, there are $m+1$ different possibilities for $x_1$ and $x_2$: $x_1$ can be anything from $0$ through $m$. For instance, when $m=21$, there are $22$ possibilities for $x_1$ and $x_2$, not just one.

Here’s a slightly expanded version of the book’s solution, which does take all of that into account.

We give Lucky $7$ balls to start with. Then we pick some $kin{0,1,ldots,20}$ and distribute $k$ balls between Alice and Eve; this can be done in $k+1$ ways. We’re left with $23-k$ balls to distribute between Lucky and the fourth person, and we can do this in $24-k$ ways. We can combine any of the distributions of $k$ balls between Alice and Eve with any of the $24-k$ distributions of the remaining balls between Lucky and the fourth person, so there must be altogether $(k+1)(24-k)$ ways to distribute the balls so that Lucky gets at least $7$ balls, and between them Alice and Eve get $k$ balls. Now we simply add up the numbers for the different possible values of $k$ to get $sum_{k=0}^{20}(k+1)(24-k)$.

Correct answer by Brian M. Scott on January 11, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP