Verbindungen doppelt zählen
Parität beim Zählen und Auswählen · Abschnitt 51 von 60
Gelöstes Beispiel
Beispiel: Handschläge
Idee. Jeder Handschlag gehört zu zwei Personen.
Rechnung. Summe aller Handschlagzahlen (bei Handschlägen) → gerade.
Du brauchst die einzelnen Zahlen gar nicht zu kennen.
Satz
Handschlaglemma (freundlich formuliert)
In jeder Gruppe, in der man sich (paarweise) die Hand schüttelt, ist die Anzahl der Personen mit ungerader Handschlagzahl immer gerade.
(Mathematisch: In einem endlichen ungerichteten Graphen ist die Zahl der Knoten mit ungeradem Grad gerade.)
Beweis
Modulo 2 gelesen
Die Summe aller Handschlagzahlen ist → gerade. Gerade Beiträge verschwinden modulo 2. Nur Personen mit ungerader Handschlagzahl tragen 1 bei – ihre Anzahl muss also gerade sein.
Achtung
Was das Lemma **nicht** sagt
Eine gerade Anzahl „ungerader“ Personen garantiert noch nicht, dass jede erdachte Liste von Handschlagzahlen auch wirklich möglich ist. Das Lemma ist eine notwendige Bedingung – nicht die ganze Geschichte.