Zeige, dass aus 5 natürlichen Zahlen stets 3 ausgewählt werden können, deren Summe durch 3 teilbar ist.

Um zu zeigen, dass aus 5 natürlichen Zahlen stets 3 ausgewählt werden können, deren Summe durch 3 teilbar ist, nutzen wir den Satz von Dirichlet (auch bekannt als das Schubfachprinzip). Jede natürliche Zahl hat einen Rest, wenn sie durch 3 geteilt wird. Die möglichen Reste sind 0, 1 und 2. Das bedeutet, dass jede natürliche Zahl in eine der drei Klassen fällt: - Klasse 0: Zahlen, die bei Division durch 3 den Rest 0 haben. - Klasse 1: Zahlen, die bei Division durch 3 den Rest 1 haben. - Klasse 2: Zahlen, die bei Division durch 3 den Rest 2 haben. Wenn wir 5 natürliche Zahlen haben, können wir diese in die drei Klassen einordnen. Nach dem Schubfachprinzip müssen mindestens zwei dieser Zahlen in einer der Klassen sein, da es nur drei Klassen gibt und wir fünf Zahlen haben. Es gibt nun zwei Fälle zu betrachten: 1. **Fall 1:** Es gibt mindestens 3 Zahlen in einer der Klassen (z.B. Klasse 0). In diesem Fall ist die Summe dieser drei Zahlen durch 3 teilbar, da die Summe von Zahlen, die alle den Rest 0 haben, ebenfalls den Rest 0 hat. 2. **Fall 2:** Es gibt in den Klassen 1 und 2 jeweils mindestens 2 Zahlen. In diesem Fall können wir eine Zahl aus Klasse 1 und zwei Zahlen aus Klasse 2 (oder umgekehrt) auswählen. Die Summe dieser Zahlen hat die Form: - \(1 + 2 + 2 = 5\) (Rest 2) - \(2 + 1 + 1 = 4\) (Rest 1) - \(0 + 0 + 0 = 0\) (Rest 0) - \(1 + 1 + 1 = 3\) (Rest 0) - \(2 + 2 + 2 = 6\) (Rest 0) In jedem Fall können wir also eine Kombination finden, die eine Summe ergibt, die durch 3 teilbar ist. Somit haben wir gezeigt, dass aus 5 natürlichen Zahlen immer 3 ausgewählt werden können, deren Summe durch 3 teilbar ist.