Le Monde puzzle on sums of products

Mathematical games 2 Minutes

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 ith 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 ith 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.

Published by Robin Ryder

Published

One thought on “Le Monde puzzle on sums of products”

  1. Pingback: Welcome, Robin! « Xi'an's Og

Leave a comment