Das Langford-Pairing

Das Langford-Problem bzw. das Langford-Pairing ist nach dem schottischen Mathematiker C. Dudley Longford benannt. 1958 beobachtete er seinen Sohn beim Spielen mit bunten Bauklötzen. Dabei bemerkte er, dass dieser drei Paare verschieden farbiger Klötzchen so aufeinander gestapelt hatte, dass sich zwischen dem roten Paar ein Baustein, zwischen dem blauen Paar zwei Bausteine und zwischen dem grünen Paar drei Bausteine befanden.

Langford fügte ein gelbes Paar hinzu und stellte fest, dass es auch hierzu eine Lösung gab. Zwischen dem gelben Paar befanden sich vier Bausteine.

Longford ersetzte daraufhin die Farben mit Zahlen in der Form 41312432, so dass zwischen der jeweiligen Zahl genau so viele Zahlen standen, wie sie selbst repräsentierte. Also zwischen den beiden 4en vier andere Zahlen, zwischen den beiden 3en, drei Zahlen, zwischen den beiden 2en zwei und den beiden 1sen eine Zahl. Langford forschte weiter und fand Lösungen für 7, 8, 11, 12 und 15 Paaren von Zahlen.

Langford konnte aber keine Lösung für n = 5, 6, 9 oder 10 Paaren von Zahlen finden. 1959 bewies der Mathemtiker Roy O. Davis, dass die Anzahl der Zahlenpaare ‘n‘ entweder durch 4 teilbar (wie z.B. die 12) oder eins weniger als eine durch 4 teilbare Zahl (wie z.B. die 15) sein musste. Er fragte sich auch, wie viele veschiedene Lösungen so gestalteter Zahlenreihen es geben mochte. (siehe links)

Mit zunehmendem n gibt es eine steigende Anzahl von Langford-Sequenzen. Es gibt nur eine Lösung für n=3 und n=4, 26 Lösungen für n=7, 150 für n=8, 17.792 für n=11, 108.144 für n=12 etc und schon 46.845.158.056.515.936 für n=24. Offensichtlich ist es extrem rechenintensiv, alle Lösungen für ein gegebenes n zu finden. Zuletzt wurde die Anzahl Lösungen für n= 27 und 28 berechnet. Weiter kam man bisher nicht.