Wie zeigt man, dass sich aus fünf natürlichen Zahlen stets drei auswählen lassen, deren Summe durch drei teilbar ist?

Um zu zeigen, dass aus fünf natürlichen Zahlen stets drei ausgewählt werden können, deren Summe durch drei teilbar ist, kann man den Satz von Dirichlet (auch bekannt als das Schubfachprinzip) verwenden. 1. **Restklassen modulo 3**: 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 Restklassen fällt: \(0 \mod 3\), \(1 \mod 3\) oder \(2 \mod 3\). 2. **Anzahl der Zahlen**: Wenn wir fünf natürliche Zahlen haben, können wir diese in die drei Restklassen einordnen. Nach dem Schubfachprinzip müssen mindestens zwei dieser fünf Zahlen in der gleichen Restklasse liegen, da es nur drei Restklassen gibt. 3. **Fallunterscheidung**: - **Fall 1**: Wenn mindestens drei der fünf Zahlen in einer Restklasse sind (z.B. drei Zahlen haben den Rest 0), dann ist die Summe dieser drei Zahlen durch 3 teilbar. - **Fall 2**: Wenn zwei Zahlen in einer Restklasse sind und die anderen drei in einer anderen Restklasse, dann können wir die beiden Zahlen aus der ersten Restklasse und eine Zahl aus der zweiten Restklasse auswählen. Die Summe dieser drei Zahlen wird ebenfalls durch 3 teilbar sein, da die beiden Zahlen in der ersten Restklasse zusammen einen Rest von 0 haben und die Zahl aus der zweiten Restklasse einen Rest von 1 oder 2 hat, was die Summe nicht beeinflusst. - **Fall 3**: Wenn die Verteilung so ist, dass zwei Zahlen in einer Restklasse und zwei in einer anderen sind, bleibt eine Zahl in der dritten Restklasse. In diesem Fall können wir zwei Zahlen aus der Restklasse mit zwei Zahlen und eine Zahl aus der Restklasse mit einer Zahl auswählen, was ebenfalls zu einer Summe führt, die durch 3 teilbar ist. 4. **Schlussfolgerung**: In jedem Fall können wir also immer drei Zahlen auswählen, deren Summe durch 3 teilbar ist. Daher ist die Aussage bewiesen.