[Diskrete] Offline-Übungsblatt 3, Aufgabe 4b)

[Muffi]

Zu zeigen: Unter n+1 beliebigen ganzen Zahlen gibt es zwei verschiedene, etwa a und b, so dass n die Differenz a-b teilt.

Dass das gilt, ist klar. Aber hat jemand eine Ahnung, wie ich hier m it dem Schubfachprinzip argumentiere? Ich steh irgendwie auf dem Schlauch.

[MartinL]

Annahme für n: dann habe ich n+1 zahlen zur Verfügung.

Man färbt den Zahlenstrahl von 0 ausgehend mit genau n Farben periodisch ein. Sobald nun 2 Zahlen gleicher Farbe "gezogen" wurden ist die Bedingung erfüllt, denn diese sind genau um k*n weit auseinander auf dem Zahlenstrahl. Ihre Differenz teilt also n.

Es gibt für die Zahlen nun genau n verschiedene Färbungen und nach obiger Argumentation ist die Bed. genau dann erfüllt, sobald man 2 Zahlen gleicher Farbe gezogen hat. Zieht man nun n+1 Zahlen so müssen nach dem Schubfachprinzip mindestens 2 von einer Farbe sein.

Man kann es sich vorstellen als würde man die gezogenen Zahlen nach ihre Farbe sortiert in Schubfächer ablegen. Egal welche Zahl man zieht sie passt in eines der n Schubfächer. Nun müssen nach dem Schubfachprinzip In einer der n Schubladen mindestens. Elemente sein.
Also ist obige Bed. erfüllt und die Behauptung wahr.

Falls noch Fragen bestehen ... drunter Posten .. ich hoffe es wurde einigermaßen klar.

Gruß,

Martin

[Muffi]

Oh, klar. Irgendwie hätte ich wohl mal eine Pause machen sollen.

Danke!