'-'-'-'-'-'-'

Ziemlich langweilig also. Nun fanden aber kürzlich Linealhersteller heraus, dass man die Produktionskosten senken kann, wenn man einige der Marken weglässt, ohne dabei die Funktionalität des Lineals zu beeinträchtigen. Zum Beispiel kann man mit dem Lineal

'-'---'--'

auch alle Abstände messen, die man mit dem Standard-Lineal gleicher Länge messen kann.

Wie viele Marken kann man denn überhaupt weglassen, wenn man alle Abstände bis zu einer gewissen Länge messen will? Dies ist im wesentlichen die Fragestellung um die es hier geht, und die aus eintönigen Linealen höchst interessante Objekte der Kombinatorik macht.

Als erstes wollen wir aber sicherstellen, dass alle Abstände, die gleich oder kleiner der Länge des Lineals sind, auch gemessen werden können - eine Bedingung sine qua non für ein vernünftiges Lineal. Ein Lineal, das diese Eigenschaft besitzt nennen wir vollständig, denn es hat genug Marken um seine Grundaufgabe zu erfüllen. Lineale, die dies nicht können (unvollständige Lineale), werden wir hier nicht betrachten.

Als nächstes betrachten wir solche vollständigen Lineale, die so wenige Marken wie nur möglich haben. Sie werden perfekte Lineale genannt. Es sind dies also vollständige Lineale, wobei das Weglassen auch nur einer einzigen Marke sie unvollständig werden ließe. Solche perfekten Lineale haben eine gewisse ästhetische Qualität: sie erfüllen ihre Aufgabe mit einem Minimum an Komplexität.

Interessanter Weise unterscheiden sich perfekte Lineale mit der gleichen Anzahl von Marken dennoch in ihrer Nützlichkeit. Betrachten wir dazu die folgenden perfekten Lineale. Alle haben sie 4 Marken. (Die Zahlen entsprechen der Position der Marke auf dem Lineal.)

[0, 1, 3, 4],   [0, 1, 3, 5],   [0, 1, 4, 6]

Aber mit dem dritten Lineal kann man 33% mehr messen als mit dem ersten. So würde man sicherlich das dritte Lineal wählen, wenn man eines dieser drei Lineale kaufen wollte.

Aber das Entscheidende in Bezug auf das dritte Lineal ist, dass es kein anderes Lineal mit 4 Marken gibt, welches vollständig ist und mehr Längen messen kann. Das heißt, dass die Marken einen maximalen Messbereich abdecken. Solche Lineale werden optimal genannt. Optimale Lineale vereinigen also die Ästhetik einer minimalen Komplexität mit einem Maximum an Nützlichkeit.

Lineale mit dieser Eigenschaft sind ziemlich seltene Exemplare. Zum Beispiel gibt es 52012 perfekte Lineale mit 14 Marken, aber nur 4 von ihnen sind optimale Lineale.

Optimale Lineale, die es zu jeder Anzahl von Marken gibt, haben eine eigentümliche Länge. Tatsächlich wird ihre Länge, in Abhängigkeit von der Anzahl der Marken, beschrieben durch die Folge

0, 1, 3, 6, 9, 13, 17, 23, ...

Aber diese Zahlen zählen auch die maximale Anzahl von Kanten in anmutigen Graphen mit n Knoten ab und betten damit das Studium der perfekten Lineale in die Graphentheorie, in die Kombinatorik und in die additive Zahlentheorie ein.

Natürlich würde man jetzt auch noch gerne wissen, wie man solche optimalen Lineale konstruiert. Dies scheint auf den ersten Blick keine einfache Aufgabe zu sein. Aber es existiert eine unbewiesene Vermutung, dass es für optimale Lineale einen einfachen Bauplan gibt.

Die Vermutung besagt, dass ein Lineal mit mehr als 14 Marken nur dann optimal sein kann, wenn es ein Wichmann-Lineal ist, benannt nach B. Wichmann, der sie 1962 eingeführt hat in einer Arbeit A note on restricted difference bases.