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




Zu Frage 1

512

Hat eine Menge  M  n  Elemente, so hat  M×M  n2  Elemente. Hat eine Menge  m  Elemente, so hat ihre Potenzmenge (Menge aller Teilmengen)  2m  Elemente (da in den Teilmengen jedes Element entweder vorkommt oder fehlt). Hier ist  n = 3  und  m = n2 = 9 , also hat  M×M  29 = 512  Teilmengen.


Zu Frage 2

x  enthält  pX  in mindestens zweiter Potenz.

Dies folgt direkt aus der Definition in (4).


Zu Frage 3

171

In der folgenden Tabelle sind die neun Grundtypen für transitive Relationen auf einer dreielementigen Menge als Graphen dargestellt. Da die Lage von  A, B, C  auf den drei Knoten der Graphen nicht spezifiziert ist, steht in der zweiten Spalte die Anzahl der Möglichkeiten für die Positionierung der Pfeile. Diese Anzahl ist z.B. beim zweiten Graphen gleich 6, weil man 3 Möglichkeiten für den Ursprung des Pfeils hat, und dann jeweils 2 Möglichkeiten für das Ziel des Pfeils; beim dritten Graphen kann der Doppelpfeil 2 von 3 Knoten verbinden, dafür gibt es 3 Möglichkeiten; usw. In der dritten Spalte sind die Möglichkeiten dargestellt, die sich aus der Färbung der grünen Punkte in schwarz oder weiß ergeben (es kommen nur 1, 2 und 23 vor). Die Zahlen in der zweiten und dritten Spalte sind die Faktoren, die multipliziert in der vierten Spalte die Gesamtanzahl der Relationen ergeben, für die die einzelnen Graphen stehen.

Tabelle 1


Zu Frage 4

Die folgende Tabelle ist wie die Tabelle zu Frage 3 aufgebaut. Oben links steht die Struktur der Graphen: Für  X, Y, Z  kann man  A, B, C  in beliebiger Anordnung einsetzen;  p, q, r  sind dann beliebige (verschiedene) Primzahlen, die den  X, Y, Z  zugeordnet werden. Wird ein grüner Punkt zu einem weißen Punkt, so ist der zugehörige Exponent gleich  1 , da keine Schleife vorliegt. Wird ein grüner Punkt zu einem schwarzen Punkt, so steht er für eine Schleife und der zugehörige Exponent ist gleich  2  oder größer. Überall wurden möglichst einfache  x, y, z  gewählt. Eine vollständige Übersicht der möglichen  x, y, z  findet man unten bei der Zusatzaufgabe.

Tabelle 2


Zu Frage 5

Sei  a = p·pi·qj·rk . Das erste Tripel im Code hat Nullen an den Stellen, für die der zugehörige Exponent gleich  0  ist, und Einsen sonst. Entsprechendes gilt für  b  und das zweite Tripel, sowie für  c  und das dritte Tripel. Damit lässt sich nun die "Schachteldarstellung" leicht angeben. Die drei Tripel stehen für die drei Schachteln:

A  ↔  1. Tripel  ↔  grüne Schachtel
B  ↔  2. Tripel  ↔  rote Schachtel
C  ↔  3. Tripel  ↔  schwarze Schachtel

Der Inhalt der Schachteln bestimmt sich aus dem zugehörigen Tripel: die erste Ziffer bestimmt, ob eine grüne Kugel vorhanden ist  ( 1 = ja,  0 = nein), analog für die beiden anderen Ziffern. Wir betrachten ein Beispiel:

a = p6·q9·r
b
 = q
c
 = p2·r2
111 000 101 Schachteln

Dieser Zusammenhang lässt sich auch in umgekehrter Reihenfolge lesen, also beginnend bei den Schachteln. Im Beispiel entspricht dem Code:

a = p>1·q>0·r>0      b = q      c = p>0·r>1

Damit ist die Frage vollständig beantwortet.


Zusatzaufgabe

Wir haben schon bei den Beispielen unter (7) gesehen, dass zu einer transitiven Relation mehrere Darstellungen in Form der Codes gehören können. Ein kleines Programm hilft, eine vollständige Äquivalenzliste zu erzeugen. Diese ist hier in einer
Übersicht ausgelagert.




Publiziert 2009-06-13          Stand 2008-09-28


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


Manfred Börgens   |    zur Leitseite