Théorème de Schur

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur les redirections Pour d'autres théorèmes de Schur, voir Issai Schur.

En mathématiques, le théorème de Schur énonce que, pour toute partition de l'ensemble des entiers strictements positifs en un nombre fini c de parties, l'une des parties contient trois entiers x, y, z tels que :

x + y = z.

Concrètement, si on attribue une couleur à chaque entier, il existe trois entiers x, y, z de même couleur tels que x + y = z.

Plus précisément, si c est le nombre de couleurs utilisées, il existe un plus petit entier S(c), appelé nombre de Schur, tel que le même résultat s'applique à l'ensemble fini {1, ..., S(c)}.

Exemple : c=2. Montrons que S(2)=5. On constate qu'il existe une partition et une seule de {1, ...,4} en deux parties dont aucune ne contient trois entiers x,y,z tels que x+y=z, à savoir la partition suivante : 1, 2, 3, 4, et qu'il est impossible d'ajouter 5 à l'une des deux parties sans créer une somme x+y=5 dans cette partie, car on aura 5 = 1 + 4 ou 5 = 2 + 3

c=3. Montrons que S(3) est au moins égal à 14. En effet, il existe une partition de {1, ...,13} en trois parties dont aucune ne contient trois entiers x,y,z tels que x+y=z, à savoir la partition suivante : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13. On remarque qu'il est impossible d'ajouter 14, car selon la couleur du nombre 14, on prendra : 14 = 1 + 13 ou 14 = 2 + 12 ou 14 = 9 + 5. En recensant toutes les partitions analogues de {1, ...,13} (car ce n'est pas la seule de ce type) on s'apercevrait qu'on ne peut jamais ajouter 14. Par suite, S(3)=14.

Ce résultat peut être considéré comme un exemple de la théorie de Ramsey.

En combinatoire[modifier | modifier le code]

En combinatoire, un autre théorème, aussi appelé théorème de Schur, concerne le nombre de manières d'exprimer un entier naturel comme combinaison linéaire à coefficients non négatifs d'un ensemble donné d'entiers premiers entre eux . Plus précisément, si \{a_1,\ldots,a_n\} est un ensemble d'entiers tels que \operatorname{pgcd}(a_1,\ldots,a_n)=1, alors le nombre de tuples distincts (c_1,\ldots,c_n) tels que x=c_1a_1 + \cdots + c_na_n admet comme expression, quand x tend vers l'infini :

\frac{x^{n-1}}{(n-1)!a_1\cdots a_n}\left(1+o(1)\right).

En particulier, pour tout ensemble \{a_1,\ldots,a_n\} d'entiers premiers entre eux, il existe une valeur de x telle que tout entier plus grand admet au moins une représentation comme combinaison linaire de a_1,\ldots,a_n. Cette conséquence du théorème est en rapport avec le contexte plus familier du problème des pièces de monnaie de représenter un certain montant d'argent à l'aide de pièces de monnaies de valeur faciale donnée. Si ces valeurs faciales sont premières entre elles, comme 2 et 5, tout montant assez grand peut être représenté en utilisant uniquement ces pièces.

Articles connexes[modifier | modifier le code]