Kombinations-Training

Unter $n+1$ Zahlen im Intervall $[0,1]$ gibt es zwei mit Abstand höchstens $1/n$. Zeige dies durch Sortierung und Schubfach.

Wähle unter $n+1$ ganzen Zahlen zwei mit gleicher Restklasse modulo $n$ und darunter ein Paar kleinster positiver Differenz. Was folgt?

Ein Graph hat $n$ Knoten und $m$ Kanten. Zeige, dass ein Knoten Grad mindestens $2m/n$ besitzt.

Zeige entsprechend, dass ein Knoten Grad höchstens $2m/n$ besitzt.

Haufen dürfen durch Steintransfers ausgeglichen werden. Erkläre die Rollen von Summeninvariante und größtem Haufen.

Beim Ersetzen der größeren positiven Zahl durch die Differenz bleibt der ggT gleich. Warum braucht der Beweis zusätzlich eine Extremal- oder Monovariantenidee?

Erkläre, warum bei Abstandsschranken Sortierung oft schärfer ist als eine beliebige Intervallzerlegung.

Formuliere die Rollen von Extremalwahl, Doppelzählung, Schubfach und Invariante in einem kombinierten Beweis.