Almost all the pairwise products

We have $\begin{aligned} S &= ab+bd+da+bc+cd \\ &= b(a+c+d) + d(a+c) \\ &= b(120-b) + d(120-b-d) \\ &= -b^2 + -d^2 + 120b + 120d - bd. \qquad \textbf{(1)} \end{aligned}$ We could interpret this expression as a quadratic in $b$ : $S = -b^2 + (120-d)b + (120d-d^2).$ So, keeping $d$ constant, $S$ is maximized when $\qquad b = \dfrac{-(120-d)}{2(-1)} = \dfrac{120-d}{2}. \qquad \textbf{(2)}$ We could also interpret the expression as a quadratic in $d$ : $S = -d^2 + (120-b)d + (120b-b^2).$ Notice that this expression is the same as the previous one, except $b$ and $d$ are switched. (This was inevitable, since our formula for $S$ is symmetric in $b, d$ .) Therefore, $S$ is maximized when $\qquad d = \dfrac{120-b}{2} \qquad \textbf{(3)}.$

We have a system of equations for $b$ and $d$ (equations $(2)$ and $(3)$ ), which we can solve to get $b=d=40.$ Then $a+c = 120 - 40- 40 = 40,$ and since $(1)$ is not dependent on $a$ and $c,$ any choices of $a$ and $c$ will produce the same value of $S.$ The possible ordered pairs are $(a,c) = (1,39), (2,38), \ldots, (39, 1),$ so there are $\boxed{39}$ ordered quadruples for which $S$ is maximized.

Note: the maximum value of $S$ is $\begin{aligned} S &= -b^2 -d^2 + 120b + 120d - bd \\ &= -40^2 - 40^2 + 120 \cdot 40 + 120 \cdot 40 - 40^2 = 4800. \end{aligned}$

We note that the maximum is $\frac{1}{2}$ of the maximum of $2S$ .

$2S=2ab+2bd+2da+2bc+2cd=(a+b+c+d)^2-(a^2+b^2+c^2+d^2)-2ac=14400-(a^2+b^2+c^2+d^2+2ac$ .

To maximize $2S$ , we have to minimize $a^2+b^2+c^2+d^2+2ac=(a+c)^2+b^2+d^2$ .

By the QM-AM inequality, we get $\sqrt{\frac{(a+c)^2+b^2+d^2}{3}} \ge \frac{(a+c)+b+d)}{3}$ with equality iff $a+c=b=d$ Hence $\sqrt{\frac{(a+c)^2+b^2+d^2}{3}} \ge \frac{120}{3}=40$ . Thus $\frac{(a+c)^2+b^2+d^2}{3} \ge 1600$ , so $(a+c)^2+b^2+d^2 \ge 4800$ with equality iff $a+c=b=d=\frac{120}{3}=40$ .

Hence we now have to find the number of ordered pairs $(a,c)$ such that $a+c=40$ . Note that the possible $(a,c)$ are $(1,39), (2,38), ..., (39,1)$ , so there are $\boxed{39}$ ordered quadruples $(a, b, c, d)$ for which $S$ attains its maximum.

Note that:

$S = (a+c)(b+d) + bd = (120-b-d)(b+d) + bd$

so we only need to focus on the ordered pair $(b, d)$ . Without loss of generality, suppose $b\ge d$ . If $b \ge d+2$ , then upon replacing $(b,d)$ by $(b-1, d+1)$ , the first term on the right-hand side remains the same while $bd$ is replaced by:

$(b-1)(d+1) = bd + (b-d) - 1\ge bd +1 > bd$

so for maximum $S$ , we must have $b-d \le 1$ . Thus we consider two cases.

Case 1 : $b=d$ . This gives us:

$\begin{aligned} S &= 2b(120-2b) + b^2 = 240b - 3b^2\\ &= -3[ (b-40)^2 - 1600] \le 4800.\end{aligned}$

So the maximum is 4800 in this case, which is attained when $b=d=40$ .

Case 2 : $b = d+1$ . This gives:

$\begin{aligned} S &= (2d+1)(119-2d) + d(d+1) = -3d^2 + 237d + 119\\ &= -3(d - \frac {79}2)^2 + \frac{19199} 4 \le 4799 \end{aligned}$

with equality if and only if $d= 39, 40$ .

Hence, the first case is where $\max(S)$ is attained, which gives $b=d=40$ . The solutions thus correspond to ordered pairs $(a, c)$ satisfying $a+c = 40$ . Hence there are 39 solutions.

We have $S = (b+d)(a+b)+bd = (b+d)(120-(b+d))+bd.$ AM-GM inequality yields $bd \le \Big(\frac{b+d}{2}\Big)^2$ with equality if and only if $b=d.$ Hence $S \le t(120-t)+\Big(\frac{t}{2}\Big)^2 = -\frac{3}{4}(t^2-160t).$ where $t=b+d.$ Since the last expression is a quadratic with negative leading coefficient, its maximum occurs when $t=-(-160)/(2(1)) = 80.$ This implies $S$ attains its maximum when and only when $t=b+d=80$ and $b=d$ , which is equivalent to saying $b=d=40.$ Therefore the answer to the question is the number of ordered quadruples $(a,b,c,d)$ with $c=d=40$ and $a,b$ being positive integers with $a+b=40$ . Since we have $1\le b=40-a$ or $a\le 39$ , this is equivalent to count the number of integers $a$ with $1\le a \le 39$ . Obviously, that number is $\boxed{39}.$

$\begin{aligned} S &= ab + bd + da + bc + cd \\ &= (b+d)(a+b+c+d) - (b^2 + d^2 + bd) \\ &= 120(b+d) - (b+d)^2 + bd. \end{aligned}$

By AM-GM,

$\frac{b+d}{2} \geq \sqrt{b d} \implies b d \leq \frac{(b+d)^2}{4}$

with equality if and only if $b=d$ . So,

$\begin{aligned} S &= 120(b+d) - (b+d)^2 + bd \\ &\leq 120(b+d) - (b+d)^2 + \frac{(b+d)^2}{4} \\ &= -\frac{3}{4} \left( (b+d)^2 - 160(b+d) \right) \\ &= 4800 - \frac{3}{4} (b+d-80)^2. \end{aligned}$

Therefore, $S$ attains its maximum value of $4800$ if and only if

$b = d = \frac{80}{2} = 40.$

We know that

$a + b + c + d = 120 \implies a + c = 120 - (b + d) = 120 - 80 = 40$

and thus $c = 40 - a$ . Since $a,c$ are positive integers,

$1 \leq a \leq 39,$

for a total of $\boxed{39}$ ordered quadruples $(a,b,c,d)$ for which $S$ attains its maximum.

Let $\lambda$ be the Lagrange multiplier. We wish to maximize $S(a,b,c,d)$ under the constraint $a+b+c+d=120$ . Then, applying the concept of Lagrange mulitpliers ( $\overrightarrow{\bigtriangledown}f(x, y,z)=\lambda \overrightarrow{\bigtriangledown}g(x, y,z)$ and $g(x,y,z)=0$ ), we get the equations:

$b+d=\lambda \\ a+d+c=\lambda \\ b+d=\lambda \\ b+a+c=\lambda \\ a+b+c+d=120$

The first and the third equation are similar. Hence, the solution is not unique. Solving such system gives us $\lambda=80, b=d=40$ and $a+c=40$ . For the set of positive integers, there are only $40-1=39$ pairs such that their sum is $40$ . But because, the values of $b$ and $d$ are fixed already, the number of quadruples, all elements of which are positive integers, that maximizes $S$ is therefore $39$ .

Note that , $ab + bd + da + bc + cd = (a+c)(b + d) +bd$ .To maximise bd , $b = d$ $\Rightarrow S = (120 - 2b)(2b) + b^2 = 240b - 3b^2$ Now this is a simple quadratic function which is maximum when b = 40. Hence , $b = 40 , d = 40 , a + c = 120 - (b + d) = 40$ . Now , since b and d have fixed value (i.e., 40) , we have to select only a and c.Hence, the no. of ordered quadruples = [No. of solutions of $a + c = 40] = \fbox{39}$

First note that when $S = ab + ad + bc + bd + cd$ is maximum, so is $2S = 2(ab + ad + bc + bd + cd) \equiv S_1$ With abbreviations $\sum a \equiv a+b+c+d = 120, \quad \text{ and } \quad \sum a^2 \equiv a^2+b^2+c^2+d^2,$ the following identity holds: $S_1 = \left(\sum a\right)^2 - \sum a^2 - 2ac = M - \sum a^2 - 2ac,$ where $M = 120^2$ .

We need to maximize $S_1$ subject to the constraint $\sum a - 120 = 0$ . Introducing the Lagrange multiplier $\lambda$ , we must maximize $S' = M - \sum a^2 - 2ac +\lambda \left(\sum a - 120 = 0\right).$ Treating $a,b,c,d$ as continuous variables, maximizing w.r.t these variables gives $\partial_a S' = 0 \ \Rightarrow -2(a+c) + \lambda = 0;$ $\partial_c S' = 0 \ \Rightarrow -2(a+c) + \lambda =0 ;$ $\partial_b S' = 0 \ \Rightarrow -2b + \lambda = 0;$ $\partial_d S' = 0 \ \Rightarrow -2d + \lambda = 0,$ where $\partial_a \equiv \partial /\partial a$ and so on. The last two equations imply $b = d = \lambda/2 \equiv x$ Whereas the first two equations imply $a+c = \lambda/2 = x.$ Thus, $a+b+c+d = (a+c)+b+d = 3x = 120 \quad \Rightarrow \quad x = 40.$ Therefore, $b$ and $d$ are fixed, and $a$ and $c$ can take a number of possibilities give by $b = d = 40, \ \text{ and } a+c = 40.$ Thus, possible combinations of $a$ and $c$ are 39 given both are positive.

Suppose P=b+d, we have:

$S=(a+c)(b+d)+bd=P(120-P)+b(P-b)$

$\leq P(120-P)+\frac{P^2}{4}=120P-\frac{3P^2}{4}$ .

Therefore, S attains its maximum when $b=\frac{P}{2}$ and $P=\frac{120}{2*\frac{3}{4}}=80$ , or $b=d=40$ .

We notice that maxS=4800 when b=d=40, regardless to the value of a,c. a,c can be any integer from 1 to 39 as long as a+c=40.

Therefore, there are 39 quadruples (a,b,c,d) satisfy the given condition.

Let's search for some symmetry in the equation: \S = ab + bd + da +bc +cd\

The sum of all pairwise products of $a$ , $b$ , $c$ , and $d$ is $\frac{(a+b+c+d)^2-(a^2+b^2+c^2+d^2)}{2} \\ = \frac{120^2-(a^2+b^2+c^2+d^2)}{2}$ The sum $S$ is henceforth $\frac{120^2-(a^2+b^2+c^2+d^2)}{2}-ac$ , which we wish to maximize. This is equivalent to minimizing $\frac{a^2+b^2+c^2+d^2}{2}+ac$ . Multiplying through by 2, this is equivalent in turn to minimizing $a^2+2ac+c^2+b^2+d^2 = (a+c)^2+b^2+d^2$ . This expression is clearly minimized by having $a+c=b=d=40$ . This stipulation allows $\textbf{39}$ ordered quadruples, corresponding to $a$ (or equivalently, $c$ ) ranging from 1 to 39, inclusive.

You can rewrite $S$ as $S=\frac{(a+b+c+d)^2-((a+c)^2+b^2+d^2)}{2}$

We know $a+b+c+d=120$ so all we need to do is minimise $((a+c)^2+b^2+d^2)$

Using the quadratic mean-arithmetic mean inequality with terms $(a+c), b, d$ we have $\sqrt{\frac{(a+c)^2+b^2+d^2}{3}} \geq \frac{(a+c)+b+d}{3}$

with equality if and only if $a+c=b=d$

As we know that $a+b+c+d=120$ , we must have $a+c=b=d=40$

So we have the condition $a+c=40$ and if $a$ is a positive integer, it can take any of the values 1 to 39 inclusive.

So there are 39 solutions in total

Since S contains all the pairwise products except ac, we can write $2S = 2ab + 2bd + 2da + 2bc + 2cd = (a+b+c+d)^2 - a^2 - b^2 - c^2 - d^2 - 2ac$ $2S = 120^2 - (a+c)^2 - b^2 - d^2$

Thus we are minimizing $(a+c)^2 + b^2 + d^2$ subject to $(a+c) + b + d = 120$ . By repeated use of the AM-GM inequality we can find that the minimum is when $(a+c) = b = d = 40$

Any quadruple in which a+c add up to 40 will work, and there are 39 of these with a and c positive, giving 39 solutions.