Les deux piles

Ce problème assez surprenant m’a été posé par Amic. On peut le trouver sur affairedelogique.com.

Les deux piles (*)

Alice possède \({2N}\) cartes, portant les numéros de 1 à \({2N}\). Elle mélange les cartes, et en fait deux piles A et B de \({N}\) cartes chacune. Elle range la pile A dans l’ordre croissant, et la pile B dans l’ordre décroissant. Enfin, elle prend la première carte de chaque pile, calcule la valeur absolue de leur différence, et range les deux cartes. Elle fait de même avec toutes les cartes suivantes, et additionne tous les résultats. Quelle est la somme totale ?

Et non, la somme totale ne dépend du mélange initial !

Cliquez ici pour voir la solution
La réponse est \({N^2}\). Voici un argument simple pour s’en convaincre. On divise la pile \({A}\) en \({A^-}\) l’ensemble des cartes plus petites ou égale à \({N}\), et \({A^+}\) l’ensemble des cartes strictement plus grandes que \({N}\). De même pour la pile \({B = B^- \cup B^+}\). On a donc

\(\displaystyle | A^- | + | B^- | = | A^+ | + | B^+ | = N \quad \text{et} \quad | A^- | + | A^+ | = | B^- | + | B^+ | = N. \)

On en déduit que

\(\displaystyle | A^- | = N – | B^- | = N – (N – | B^+|) = | B^+ |, \)

et donc

\(\displaystyle | A^- | = | B^+ | \quad \text{et, de même, } \quad | A^+ | = | B^- |. \)

Autrement dit, au moment où Alice passe de pile \({A^+}\) à la pile \({A^-}\), elle passe aussi de la pile \({B^-}\) à la pile \({B^+}\). Avant ce moment, les cartes de \({A^+}\) étant plus grandes que les cartes que \({B^-}\), la valeur absolue de la différence est égale à la différence entre la carte de \({A^+}\) et la carte de \({B^-}\). Après ce moment, la valeur absolue est la différence entre les cartes de \({B^+}\) et les cartes de \({A^-}\). Alice calcule donc la somme

\(\displaystyle S := \sum_{c \in A^+} c \ – \sum_{c \in B^-} c + \sum_{c \in B^+} c \ – \sum_{c \in A^-} c = \sum_{c \in A^+ \cup B^+} c \ – \sum_{c \in A^- \cup B^-} c. \)

Or \({A^- \cup B^- = \{ 1, 2, \cdots, N\}}\) et \({A^+ \cup B^+ = \{N+1, N+2, \cdots, 2N\}}\). Un rapide calcule donne donc

\(\displaystyle S = \sum_{k=N+1}^{2N} k^2 – \sum_{k=1}^N k^2 = \sum_{k = 1}^N (N+k)^2 – k^2 = \sum_{k=1}^N N^2 + 2 Nk = N^3 – 2N \frac{N(N-1)}{2} = N^2. \)

Lien pour marque-pages : Permaliens.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *