Beweiswerkstatt

Beim Ausgleichen aus Kapitel 13 bleibt die Gesamtzahl der Steine konstant, während $D=\sum_i|a_i-q|$ sinkt. Erkläre präzise den Unterschied der beiden Größen.

Für positive ganze Zahlen $(a,b)$ ersetze die größere durch die positive Differenz der beiden. Zeige, dass der Prozess endet und der ggT invariant bleibt.

Bestimme den Endzustand des Differenzalgorithmus für $(84,30)$, ohne alle Schritte ausschreiben zu müssen.

In einem Reduktionsbeweis gibt es viele erlaubte Züge, aber nur Züge am größten Objekt senken die gewählte Komplexität sicher. Erkläre, wie Extremalwahl und Invariante logisch verbunden werden.

Münzen tragen positive ganzzahlige Werte. Zwei Münzen dürfen durch eine Münze ersetzt werden, deren Wert ihre Summe ist. Zeige, dass der Prozess unabhängig von der Reihenfolge bei genau einer Münze mit dem ursprünglichen Gesamtwert endet.

Eine Zahl darf um 6 oder 10 in beide Richtungen verändert werden. Beweise vollständig, welche Zahlen von 0 erreichbar sind.

Erkläre, warum beim Differenzalgorithmus stets die größere Zahl verändert werden muss, wenn Positivität und strikter Abstieg der Summe erhalten bleiben sollen.

Formuliere eine universelle Checkliste für Beweise, die Invarianten mit Schubfach, Konstruktion, Extremalprinzip oder Monovarianten verbinden.