Les suites de Langford

Publié le 6 mai 202122 juin 2021 par Herve Kabla

Je ne connaissais pas les suites de Langford, jusqu’à la semaine dernière. Mais elles ont fait une entrée fracassante dans ma vie. En fait, elles sont même entrées il y a bien plus longtemps que je ne l’imaginais. Je ne connaissais simplement pas leur nom jusqu’à ce jour.

Le problème d’une vie

Car les suites de Langford, voyez-vous, sont la dénomination exacte d’un problème qui me hante depuis plusieurs années. Un problème dont j’étais – jusqu’à hier – à peu près certain de ne jamais connaître la solution. Un peu comme l’existence de Dieu, sauf que l’existence de Dieu pose problème à la moitié de l’humanité ou presque, alors que les suites de Langford ne concernent qu’une poignée d’individus. Et pourtant, j’ai fait tout mon possible pour qu’elles concernent un peu plus de monde chaque jour.

D’ailleurs, cet article s’inscrit dans cette démarche visant à rendre les suites de Langford un peu plus populaires. Et mine de rien, ça marche, puisqu’après avoir achevé la lecture de cet article, vous pourrez en parler autour de vous.

Car voyez-vous, les suites de Langford sont un problème dont j’ai pris connaissance dans les années 90, à la lecture d’un article de La Recherche, que ma soeur avait probablement laissé traîner à la maison. Funeste idée, qui me hante depuis ce jour. Ne sachant comment les désigner de manière scientifique, je leur ai donné un petit nom : le problème des K boules. Ça sonne bien, ça leur donne un petit air afghan (Kaboul, K boules, vous pigez ?), et puis il y a du K dedans, et quand on s’appelle Kabla, forcément, ça conforte, un peu.

Ce problème des K boules, ma femme ou mes enfants pourraient vous en parler, tant je l’ai vulgarisé auprès de mes proches, ou de toute personne invitée à partager un repas à la maison. Car son énoncé est d’une simplicité enfantine, et ne demande aucune connaissance mathématique.

D’ailleurs, le voici.

Choisissez un entier N, supérieur ou égal à 2. Prenez N paires de boules numérotées de 1 à N. Vous disposez donc de 2N boules : 2 boules numérotées 1, 2 boules numérotées 2, etc. jusqu’à N. Maintenant, je vous demande de ranger ces 2N boules sur une ligne de telle sorte qu’entre les boules numérotées k, il y ait exactement k boules.

Vous constaterez facilement qu’avec N=2, il n’y a pas de solution, qu’avec N=3 on trouve facilement au moins une configuration, qu’avec N=4 c’est un peu plus corsé, mais qu’avec N=5, vous ne trouverez rien même en y passant quelques heures.

Attention : spoiler

Eh oui, attention spoiler, car je vais donner une indication.

Vous êtes prêts à lire ce qui suit ? Sinon passez au titre suivant.

Spoiler : il n’existe de solutions que pour N multiple de 4 ou N congru à 3 modulo 4, ce qui signifie, pour les non initiés, que dans la division euclidienne de N par 4, il reste 3.

Ça se montre assez facilement, mais il faut y réfléchir quelques minutes.

Ou quelques heures, ça dépend.

Cette propriété sur N explique pourquoi il n’y a pas de solution pour N=5 (congru à 1 modulo 4) ou N=6 (congru à 2 modulo 4), mais qu’il en existe pour N=7 ou N=8 (c’est un bon passe-temps pour un weekend pluvieux).

Idem, pas de solution pour N=9 ou 10, mais plein de solutions pour N=11 ou 12. Une des solutions pour N=12 constituait d’ailleurs la signature de mes emails sur Lotus Notes, du temps où j’officiais chez Dassault Systèmes. À chacun ses signes distinctifs.

Vous pouvez reprendre la lecture

Le sujet qui m’obsède, donc, c’est de trouver toutes les valeurs de N pour lesquelles il existe une solution. Et donc, de prouver que la condition nécessaire énoncée au paragraphe précédent (attention spoiler) est aussi suffisante.

Accessoirement, j’ai aussi cherché, en vain, de mettre au point un algorithme autre que la force brute (ie passer toutes les combinaisons en revue) pour trouver les solutions pour un N donné. J’y ai passé des heures, des journées entières.

En vain.

Je n’ai réussi qu’à mettre au point deux minables petits programmes, un écrit en C truffé de bugs, qui ne trouvait pas toutes les solutions, et un autre en Python, un peu plus solide, mais dont les performances explosent avec la combinatoire liée au nombre de permutations sur 2N boules…

J’en ai parlé à des amis matheux. Rien n’en est sorti.

J’en ai parlé à mes élèves, du temps où j’enseignai le marketing digital à l’X. Seul un, Robin Guillard, s’y est vraiment intéressé, avec une approche originale. Mais je n’ai pas eu de nouvelles de sa part depuis longtemps.

Alors par dépit, et ayant découvert très récemment le site Mathematics Stack Exchange, j’ai posté le problème, espérant qu’un membre de cette auguste communauté se pencherait dessus.

Hélas, je n’ai rien obtenu, si ce n’est la confirmation qu’ils ‘agit d’un problème connu, déjà abordé par d’autres chercheurs (d’où sa probable mention dans La Recherche). Il porte même un joli nom, celui des suites de Langford, qui est d’ailleurs le pendant des suites de Skolem (les mêmes à un décalage près).

Voilà, vous en savez suffisamment, désormais, sur l’une de mes obsessions.

Vous pourrez désormais vous adonner à la recherche de solutions.

Faites le, avec vos proches et vos amis. Vous verrez, c’est très sympathique, par exemple à table (lorsque la crise Covid le permettra, vous prenez deux verres, deux bouteilles, le sel et le poivre, et vous disposez ainsi de 3 paires d’objets à aligner…

Et miracle…

Et hier soir, je suis tombé sur cet article, qui affirme qu’un certain Roy Davies a fourni une solution explicite. Une solution limpide. Il ne produit pas toutes les combinaisons. Mais il fournit une méthode extrêmement malicieuse pour en produire au moins une, remarquant des configurations parfaitement adaptées au problème, comme par exemple 8 6 4 2 _ _ 2 4 6 8, ou bien 9 7 5 3 1 _ 1 3 5 7 9. Il suffit alors de les imbriquer intelligemment, en les divisant en deux paquets, et Roy Davies fournit une astuce pour cela.

C’est un véritable soulagement.

Hier, j’ai eu le sentiment de finir ma journée en étant un peu moins stupide.