Nombre de brins

Plutôt que brin d’un entrelacs, nous parlerons ici de « composante connexe » (essayez de le placer en soirée, ça fait son effet).

On se demande combien un entrelacs aura de composantes connexes, c’est-à-dire combien il faudra de crayons de couleur pour le colorier de manière à ce que chaque brin soit de la même couleur tout du long et que deux brins diférents aient toujours des couleurs différentes.

Si vous prenez un carré, avec p sommets sur un côté, vous aurez alors, exactement p brins, qui font tout simplement un bout de diagonale Nord-Est, rebondissent en haut, redescendent Sud-Est, rebondissent à droite, redescendent Sud-Ouest, rebondissent en bas, remontent Nord-Ouest, pour finir sur le côté gauche. Le carré par exemple, qui compte deux sommets, aura deux anneaux très simples entremêlés.

Si vous avez un rectangle de pxq sommets, ce que vous obtiendrez c’est... Allez, dîtes moi, qu’est-ce qu’on peut faire quand on a deux entiers ? Les additionner, les soustraire, les multiplier, les diviser, oui, certes mais on veut quand-même que si p=q, on obtienne p. Vous ne voyez pas ? C’est le Plus Grand Commun Diviseur.

Le nombre de brins dans un rectangle de pxq est le PGCD(p,q). Par exemple, si vous prenez 12x9, vous aurez 3 brins car 12=4x3 et 9=3x3. Si vous prenez 4x5, vous n’en aurez qu’un seul car 4 et 5 n’ont pas de diviseurs en commun (à part 1). C’est vrai dès que vous prenez un côté qui est un nombre premier, par exemple 6353x8527 n’aura qu’un seul brin (très très long) ! Vous pouvez chercher des nombres premiers ici.

Si vous prenez des triangles maintenant... c’est presque pareil : un triangle équilatéral de côté p aura (p+1)÷2 brins. Par exemple le triangle (2 sommets) est associé au nœud de trèfle, qui a une seule composante.

La chose se complique quand on introduit les murs : un mur empêchant le croisement entre deux brins différents les soude ! Tandis que pour un mur empêchant un croisement du même brin, un des deux types de mur ne perturbera pas le brin, l’autre type de mur le coupera en deux !

Une question intéressante est ensuite la statistique du nombre de brins, quelle est la valeur moyenne du nombre de brins, dans un rectangle de taille pxq, avec un nombre m de murs (c’est plutôt la proportion m/(pxq) qui est pertinente) ?