Kvant Math Problem 965
Let
Verified: yes
Verdicts: PASS + PASS
Solve time: 13m19s
Source on kvant.digital
Problem
Given six numbers $a_1$, $a_2$, $\ldots$, $a_6$. To compute directly the sum of their pairwise products $a_1 a_2+a_1 a_3+\ldots+a_5 a_6$, one needs 15 multiplications and 14 additions. Show how one can simultaneously find the sum of these numbers, the sum of their products taken two at a time, three at a time, four at a time, and five at a time, using only 15 additions and 14 multiplications in total.
N. B. Vasiliev
Exploration
Let
$$e_1=\sum a_i,\qquad e_2=\sum_{i<j}a_i a_j,\qquad e_3=\sum_{i<j<k}a_i a_j a_k,$$
and similarly $e_4,e_5,e_6$. The problem asks for $e_1,e_2,e_3,e_4,e_5$.
The expression
$$(x+a_1)(x+a_2)\cdots(x+a_6)$$
has coefficients $e_1,e_2,e_3,e_4,e_5,e_6$. Hence if these coefficients can be computed efficiently, all required sums are obtained simultaneously.
Suppose we multiply the factors successively. After multiplying by $x+a_k$, the coefficients satisfy
$$c_r' = c_r + a_k c_{r-1}.$$
This is the usual recurrence for elementary symmetric polynomials. For six numbers there are only six factors, so perhaps the total number of arithmetic operations can be counted exactly.
Start with the polynomial $1$. Multiplying by $x+a_1$ requires no arithmetic, since the coefficients become $1,a_1$.
To incorporate $a_2$, only one multiplication and one addition are needed:
$$e_2=a_1a_2,\qquad e_1=a_1+a_2.$$
To incorporate $a_3$, we update three coefficients; this costs $2$ multiplications and $2$ additions. For $a_4$ the cost is $3$ and $3$, for $a_5$ it is $4$ and $4$, for $a_6$ it is $5$ and $5$.
The total cost is
$$1+2+3+4+5=15$$
multiplications and the same number of additions. However the first update actually produces $e_2=a_1a_2$ without any addition, so the additions are
$$0+1+2+3+4+5=15.$$
This is one addition too many.
A closer count shows that when $a_2$ is inserted, $e_1=a_1+a_2$ needs one addition, while $e_2=a_1a_2$ needs no addition. For insertion of $a_k$ with $k\ge3$, the number of additions equals $k-1$. Hence
$$1+2+3+4+5=15$$
additions again.
The statement allows only $15$ additions and $14$ multiplications. Since the final coefficient $e_6=a_1a_2a_3a_4a_5a_6$ is not required, we should avoid computing it.
When $a_k$ is inserted, only coefficients up to degree $5$ are needed. For $k=6$, updating the sixth coefficient would require exactly one multiplication and no addition:
$$e_6'=a_6 e_5.$$
Omitting this computation saves one multiplication and leaves all coefficients $e_1,\dots,e_5$ correct. Then the totals become $14$ multiplications and $15$ additions, exactly as required.
The delicate point is the operation count. The recurrence itself is standard; one must verify carefully that discarding the computation of $e_6$ saves precisely one multiplication and does not affect any coefficient $e_1,\dots,e_5$.
Problem Understanding
We are given six numbers $a_1,\dots,a_6$. We must construct a procedure that simultaneously computes the elementary symmetric sums
$$e_1=\sum a_i,\quad e_2=\sum_{i<j}a_ia_j,\quad e_3,\quad e_4,\quad e_5,$$
using only $15$ additions and $14$ multiplications altogether.
This is a Type D problem. We must exhibit an explicit computation scheme and verify both its correctness and its arithmetic cost.
The core difficulty is obtaining all symmetric sums at once instead of computing each separately. The coefficients of the polynomial
$$\prod_{i=1}^{6}(x+a_i)$$
encode exactly these sums, and successive multiplication by the linear factors updates the coefficients with very few operations.
Proof Architecture
The first claim is that after multiplying $\prod_{i=1}^{k}(x+a_i)$, the coefficient of $x^{k-r}$ equals the elementary symmetric sum of degree $r$ in $a_1,\dots,a_k$; this follows from the expansion of the product.
The second claim is that when a new factor $x+a_k$ is introduced, the coefficients satisfy the recurrence
$$e_r^{(k)}=e_r^{(k-1)}+a_k e_{r-1}^{(k-1)}.$$
This comes from separating terms that contain $a_k$ from those that do not.
The third claim is that updating all coefficients $e_1,\dots,e_5$ for six variables requires $15$ additions and $14$ multiplications; this is obtained by counting the operations performed by the recurrence and omitting the unnecessary computation of $e_6$.
The most delicate point is the operation count, especially the saving of exactly one multiplication when $e_6$ is not computed.
Solution
For $k=1,\dots,6$, let
$$e_r^{(k)}$$
denote the elementary symmetric sum of degree $r$ in the numbers $a_1,\dots,a_k$. Thus
$$e_0^{(k)}=1,$$
and
$$\prod_{i=1}^{k}(x+a_i) = x^k+e_1^{(k)}x^{k-1}+e_2^{(k)}x^{k-2} +\cdots+e_k^{(k)}.$$
Multiplying
$$\prod_{i=1}^{k-1}(x+a_i)$$
by $x+a_k$, the coefficient of $x^{k-r}$ in the new product is
$$e_r^{(k-1)}+a_k e_{r-1}^{(k-1)}.$$
Hence
$$e_r^{(k)} = e_r^{(k-1)} + a_k e_{r-1}^{(k-1)} \qquad (r\ge1).$$
Starting with
$$e_0=1,\qquad e_1=e_2=e_3=e_4=e_5=0,$$
we process $a_1,a_2,\dots,a_6$ successively. When $a_k$ is inserted, the coefficients are updated in descending order:
$$e_5\leftarrow e_5+a_k e_4,$$
$$e_4\leftarrow e_4+a_k e_3,$$
$$e_3\leftarrow e_3+a_k e_2,$$
$$e_2\leftarrow e_2+a_k e_1,$$
$$e_1\leftarrow e_1+a_k.$$
Updating in descending order ensures that every formula uses the coefficients from the preceding stage.
After the six numbers have been processed, the quantities $e_1,e_2,e_3,e_4,e_5$ are exactly the sums of the numbers taken one at a time, two at a time, three at a time, four at a time, and five at a time.
It remains to count the operations.
For $a_1$, no arithmetic operation is needed.
For $a_2$, we compute
$$e_2=a_2e_1, \qquad e_1\leftarrow e_1+a_2,$$
which uses $1$ multiplication and $1$ addition.
For $a_3$, the updates of $e_3,e_2,e_1$ use $2$ multiplications and $2$ additions.
For $a_4$, the updates of $e_4,e_3,e_2,e_1$ use $3$ multiplications and $3$ additions.
For $a_5$, the updates of $e_5,e_4,e_3,e_2,e_1$ use $4$ multiplications and $4$ additions.
For $a_6$, only $e_5,e_4,e_3,e_2,e_1$ are required. Updating them uses $4$ multiplications and $5$ additions. The multiplication that would produce
$$e_6=a_6e_5$$
is omitted because $e_6$ is not requested.
The total number of multiplications is
$$1+2+3+4+4=14,$$
and the total number of additions is
$$1+2+3+4+5=15.$$
Thus all required sums are obtained using exactly $14$ multiplications and $15$ additions.
The required construction is the successive coefficient update described above, yielding
$$\boxed{\bigl(e_1,e_2,e_3,e_4,e_5\bigr)}.$$
Verification of Key Steps
The recurrence
$$e_r^{(k)} = e_r^{(k-1)} + a_k e_{r-1}^{(k-1)}$$
can be derived independently by examining degree-$r$ products. Every such product either avoids $a_k$, contributing $e_r^{(k-1)}$, or contains $a_k$, in which case the remaining $r-1$ factors contribute $e_{r-1}^{(k-1)}$. These two classes are disjoint and exhaustive.
The descending update order is essential. If one updated $e_1$ first, then the computation of $e_2\leftarrow e_2+a_k e_1$ would use the already modified value of $e_1$, producing extra terms involving $a_k^2$. Updating from $e_5$ down to $e_1$ guarantees that every formula uses coefficients from the previous stage.
For the operation count, the last stage deserves special attention. With six variables there would normally be five multiplications for updating $e_6,e_5,e_4,e_3,e_2$. Since $e_6$ is not needed, the update
$$e_6\leftarrow e_6+a_6e_5$$
is omitted. No other coefficient depends on the new value of $e_6$, so the omission affects nothing except the count, reducing the number of multiplications from $15$ to $14$.
Alternative Approaches
One may describe the same method entirely in terms of the polynomial
$$P(x)=\prod_{i=1}^{6}(x+a_i).$$
Starting from $P_1(x)=x+a_1$, one multiplies successively by $x+a_2,\dots,x+a_6$, retaining only the six highest coefficients. The coefficients after the final multiplication are precisely $1,e_1,e_2,e_3,e_4,e_5$. Counting the arithmetic needed to update these coefficients gives the same totals.
Another viewpoint uses a triangular table analogous to Pascal's triangle. The entry in row $k$ and column $r$ is $e_r^{(k)}$, and each entry is obtained from the two neighboring entries in the preceding row via
$$e_r^{(k)} = e_r^{(k-1)} + a_k e_{r-1}^{(k-1)}.$$
This makes the combinatorial meaning of the recurrence transparent, although the polynomial interpretation gives the shortest route to the construction.