How many solutions to $x_1 +x_2 +x_3 +x_4 = 1097$ , in nonnegative integers $x_1$, $x_2$, $x_3$, and $x_4$ which satisfy at least one of the inequalities $x_1 \geq 100$, $x_2 \leq 499$?
I understand how to calculate the number of solutions to the unrestricted problem: $1097 + 4 – 1 \choose 1097$ solutions $= \binom{1100}{1097} = \binom{1100}{3}$
I also know how to handle a single restriction being added. For example if we just take $x_1 \geq 100$: We have $x_1 = x_1' + 100$. Then our problem is equivalent to $x_1' + x_2 + x_3 + x_4 = 997$. Then we have $\binom{4 + 997 -1}{997} = \binom{1000}{3}$ solutions
Finally, I know if we had to meet both restrictions, we could do the unrestricted number of solutions – the number of solutions that violate each requirement. Where I'm running into trouble is determining how to calculate the number of solutions that meet at least one restriction. How can I find the number of solutions that violate both restrictions?
Best Answer
When I'm confronted with 'at least one' problem types, I usually go to the opposite case. Namely, the number solutions to $x_1 +x_2 +x_3 +x_4 = 1097$, with $x_1, x_2, x_3, x_4 \geq 0$ which satisfy at least one of the inequalities $x_1 \geq 100, x_2 \leq 499$, is going to be equal to the $\textit{total}$ amount of solutions to $x_1 +x_2 +x_3 +x_4 = 1097$ with $x_1, x_2, x_3, x_4 \geq 0$ $\textbf{minus}$ the amount of solutions to $x_1 +x_2 +x_3 +x_4 = 1097$ with $x_1, x_2, x_3, x_4 \geq 0$ in which none of the inequalities hold (so we have $x_1 < 100 \ \textbf{and} \ x_2 > 499$, or $x_1 \leq 99$ and $x_2 \geq 500$ as $x_1$ and $x_2$ are integers).
This should be a lot easier to compute, and I hope this gives you a nudge into the right direction.