The Immortal Kangaroo Sequence - Numberphile

La "séquence virgule" est une construction mathématique proposée par Eric Angelini, qui s'appuie sur l'idée de considérer les virgules entre les termes d'une séquence comme des séparateurs. Pour chaque virgule, on définit un "séparateur de virgule" en regardant les chiffres immédiatement à gauche et à droite de la virgule. Par exemple, dans la séquence 1, 4, 9, 16, 25, le séparateur de virgule entre 1 et 4 est 14, entre 4 et 9 est 49, etc. L'idée centrale d'Angelini était de trouver une séquence où la séquence des séparateurs de virgules est identique à la séquence des différences entre les termes successifs. Pour trouver une telle séquence, on applique des règles strictes : pas de répétitions, une séquence infinie, des nombres positifs, et toujours choisir le plus petit nombre possible, en commençant par 1. Le processus commence par le nombre 1. On cherche le terme suivant de manière à ce que la différence entre ce nouveau terme et 1 soit un nombre dont les deux chiffres sont déterminés par les chiffres entourant la virgule. Par exemple, si le terme suivant est 12, la différence est 11. Le séparateur de virgule est alors 11. On cherche ensuite le terme suivant, en considérant que le séparateur de virgule doit commencer par le chiffre des unités de la différence précédente (ici, 1). Par exemple, si le séparateur de virgule est 23, la différence entre le terme actuel et le terme suivant est 23. Si le terme actuel est 12, le terme suivant sera 12 + 23 = 35. On vérifie ensuite que le séparateur de virgule entre 12 et 35 est bien 23. Ce processus est itératif. Cependant, cette construction peut mener à des impasses, appelées "mines antipersonnel" (landmines). Une mine antipersonnel est un nombre tel qu'il n'existe aucun terme suivant possible selon les règles établies. La structure de ces mines est particulière : un nombre dont les deux derniers chiffres somment à neuf, précédé par un nombre quelconque de neuf. Par exemple, 99999945 est une mine antipersonnel. Si la séquence atteint un tel nombre, elle s'arrête. Des calculs ont montré que si l'on commence la séquence avec le nombre 1, elle atteint une mine antipersonnel après environ 2,1 millions de termes. Si l'on commence avec 3, la séquence s'arrête après seulement deux termes. D'autres points de départ sont étudiés, comme 4 et 5, qui mènent également à des mines antipersonnel après un certain temps. Il existe une analogie avec un kangourou qui saute sur un chemin numéroté, où chaque saut représente une étape de la séquence. Les mines antipersonnel sont des "terrains piégés". Les sauts du kangourou sont limités, entre 1 et 99 unités. Les mines antipersonnel sont concentrées dans certaines régions, notamment lorsque les nombres deviennent grands. Bien qu'il y ait des périodes de sécurité, le risque d'atterrir sur une mine augmente. Une estimation simplifiée suggère que la probabilité de mourir est d'environ 12 sur 100, menant à une espérance de vie d'environ 10 puissance 8.3 étapes. Des recherches ont été menées pour prouver que toutes les séquences finissent par mourir, quelle que soit la base numérique utilisée. En base 2, les séquences sont infinies et ne meurent jamais. En base 3, une preuve assistée par ordinateur, bien que complexe, a démontré que toutes les séquences meurent. Cette preuve a été étendue à des bases jusqu'à 643. Pour la base 10, il a également été prouvé que toutes les séquences finissent par mourir, même si la preuve est difficile. Cependant, une légère modification de la règle permet de créer des séquences "immortelles". Si, à un moment donné, il existe deux choix possibles pour le terme suivant (c'est-à-dire deux nombres qui satisfont la condition du séparateur de virgule), on peut choisir de prendre le chemin le plus long. En choisissant judicieusement parmi ces bifurcations, on peut potentiellement éviter les mines antipersonnel et obtenir une séquence infinie. L'existence d'une telle séquence immortelle est prouvée par un argument mathématique qui utilise le lemme de König, lequel dépend de l'axiome du choix. Cet axiome permet d'affirmer l'existence d'un chemin infini sans pour autant fournir une méthode constructive pour le trouver. Il existe une séquence binaire (une suite de 0 et de 1) qui, appliquée à ces choix, génère une séquence immortelle. Cette séquence est répertoriée dans l'Online Encyclopedia of Integer Sequences (OEIS), mais sa règle exacte n'est pas connue au-delà de quelques dizaines de termes. L'analyse de l'ensemble des séquences révèle que tous les chemins finissent par converger vers un nombre inférieur à 99. Il existe environ 50 points de départ distincts (composantes connectées dans un graphe) qui mènent à des arbres de séquences. L'existence d'une séquence immortelle implique qu'au moins un de ces arbres doit être infini. Des recherches ont identifié que le nombre 20, en base 10, est un point de départ particulier qui, si l'on fait les bons choix aux bifurcations, peut mener à une séquence immortelle. Les chercheurs ont pu déterminer les premiers choix à faire pour éviter la mort à partir de ce point de départ. Les questions ouvertes persistent : déterminer la longueur exacte d'une séquence avant qu'elle ne meure pour un point de départ donné, et trouver une preuve générale pour toutes les bases supérieures à deux, ainsi qu'une méthode constructive pour identifier le chemin immortel sans faire appel à l'axiome du choix.