TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 191

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

zwei, deren Differenz durch 14 teilbar ist.

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

Lösungsvorschlag

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.