To end our story about Markov numbers, we turn to the second theme, the uniqueness conjecture. We have seen several different versions ranging from numbers and matrices to hyperbolic geometry and matchings of graphs. The uniqueness results in Chapters 3 and 4 were based directly on the Markov equation and some simple congruences derived from it. Now we want to take a closer look at some of the systematic approaches attempted so far. They are arranged in three groups of increasing complexity:

Zusammenfassung

Erinnern wir uns an das Job-Zuordnungsproblem. Gegeben ist eine Menge S = {P₁,...,P_n} von Personen und eine Menge T = {J₁,...,J_n} von Jobs. Wir setzen P_iJ_j ∈ K, falls P_i für den Job J_i geeignet ist. Wir wollen nun eine Zuordnung P_i → J_φ(i) finden, so daß jede Person P_i einen geeigneten J_φ(i) findet. Wann ist dies möglich? Allgemein werden wir Gewichte auf den Kanten P_iJ_j haben (die wir z.B. als Eignungskoeffizienten interpretieren können), und die Zuordnung soll optimal (= maximal groß) werden.

Zusammenfassung

Wir haben gesehen, dass die Primzahlen 2, 3, 5, 7, . . . eine unendliche Folge bilden. Daraus kann man auch folgern, dass es beliebig große Lücken zwischen den Primzahlen geben muss. Schreibt man nämlich N := 2 · 3 · 5 · · · p für das Produkt aller Primzahlen, die kleiner sind als k + 2, dann kann keine der k Zahlen

N + 2,N + 3,N + 4, . . .,N + k,N + (k + 1)

prim sein, denn für 2 ≤ i ≤ k +1 hat i einen Primfaktor, der kleiner ist als k + 2, und dieser Faktor teilt auch N, und damit auch N + i. Mit diesem Rezept finden wir zum Beispiel für k = 10, dass keine der zehn Zahlen

2312, 2313, 2314, . . ., 2321

prim ist.

Plane graphs and their colorings have been the subject of intensive research since the beginnings of graph theory because of their connection to the four-color problem. As stated originally the four-color problem asked whether it is always possible to color the regions of a plane map with four colors such that regions which share a common boundary (and not just a point) receive different colors. The figure on the right shows that coloring the regions of a map is really the same task as coloring the points of a plane graph. As in Chapter 10 (page 57) place a point in the interior of each region (including the outer region) and connect two such points belonging to neighboring regions by a line through the common boundary.

Zusammenfassung.

Angenommen, jemand denkt sich eine Zahl $x$ zwischen 1 und einer Million, und ein zweiter Spieler soll diese Zahl durch Fragen: „Ist $x\leq i$ ?” ermitteln. Da $10^{6}<2^{20}$ ist, kann die Zahl $x$ durch die übliche Halbierungsmethode mit 20 Fragen bestimmt werden. Was aber, wenn der erste Spieler einmal (oder öfter) lügen darf? Wieviele Fragen werden dann benötigt? Dieses Spiel ist als „Ulams Liar Problem” bekannt geworden. Wir wollen das allgemeine Problem ( $n$ Zahlen, $d$ Lügen) studieren und insbesondere Ulams Problem für eine Lüge lösen.