Exercice 46

1. Le produit ne dépend pas de l'ordre des termes : il suffit d'examiner les décompositions rangées par termes décroissants. Pour $n = 6$, par exemple, on en trouve onze, de produits respectifs $$\underbrace{6}_{(6)},\ \underbrace{5}_{(5,1)},\ \underbrace{8}_{(4,2)},\ \underbrace{4}_{(4,1,1)},\ \underbrace{9}_{(3,3)},\ \underbrace{6}_{(3,2,1)},\ \underbrace{3}_{(3,1,1,1)},\ \underbrace{8}_{(2,2,2)},\ \underbrace{4}_{(2,2,1,1)},\ \underbrace{2}_{(2,1,1,1,1)},\ \underbrace{1}_{(1,1,1,1,1,1)}.$$ On procède de même pour les autres valeurs de $n$, et l'on obtient le tableau suivant.

On voit déjà apparaître les règles que la question 3 établira : le terme $1$ ne sert à rien dès que $n \geqslant 2$, un terme $5$ ou $6$ gagne à être coupé en deux, et $4$ fait aussi bien que $2 + 2$.

2. Soit $(x_{1}, \dots, x_{p})$ une décomposition de $n$. Chaque terme vérifie $1 \leqslant x_{i} \leqslant n$, et la somme des $p$ termes, au moins égale à $p$, vaut $n$ : on a donc $p \leqslant n$. Le produit est alors majoré : $$x_{1} \times \dots \times x_{p} \leqslant n^{p} \leqslant n^{n}.$$ L'ensemble des produits des décompositions de $n$ est ainsi une partie de $\mathbb{Z}$ majorée par $n^{n}$, non vide puisqu'elle contient le produit $n$ de la décomposition $(n)$. D'après la question 10 de l'exercice 42, elle possède un plus grand élément. $$\boxed{M_{n} \text{ existe, et } n \leqslant M_{n} \leqslant n^{n}.}$$ Piège : cette étape n'est pas une formalité. La question 3 raisonne sur une décomposition de produit maximal, et un raisonnement portant sur un objet dont on n'a pas établi l'existence peut aboutir à des absurdités. Ainsi, « soit $N$ le plus grand entier naturel ; si $N \geqslant 2$, alors $N^{2} > N$, ce qui est impossible ; donc $N = 1$ » est un raisonnement correct à partir d'une hypothèse fausse : le plus grand entier naturel n'existe pas.

3. (a) Soit $(x_{1}, \dots, x_{p})$ une décomposition de $n$ de produit $M_{n}$. On raisonne par l'absurde, en montrant qu'une décomposition contenant un terme interdit pourrait être modifiée en une décomposition de produit strictement plus grand.

Supposons qu'un terme $x_{i}$ vaille $1$. Comme $n \geqslant 2$, la décomposition $(n)$ est exclue, donc $p \geqslant 2$ et il existe un autre terme $x_{j}$, avec $j \neq i$. Remplaçons les deux termes $x_{i} = 1$ et $x_{j}$ par le seul terme $x_{j} + 1$ : la somme est inchangée, et, en notant $Q$ le produit des autres termes, égal à $1$ s'il n'y en a pas, le produit passe de $Q \times 1 \times x_{j}$ à $Q\,(x_{j} + 1)$, qui est strictement plus grand. C'est contraire à la maximalité de $M_{n}$.

Supposons qu'un terme $x_{i}$ vérifie $x_{i} \geqslant 5$. Remplaçons-le par les deux termes $2$ et $x_{i} - 2$, qui sont des entiers non nuls de somme $x_{i}$. Le facteur $x_{i}$ du produit est remplacé par $$2\,(x_{i} - 2) = x_{i} + (x_{i} - 4) > x_{i},$$ et le produit augmente strictement : c'est encore impossible. $$\boxed{\text{Les termes d'une décomposition de produit } M_{n} \text{ appartiennent tous à } \{2,\ 3,\ 4\}.}$$

3. (b) Partons d'une décomposition de produit $M_{n}$ et remplaçons chacun de ses termes égaux à $4$ par deux termes égaux à $2$. La somme ne change pas, et le produit non plus, puisque $2 \times 2 = 4$ : on obtient une décomposition de produit $M_{n}$ formée de $2$ et de $3$. Si le terme $2$ y figurait au moins trois fois, on remplacerait trois termes $2$, de somme $6$, par deux termes $3$, de même somme ; le produit serait multiplié par $\frac{3 \times 3}{2 \times 2 \times 2} = \frac{9}{8} > 1$, ce qui contredirait la maximalité. $$\boxed{\text{Il existe une décomposition de produit } M_{n} \text{ formée de } 2 \text{ et de } 3, \text{ avec au plus deux } 2.}$$

4. Pour $n \geqslant 2$, considérons la décomposition de la question 3 (b), et notons $a \in \{0, 1, 2\}$ le nombre de ses termes égaux à $2$, et $b$ le nombre de ses termes égaux à $3$. Alors $2a + 3b = n$ et $M_{n} = 2^{a}\,3^{b}$. Les trois valeurs possibles de $2a$ sont $0$, $2$ et $4$, et une seule convient dans chaque cas.

• Si $n = 3q$, alors $2a = 3(q - b)$ est un multiple de $3$, ce qui impose $a = 0$, puis $b = q$.

• Si $n = 3q + 1$, alors $2a - 1 = 3(q - b)$, et parmi $-1$, $1$ et $3$ seul $3$ est multiple de $3$ : $a = 2$, puis $b = q - 1$. On note que $q \geqslant 1$, puisque $n \geqslant 2$.

• Si $n = 3q + 2$, alors $2a - 2 = 3(q - b)$, et parmi $-2$, $0$ et $2$ seul $0$ est multiple de $3$ : $a = 1$, puis $b = q$.

Le cas $n = 1$ est à part : la seule décomposition est $(1)$, et $M_{1} = 1$. $$\boxed{M_{3q} = 3^{q} \ (q \geqslant 1)} \qquad \boxed{M_{3q+1} = 4 \times 3^{q-1} \ (q \geqslant 1)} \qquad \boxed{M_{3q+2} = 2 \times 3^{q} \ (q \geqslant 0)}$$ On retrouve les valeurs de la question 1 : $M_{4} = 4$, $M_{5} = 6$, $M_{6} = 9$. ✓ Comme $10 = 3 \times 3 + 1$ et $2026 = 3 \times 675 + 1$, on obtient $$\boxed{M_{10} = 4 \times 3^{2} = 36} \qquad\text{et}\qquad \boxed{M_{2026} = 4 \times 3^{674}.}$$ La valeur $M_{10} = 36$ est bien celle de la décomposition $(3,3,4)$ de l'énoncé, qui était donc optimale. Ces résultats ont été confirmés par ordinateur, en examinant toutes les décompositions pour $n \leqslant 60$.

À retenir : la méthode employée, qui consiste à supposer qu'un optimum existe puis à montrer qu'une modification locale l'améliorerait s'il ne vérifiait pas certaines conditions, s'appelle un argument d'échange. Elle est très répandue en optimisation et en algorithmique. La prédominance du terme $3$ a une explication : si l'on découpe $n$ en parts égales de taille $x$, le produit vaut $x^{n/x}$, et l'étude de la fonction $x \mapsto \frac{\ln x}{x}$, possible dès le chapitre 5, montre que ce produit est maximal pour $x = \mathrm{e} \approx 2{,}718$, dont $3$ est l'entier le plus proche. Le cas $n = 1976$ a fait l'objet du problème 4 de l'Olympiade internationale de mathématiques de 1976 ; la réponse est $M_{1976} = 2 \times 3^{658}$.