Lateinische Rechtecke < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Zu beweisen ist Lemma 1: Jedes (r × n)-Lateinische Rechteck mit r < n kann zu einem ((r + 1) × n)- Lateinischen Rechteck erweitert werden. |
Ich habe dazu den Satz von Hall angewendet, welcher besagt, dass:
Sei A1, A2, . . . , An eine Familie von Teilmengen einer endlichen Menge X. Ein System von verschiedenen Vertretern für diese Folge existiert dann und nur dann, wenn für 1 ≤ m ≤ n jede Vereinigung von m Mengen Ai mindestens m Elemente enthält.
Lemma 1: Jedes (r × n)-Lateinische Rechteck mit r < n kann zu einem ((r + 1) × n)- Lateinischen Rechteck erweitert werden.
Beweis: Hierzu benötigt man den Heiratssatz. Aj sei die Menge der Zahlen, die nicht in Spalte j vorkommen. Daraus folgt, dass jede Menge Aj die Größe n − r hat und jedes Element in genau n − r Mengen Aj enthalten ist, da es genau r mal im Rechteck auftritt. Je m dieser Mengen Aj enthalten deshalb zusammen m(n−r) Elemente.Wenn n−r ≥ m ist, enthalten diese m Mengen also mindestens m verschiedene; denn wenn weniger als m verschiedene Zahlen, d. h. maximal m − 1 in diesen m der Aj aufträten, würden in ihnen h¨ochstens (m − 1)(n − r), nicht aber m(n −r) Elemente enthalten sein. Also ist die Bedingung von Hall erfüllt. Damit ist bewiesen, dass jedes Lateinische Rechteck
zu einem Lateinischen Quadrat vervollständigt werden kann.
Ich verstehe nicht, wieso es mindestens m verschiedene Elemente sein müssen - ich weiß zwar, dass letztendlich immer m verschiedene Felder gefüllt werden müssen und dass die Zeilen und Spaltenbedingungen eingehalten werden müssen, aber wieso das genau so sein muss, weiß ich nicht...glg
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:20 Fr 30.01.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
