14.10.2013, 17:52
Beweis: Die Zuordnung von Häusern und Tieren ist unabhängig, sobald die Symbole platziert sind. Also können wir uns oBdA auf Tiere (und Bäume) beschränken.
Es seinen zwei mögliche Zuordnungen gegeben. Betrachte folgenden Graphen: Die Felder mit Symbolen sind Knotenpunkte und man verbindet je zwei genau dann durch eine Kante, wenn sie in einer Zuordnung zueinander gehören, in der anderen aber nicht. D.h. die Kanten geben an, wo sich die Zuordnungen unterscheiden. Von jedem Knotenpunkt gehen 0 oder zwei Kanten aus: 0, wenn die Zuordnungen dieses Knotens gleich sind, 2 wenn nicht. Deshalb sind alle Zusammenhangskomponenten Kreise oder isolierte Knoten. Wenn von einem Knoten zwei Kanten ausgehen, dann liegen sie sich die entsprechenden Symbole gegenüber, da sie sich nicht diagonal berühren dürfen. D.h. Pfade entlang der Kanten knicken nie ab. Es gibt aber keine Kreise auf dem Gitter, bei dem die Pfade nie abknicken. Folglich haben alle Knoten Grad 0, d.h. gibt es keine Kanten und die Zuordnungen sind identisch. qed
Es seinen zwei mögliche Zuordnungen gegeben. Betrachte folgenden Graphen: Die Felder mit Symbolen sind Knotenpunkte und man verbindet je zwei genau dann durch eine Kante, wenn sie in einer Zuordnung zueinander gehören, in der anderen aber nicht. D.h. die Kanten geben an, wo sich die Zuordnungen unterscheiden. Von jedem Knotenpunkt gehen 0 oder zwei Kanten aus: 0, wenn die Zuordnungen dieses Knotens gleich sind, 2 wenn nicht. Deshalb sind alle Zusammenhangskomponenten Kreise oder isolierte Knoten. Wenn von einem Knoten zwei Kanten ausgehen, dann liegen sie sich die entsprechenden Symbole gegenüber, da sie sich nicht diagonal berühren dürfen. D.h. Pfade entlang der Kanten knicken nie ab. Es gibt aber keine Kreise auf dem Gitter, bei dem die Pfade nie abknicken. Folglich haben alle Knoten Grad 0, d.h. gibt es keine Kanten und die Zuordnungen sind identisch. qed