Exercice 49

On appelle $U$ et $V$ les deux parties, et l'on raisonne par l'absurde : on suppose qu'aucune ne contient trois entiers en progression arithmétique. On écrira simplement « $(a,b,c)$ interdit » pour rappeler qu'une progression $(a,b,c)$ ne peut pas être contenue dans une seule partie.

1. Premier cas : $4$ et $6$ sont dans la même partie, disons $U$. Les progressions $(2,4,6)$, $(4,5,6)$ et $(4,6,8)$ forcent $2$, $5$ et $8$ à être dans $V$. Mais $(2,5,8)$ est une progression contenue dans $V$ : contradiction.

Second cas : $4$ et $6$ sont dans des parties différentes ; quitte à échanger les noms, $4 \in U$ et $6 \in V$.

• Si $5 \in U$ : $(3,4,5)$ donne $3 \in V$ ; $(3,6,9)$ donne $9 \in U$ ; $(5,7,9)$ donne $7 \in V$ ; $(6,7,8)$ donne $8 \in U$ ; $(2,5,8)$ donne $2 \in V$ ; $(1,2,3)$ donne $1 \in U$. Mais alors $(1,5,9)$ est contenue dans $U$ : contradiction.

• Si $5 \in V$ : $(5,6,7)$ donne $7 \in U$ ; $(1,4,7)$ donne $1 \in V$ ; $(1,5,9)$ donne $9 \in U$ ; $(7,8,9)$ donne $8 \in V$ ; $(2,5,8)$ donne $2 \in U$ ; $(2,3,4)$ donne $3 \in V$. Mais alors $(1,3,5)$ est contenue dans $V$ : contradiction.

2. Non. Les progressions arithmétiques de trois termes dans $[\![1\,;8]\!]$ sont au nombre de douze : $$\begin{array}{ll} \text{raison } 1 : & (1,2,3),\ (2,3,4),\ (3,4,5),\ (4,5,6),\ (5,6,7),\ (6,7,8) \\ \text{raison } 2 : & (1,3,5),\ (2,4,6),\ (3,5,7),\ (4,6,8) \\ \text{raison } 3 : & (1,4,7),\ (2,5,8) \end{array}$$ Le partage $\{1,2,5,6\}$, $\{3,4,7,8\}$ n'en laisse aucune dans une même partie, comme on le vérifie sur cette liste.

Pour trouver tous les partages exceptionnels, on reprend le raisonnement de la question 1, sans les progressions qui utilisent $9$. Le premier cas mène toujours à une contradiction, car $(2,5,8)$ reste dans $[\![1\,;8]\!]$. Dans le second cas, avec $4 \in U$ et $6 \in V$ :

• si $5 \in V$ : $(5,6,7)$, $(1,4,7)$ et $(1,3,5)$ donnent successivement $7 \in U$, $1 \in V$, $3 \in U$ ; puis $(2,3,4)$ donne $2 \in V$ et $(2,5,8)$ donne $8 \in U$. On obtient $U = \{3,4,7,8\}$ et $V = \{1,2,5,6\}$ ;

• si $5 \in U$ et $7 \in V$ : $(3,4,5)$, $(6,7,8)$, $(2,5,8)$, $(1,2,3)$ donnent $3 \in V$, $8 \in U$, $2 \in V$, $1 \in U$. On obtient $U = \{1,4,5,8\}$ et $V = \{2,3,6,7\}$ ;

• si $5 \in U$ et $7 \in U$ : $(3,4,5)$, $(1,4,7)$, $(1,2,3)$, $(2,5,8)$ donnent $3 \in V$, $1 \in V$, $2 \in U$, $8 \in V$. On obtient $U = \{2,4,5,7\}$ et $V = \{1,3,6,8\}$.

Dans chaque cas, toutes les progressions de la liste ont été examinées : aucune n'est contenue dans une seule partie. Exactement trois partages font exception : $$\boxed{\{1,2,5,6\} \text{ et } \{3,4,7,8\}} \qquad \boxed{\{1,4,5,8\} \text{ et } \{2,3,6,7\}} \qquad \boxed{\{1,3,6,8\} \text{ et } \{2,4,5,7\}}$$ Ce résultat a été confirmé par l'examen informatique des $2^{8} = 256$ manières de répartir les entiers.

3. Soit $\mathbb{N}^{*}$ partagé en deux parties. Pour tout entier $k \geqslant 0$, les neuf entiers $k + 1$, …, $k + 9$ se répartissent entre les deux parties ; comme une translation conserve les progressions arithmétiques, la question 1 s'applique à eux et fournit une progression contenue dans une seule partie. En prenant $k = 0$, $9$, $18$, …, on obtient des blocs disjoints. $$\boxed{\text{L'une des parties contient une infinité de progressions arithmétiques de trois termes.}}$$ À retenir : le nombre $9$ est le plus petit possible, d'après la question 2. Ce résultat est le premier cas du théorème de van der Waerden (1927) : quel que soit le nombre de parties, et quelle que soit la longueur voulue, tout partage de $\mathbb{N}^{*}$ en un nombre fini de parties laisse dans l'une d'elles des progressions arithmétiques aussi longues que l'on veut.