Themenbuch
Extremalprinzip
Mit dem größten oder kleinsten Objekt beginnen – vom engsten Paar zur Olympiade
Ein freundlicher Weg von der bewussten Extremalwahl über kleinste Gegenbeispiele bis zu olympiadetauglichen Reduktions- und Strukturbeweisen.
Was du lernst
- Wirksame Extremalgrößen erkennen und wählen.
- Aus Extremalität lokale Struktur ablesen.
- Widerspruchs- und Reduktionsbeweise klar und vollständig schreiben.
Rahmen
- Lernzeit
- 31 Std. 50 Min.
- Voraussetzungen
- Endliche Mengen · Ordnungen · Einfache Beweise · Lust, kurze Begründungen zu schreiben
Im Buch suchen
Finde Kapitel, Lernziele und Methoden.
Inhaltsverzeichnis
Lernkarte
- 1Extremobjekte erkennen und wählen
Fundament
- 2Extremalwiderspruch und kleinste Gegenbeispiele
baut auf den vorherigen Ideen auf
- 3Sortierung, Lücken und Inversionen
baut auf den vorherigen Ideen auf
- 4Maximale Strukturen und Austausch
baut auf den vorherigen Ideen auf
- 5Kleinste Teiler, Reste und Bézout
baut auf den vorherigen Ideen auf
- 6Primfaktoren, kleinste Lösungen und Abstieg
baut auf den vorherigen Ideen auf
- 7Extreme Mengenfamilien und Überdeckungen
baut auf den vorherigen Ideen auf
- 8Schnitte, Paarungen und Austauschpfade
baut auf den vorherigen Ideen auf
- 9Längste Wege, kürzeste Zyklen und Grade
baut auf den vorherigen Ideen auf
- 10Spannbäume, Zyklen und Kantentausch
baut auf den vorherigen Ideen auf
- 11Äußerste Punkte, Stützgeraden und Hüllen
baut auf den vorherigen Ideen auf
- 12Fernste Paare und maximale Flächen
baut auf den vorherigen Ideen auf
- 13Schubfach, Doppelzählung und Invarianten
baut auf den vorherigen Ideen auf
- 14Induktion, Monovarianten und Beweiswerkstatt
baut auf den vorherigen Ideen auf
- 15Strategiewahl, Extremalkandidaten und Beweiswerkstatt
baut auf den vorherigen Ideen auf
- 16Extremalprinzip-Olympiade-Generalprobe
baut auf den vorherigen Ideen auf
Zentrale Methoden
Die richtige Extremalgröße auswählen
Wähle genau die Größe maximal oder minimal, deren Extremalität einen verbotenen Nachbarn, eine scharfe Schranke oder einen Reduktionszug erzwingt.
Warum funktioniert sie?
Wähle genau die Größe maximal oder minimal, deren Extremalität einen verbotenen Nachbarn, eine scharfe Schranke oder einen Reduktionszug erzwingt.
Erkennungssignale
- Die Aufgabe enthält viele gleichartige Objekte, aber keine natürliche Reihenfolge der Bearbeitung.
- Wörter wie größter, kleinster, längster, kürzester, äußerster oder frühester sind sinnvoll definierbar.
Vorgehen
- 1. Objektmenge festlegen: Bestimme, unter welchen Objekten gewählt wird.
- 2. Ordnungsgröße testen: Vergleiche Größe, Lage, Grad, Länge oder Komplexität.
- 3. Extrem wählen: Fixiere ein Objekt mit maximalem oder minimalem Wert.
- 4. Zusatzstruktur ableiten: Frage, was wegen der Extremalität daneben nicht mehr passieren kann.
Geeignet
- du eine endliche oder wohlfundierte Objektmenge nach Größe, Lage, Grad oder Komplexität ordnen kannst
Reicht nicht
- das gewählte Extrem nicht existiert oder keinen nutzbaren lokalen Schluss liefert
Die Existenz eines Extrems sichern
Endlichkeit oder Wohlordnung garantiert, dass deine Menge wirklich ein Maximum oder Minimum besitzt.
Warum funktioniert sie?
Endlichkeit oder Wohlordnung garantiert, dass deine Menge wirklich ein Maximum oder Minimum besitzt.
Erkennungssignale
- Ein Beweis beginnt mit „Wähle ein kleinstes ...“.
- Die zugrunde liegende Menge könnte leer oder unendlich sein.
Vorgehen
- 1. Nichtleere Menge prüfen: Zeige, dass mindestens ein Kandidat existiert.
- 2. Existenzgrund nennen: Nutze Endlichkeit, Wohlordnung oder eine kompakte geometrische Situation.
- 3. Bindungen zulassen: Eindeutigkeit ist meist unnötig; wähle einen der Extremkandidaten.
- 4. Reichweite beachten: Bei offenen oder dichten unendlichen Mengen kann ein Extrem fehlen.
Geeignet
- du eine endliche oder wohlfundierte Objektmenge nach Größe, Lage, Grad oder Komplexität ordnen kannst
Reicht nicht
- das gewählte Extrem nicht existiert oder keinen nutzbaren lokalen Schluss liefert
Lokale Struktur am Extrem ausnutzen
Ein Extremobjekt kann keinen Nachbarn haben, der es in der gewählten Richtung übertrifft – genau dieses Verbot liefert den Beweisschritt.
Warum funktioniert sie?
Ein Extremobjekt kann keinen Nachbarn haben, der es in der gewählten Richtung übertrifft – genau dieses Verbot liefert den Beweisschritt.
Erkennungssignale
- Ein längster Weg, kürzester Kreis oder äußerster Punkt wurde gewählt.
- Ein lokaler Anbau oder eine Abkürzung würde das Extrem verbessern.
Vorgehen
- 1. Mögliche Verbesserung annehmen: Teste einen Nachbarn, eine Verlängerung oder eine Abkürzung.
- 2. Neues Objekt konstruieren: Zeige, wie daraus ein strengeres Extrem entstünde.
- 3. Extremalität widersprechen: Die Verbesserung ist wegen der Wahl unmöglich.
- 4. Verbot übersetzen: Formuliere die erhaltene lokale Struktur als benötigte Aussage.
Geeignet
- du eine endliche oder wohlfundierte Objektmenge nach Größe, Lage, Grad oder Komplexität ordnen kannst
Reicht nicht
- das gewählte Extrem nicht existiert oder keinen nutzbaren lokalen Schluss liefert
Maximal und maximum unterscheiden
Maximal heißt nicht erweiterbar; maximum heißt unter allen Kandidaten größtmöglich.
Warum funktioniert sie?
Maximal heißt nicht erweiterbar; maximum heißt unter allen Kandidaten größtmöglich.
Erkennungssignale
- Objekte werden durch Hinzufügen erweitert.
- Ein Beweis benötigt nur lokale Nichterweiterbarkeit oder wirklich optimale Größe.
Vorgehen
- 1. Ordnung benennen: Kläre, ob nach Inklusion oder Zahlenwert verglichen wird.
- 2. Maximalität formulieren: Kein echtes größeres zulässiges Objekt enthält den Kandidaten.
- 3. Maximum formulieren: Kein zulässiges Objekt besitzt größeren Zahlenwert.
- 4. Benötigte Stärke wählen: Verwende nur die Aussage, die der Folgeschritt wirklich braucht.
Geeignet
- du eine endliche oder wohlfundierte Objektmenge nach Größe, Lage, Grad oder Komplexität ordnen kannst
Reicht nicht
- das gewählte Extrem nicht existiert oder keinen nutzbaren lokalen Schluss liefert
Durch eine Extremverbesserung widersprechen
Unter der Gegenannahme erzeugt eine lokale Änderung ein noch größeres oder kleineres zulässiges Objekt und widerspricht der Extremalwahl.
Warum funktioniert sie?
Unter der Gegenannahme erzeugt eine lokale Änderung ein noch größeres oder kleineres zulässiges Objekt und widerspricht der Extremalwahl.
Erkennungssignale
- Die gewünschte Eigenschaft soll an einem Extremobjekt bewiesen werden.
- Ihr Scheitern würde eine Verlängerung, Verkürzung oder Verschiebung ermöglichen.
Vorgehen
- 1. Extrem fixieren: Begründe Existenz und Zulässigkeit.
- 2. Zieleigenschaft verneinen: Nimm an, das Extrem habe die gewünschte Struktur nicht.
- 3. Strengeres Objekt bauen: Nutze die angenommene Lücke für eine Verbesserung.
- 4. Widerspruch schließen: Das neue Objekt verletzt die Definition des Extrems.
Geeignet
- du eine endliche oder wohlfundierte Objektmenge nach Größe, Lage, Grad oder Komplexität ordnen kannst
Reicht nicht
- das gewählte Extrem nicht existiert oder keinen nutzbaren lokalen Schluss liefert
Ein kleinstes Gegenbeispiel widerlegen
Existierte ein Gegenbeispiel, so gäbe es ein kleinstes; eine Reduktion erzeugt ein noch kleineres Gegenbeispiel oder löst den Fall direkt.
Warum funktioniert sie?
Existierte ein Gegenbeispiel, so gäbe es ein kleinstes; eine Reduktion erzeugt ein noch kleineres Gegenbeispiel oder löst den Fall direkt.
Erkennungssignale
- Eine Aussage gilt für positive ganze Größen und kleinere Fälle helfen beim aktuellen Fall.
- Direkte Induktion ist möglich, aber eine Gegenbeweisform passt natürlicher.
Vorgehen
- 1. Gegenbeispiele annehmen: Definiere ihre positive ganzzahlige Größe.
- 2. Kleinstes wählen: Nutze die Wohlordnung der positiven ganzen Zahlen.
- 3. Reduzieren: Führe das kleinste Gegenbeispiel auf kleinere gültige Fälle zurück.
- 4. Widerspruch folgern: Die Reduktion zeigt den Fall oder erzeugt ein kleineres Gegenbeispiel.
Geeignet
- du eine endliche oder wohlfundierte Objektmenge nach Größe, Lage, Grad oder Komplexität ordnen kannst
Reicht nicht
- das gewählte Extrem nicht existiert oder keinen nutzbaren lokalen Schluss liefert
Ein Extremobjekt reduzieren
Entferne oder vereinfache ein Extremteil so, dass eine kleinere Instanz entsteht und die Lösung zurückübertragen werden kann.
Warum funktioniert sie?
Entferne oder vereinfache ein Extremteil so, dass eine kleinere Instanz entsteht und die Lösung zurückübertragen werden kann.
Erkennungssignale
- Ein Endpunkt, Blatt, kleinstes Element oder Randobjekt lässt sich sauber entfernen.
- Die Aufgabe besitzt eine natürliche Größenreduktion.
Vorgehen
- 1. Reduzierbares Extrem finden: Wähle Blatt, Endpunkt, äußerstes oder kleinstes Objekt.
- 2. Kleinere Instanz bilden: Entferne oder vereinfache das Extrem unter Erhalt der Voraussetzungen.
- 3. Kleinere Aussage nutzen: Wende Minimalität, Induktion oder bekannte Struktur an.
- 4. Zurückbauen: Füge das Extrem wieder ein und kontrolliere die Zielaussage.
Geeignet
- du eine endliche oder wohlfundierte Objektmenge nach Größe, Lage, Grad oder Komplexität ordnen kannst
Reicht nicht
- das gewählte Extrem nicht existiert oder keinen nutzbaren lokalen Schluss liefert
Einen Extremalbeweis auditieren
Ein vollständiger Extremalbeweis benennt Kandidatenmenge, Ordnungsgröße, Existenz, Extremalfolge und exakten Widerspruch.
Warum funktioniert sie?
Ein vollständiger Extremalbeweis benennt Kandidatenmenge, Ordnungsgröße, Existenz, Extremalfolge und exakten Widerspruch.
Erkennungssignale
- Eine Lösung sagt nur „Nimm das größte Objekt“.
- Mehrere mögliche Extremalgrößen oder Reduktionsschritte müssen geprüft werden.
Vorgehen
- 1. Wahl prüfen: Sind Menge, Größe und Existenz des Extrems klar?
- 2. Verbesserung prüfen: Ist das neu gebaute Objekt zulässig und wirklich strenger?
- 3. Reduktion prüfen: Bleiben alle Voraussetzungen in der kleineren Instanz erhalten?
- 4. Schluss prüfen: Widerspricht das Ergebnis exakt der Extremdefinition?
Geeignet
- du eine endliche oder wohlfundierte Objektmenge nach Größe, Lage, Grad oder Komplexität ordnen kannst
Reicht nicht
- das gewählte Extrem nicht existiert oder keinen nutzbaren lokalen Schluss liefert
Nach dem Sortieren nur Nachbarn prüfen
In einer sortierten Folge nimmst du eine kleinste positive Differenz von zwei aufeinanderfolgenden Elementen.
Warum funktioniert sie?
In einer sortierten Folge nimmst du eine kleinste positive Differenz von zwei aufeinanderfolgenden Elementen.
Erkennungssignale
- Zahlen oder Punkte auf einer Geraden werden über Abstände verglichen.
- Alle Paare scheinen betrachtet werden zu müssen.
Vorgehen
- 1. Sortieren: Schreibe .
- 2. Beliebiges Paar zerlegen: Für gilt .
- 3. Kleinste Lücke lokalisieren: Eine Summe positiver Nachbarlücken ist nicht kleiner als jede ihrer Komponenten.
- 4. Nachbarpaar wählen: Das globale Minimum liegt unter benachbarten Elementen.
Geeignet
- eine geordnete Folge, Nachbarschaftsstruktur oder lokal verbesserbare Auswahl vorliegt
Reicht nicht
- die verwendete Ordnung oder Austauschoperation die Zulässigkeit nicht erhält
Eine extreme Lücke mit dem Durchschnitt vergleichen
Die Summe aller Nachbarlücken ist die Gesamtausdehnung; daher ist mindestens eine Lücke höchstens und mindestens eine mindestens so groß wie der Durchschnitt.
Warum funktioniert sie?
Die Summe aller Nachbarlücken ist die Gesamtausdehnung; daher ist mindestens eine Lücke höchstens und mindestens eine mindestens so groß wie der Durchschnitt.
Erkennungssignale
- Mehrere geordnete Punkte liegen in einem festen Intervall.
- Eine nahe oder weit getrennte Nachbarschaft soll erzwungen werden.
Vorgehen
- 1. Lücken definieren: Setze .
- 2. Teleskopsumme bilden: Nutze .
- 3. Durchschnitt berechnen: Die mittlere Lücke ist .
- 4. Extremlücke folgern: Minimum liegt höchstens, Maximum mindestens beim Durchschnitt.
Geeignet
- eine geordnete Folge, Nachbarschaftsstruktur oder lokal verbesserbare Auswahl vorliegt
Reicht nicht
- die verwendete Ordnung oder Austauschoperation die Zulässigkeit nicht erhält
Das erste oder letzte Hindernis wählen
Das linkeste, früheste oder letzte fehlerhafte Objekt hat auf einer Seite bereits kontrollierte Struktur.
Warum funktioniert sie?
Das linkeste, früheste oder letzte fehlerhafte Objekt hat auf einer Seite bereits kontrollierte Struktur.
Erkennungssignale
- Eine geordnete Folge soll eine lokale Fehlstelle enthalten.
- Vor einem ersten Fehler oder nach einem letzten Fehler ist alles regulär.
Vorgehen
- 1. Fehler definieren: Formuliere genau, wann Ordnung oder Zielstruktur verletzt ist.
- 2. Ersten Fehler wählen: Nutze die natürliche Indexordnung.
- 3. Vorgängerstruktur verwenden: Alle früheren Positionen erfüllen die gewünschte Eigenschaft.
- 4. Lokalen Schluss ziehen: Am Übergang entsteht ein benachbartes Hindernis oder ein legaler Korrekturzug.
Geeignet
- eine geordnete Folge, Nachbarschaftsstruktur oder lokal verbesserbare Auswahl vorliegt
Reicht nicht
- die verwendete Ordnung oder Austauschoperation die Zulässigkeit nicht erhält
Ordnung und Schubfach verbinden
Sortierung macht die Schubfächer zu Intervallen; eine überfüllte Lücke oder Zelle liefert benachbarte Struktur.
Warum funktioniert sie?
Sortierung macht die Schubfächer zu Intervallen; eine überfüllte Lücke oder Zelle liefert benachbarte Struktur.
Erkennungssignale
- Viele geordnete Objekte liegen in einer beschränkten Strecke.
- Eine Abstandsschranke soll ohne Kenntnis der genauen Positionen bewiesen werden.
Vorgehen
- 1. Bereich zerlegen: Teile das Intervall in gleich große Teilintervalle.
- 2. Objekte einordnen: Verwende Positionen oder sortierte Ränge.
- 3. Kollision erzwingen: Mehr Punkte als Teilintervalle liefern zwei im selben Fach.
- 4. Abstand übersetzen: Zwei Punkte im selben Teilintervall erfüllen die gewünschte Schranke.
Geeignet
- eine geordnete Folge, Nachbarschaftsstruktur oder lokal verbesserbare Auswahl vorliegt
Reicht nicht
- die verwendete Ordnung oder Austauschoperation die Zulässigkeit nicht erhält
Eine Struktur bis zur Maximalität erweitern
Füge zulässige Objekte hinzu, bis keines mehr ergänzt werden kann – die Nichterweiterbarkeit kontrolliert alle Außenobjekte.
Warum funktioniert sie?
Füge zulässige Objekte hinzu, bis keines mehr ergänzt werden kann – die Nichterweiterbarkeit kontrolliert alle Außenobjekte.
Erkennungssignale
- Eine unabhängige Menge, Paarung, disjunkte Familie oder Auswahl wird gesucht.
- Größtmögliche Kardinalität ist nicht nötig, lokale Abdeckung genügt.
Vorgehen
- 1. Zulässigkeit definieren: Lege fest, welche Erweiterungen erlaubt sind.
- 2. Gierig erweitern: Füge ein beliebiges zulässiges Objekt hinzu.
- 3. Endlichkeit nutzen: Der Prozess endet bei einer maximalen Struktur.
- 4. Außenobjekte kontrollieren: Jedes nicht gewählte Objekt muss eine Erweiterung konkret blockieren.
Geeignet
- eine geordnete Folge, Nachbarschaftsstruktur oder lokal verbesserbare Auswahl vorliegt
Reicht nicht
- die verwendete Ordnung oder Austauschoperation die Zulässigkeit nicht erhält
Eine Extremalauswahl durch Austausch prüfen
Ersetze ein ungünstiges gewähltes Objekt durch ein besseres ungewähltes; wäre das legal und strikt besser, war die Auswahl nicht optimal.
Warum funktioniert sie?
Ersetze ein ungünstiges gewähltes Objekt durch ein besseres ungewähltes; wäre das legal und strikt besser, war die Auswahl nicht optimal.
Erkennungssignale
- Eine Auswahl fester Größe maximiert Summe, Gewicht oder eine lexikographische Signatur.
- Ein gewähltes schlechtes und ein ungewähltes besseres Objekt sind vergleichbar.
Vorgehen
- 1. Optimale Auswahl fixieren: Wähle eine Auswahl mit extremem Zielfunktionswert.
- 2. Schlechtes und besseres Objekt finden: Identifiziere ein austauschbares Paar.
- 3. Zulässigkeit erhalten: Prüfe, dass der Austausch alle Nebenbedingungen bewahrt.
- 4. Verbesserung widersprechen: Der streng bessere Wert widerspricht der optimalen Wahl.
Geeignet
- eine geordnete Folge, Nachbarschaftsstruktur oder lokal verbesserbare Auswahl vorliegt
Reicht nicht
- die verwendete Ordnung oder Austauschoperation die Zulässigkeit nicht erhält
Lokale Verbesserungen bis zum Stillstand durchführen
Eine ganzzahlige Zielfunktion steigt oder fällt bei jeder Korrektur streng; am Ende erfüllt ein lokal nicht verbesserbarer Zustand die gewünschte Struktur.
Warum funktioniert sie?
Eine ganzzahlige Zielfunktion steigt oder fällt bei jeder Korrektur streng; am Ende erfüllt ein lokal nicht verbesserbarer Zustand die gewünschte Struktur.
Erkennungssignale
- Benachbarte Vertauschungen oder lokale Ersetzungen korrigieren Fehler.
- Terminierung und Struktur des Endzustands sollen gemeinsam bewiesen werden.
Vorgehen
- 1. Fehlerzug definieren: Gib eine lokale Operation an, die eine Verletzung korrigiert.
- 2. Potenzial wählen: Nutze Inversionszahl, Summe oder lexikographischen Rang.
- 3. Strikte Änderung zeigen: Jeder Korrekturzug verbessert das Potenzial.
- 4. Endstruktur lesen: Ohne lokalen Fehler gilt die gewünschte globale Eigenschaft.
Geeignet
- eine geordnete Folge, Nachbarschaftsstruktur oder lokal verbesserbare Auswahl vorliegt
Reicht nicht
- die verwendete Ordnung oder Austauschoperation die Zulässigkeit nicht erhält
Den kleinsten Teiler größer als 1 wählen
Der kleinste Teiler einer Zahl muss prim sein, denn ein echter Faktor von wäre ein noch kleinerer Teiler.
Warum funktioniert sie?
Der kleinste Teiler einer Zahl muss prim sein, denn ein echter Faktor von wäre ein noch kleinerer Teiler.
Erkennungssignale
- Eine zusammengesetzte Zahl soll einen Primteiler besitzen.
- Teiler sind positive ganze Zahlen und damit wohlgeordnet.
Vorgehen
- 1. Teilermenge bilden: Betrachte alle Teiler größer als 1.
- 2. Kleinsten wählen: Die Menge ist nichtleer, da die Zahl selbst dazugehört.
- 3. Zusammengesetztheit annehmen: Schreibe mit .
- 4. Minimalität widersprechen: Dann teilt ebenfalls die Ausgangszahl.
Geeignet
- positive ganze Teiler, Reste, Linearkombinationen oder Lösungen durch die Wohlordnung minimiert werden können
Reicht nicht
- die Kandidatenmenge keine positiven Elemente besitzt oder der Reduktionsschritt die arithmetischen Voraussetzungen verliert
Einen kleinsten nichtnegativen Rest wählen
Unter allen nichtnegativen ist die kleinste kleiner als – sonst könntest du nochmals abziehen.
Warum funktioniert sie?
Unter allen nichtnegativen ist die kleinste kleiner als – sonst könntest du nochmals abziehen.
Erkennungssignale
- Die Division mit Rest soll aus der Wohlordnung hergeleitet werden.
- Ganzzahlige Verschiebungen um ein festes treten auf.
Vorgehen
- 1. Nichtnegative Kandidaten sichern: Wähle so klein, dass .
- 2. Minimum wählen: Setze minimal nichtnegativ.
- 3. Obere Schranke zeigen: Aus folgte der kleinere Kandidat .
- 4. Darstellung schließen: Damit gilt und .
Geeignet
- positive ganze Teiler, Reste, Linearkombinationen oder Lösungen durch die Wohlordnung minimiert werden können
Reicht nicht
- die Kandidatenmenge keine positiven Elemente besitzt oder der Reduktionsschritt die arithmetischen Voraussetzungen verliert
Die kleinste positive Linearkombination nutzen
Die kleinste positive Zahl der Form teilt sowohl als auch und ist dadurch ihr ggT.
Warum funktioniert sie?
Die kleinste positive Zahl der Form teilt sowohl als auch und ist dadurch ihr ggT.
Erkennungssignale
- Der ggT soll mit Bézout verbunden werden.
- Ganzzahlige Linearkombinationen sind unter Differenzen abgeschlossen.
Vorgehen
- 1. Positive Kombinationen betrachten: Wähle das kleinste .
- 2. Mit Rest teilen: Schreibe mit .
- 3. Rest als Kombination schreiben: ist wieder eine Linearkombination von .
- 4. Minimalität anwenden: Daher ist ; ebenso teilt die Zahl .
Geeignet
- positive ganze Teiler, Reste, Linearkombinationen oder Lösungen durch die Wohlordnung minimiert werden können
Reicht nicht
- die Kandidatenmenge keine positiven Elemente besitzt oder der Reduktionsschritt die arithmetischen Voraussetzungen verliert
Bézout auf eine Teilbarkeitsaussage übertragen
Eine Darstellung multipliziert die gewünschte Zahl in eine Summe offensichtlich teilbarer Terme.
Warum funktioniert sie?
Eine Darstellung multipliziert die gewünschte Zahl in eine Summe offensichtlich teilbarer Terme.
Erkennungssignale
- Es gilt und .
- Teilerfremdheit soll eine Teilbarkeit kürzen.
Vorgehen
- 1. Bézout darstellen: Finde mit .
- 2. Mit Zielzahl multiplizieren: Schreibe .
- 3. Beide Terme prüfen: teilt und wegen auch .
- 4. Summe folgern: Damit teilt die Zahl .
Geeignet
- positive ganze Teiler, Reste, Linearkombinationen oder Lösungen durch die Wohlordnung minimiert werden können
Reicht nicht
- die Kandidatenmenge keine positiven Elemente besitzt oder der Reduktionsschritt die arithmetischen Voraussetzungen verliert
Eine zusammengesetzte Zahl in kleinere Faktoren zerlegen
Ein kleinstes Gegenbeispiel zur Primfaktorzerlegung ist zusammengesetzt und zerfällt in zwei kleinere Zahlen, die nach Minimalität bereits zerlegbar sind.
Warum funktioniert sie?
Ein kleinstes Gegenbeispiel zur Primfaktorzerlegung ist zusammengesetzt und zerfällt in zwei kleinere Zahlen, die nach Minimalität bereits zerlegbar sind.
Erkennungssignale
- Eine Aussage über alle ganzen Zahlen größer als 1 betrifft Produkte.
- Ein zusammengesetztes Gegenbeispiel besitzt kleinere Faktoren.
Vorgehen
- 1. Kleinstes Gegenbeispiel wählen: Nutze die Wohlordnung.
- 2. Primfall ausschließen: Eine Primzahl ist bereits ein Produkt aus einer Primzahl.
- 3. Echt faktorisieren: Schreibe mit .
- 4. Kleinere Zerlegungen verbinden: Die Zerlegungen von liefern eine für .
Geeignet
- positive ganze Teiler, Reste, Linearkombinationen oder Lösungen durch die Wohlordnung minimiert werden können
Reicht nicht
- die Kandidatenmenge keine positiven Elemente besitzt oder der Reduktionsschritt die arithmetischen Voraussetzungen verliert
Eine kleinste positive Lösung absteigen lassen
Aus einer hypothetischen kleinsten Lösung baust du eine neue positive Lösung mit kleinerem Größenparameter.
Warum funktioniert sie?
Aus einer hypothetischen kleinsten Lösung baust du eine neue positive Lösung mit kleinerem Größenparameter.
Erkennungssignale
- Eine diophantische Gleichung ist homogen oder unter Skalierung stabil.
- Teilbarkeitsfolgen zwingen alle Variablen durch denselben Faktor.
Vorgehen
- 1. Lösungsgröße wählen: Minimiere etwa Summe, Maximum oder Nenner.
- 2. Teilbarkeit erzwingen: Leite einen gemeinsamen Faktor der Variablen her.
- 3. Herunterskalieren: Teile durch den Faktor und prüfe dieselbe Gleichung.
- 4. Minimalität widersprechen: Die neue positive Lösung ist echt kleiner.
Geeignet
- positive ganze Teiler, Reste, Linearkombinationen oder Lösungen durch die Wohlordnung minimiert werden können
Reicht nicht
- die Kandidatenmenge keine positiven Elemente besitzt oder der Reduktionsschritt die arithmetischen Voraussetzungen verliert
Einen zahlentheoretischen Abstieg auditieren
Ein gültiger Abstieg bewahrt Ganzzahligkeit, Positivität und Gleichung und senkt eine wohlfundierte Größe strikt.
Warum funktioniert sie?
Ein gültiger Abstieg bewahrt Ganzzahligkeit, Positivität und Gleichung und senkt eine wohlfundierte Größe strikt.
Erkennungssignale
- Eine Lösung sagt nur „so geht es immer weiter“.
- Beim Teilen könnten Ganzzahligkeit oder Positivität verloren gehen.
Vorgehen
- 1. Größe definieren: Nenne die positive ganze Größe, die sinkt.
- 2. Neue Lösung prüfen: Kontrolliere alle Gleichungen und Voraussetzungen.
- 3. Strikten Abstieg zeigen: Zeige, dass die neue Größe echt kleiner ist.
- 4. Wohlordnung anwenden: Eine unendliche strikt fallende Folge positiver ganzer Zahlen existiert nicht.
Geeignet
- positive ganze Teiler, Reste, Linearkombinationen oder Lösungen durch die Wohlordnung minimiert werden können
Reicht nicht
- die Kandidatenmenge keine positiven Elemente besitzt oder der Reduktionsschritt die arithmetischen Voraussetzungen verliert
Eine Menge extremer Größe wählen
Eine größte oder kleinste Mitgliedsmenge bündelt die Kardinalitätsbedingungen der ganzen Familie.
Warum funktioniert sie?
Eine größte oder kleinste Mitgliedsmenge bündelt die Kardinalitätsbedingungen der ganzen Familie.
Erkennungssignale
- Eine endliche Mengenfamilie oder kombinatorische Auswahl soll erweitert, verkleinert oder lokal verbessert werden.
Vorgehen
- 1. Extremalauswahl treffen: Wähle maximal nach Inklusion, minimal nach Größe oder optimal nach einer Zielfunktion.
- 2. Scheitern annehmen: Nimm ein unkontrolliertes Außenobjekt oder eine fehlende Zeugenstruktur an.
- 3. Lokal verändern: Erweitere, entferne oder tausche Objekte unter Erhalt der Zulässigkeit.
- 4. Extremalität anwenden: Die strikte Verbesserung liefert Widerspruch oder die gesuchte Struktur.
Geeignet
- Zulässigkeit durch Disjunktheit, Überdeckung, Paarung oder Schnittstruktur beschrieben ist
Reicht nicht
- die lokale Änderung die kombinatorischen Nebenbedingungen nicht erhält
Eine maximale disjunkte Teilfamilie wählen
Jede nicht gewählte Menge muss eine gewählte schneiden – sonst wäre die Familie erweiterbar.
Warum funktioniert sie?
Jede nicht gewählte Menge muss eine gewählte schneiden – sonst wäre die Familie erweiterbar.
Erkennungssignale
- Eine endliche Mengenfamilie oder kombinatorische Auswahl soll erweitert, verkleinert oder lokal verbessert werden.
Vorgehen
- 1. Extremalauswahl treffen: Wähle maximal nach Inklusion, minimal nach Größe oder optimal nach einer Zielfunktion.
- 2. Scheitern annehmen: Nimm ein unkontrolliertes Außenobjekt oder eine fehlende Zeugenstruktur an.
- 3. Lokal verändern: Erweitere, entferne oder tausche Objekte unter Erhalt der Zulässigkeit.
- 4. Extremalität anwenden: Die strikte Verbesserung liefert Widerspruch oder die gesuchte Struktur.
Geeignet
- Zulässigkeit durch Disjunktheit, Überdeckung, Paarung oder Schnittstruktur beschrieben ist
Reicht nicht
- die lokale Änderung die kombinatorischen Nebenbedingungen nicht erhält
Einen privaten Zeugen erzwingen
In einer inklusionsminimalen Überdeckung hat jedes gewählte Objekt einen privaten Punkt, den kein anderes abdeckt.
Warum funktioniert sie?
In einer inklusionsminimalen Überdeckung hat jedes gewählte Objekt einen privaten Punkt, den kein anderes abdeckt.
Erkennungssignale
- Eine endliche Mengenfamilie oder kombinatorische Auswahl soll erweitert, verkleinert oder lokal verbessert werden.
Vorgehen
- 1. Extremalauswahl treffen: Wähle maximal nach Inklusion, minimal nach Größe oder optimal nach einer Zielfunktion.
- 2. Scheitern annehmen: Nimm ein unkontrolliertes Außenobjekt oder eine fehlende Zeugenstruktur an.
- 3. Lokal verändern: Erweitere, entferne oder tausche Objekte unter Erhalt der Zulässigkeit.
- 4. Extremalität anwenden: Die strikte Verbesserung liefert Widerspruch oder die gesuchte Struktur.
Geeignet
- Zulässigkeit durch Disjunktheit, Überdeckung, Paarung oder Schnittstruktur beschrieben ist
Reicht nicht
- die lokale Änderung die kombinatorischen Nebenbedingungen nicht erhält
Eine längste Inklusionskette nutzen
Eine längste Kette kann an keinem Ende durch ein vergleichbares Familienmitglied erweitert werden.
Warum funktioniert sie?
Eine längste Kette kann an keinem Ende durch ein vergleichbares Familienmitglied erweitert werden.
Erkennungssignale
- Eine endliche Mengenfamilie oder kombinatorische Auswahl soll erweitert, verkleinert oder lokal verbessert werden.
Vorgehen
- 1. Extremalauswahl treffen: Wähle maximal nach Inklusion, minimal nach Größe oder optimal nach einer Zielfunktion.
- 2. Scheitern annehmen: Nimm ein unkontrolliertes Außenobjekt oder eine fehlende Zeugenstruktur an.
- 3. Lokal verändern: Erweitere, entferne oder tausche Objekte unter Erhalt der Zulässigkeit.
- 4. Extremalität anwenden: Die strikte Verbesserung liefert Widerspruch oder die gesuchte Struktur.
Geeignet
- Zulässigkeit durch Disjunktheit, Überdeckung, Paarung oder Schnittstruktur beschrieben ist
Reicht nicht
- die lokale Änderung die kombinatorischen Nebenbedingungen nicht erhält
Einen maximalen Schnitt lokal prüfen
Bei maximal vielen Schnittkanten hat jeder Knoten mindestens so viele Nachbarn auf der Gegenseite wie auf seiner Seite.
Warum funktioniert sie?
Bei maximal vielen Schnittkanten hat jeder Knoten mindestens so viele Nachbarn auf der Gegenseite wie auf seiner Seite.
Erkennungssignale
- Eine endliche Mengenfamilie oder kombinatorische Auswahl soll erweitert, verkleinert oder lokal verbessert werden.
Vorgehen
- 1. Extremalauswahl treffen: Wähle maximal nach Inklusion, minimal nach Größe oder optimal nach einer Zielfunktion.
- 2. Scheitern annehmen: Nimm ein unkontrolliertes Außenobjekt oder eine fehlende Zeugenstruktur an.
- 3. Lokal verändern: Erweitere, entferne oder tausche Objekte unter Erhalt der Zulässigkeit.
- 4. Extremalität anwenden: Die strikte Verbesserung liefert Widerspruch oder die gesuchte Struktur.
Geeignet
- Zulässigkeit durch Disjunktheit, Überdeckung, Paarung oder Schnittstruktur beschrieben ist
Reicht nicht
- die lokale Änderung die kombinatorischen Nebenbedingungen nicht erhält
Eine Auswahl durch einen augmentierenden Austausch verbessern
Ein alternierender Austausch mit mehr neuen als entfernten Objekten widerspricht maximaler Kardinalität.
Warum funktioniert sie?
Ein alternierender Austausch mit mehr neuen als entfernten Objekten widerspricht maximaler Kardinalität.
Erkennungssignale
- Eine endliche Mengenfamilie oder kombinatorische Auswahl soll erweitert, verkleinert oder lokal verbessert werden.
Vorgehen
- 1. Extremalauswahl treffen: Wähle maximal nach Inklusion, minimal nach Größe oder optimal nach einer Zielfunktion.
- 2. Scheitern annehmen: Nimm ein unkontrolliertes Außenobjekt oder eine fehlende Zeugenstruktur an.
- 3. Lokal verändern: Erweitere, entferne oder tausche Objekte unter Erhalt der Zulässigkeit.
- 4. Extremalität anwenden: Die strikte Verbesserung liefert Widerspruch oder die gesuchte Struktur.
Geeignet
- Zulässigkeit durch Disjunktheit, Überdeckung, Paarung oder Schnittstruktur beschrieben ist
Reicht nicht
- die lokale Änderung die kombinatorischen Nebenbedingungen nicht erhält
Extremale Mengensysteme auditieren
Der Audit trennt Inklusionsmaximalität, Kardinalitätsmaximum, Minimalität und lokale Austauschoptimalität.
Warum funktioniert sie?
Der Audit trennt Inklusionsmaximalität, Kardinalitätsmaximum, Minimalität und lokale Austauschoptimalität.
Erkennungssignale
- Eine endliche Mengenfamilie oder kombinatorische Auswahl soll erweitert, verkleinert oder lokal verbessert werden.
Vorgehen
- 1. Extremalauswahl treffen: Wähle maximal nach Inklusion, minimal nach Größe oder optimal nach einer Zielfunktion.
- 2. Scheitern annehmen: Nimm ein unkontrolliertes Außenobjekt oder eine fehlende Zeugenstruktur an.
- 3. Lokal verändern: Erweitere, entferne oder tausche Objekte unter Erhalt der Zulässigkeit.
- 4. Extremalität anwenden: Die strikte Verbesserung liefert Widerspruch oder die gesuchte Struktur.
Geeignet
- Zulässigkeit durch Disjunktheit, Überdeckung, Paarung oder Schnittstruktur beschrieben ist
Reicht nicht
- die lokale Änderung die kombinatorischen Nebenbedingungen nicht erhält
Endpunkte eines längsten Weges untersuchen
Ein Endpunkt kann keinen Nachbarn außerhalb des Weges haben – sonst könntest du den Weg verlängern.
Warum funktioniert sie?
Ein Endpunkt kann keinen Nachbarn außerhalb des Weges haben – sonst könntest du den Weg verlängern.
Erkennungssignale
- Ein endlicher Graph enthält Wege, Zyklen, Grade oder gewichtete Kanten, die extrem gewählt werden können.
Vorgehen
- 1. Extrem wählen: Fixiere längsten Weg, kürzesten Zyklus, größten Grad oder leichtesten Baum.
- 2. Lokale Abweichung annehmen: Nimm einen Außennachbarn, eine Sehne oder eine bessere Kante an.
- 3. Graphobjekt verändern: Verlängere, kürze oder tausche entlang eines Zyklus.
- 4. Extremalität anwenden: Die strikte Verbesserung liefert Struktur oder Widerspruch.
Geeignet
- Verlängern, Abkürzen oder Austauschen die Graphstruktur erhält
Reicht nicht
- der konstruierte Weg, Zyklus oder Baum nicht einfach bzw. nicht zusammenhängend bleibt
Einen kürzesten Zyklus wählen
Eine Sehne würde einen kürzeren Zyklus erzeugen – der Extremzyklus ist daher sehnenlos.
Warum funktioniert sie?
Eine Sehne würde einen kürzeren Zyklus erzeugen – der Extremzyklus ist daher sehnenlos.
Erkennungssignale
- Ein endlicher Graph enthält Wege, Zyklen, Grade oder gewichtete Kanten, die extrem gewählt werden können.
Vorgehen
- 1. Extrem wählen: Fixiere längsten Weg, kürzesten Zyklus, größten Grad oder leichtesten Baum.
- 2. Lokale Abweichung annehmen: Nimm einen Außennachbarn, eine Sehne oder eine bessere Kante an.
- 3. Graphobjekt verändern: Verlängere, kürze oder tausche entlang eines Zyklus.
- 4. Extremalität anwenden: Die strikte Verbesserung liefert Struktur oder Widerspruch.
Geeignet
- Verlängern, Abkürzen oder Austauschen die Graphstruktur erhält
Reicht nicht
- der konstruierte Weg, Zyklus oder Baum nicht einfach bzw. nicht zusammenhängend bleibt
Einen Knoten extremen Grades wählen
Minimaler oder maximaler Grad übersetzt globale Kanteninformation in lokale Nachbarschaft.
Warum funktioniert sie?
Minimaler oder maximaler Grad übersetzt globale Kanteninformation in lokale Nachbarschaft.
Erkennungssignale
- Ein endlicher Graph enthält Wege, Zyklen, Grade oder gewichtete Kanten, die extrem gewählt werden können.
Vorgehen
- 1. Extrem wählen: Fixiere längsten Weg, kürzesten Zyklus, größten Grad oder leichtesten Baum.
- 2. Lokale Abweichung annehmen: Nimm einen Außennachbarn, eine Sehne oder eine bessere Kante an.
- 3. Graphobjekt verändern: Verlängere, kürze oder tausche entlang eines Zyklus.
- 4. Extremalität anwenden: Die strikte Verbesserung liefert Struktur oder Widerspruch.
Geeignet
- Verlängern, Abkürzen oder Austauschen die Graphstruktur erhält
Reicht nicht
- der konstruierte Weg, Zyklus oder Baum nicht einfach bzw. nicht zusammenhängend bleibt
Einen zusammenhängenden Graphen zum Spannbaum reduzieren
Entferne aus einem Zyklus eine Kante: Zusammenhang bleibt, Kantenanzahl sinkt.
Warum funktioniert sie?
Entferne aus einem Zyklus eine Kante: Zusammenhang bleibt, Kantenanzahl sinkt.
Erkennungssignale
- Ein endlicher Graph enthält Wege, Zyklen, Grade oder gewichtete Kanten, die extrem gewählt werden können.
Vorgehen
- 1. Extrem wählen: Fixiere längsten Weg, kürzesten Zyklus, größten Grad oder leichtesten Baum.
- 2. Lokale Abweichung annehmen: Nimm einen Außennachbarn, eine Sehne oder eine bessere Kante an.
- 3. Graphobjekt verändern: Verlängere, kürze oder tausche entlang eines Zyklus.
- 4. Extremalität anwenden: Die strikte Verbesserung liefert Struktur oder Widerspruch.
Geeignet
- Verlängern, Abkürzen oder Austauschen die Graphstruktur erhält
Reicht nicht
- der konstruierte Weg, Zyklus oder Baum nicht einfach bzw. nicht zusammenhängend bleibt
Kanten entlang eines Zyklus austauschen
Eine neue Kante erzeugt im Baum genau einen Zyklus; entfernst du eine geeignete Zykluskante, entsteht ein besserer Baum.
Warum funktioniert sie?
Eine neue Kante erzeugt im Baum genau einen Zyklus; entfernst du eine geeignete Zykluskante, entsteht ein besserer Baum.
Erkennungssignale
- Ein endlicher Graph enthält Wege, Zyklen, Grade oder gewichtete Kanten, die extrem gewählt werden können.
Vorgehen
- 1. Extrem wählen: Fixiere längsten Weg, kürzesten Zyklus, größten Grad oder leichtesten Baum.
- 2. Lokale Abweichung annehmen: Nimm einen Außennachbarn, eine Sehne oder eine bessere Kante an.
- 3. Graphobjekt verändern: Verlängere, kürze oder tausche entlang eines Zyklus.
- 4. Extremalität anwenden: Die strikte Verbesserung liefert Struktur oder Widerspruch.
Geeignet
- Verlängern, Abkürzen oder Austauschen die Graphstruktur erhält
Reicht nicht
- der konstruierte Weg, Zyklus oder Baum nicht einfach bzw. nicht zusammenhängend bleibt
Eine leichteste Schnittkante sichern
Überquert ein Spannbaum einen Schnitt mit einer schwereren Kante, kann eine leichteste Schnittkante sie austauschen.
Warum funktioniert sie?
Überquert ein Spannbaum einen Schnitt mit einer schwereren Kante, kann eine leichteste Schnittkante sie austauschen.
Erkennungssignale
- Ein endlicher Graph enthält Wege, Zyklen, Grade oder gewichtete Kanten, die extrem gewählt werden können.
Vorgehen
- 1. Extrem wählen: Fixiere längsten Weg, kürzesten Zyklus, größten Grad oder leichtesten Baum.
- 2. Lokale Abweichung annehmen: Nimm einen Außennachbarn, eine Sehne oder eine bessere Kante an.
- 3. Graphobjekt verändern: Verlängere, kürze oder tausche entlang eines Zyklus.
- 4. Extremalität anwenden: Die strikte Verbesserung liefert Struktur oder Widerspruch.
Geeignet
- Verlängern, Abkürzen oder Austauschen die Graphstruktur erhält
Reicht nicht
- der konstruierte Weg, Zyklus oder Baum nicht einfach bzw. nicht zusammenhängend bleibt
Graph-Extremalbeweise auditieren
Der Audit prüft Einfachheit, Zusammenhang, Zyklenfreiheit und strikte Verbesserung des Graphobjekts.
Warum funktioniert sie?
Der Audit prüft Einfachheit, Zusammenhang, Zyklenfreiheit und strikte Verbesserung des Graphobjekts.
Erkennungssignale
- Ein endlicher Graph enthält Wege, Zyklen, Grade oder gewichtete Kanten, die extrem gewählt werden können.
Vorgehen
- 1. Extrem wählen: Fixiere längsten Weg, kürzesten Zyklus, größten Grad oder leichtesten Baum.
- 2. Lokale Abweichung annehmen: Nimm einen Außennachbarn, eine Sehne oder eine bessere Kante an.
- 3. Graphobjekt verändern: Verlängere, kürze oder tausche entlang eines Zyklus.
- 4. Extremalität anwenden: Die strikte Verbesserung liefert Struktur oder Widerspruch.
Geeignet
- Verlängern, Abkürzen oder Austauschen die Graphstruktur erhält
Reicht nicht
- der konstruierte Weg, Zyklus oder Baum nicht einfach bzw. nicht zusammenhängend bleibt
Einen äußersten Punkt und eine Stützgerade wählen
Eine maximale Projektion legt alle Punkte auf eine Seite einer Geraden – die Stützgerade.
Warum funktioniert sie?
Eine maximale Projektion legt alle Punkte auf eine Seite einer Geraden – die Stützgerade.
Erkennungssignale
- Eine endliche Punkt- oder Figurenmenge besitzt extreme Lage, Distanz, Richtung oder Fläche.
Vorgehen
- 1. Größe wählen: Projiziere, miss Abstand, Winkel oder Fläche.
- 2. Extrem fixieren: Wähle äußersten Punkt, kleinstes Paar oder größte Figur.
- 3. Lokal verändern: Verschiebe eine Stützgerade oder tausche einen Eckpunkt.
- 4. Verbesserung ausschließen: Nutze den Widerspruch zur Extremalität.
Geeignet
- geometrische Kandidaten endlich sind oder ein Extrem sicher angenommen werden kann
Reicht nicht
- Degeneration oder fehlende Existenz übersehen wird
Ecken der konvexen Hülle nutzen
Äußerste Richtungen reduzieren die Punktmenge auf ihre Randpunkte.
Warum funktioniert sie?
Äußerste Richtungen reduzieren die Punktmenge auf ihre Randpunkte.
Erkennungssignale
- Eine endliche Punkt- oder Figurenmenge besitzt extreme Lage, Distanz, Richtung oder Fläche.
Vorgehen
- 1. Größe wählen: Projiziere, miss Abstand, Winkel oder Fläche.
- 2. Extrem fixieren: Wähle äußersten Punkt, kleinstes Paar oder größte Figur.
- 3. Lokal verändern: Verschiebe eine Stützgerade oder tausche einen Eckpunkt.
- 4. Verbesserung ausschließen: Nutze den Widerspruch zur Extremalität.
Geeignet
- geometrische Kandidaten endlich sind oder ein Extrem sicher angenommen werden kann
Reicht nicht
- Degeneration oder fehlende Existenz übersehen wird
Ein nächstes Punktepaar wählen
Ein dritter zu naher Punkt oder eine feinere Zerlegung widerspricht dem Minimalabstand.
Warum funktioniert sie?
Ein dritter zu naher Punkt oder eine feinere Zerlegung widerspricht dem Minimalabstand.
Erkennungssignale
- Eine endliche Punkt- oder Figurenmenge besitzt extreme Lage, Distanz, Richtung oder Fläche.
Vorgehen
- 1. Größe wählen: Projiziere, miss Abstand, Winkel oder Fläche.
- 2. Extrem fixieren: Wähle äußersten Punkt, kleinstes Paar oder größte Figur.
- 3. Lokal verändern: Verschiebe eine Stützgerade oder tausche einen Eckpunkt.
- 4. Verbesserung ausschließen: Nutze den Widerspruch zur Extremalität.
Geeignet
- geometrische Kandidaten endlich sind oder ein Extrem sicher angenommen werden kann
Reicht nicht
- Degeneration oder fehlende Existenz übersehen wird
Ein fernstes Punktepaar wählen
Ein Durchmesserpaar kontrolliert Projektionen und liegt auf dem konvexen Rand.
Warum funktioniert sie?
Ein Durchmesserpaar kontrolliert Projektionen und liegt auf dem konvexen Rand.
Erkennungssignale
- Eine endliche Punkt- oder Figurenmenge besitzt extreme Lage, Distanz, Richtung oder Fläche.
Vorgehen
- 1. Größe wählen: Projiziere, miss Abstand, Winkel oder Fläche.
- 2. Extrem fixieren: Wähle äußersten Punkt, kleinstes Paar oder größte Figur.
- 3. Lokal verändern: Verschiebe eine Stützgerade oder tausche einen Eckpunkt.
- 4. Verbesserung ausschließen: Nutze den Widerspruch zur Extremalität.
Geeignet
- geometrische Kandidaten endlich sind oder ein Extrem sicher angenommen werden kann
Reicht nicht
- Degeneration oder fehlende Existenz übersehen wird
Eine Figur maximaler Fläche wählen
Ein Eckpunktaustausch zu größerer Höhe würde die maximale Fläche verbessern – also ist er unmöglich.
Warum funktioniert sie?
Ein Eckpunktaustausch zu größerer Höhe würde die maximale Fläche verbessern – also ist er unmöglich.
Erkennungssignale
- Eine endliche Punkt- oder Figurenmenge besitzt extreme Lage, Distanz, Richtung oder Fläche.
Vorgehen
- 1. Größe wählen: Projiziere, miss Abstand, Winkel oder Fläche.
- 2. Extrem fixieren: Wähle äußersten Punkt, kleinstes Paar oder größte Figur.
- 3. Lokal verändern: Verschiebe eine Stützgerade oder tausche einen Eckpunkt.
- 4. Verbesserung ausschließen: Nutze den Widerspruch zur Extremalität.
Geeignet
- geometrische Kandidaten endlich sind oder ein Extrem sicher angenommen werden kann
Reicht nicht
- Degeneration oder fehlende Existenz übersehen wird
Geometrische Extremalbeweise auditieren
Existenz, Degeneration, Stützrichtung und strikte Flächen- oder Distanzverbesserung prüfst du getrennt.
Warum funktioniert sie?
Existenz, Degeneration, Stützrichtung und strikte Flächen- oder Distanzverbesserung prüfst du getrennt.
Erkennungssignale
- Eine endliche Punkt- oder Figurenmenge besitzt extreme Lage, Distanz, Richtung oder Fläche.
Vorgehen
- 1. Größe wählen: Projiziere, miss Abstand, Winkel oder Fläche.
- 2. Extrem fixieren: Wähle äußersten Punkt, kleinstes Paar oder größte Figur.
- 3. Lokal verändern: Verschiebe eine Stützgerade oder tausche einen Eckpunkt.
- 4. Verbesserung ausschließen: Nutze den Widerspruch zur Extremalität.
Geeignet
- geometrische Kandidaten endlich sind oder ein Extrem sicher angenommen werden kann
Reicht nicht
- Degeneration oder fehlende Existenz übersehen wird
Extremalwahl mit Schubfach verbinden
Sortierung oder ein Extrem reduziert die möglichen Fächer und macht eine erzwungene Kollision scharf.
Warum funktioniert sie?
Sortierung oder ein Extrem reduziert die möglichen Fächer und macht eine erzwungene Kollision scharf.
Erkennungssignale
- Eine Extremalwahl liefert Struktur, aber Existenz, Zählung oder Terminierung benötigt eine zweite Methode.
Vorgehen
- 1. Extremalrolle bestimmen: Wähle Objekt und leite seine lokale Struktur ab.
- 2. Offene Lücke benennen: Fehlen Kollision, Zählwert, Erhaltung, Reduktion oder Terminierung?
- 3. Zweitmethode anwenden: Nutze genau das Extremal-Zwischenergebnis als Voraussetzung.
- 4. Kette schließen: Prüfe Übergang und Reichweite des Gesamtschlusses.
Geeignet
- du die Rolle jeder Methode als eigenen Beweisschritt benennen kannst
Reicht nicht
- Methoden nur nebeneinander genannt werden, ohne dass ein Zwischenergebnis den nächsten Schritt ermöglicht
Extremalwahl mit Doppelzählung verbinden
Eine globale Summe erzwingt ein Objekt extremen lokalen Beitrags – Doppelzählung trifft Extrem.
Warum funktioniert sie?
Eine globale Summe erzwingt ein Objekt extremen lokalen Beitrags – Doppelzählung trifft Extrem.
Erkennungssignale
- Eine Extremalwahl liefert Struktur, aber Existenz, Zählung oder Terminierung benötigt eine zweite Methode.
Vorgehen
- 1. Extremalrolle bestimmen: Wähle Objekt und leite seine lokale Struktur ab.
- 2. Offene Lücke benennen: Fehlen Kollision, Zählwert, Erhaltung, Reduktion oder Terminierung?
- 3. Zweitmethode anwenden: Nutze genau das Extremal-Zwischenergebnis als Voraussetzung.
- 4. Kette schließen: Prüfe Übergang und Reichweite des Gesamtschlusses.
Geeignet
- du die Rolle jeder Methode als eigenen Beweisschritt benennen kannst
Reicht nicht
- Methoden nur nebeneinander genannt werden, ohne dass ein Zwischenergebnis den nächsten Schritt ermöglicht
Extremalwahl mit Invarianten verbinden
Die Invariante hält die Klasse; die Extremalwahl liefert darin Fortschritt oder Struktur.
Warum funktioniert sie?
Die Invariante hält die Klasse; die Extremalwahl liefert darin Fortschritt oder Struktur.
Erkennungssignale
- Eine Extremalwahl liefert Struktur, aber Existenz, Zählung oder Terminierung benötigt eine zweite Methode.
Vorgehen
- 1. Extremalrolle bestimmen: Wähle Objekt und leite seine lokale Struktur ab.
- 2. Offene Lücke benennen: Fehlen Kollision, Zählwert, Erhaltung, Reduktion oder Terminierung?
- 3. Zweitmethode anwenden: Nutze genau das Extremal-Zwischenergebnis als Voraussetzung.
- 4. Kette schließen: Prüfe Übergang und Reichweite des Gesamtschlusses.
Geeignet
- du die Rolle jeder Methode als eigenen Beweisschritt benennen kannst
Reicht nicht
- Methoden nur nebeneinander genannt werden, ohne dass ein Zwischenergebnis den nächsten Schritt ermöglicht
Extremalobjekt für Induktion entfernen
Ein Blatt, Randobjekt oder kleinstes Element erzeugt eine kleinere Instanz – die Lösung baust du zurück.
Warum funktioniert sie?
Ein Blatt, Randobjekt oder kleinstes Element erzeugt eine kleinere Instanz – die Lösung baust du zurück.
Erkennungssignale
- Eine Extremalwahl liefert Struktur, aber Existenz, Zählung oder Terminierung benötigt eine zweite Methode.
Vorgehen
- 1. Extremalrolle bestimmen: Wähle Objekt und leite seine lokale Struktur ab.
- 2. Offene Lücke benennen: Fehlen Kollision, Zählwert, Erhaltung, Reduktion oder Terminierung?
- 3. Zweitmethode anwenden: Nutze genau das Extremal-Zwischenergebnis als Voraussetzung.
- 4. Kette schließen: Prüfe Übergang und Reichweite des Gesamtschlusses.
Geeignet
- du die Rolle jeder Methode als eigenen Beweisschritt benennen kannst
Reicht nicht
- Methoden nur nebeneinander genannt werden, ohne dass ein Zwischenergebnis den nächsten Schritt ermöglicht
Extremalwahl mit Monovarianten verbinden
Das Extrem macht einen legalen Verbesserungszug sichtbar; eine streng monotone ganzzahlige Größe erzwingt Terminierung.
Warum funktioniert sie?
Das Extrem macht einen legalen Verbesserungszug sichtbar; eine streng monotone ganzzahlige Größe erzwingt Terminierung.
Erkennungssignale
- Eine Extremalwahl liefert Struktur, aber Existenz, Zählung oder Terminierung benötigt eine zweite Methode.
Vorgehen
- 1. Extremalrolle bestimmen: Wähle Objekt und leite seine lokale Struktur ab.
- 2. Offene Lücke benennen: Fehlen Kollision, Zählwert, Erhaltung, Reduktion oder Terminierung?
- 3. Zweitmethode anwenden: Nutze genau das Extremal-Zwischenergebnis als Voraussetzung.
- 4. Kette schließen: Prüfe Übergang und Reichweite des Gesamtschlusses.
Geeignet
- du die Rolle jeder Methode als eigenen Beweisschritt benennen kannst
Reicht nicht
- Methoden nur nebeneinander genannt werden, ohne dass ein Zwischenergebnis den nächsten Schritt ermöglicht
Eine Extremal-Methodenkette auditieren
Jeder Übergang benennt Voraussetzung, Zwischenergebnis und die noch offene Teilaussage.
Warum funktioniert sie?
Jeder Übergang benennt Voraussetzung, Zwischenergebnis und die noch offene Teilaussage.
Erkennungssignale
- Eine Extremalwahl liefert Struktur, aber Existenz, Zählung oder Terminierung benötigt eine zweite Methode.
Vorgehen
- 1. Extremalrolle bestimmen: Wähle Objekt und leite seine lokale Struktur ab.
- 2. Offene Lücke benennen: Fehlen Kollision, Zählwert, Erhaltung, Reduktion oder Terminierung?
- 3. Zweitmethode anwenden: Nutze genau das Extremal-Zwischenergebnis als Voraussetzung.
- 4. Kette schließen: Prüfe Übergang und Reichweite des Gesamtschlusses.
Geeignet
- du die Rolle jeder Methode als eigenen Beweisschritt benennen kannst
Reicht nicht
- Methoden nur nebeneinander genannt werden, ohne dass ein Zwischenergebnis den nächsten Schritt ermöglicht
Eine Wettbewerbsaufgabe diagnostizieren
Übersetze Signalwörter und Zieltyp in eine kurze Liste sinnvoller Extremalobjekte.
Warum funktioniert sie?
Übersetze Signalwörter und Zieltyp in eine kurze Liste sinnvoller Extremalobjekte.
Erkennungssignale
- Eine unbekannte Aufgabe enthält mehrere denkbare größte, kleinste, längste oder maximal erweiterte Objekte.
- Die Lösung muss nicht nur gefunden, sondern unter Wettbewerbsbedingungen vollständig begründet werden.
Vorgehen
- 1. Aufgabe diagnostizieren: Markiere Kandidatenmenge, mögliche Ordnungsgrößen und die verlangte Zielaussage.
- 2. Extremalkandidaten testen: Prüfe, welche Wahl eine verbotene Verbesserung oder eine kleinere Instanz erzeugt.
- 3. Beweiskette schreiben: Begründe Existenz, lokale Folge, Zulässigkeit und strenge Verbesserung ausdrücklich.
- 4. Antwort auditieren: Lies vom Ziel rückwärts und kontrolliere Randfälle, Quantoren und den exakten Schluss.
Geeignet
- Kandidatenwahl, Extremalfolge und Schluss als getrennte Beweisschritte geprüft werden können
Reicht nicht
- eine Extremalwahl keine neue lokale Struktur oder keinen echten Reduktionsschritt liefert
Extremalkandidaten gezielt auswählen
Bewerte Kandidaten danach, ob ihre Extremalität genau die für das Ziel benötigte lokale Aussage erzwingt.
Warum funktioniert sie?
Bewerte Kandidaten danach, ob ihre Extremalität genau die für das Ziel benötigte lokale Aussage erzwingt.
Erkennungssignale
- Eine unbekannte Aufgabe enthält mehrere denkbare größte, kleinste, längste oder maximal erweiterte Objekte.
- Die Lösung muss nicht nur gefunden, sondern unter Wettbewerbsbedingungen vollständig begründet werden.
Vorgehen
- 1. Aufgabe diagnostizieren: Markiere Kandidatenmenge, mögliche Ordnungsgrößen und die verlangte Zielaussage.
- 2. Extremalkandidaten testen: Prüfe, welche Wahl eine verbotene Verbesserung oder eine kleinere Instanz erzeugt.
- 3. Beweiskette schreiben: Begründe Existenz, lokale Folge, Zulässigkeit und strenge Verbesserung ausdrücklich.
- 4. Antwort auditieren: Lies vom Ziel rückwärts und kontrolliere Randfälle, Quantoren und den exakten Schluss.
Geeignet
- Kandidatenwahl, Extremalfolge und Schluss als getrennte Beweisschritte geprüft werden können
Reicht nicht
- eine Extremalwahl keine neue lokale Struktur oder keinen echten Reduktionsschritt liefert
Schwache Extremalideen mit Gegenbeispielen prüfen
Ein kleines Gegenbeispiel zeigt schnell, ob ein Extrem fehlt, die falsche Ordnung gewählt wurde oder der behauptete Schluss zu stark ist.
Warum funktioniert sie?
Ein kleines Gegenbeispiel zeigt schnell, ob ein Extrem fehlt, die falsche Ordnung gewählt wurde oder der behauptete Schluss zu stark ist.
Erkennungssignale
- Eine unbekannte Aufgabe enthält mehrere denkbare größte, kleinste, längste oder maximal erweiterte Objekte.
- Die Lösung muss nicht nur gefunden, sondern unter Wettbewerbsbedingungen vollständig begründet werden.
Vorgehen
- 1. Aufgabe diagnostizieren: Markiere Kandidatenmenge, mögliche Ordnungsgrößen und die verlangte Zielaussage.
- 2. Extremalkandidaten testen: Prüfe, welche Wahl eine verbotene Verbesserung oder eine kleinere Instanz erzeugt.
- 3. Beweiskette schreiben: Begründe Existenz, lokale Folge, Zulässigkeit und strenge Verbesserung ausdrücklich.
- 4. Antwort auditieren: Lies vom Ziel rückwärts und kontrolliere Randfälle, Quantoren und den exakten Schluss.
Geeignet
- Kandidatenwahl, Extremalfolge und Schluss als getrennte Beweisschritte geprüft werden können
Reicht nicht
- eine Extremalwahl keine neue lokale Struktur oder keinen echten Reduktionsschritt liefert
Einen Extremalbeweis abgabereif schreiben
Baue die Lösung aus Wahl, Existenz, Extremalfolge, Verbesserung oder Reduktion und Antwortsatz auf.
Warum funktioniert sie?
Baue die Lösung aus Wahl, Existenz, Extremalfolge, Verbesserung oder Reduktion und Antwortsatz auf.
Erkennungssignale
- Eine unbekannte Aufgabe enthält mehrere denkbare größte, kleinste, längste oder maximal erweiterte Objekte.
- Die Lösung muss nicht nur gefunden, sondern unter Wettbewerbsbedingungen vollständig begründet werden.
Vorgehen
- 1. Aufgabe diagnostizieren: Markiere Kandidatenmenge, mögliche Ordnungsgrößen und die verlangte Zielaussage.
- 2. Extremalkandidaten testen: Prüfe, welche Wahl eine verbotene Verbesserung oder eine kleinere Instanz erzeugt.
- 3. Beweiskette schreiben: Begründe Existenz, lokale Folge, Zulässigkeit und strenge Verbesserung ausdrücklich.
- 4. Antwort auditieren: Lies vom Ziel rückwärts und kontrolliere Randfälle, Quantoren und den exakten Schluss.
Geeignet
- Kandidatenwahl, Extremalfolge und Schluss als getrennte Beweisschritte geprüft werden können
Reicht nicht
- eine Extremalwahl keine neue lokale Struktur oder keinen echten Reduktionsschritt liefert
Extremalaufgaben unter Zeitdruck bearbeiten
Sichere zuerst Aufgaben mit klarer Extremalfolge und reserviere Zeit für Zulässigkeits- und Randfallprüfungen.
Warum funktioniert sie?
Sichere zuerst Aufgaben mit klarer Extremalfolge und reserviere Zeit für Zulässigkeits- und Randfallprüfungen.
Erkennungssignale
- Eine unbekannte Aufgabe enthält mehrere denkbare größte, kleinste, längste oder maximal erweiterte Objekte.
- Die Lösung muss nicht nur gefunden, sondern unter Wettbewerbsbedingungen vollständig begründet werden.
Vorgehen
- 1. Aufgabe diagnostizieren: Markiere Kandidatenmenge, mögliche Ordnungsgrößen und die verlangte Zielaussage.
- 2. Extremalkandidaten testen: Prüfe, welche Wahl eine verbotene Verbesserung oder eine kleinere Instanz erzeugt.
- 3. Beweiskette schreiben: Begründe Existenz, lokale Folge, Zulässigkeit und strenge Verbesserung ausdrücklich.
- 4. Antwort auditieren: Lies vom Ziel rückwärts und kontrolliere Randfälle, Quantoren und den exakten Schluss.
Geeignet
- Kandidatenwahl, Extremalfolge und Schluss als getrennte Beweisschritte geprüft werden können
Reicht nicht
- eine Extremalwahl keine neue lokale Struktur oder keinen echten Reduktionsschritt liefert
Eine vollständige Lösung rückwärts auditieren
Prüfe vom Antwortsatz aus, ob jeder vorherige Schritt genau die nächste Voraussetzung liefert.
Warum funktioniert sie?
Prüfe vom Antwortsatz aus, ob jeder vorherige Schritt genau die nächste Voraussetzung liefert.
Erkennungssignale
- Eine unbekannte Aufgabe enthält mehrere denkbare größte, kleinste, längste oder maximal erweiterte Objekte.
- Die Lösung muss nicht nur gefunden, sondern unter Wettbewerbsbedingungen vollständig begründet werden.
Vorgehen
- 1. Aufgabe diagnostizieren: Markiere Kandidatenmenge, mögliche Ordnungsgrößen und die verlangte Zielaussage.
- 2. Extremalkandidaten testen: Prüfe, welche Wahl eine verbotene Verbesserung oder eine kleinere Instanz erzeugt.
- 3. Beweiskette schreiben: Begründe Existenz, lokale Folge, Zulässigkeit und strenge Verbesserung ausdrücklich.
- 4. Antwort auditieren: Lies vom Ziel rückwärts und kontrolliere Randfälle, Quantoren und den exakten Schluss.
Geeignet
- Kandidatenwahl, Extremalfolge und Schluss als getrennte Beweisschritte geprüft werden können
Reicht nicht
- eine Extremalwahl keine neue lokale Struktur oder keinen echten Reduktionsschritt liefert