TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 186

Aus VoWi
Zur Navigation springen Zur Suche springen

Zeigen Sie mithilfe des Schubfachprinzips: Unter je 15 natürlichen Zahlen gibt es mindestens

zwei, deren Differenz durch 14 teilbar ist.

Lösungsvorschlag[Bearbeiten]

Man nimmt die Restklassen Modulo 14 zur Hilfe.

 x \equiv y \pmod m \Leftrightarrow m \vert x - y

Jede Restklasse ist ein Schubfach. Somit haben wir 14 Fächer. 14 der 15 natürlichen Zahlen können wir im besten Fall so wählen, dass jedes Schubfach genau einer der Zahlen enthält. Die 15. Zahl bleibt dann nichts anderes übrig als in einem Schubfach bzw. Restklasse zu liegen, die bereits eine andere Zahl enthält. Und wenn zwei Zahlen in der gleichen Restklasse liegen, dann ist ihre Differenz durch den Modulo, in dem Fall 14, teilbar.