Kombinations-Training

Unter 13 ganzen Zahlen gibt es zwei, deren Differenz sowohl durch 2 als auch durch 3 teilbar ist. Zeige dies über Signaturen.

Eine Folge von Zuständen in einer Menge mit 100 Elementen wird deterministisch erzeugt: Der nächste Zustand hängt nur vom aktuellen ab. Zeige, dass die Folge ab irgendeinem Zeitpunkt periodisch ist.

Zeige, dass die Folge $2^0,2^1,2^2,\ldots$ modulo 15 schließlich periodisch ist, und bestimme hier den Zyklus.

In einem Graphen mit mindestens drei Knoten gibt es zwei Knoten, deren Grade dieselbe Parität haben. Erkläre die Methodenkette und warum sie schwächer als eine exakte Gradkollision ist.

Für ganze Zahlen $a_1,\ldots,a_n$ zeige: Es gibt einen nichtleeren zusammenhängenden Block, dessen Summe durch $n$ teilbar ist.

Auf $n$ Haufen mit insgesamt $S$ Steinen darf je ein Stein zwischen beliebigen Haufen verschoben werden. Beweise: Alle Haufen können genau dann gleich groß gemacht werden, wenn $n\mid S$.

Starte mit einem beliebigen Rest $x_0$ modulo 10 und setze $x_{k+1}\equiv3x_k+1\pmod{10}$. Zeige, dass die Folge periodisch wird; erkläre, was ohne weitere Rechnung nicht über die Periodenlänge folgt.

Formuliere einen vollständigen Beweis-Audit für Aufgabe 6 und benenne die Rolle von Invariante, Extremalwahl und Monovarinante.