Exercice 1 — Les nombres de Schur

Sujet

L'objectif de cet exercice est d'habiller des entiers strictement positifs avec des symboles géométriques, par exemple avec un rectangle 3 , un cercle (4), un triangle 5 en respectant quelques contraintes.

Définitions :

Un triplet d'entiers strictement positifs sera dit de Schur s'il est de la forme ( \(a ; b ; a+b\) ) avec \(a \leq b (1 ; 5 ; 6) ;(4 ; 4 ; 8)\) sont des triplets de Schur. ( \(1 ; 2 ; 4\) ) ; ( \(4 ; 2 ; 6\) ) ne sont pas des triplets de Schur.
Un triplet de Schur \((a ; b ; a+b)\) avec \(a \leq b\) sera dit mono-symbolique si \(a, b\) et \(a+b\) sont habillés de la même forme géométrique.

Par exemple, soit la liste :

Le triplet ( \(1 ; 1 ; 2\) ) est un triplet de Schur mono-symbolique.

\[ 42 \text { (3) } 4 \text { (5) } 6 \text { (7)(8) } 9 \]

Les triplets \((1 ; 2 ; 3)\) et \((1 ; 2 ; 4)\) ne sont pas des triplets de Schur mono-symboliques.

1. Donner trois autres triplets de Schur mono-symboliques de la liste précédente.

Théorème :

Pour un habillage comportant \(n\) symboles ( \(n\) entier strictement positif), il existe au moins un entier \(N\) pour lequel on ne trouve aucun triplet de Schur mono-symbolique dans la liste des entiers de 1 à \(N\).
On note \(\boldsymbol{S}(\boldsymbol{n})\) la plus grande valeur de \(N\) possible.
2. Détermination de \(S(2)\) :

On se donne un habillage de deux symboles : □ et ◯ . On va montrer que la liste la plus longue ne contenant pas de triplet de Schur mono-symbolique est la liste \(1,2,3,4\).
a. Ecrire les quatre triplets de Schur \((a, b, a+b)\) avec \(1 \leq a \leq b \leq a+b \leq 4\).
b. On décide d'habiller l'entier 1 avec un □ . On ne veut pas de triplet de Schur mono-symbolique. Justifier alors qu'il est nécessaire que les entiers 2 et 3 soient habillés d'un ◯ et l'entier 4 d'un □ . Justifier alors que \(S(2) \geq 4\).
c. On ajoute l'entier 5 à la liste \(1,2,3,4\). Justifier qu'il ne peut être habillé ni d'un ◯ , ni d'un \(\bigcirc\). Que vient-on de prouver ?
3. Etude du nombre de Schur \(S(3)\). On cherche à 5 montrer que \(S(3) \geq 13\). On choisit ici trois symboles : □ ,
◯ et \(\Delta\). On cherche donc à habiller chaque entier de 1 à 13 sans avoir de triplet de Schur monosymbolique. D'après la question 2., on sait que l'habillage de l'entier 5 nécessitait un nouveau symbole \(\Delta\).

On a donc la configuration suivante : □ 1 , □ 2, (3) 4, et on cherche à habiller les entiers suivants : \(6,7,8,9,10,11,12,13\).
a. Montrer que 6 ne peut être habillé d'un □ , puis à l'aide d'un raisonnement par l'absurde montrer qu'il ne peut être habillé d'un ◯.
b. De même, montrer alors que l'entier 10 ne peut pas être habillé d'un ◯ . Quel est alors l'habillage de 10 ?
c. Déterminer I'habillage des entiers restants.
d. Que peut-on en déduire pour \(S(3)\) ?
4. Nombre de Schur \(S(4)\)

On considère la liste : \(L=\left[\begin{array}{c}{[1,3,5,15,17,19,26,28,40,42,44],[2,7,8,18,21,24,27,33,37,38,43] \text {, }} \\ {[4,6,13,20,22,23,25,30,32,39,41],[1,12,14,16,29,31,34,35,36]}\end{array}\right]\)
\(\mathrm{L}[2]\) est l'élément \(\mathrm{n}^{\circ} 2\) de la liste L soit la liste \([2,7,8,18,21,24,27,33,37,38,43]\). \(\mathrm{L}[2][4]\) est l'élément \(\mathrm{n}^{\circ} 4\) de la liste L[2] soit le nombre 18 .