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.
{{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[Bearbeiten | Quelltext bearbeiten]
Man nimmt die Restklassen Modulo 14 zur Hilfe.
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.