Le nombre d'Erdős

Le problème de la semaine dernière a été résolu avec beaucoup d'ingéniosité par une lectrice qui, malheureusement, a ensuite supprimé son commentaire. Voyons comment les mathématiciens hongrois Paul Erdős et Georges Szekeres, collaborateurs réguliers et co-auteurs du théorème d'Erdős-Szekeres , l'ont abordé en leur temps. Partant du principe des cases, ils ont imaginé diviser l'ensemble des 2n premiers nombres {1, 2, …, 2n} en n sous-ensembles tels que – en prenant n + 1 nombres de l'ensemble initial – au moins deux d'entre eux appartiennent au même sous-ensemble. Ainsi, si ces sous-ensembles étaient tels que, pour deux nombres quelconques du même sous-ensemble, l'un était multiple de l'autre, l'énoncé initial serait démontré.

À cette fin, les n sous-ensembles sont définis comme les intersections de l'ensemble {1, 2, …, 2n} avec les ensembles suivants : {1, 2, 2², 2³…}, {3, 3 x 2, 3 x 2², 3 x 2³…}, {5, 5 x 2, 5 x 2², 5 x 2³,…}, …, {n-1, (n-1) x 2, (n-1) x 2², n-1) x 2³…}, où chaque élément divise le suivant de son sous-ensemble, et de plus, chaque nombre de l'ensemble initial {1, 2, …, 2n} peut s'écrire de manière unique sous la forme (2m-1) x 2ᴷ, il appartient donc à l'un de ces ensembles. Une explication quelque peu complexe que Bretos Bursó résume ainsi :

Tout nombre naturel est le produit d'une partie paire et d'une partie impaire (le produit de ses facteurs premiers égaux à 2 et celui de ses facteurs premiers impairs). Si deux nombres distincts ont la même partie impaire, alors l'un d'eux divise l'autre (celui qui est divisible par 2 fois plus que l'autre est un multiple de l'autre). Les nombres n + 1 que nous prenons ont n parties impaires possibles (1, 3, 5..., 2n-1), il y en a donc au moins deux avec la même partie impaire.

Et en parlant d'Erdős et de collaborations entre mathématiciens, on ne peut manquer de mentionner le nombre d'Erdős . Le prolifique mathématicien hongrois n'avait pas moins de 509 collaborateurs directs, dont le nombre d'Erdös (nE) est de 1 ; ceux qui ont collaboré avec l'un de ces 509, mais pas directement avec Erdös, ont un nE de 2 (soit plus de six mille), et ainsi de suite.

Selon vous, quel pourrait être votre nombre d'Erdős, en utilisant une estimation fermienne ? Je me contenterai d'une approximation raisonnable. (Indice : si vous lisez cette section régulièrement, ce sera beaucoup plus facile.)

La conjecture d'Erdős-Szekeres

Le théorème d’Erdős-Szekeres mentionné ci-dessus ne doit pas être confondu avec la conjecture du même nom.

Le théorème stipule que pour toute paire de nombres naturels (entiers et positifs) r et s, toute séquence de longueur égale ou supérieure à (r-1)(s-1) + 1 contient une sous-séquence monotone croissante de longueur s ou une sous-séquence monotone décroissante de longueur r.

Cela paraît compliqué, mais un exemple simple clarifiera le concept : pour r = 3 et s = 2, donc (r-1)(s-1) + 1 = 3, toute permutation de trois nombres possède soit une sous-suite croissante de longueur trois, soit une sous-suite décroissante de longueur deux. Prenons les six permutations possibles des nombres 1, 2 et 3 (et écrivons les suites sous forme simplifiée) :

• 123 possède une sous-séquence croissante de longueur trois en elle-même : 123
• 132 a une sous-séquence décroissante de longueur deux : 32
• 213 a une sous-séquence décroissante de longueur deux : 21
• 231 a deux sous-séquences décroissantes de longueur deux : 21 et 31
• 312 a deux sous-séquences décroissantes de longueur deux : 31 et 32
• 321 comporte trois sous-séquences décroissantes de longueur deux : 32, 31 et 21

Comment aborderiez-vous la démonstration de ce théorème à partir du principe des cases ? (Je ne demande pas une démonstration rigoureuse, juste un plan d'attaque.)

Quant à la conjecture d'Erdős-Szekeres, il s'agit d'une généralisation du « problème de la fin heureuse », ainsi nommé par Erdős car il a conduit au mariage de son ami et collaborateur Georges Szekeres avec la mathématicienne australienne Esther Klein. Mais ceci est un autre sujet.