## Le Monde puzzle on sums of products

Christian Robert is disappointed by last week-end’s Le Monde’s mathematical problem :

Take the integers 1 to 10. Group them together; the product of these numbers is 3,628,800. This is the first term of your sum. Now group these numbers in 9s. There are 10 different ways of doing this. For each group, take the product of the 9 numbers and substract the results of each of these 10 products from your sum. Repeat the process by grouping the numbers in 8s (add the product), in 7s (substract them), …, in pairs (add them) and in singletons (substract them). What is the final total? What happens if, instead of 1 to 10, you apply the same (even more interminable) procedure to the first 49 squares (1, 4, 9, 16, … 2401)?

Christian solves this the brutal way, which gives the answer but isn’t very satisfying. Here are a couple of alternative ways of getting the product  (call it $P$).

1. Consider the following 11×11 matrix:

$\begin{tabular}{*{11}{c}} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0& 2 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0& 0 & 3 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0& 0 & 0 & 4 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0& 0 & 0 & 0 & 5 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0& 0 & 0 & 0 & 0 & 6 & 1 & 1 & 1 & 1 & 1 \\ 0& 0 & 0 & 0 & 0 & 0 & 7 & 1 & 1 & 1 & 1 \\ 0& 0 & 0 & 0 & 0 & 0 & 0 & 8 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 9 & 1 & 1 \\ 0& 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 10 & 1 \\1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\end{tabular}$

The determinant is obviously 0 (the first and last row are identical). On the other hand, using the Leibniz formula to calculate the determinant would yield all the terms in the product calculated above, plus one term given by the bottom-leftmost 1 and the 1s on the diagonal above the main diagonal. Hence $0=P+1$.

2. This solution is more obvious, and  I expect Le Monde will give a solution similar to this. Let $P_n$ be the product given when using the numbers 1 to $n$. Then

$P_n=nP_{n-1} -P_{n-1} +(-1)^{n-1} \times n$

whence $P_n=(-1)^{n-1}$.

3. I was hoping to find a counting argument to solve this problem, because the alternating signs reminded me of the formula for the cardinal of a union of sets. Here’s the best I have come up with, but I’m sure there’s a better way of seeing this.

Consider the set of all sequences of 10 integers where the $i$th entry is an integer between 1 and $i$; this corresponds to the sequences which lie in the lexicographic order between $(1,1,1,\ldots , 1)$ and $(1, 2, 3, \ldots , 10)$. There are clearly $10!$ such sequences, but let’s count them in a more stupid way, noting that each sequence contains at least one $1$..

Let $A_i$ be the number of such sequences with the additional constraint that the $i$th entry is equal to $1$. Then, using $\vert \cdot \vert$ to denote the cardinal function, we have

$10! = | \cup A_{i} | = | A_1 | + | A_2 | + \ldots + | A_{10} | - |A_1 \cap A_2 | - |A_1 \cap A_3| \ldots + |A_1 \cap A_2 \cap A_3| \ldots$

Each of these terms corresponds to a term in $P$, with the exception of the last term $|A_1\cap A_2 \cap \ldots \cap A_{10}|$, which is worth $1$ and comes with the sign of $(-1)^{n-1}$.

A very similar reasoning holds if we take numbers other than 1, 2, … 10, as long as the first number is a $1$.