Manfred Börgens
Mathematische Probleme  # 67		 Liste aller Probleme mit Lösungen
voriges Problem      nächstes Problem		 zur Leitseite


Ein Modell für transitive Relationen


A, B  und C  sind leidenschaftliche Spieler und Liebhaber der Zahlen. Als sie eines Tages alle drei zu einer Fernseh-Spielshow eingeladen werden, verabreden sie  -  um die Sache noch interessanter zu machen  -  ihre Gewinne nachher untereinander neu zu verteilen. Diese Verteilung soll nach einem von ihnen ersonnenen "Vererbungsprinzip" für Primfaktoren erfolgen:

(1)
Bei den Beträgen, die nach der Show verteilt werden, soll es sich immer um natürliche Zahlen handeln, die nur die Primfaktoren  2, 3, 5  enthalten.

(2)
A's Zahl heißt  a  und muss den Faktor  pA = 2  enthalten.
B's Zahl heißt  b  und muss den Faktor  pB = 3  enthalten.
C's Zahl heißt  c  und muss den Faktor  pC = 5  enthalten.
Die  pX  wollen wir "Basisfaktoren" nennen.

(3)
Die drei Gewinne aus der Show (in der Regel verschieden, aber immer genügend groß) werden jeweils bis zur größten Zahl abgerundet, die (1) und (2) erfüllt. Die Reste verbleiben bei den Spielern und spielen danach keine Rolle mehr.

(4)
Vererbungsgesetz:
X, Y, Z  seien nun Platzhalter für die Spieler, und  x, y, z  die zugehörigen Platzhalter für die Beträge aus (2).
X → Y soll heißen:  " y  erbt alle Primfaktoren von  x "  und bedeutet für die Spieler "Y erhält einen Anteil von X's Gewinn".
Dies soll präzisiert werden:
X → Y     ⇔     x = 2x2·3x3·5x5  und  y = pY·2y2·3y3·5y5  mit  yi > 0 , falls  xi > 0 .
Man beachte, dass auch  X → X  auftreten kann.
Nochmal in Worten:  y  erbt alle Primfaktoren von  x  genau dann, wenn:
-  y  enthält (mindestens) jeden Primfaktor von  x  mindestens einmal.
-  Falls  x  den "fremden" Basisfaktor  pY  enthält, kommt dieser in  y  mindestens in zweiter Potenz vor.

Nun lässt sich leicht feststellen, an wen ein Spieler  X  etwas von seinem Gewinn abgeben muss. Die "Empfänger" (das können 0 bis 3 Personen sein, evtl. inklusive des "Gebers" X) teilen sich dann den Betrag  x  zu gleichen Teilen.

Zwei Beispiele:


X → Y  etabliert eine Relation auf der Menge  M = {A, B, C}. (Jede Teilmenge von  M×M  nennt man eine Relation; statt des geordneten Paares  (X,Y)  schreiben wir hier  X → Y.)

Zwei Fragen zum Aufwärmen:

Frage 1
Wieviele Relationen auf  {A, B, C}  gibt es?

Frage 2
Wann gilt  X → X ?

Diese Relation  " → "  ist transitiv, d.h. aus  X → Y  und  Y → Z  folgt  X → Z. Machen Sie sich dies anhand der Definition der Relation klar.

Jetzt erst kommen wir zum eigentlichen Zweck dieses Problems. Wir wollen zeigen, dass alle transitiven Relationen auf einer dreielementigen Menge mit Hilfe von  " → "  dargestellt werden können. D.h. für jede dieser transitiven Relationen lassen sich entsprechende  a, b, c  finden. Die beiden Beispiele kann man auch unter diesem Gesichtspunkt betrachten: Ausgangspunkt seien die Teilmengen von  M×M, im ersten Beispiel zweielementig, im zweiten fünfelementig, beide offenbar transitiv. Für beide Relationen konnten passende  a, b, c  angegeben werden.

Die genaue zahlenmäßige Aufteilung der Gewinne spielt offenbar für die Relation keine Rolle und wurde nur zur Veranschaulichung des Problems eingeführt. Wichtig ist nur, welche Personen sich jeden einzelnen der drei Gewinne teilen.

Zu beweisen ist also:

Ist  R  eine beliebige transitive Relation auf einer beliebigen dreielementigen Menge  M = {A, B, C}, so existieren  a, b, c  wie in (1), (2), so dass die Relation  " → "  identisch mit  R  ist.

" → "  ist somit ein Modell für alle transitiven Relationen auf dreielementigen Mengen.

Für den Beweis ist es hilfreich, sich zunächst einen Überblick über die transitiven Relationen auf  M  zu verschaffen. Eine naheliegende Darstellung ist ein gerichteter Graph mit den Knoten  A, B, C. Gilt  X → Y, so verbindet man die entsprechenden Ecken mit einem Pfeil. Gilt  X → X, so stellt man diese "Schleife" der Abkürzung halber durch einen schwarzen Punkt dar, ansonsten durch einen weißen. Für die beiden Beispiele oben sieht das so aus:

2 Beispielgraphen

Mit Hilfe solcher Graphen lassen sich die transitiven Relationen leicht darstellen. Man kommt mit wenigen Graphen aus, wenn man die Beschriftung der Knoten mit  A, B, C  fortlässt und so ganze Gruppen prinzipiell gleicher Relationen zusammenfasst. Wenn man zuerst die Pfeile auf die Kanten setzt, muss man sich nur noch überlegen, welche Knoten eine Schleife ( X → X ) erhalten müssen (wegen der Transitivität); die anderen Knoten erlauben dann die freie Wahl zwischen Schleife und keiner Schleife. Die nächste Graphik zeigt exemplarisch einen Graphen für transitive Relationen; schwarze Punkte bedeuten eine "Muss-Schleife", grüne Punkte eine "Kann-Schleife":

Beispielgraph

Dieser Graph steht für insgesamt 6 transitive Relationen: Der grüne Knoten kann von  A, B  oder  C  besetzt werden und kann jeweils eine Schleife enthalten oder nicht. Man beachte, dass wegen der Transitivität die beiden anderen Knoten "Muss-Schleifen" sind.

Wenn man die möglichen Graphen aufgezeichnet hat  -  wie gesagt, es sind nicht viele  -  kann man die nächste Frage beantworten:

Frage 3
Wieviele transitive Relationen auf  {A, B, C}  gibt es?

Jetzt fehlt nur noch der Nachweis, dass sich alle diese transitiven Relationen durch  " → "  mit geeigneten  a, b, c  darstellen lassen.

Frage 4
Wie lassen sich die transitiven Relationen auf drei Elementen durch  x, y, z  darstellen?
x, y, z  sind die Zahlen aus (4), die für beliebige Anordnungen der  a, b, c  stehen. Bei der Lösung sollte man ausgehen von den Graphen vor Frage 3. Es reicht (hier), zu jedem dieser Graphen beispielhaft ein möglichst einfaches Tripel  (x, y, z)  anzugeben.

Damit ist gezeigt: Die Transitivität für Relationen auf dreielementigen Mengen wird modellhaft beschrieben durch die Primfaktor-Vererbung gemäß (4).

Wer die hier gewählte Einkleidung der Relation  " → "  etwas umständlich findet, hat nicht ganz unrecht. Dahinter steckte die Absicht, ein anschauliches Beispiel für die Beschreibung aller transitiven Relationen zu finden. Aber man kann die gewählte Vererbungsrelation erheblich abspecken. Zunächst lassen sich beliebige Primzahlen wählen (drei verschiedene  p, q, r , jeweils zugehörig zu  X, Y, Z).
Für konkrete Probleme wie in (1)-(3) kann man dann  A, B, C  beliebig den  X, Y, Z  und beliebigen Primfaktoren  p, q, r  zuordnen.

Weiterhin spielen offenbar die Exponenten der Zahlen  x = p·pi·qj·rk ,  y = q·pi·qj·rk ,  z = r·pi·qj·rk  keine wesentliche Rolle, außer dass man die beiden Fälle Exponent = 0  und Exponent > 0  unterscheiden muss. Es reicht also zu wissen, welche Primfaktoren (unabhängig von ihrer Potenz) nach Division durch den Basisfaktor enthalten sind. Damit kann man einen "Code" für  (x, y, z)  einführen, der an einem Beispiel erklärt wird:

(5)
100 110 000  bedeutet:
100  steht für  x = p·pi·q0·r0  mit  i > 0 , also  x = pi+1 .
110  steht für  y = q·pi·qj·r0  mit  i, j > 0 , also  y = pi·qj+1 .
000  steht für  z = r·p0·q0·r0 , also  z = r .

Dies lässt sich auch graphisch veranschaulichen:

(6)
A, B, C  seien drei Schachteln in den Farben Grün, Rot und Schwarz. Jede von ihnen kann 0 bis 3 Kugeln in diesen Farben enthalten, wobei die Kugeln in einer Schachtel alle verschiedenfarbig sein müssen. Dann lautet die Vererbungsrelation:

(7)
X → Y     ⇔     Bei den Kugeln in  Y  kommen (mindestens) alle Kugelfarben sowie die Schachtelfarbe von  X  vor.

Vier Beispiele (bei  a, b, c  wurden die ursprünglichen Primzahlen und die kleinstmöglichen Exponenten gewählt):



Schachteln a = 22·3·5
b = 3
c = 2·52		 111 000 101 A → A     B → A
C → A     C → C
Schachteln a = 2·5
b = 2·3·5
c = 2·5		 001 101 100 A → B     C → B
Schachteln a = 22·3
b = 2·32
c = 5		 110 110 000 A → A     A → B
B → A     B → B
Schachteln a = 22·3
b = 2·32
c = 2·5		 110 110 100 A → A     A → B
B → A     B → B


Frage 5
Wie hängen "Primfaktordarstellung" und "Schachteldarstellung" zusammen?
Dies lässt sich am einfachsten über den Code beschreiben.

Wir haben also zwei (miteinander verwandte) Modelle gefunden, die äquivalent zur Menge der transitiven Relationen auf einer dreielementigen Menge  M  sind. Was bedeutet diese Äquivalenz genau?



Zusatzaufgabe
Man kann mit einem kleinen Programm eine vollständige Zuordnung der transitiven Relationen zu den Zahlencodes wie in (6) angeben.



Lösung


Publiziert 2009-05-16          Stand 2008-09-28

voriges Problem   |   Liste aller Probleme mit Lösungen   |    nächstes Problem

Manfred Börgens   |    zur Leitseite                                     Datenschutz





ab 2020-06-25
www.boergens.de/manfred/problem/problem067.htm