Schubfachprinzip-Aufgabe (Harry Potter)

Question

Der Zauberlehrling H.P. hat noch 11 Wochen, d.h. 77 Tage, bis zur Prüfung im Fach „Verteidigung gegen die dunklen Künste". Der „Riddikulus-Zauber" bereitet ihm besondere Probleme.

Daher beschließt er diesen jeden Tag mindestens einmal zu üben, jedoch höchstens 12 Mal in einer Woche, um seine Kräfte einzuteilen. Zeigen Sie, dass es einen Zeitraum aufeinanderfolgender Tage gibt, an denen H.P. den Zauber zusammen genau 21 Mal übt.

(Hinweis: Sei dazu $a_{1}$ die Anzahl der Übungen am ersten Tag, $a_{2}$ die Gesamtzahl der Übungen an Tag 1 und 2 , und allgemein $a_{i}, i \in\{1, \ldots, 77\}$ die Gesamtzahl der Übungen an den Tagen 1 bis $i$. Betrachten Sie die Zahlen $a_{i}$ und $a_{i}+21$ und verwenden Sie das Schubfachprinzip.)

Answer 1

Wir konzentrieren uns auf die nächsten 11 Wochen, also 77 Tage, beginnend an einem Montag. Mit $a_{n}$ bezeichnen wir die Anzahl an Spielen, welche während der ersten $n$ Tage gespielt wurden. Betrachten wir nun die Folge

$\begin{aligned}a_{1}, a_{2}, \ldots, a_{77}, a_{1}+21, a_{2}+21, \ldots, a_{77}+21 .\end{aligned}$

Die Folge umfasst 154 Terme von welchen keiner die Zahl $11 \cdot 12+21=153$ überschreitet, da wir in jeder Woche höchstens 12 mal üben. Wegen dem Schubfachprinzip müssen also zwei Folgenglieder den gleichen Wert annehmen, nennen wir sie $a_{i}$ und $a_{j}$. Nun kann es nicht sein, dass sowohl $a_{i}$ als auch $a_{j}$ unter den ersten 77 Folgenglieder sind, da H.P. ja jeden Tag mindestens einmal übt und dementsprechend die Teilfolge der ersten 77 Folgenglieder streng monoton wachsend ist. Aus dem gleichen Grund kann es nicht sein, dass sowohl $a_{i}$ als auch $a_{j}$ unter den letzten 77 Folgengliedern sind. Also ist o.V.d.A. $a_{j}=a_{i}+21$, und somit gibt es eine Folge an konsekutiven Tagen, beginnend am Tag $i+1$ und endend am Tag $j$, während welcher H.P. genau 21 mal übt.