Ordered pair inequality:- pairwise sums <=7 but total sum >=7 How many ordered pairs of non negative integers $(a,b,c,d)$ satisfy the following?
 $ a+b \leq 7 $ 
 $ c+d \leq 7 $ 
 $ a+c \leq 7 $ 
 $ b+d \leq 7 $ 
 $ a+b+c+d \geq 7$ 
My approach was as following.
Divide the problem into some cases.
Case 1
$ a+b= 0 $ (only one possible value for $ (a,b) $)
Then we must have $ c+d= 7 $ (this gives $8$ possible values for $(c,d)$)
For each such ordered pair $(a,b,c,d)$, we must have $a+c\leq7$; $b+d\leq7$; because $max(c)= max(d)= 7$, and $max(a)= max(b)= 0$. Hence $max(a+c)= max(b+d)= 7$.
So his gives us $8$ ordered pairs.
Case 2
$a+b= 1$ ($2$ possibilities for $ (a,b) $)
Then we must have $c+d= 6/7$. $c+d= 6$ gives $7$ possibilities for $(c,d)$, $c+d= 7$ gives $8$ possibilities for $(c,d)$. However observe that the following ordered pairs produce a value of $a+c$ which is greater than $7$: $ (a,c)= (1,7) $ and $ (b,d)= (1,7) $. So total number of acceptable ordered pairs $= (7+8)*2 - 2 = 28$    
But for larger values of $a+b$ there are several cases and I cannot deal with all of them. Also I am not sure if some solutions overlap and I get some extra solutions. Can anybody here please come up with a better approach than mine?
 A: I propose a different decomposition. First observe that the count you're looking for is the difference of the following two counts: the number of $(a,b,c,d)$ satisfying $a+b,a+c,d+b,d+c$ all $\le7$, minus the number of $(a,b,c,d)$ with $a+b+c+d\le6$. The second count is a standard problem, so let's concentrate on the first count.
The ordered quadruples $(a,b,c,d)$ satisfying $a+b,a+c,d+b,d+c$ all $\le7$ can be partitioned into the following categories:


*

*those with $\max\{a,b,c,d\}\le3$

*those with $\max\{a,d\}=4$

*those with $\max\{b,c\}=4$

*those with $\max\{a,d\}=5$

*those with $\max\{b,c\}=5$

*those with $\max\{a,d\}=6$

*those with $\max\{b,c\}=6$

*those with $\max\{a,d\}=7$

*those with $\max\{b,c\}=7$


I believe each of these categories can be counted pretty easily.
A: I'd suggest you to look a the values of $a$ and $d$, rather than $a$ and $b$. The first four inequalities can then be written as
$$\begin{eqnarray}
b & \leq & 7-a \\
c & \leq & 7-d \\
c & \leq & 7-a \\
b & \leq & 7-d \\
\end{eqnarray}$$
or, in more compact form, as $b,c\leq 7-\max(a,d)$.
If we ignore the fifth inequality for now, the number of solutions can be found by considering the possible values of $M=\max(a,d)$. For any particular choice of $M$, each of $b$ and $c$ can be chosen in $(7-M+1)$ ways. On the other hand, the pair $(a,d)$ can be chosen in $2M+1$ ways (since one or both must be equal to $M$). Summing the number of quadruplets for $0\leq M\leq 7$ should then be fairly simple.
After that, we'll need to get rid of the quadruplets which do not satisfy the fifth inequality. Fortunately, this inequality has a very nice property -- if it is not satisfied (i.e. if $a+b+c+d<7$), the remaining four inequalities will be satisfied trivially. Thus, so it suffices to consider it on its own and forget about the others. This is a fairly standard combinatorial problem, answer of which is just one binomial coefficient.
