Γεωμετρία και αρχή του ακραίου
Εσωτερικά γινόμενα για αποστάσεις και γωνίες, ορίζουσες Gram, εμβαδά με ορίζουσες και τύπο του κορδονιού, κυρτά σύνολα, Helly και διαχωρισμός, Pick, και η αρχή του ακραίου με συμπάγεια.
Τι πρέπει να ξέρεις απέξω
Εσωτερικό γινόμενο. Για :
Η γωνία είναι αμβλεία ακριβώς όταν , και ορθή ακριβώς όταν το γινόμενο είναι . Μια συνθήκη για αποστάσεις γίνεται έτσι συνθήκη για πρόσημα εσωτερικών γινομένων.
Ορίζουσες, εμβαδά, όγκοι. Το προσημασμένο εμβαδόν του τριγώνου με κορυφές είναι
θετικό όταν οι κορυφές είναι σε αντιωρολογιακή φορά και μηδέν ακριβώς όταν είναι συνευθειακές. Το -διάστατο simplex με κορυφές έχει όγκο .
Τύπος του κορδονιού (shoelace). Για απλό πολύγωνο με και δείκτες modulo :
Ορίζουσα Gram. Για ο πίνακας είναι θετικά ημιορισμένος, , και είναι το τετράγωνο του -διάστατου όγκου του παραλληλεπιπέδου που παράγουν τα .
Κυρτά σύνολα. Η κυρτή θήκη είναι το σύνολο των κυρτών συνδυασμών με , , . Στο αρκούν σημεία (Carathéodory)· στο επίπεδο, κάθε σημείο της θήκης ανήκει σε τρίγωνο με κορυφές από το .
Helly στο επίπεδο. Αν () είναι κυρτά και κάθε τρία έχουν κοινό σημείο, τότε όλα έχουν κοινό σημείο. Για άπειρη οικογένεια χρειάζεται επιπλέον τα σύνολα να είναι συμπαγή.
Διαχωρισμός. Δύο ξένα, μη κενά, συμπαγή κυρτά σύνολα του χωρίζονται γνησίως από υπερεπίπεδο.
Pick. Για απλό πολύγωνο με κορυφές στο , με εσωτερικά και συνοριακά σημεία του πλέγματος:
Το ευθύγραμμο τμήμα από το στο περιέχει σημεία του πλέγματος (μαζί με τα άκρα).
Ισοπεριμετρική ανισότητα. Κλειστή καμπύλη μήκους που περικλείει εμβαδόν ικανοποιεί , με ισότητα μόνο για τον κύκλο. Ανάμεσα στα -γωνα με δοσμένη περίμετρο, το κανονικό έχει το μέγιστο εμβαδόν.
Αρχή του ακραίου. Σε πεπερασμένο (ή συμπαγές) σύνολο κάθε πραγματική ποσότητα (συνεχής, στη συμπαγή περίπτωση) παίρνει μέγιστο και ελάχιστο. Διάλεξε το αντικείμενο που κάνει μια καλά διαλεγμένη ποσότητα ακραία, υπόθεσε ότι ο ισχυρισμός αποτυγχάνει, και φτιάξε αντικείμενο ακόμα πιο ακραίο: άτοπο.
Τα βασικά λήμματα
Λήμμα 1 (τέσσερα σημεία). Για κάθε :
με ισότητα ακριβώς όταν , δηλαδή όταν το είναι (ίσως εκφυλισμένο) παραλληλόγραμμο.
Απόδειξη. Αναπτύσσουμε κάθε όπως παραπάνω. Το αριστερό μέλος γίνεται , και το ίδιο ακριβώς δίνει το ανάπτυγμα του .
Λήμμα 2 (Gram). Έστω ο πίνακας με στήλες τα , οπότε .
- , άρα ο είναι θετικά ημιορισμένος, και ακριβώς όταν . Άρα ακριβώς όταν τα είναι γραμμικά εξαρτημένα.
- Αν είναι ανεξάρτητα, η Gram–Schmidt δίνει , όπου ο έχει ορθοκανονικές στήλες () και ο είναι άνω τριγωνικός με την απόσταση του από το . Τότε και . Το γινόμενο «βάση επί ύψος» επαναλαμβανόμενο είναι ακριβώς ο όγκος του παραλληλεπιπέδου.
Για : το τρίγωνο στο έχει εμβαδόν με , . Αντίστροφα, κάθε θετικά ημιορισμένος με είναι πίνακας Gram διανυσμάτων του : από τη φασματική ανάλυση παίρνουμε με , και ο έχει το πολύ μη μηδενικές γραμμές.
Λήμμα 3 (τύπος του κορδονιού). Από το θεώρημα του Green, το εμβαδόν ενός χωρίου με θετικά προσανατολισμένο σύνορο είναι . Στην πλευρά από το στο , με και , το ολοκλήρωμα είναι . Αθροίζοντας, οι όροι τηλεσκοπούνται κυκλικά σε και μένει . Η απόλυτη τιμή καλύπτει την ωρολογιακή φορά.
Ανάγνωση με τρίγωνα: κάθε όρος είναι, από τον τύπο της ορίζουσας με , το προσημασμένο εμβαδόν του τριγώνου . Ο τύπος αθροίζει λοιπόν τα τρίγωνα από την αρχή προς κάθε πλευρά· όσα διατρέχονται ωρολογιακά μετρούν αρνητικά και αφαιρούν ακριβώς ό,τι περισσεύει έξω από το πολύγωνο.
Συνέπεια: κάθε πολύγωνο με κορυφές στο έχει εμβαδόν στο .
Λήμμα 4 (Radon και Helly στο επίπεδο). Radon: τέσσερα σημεία χωρίζονται σε δύο ομάδες με τεμνόμενες κυρτές θήκες.
Απόδειξη. Τα τρία διανύσματα του είναι εξαρτημένα, άρα υπάρχουν , όχι όλα μηδέν, με και . Έστω , τα υπόλοιπα, και . Το σημείο
ανήκει και στις δύο θήκες.
Helly για . Πάρε και χώρισε τα κατά Radon σε , με κοινό σημείο . Για κάθε : αν , όλα τα με ανήκουν στο , οπότε · αν , τότε και με τον ίδιο τρόπο . Για : αντικατάστησε τα με το . Από την περίπτωση κάθε τρία από τα νέα σύνολα τέμνονται, και εφαρμόζεται επαγωγή.
Λήμμα 5 (διαχωρισμός μέσω πλησιέστερου ζεύγους). Έστω ξένα, μη κενά, συμπαγή κυρτά. Η είναι συνεχής στο συμπαγές , άρα παίρνει ελάχιστο σε κάποιο , με . Θέτουμε . Αν για κάποιο ήταν , τότε για :
για μικρό , άτοπο. Άρα στο και, συμμετρικά, στο . Αφού , το υπερεπίπεδο χωρίζει γνησίως.
Λήμμα 6 (Pick, σκιαγράφηση). Η ποσότητα είναι προσθετική όταν κολλάμε δύο πολύγωνα του πλέγματος κατά μήκος κοινής πλευράς (τα σημεία της κοινής πλευράς γίνονται εσωτερικά, και το διορθώνει τα δύο άκρα). Ο τύπος ισχύει για ορθογώνια με πλευρές στους άξονες (μέτρηση), άρα για τα ορθογώνια τρίγωνά τους, άρα για κάθε τρίγωνο (αφαιρώντας ορθογώνια τρίγωνα από ένα ορθογώνιο), άρα για κάθε απλό πολύγωνο (τριγωνοποίηση). Συνέπεια: ένα τρίγωνο του πλέγματος χωρίς άλλα σημεία του πλέγματος έχει εμβαδόν .
Λήμμα 7 (το πιο απομακρυσμένο ζεύγος). Αν είναι δύο σημεία πεπερασμένου σε μέγιστη απόσταση, τότε όλο το βρίσκεται ανάμεσα στα δύο υπερεπίπεδα που περνούν από τα και κάθετα στο . Πράγματι, αν , τότε
Ειδικά τα είναι κορυφές της .
Λήμμα 8 (Sylvester–Gallai). Αν πεπερασμένο δεν είναι όλο πάνω σε μια ευθεία, υπάρχει ευθεία που περιέχει ακριβώς δύο σημεία του .
Απόδειξη. Ανάμεσα στα ζεύγη με ευθεία από τουλάχιστον δύο σημεία του και (πεπερασμένα και τουλάχιστον ένα), διάλεξε αυτό με την ελάχιστη απόσταση , όπου η προβολή του στην . Αν η είχε τρία σημεία του , δύο από αυτά, και , θα ήταν στην ίδια κλειστή ημιευθεία της με αρχή το , με . Το είναι πάνω στο τμήμα , οπότε η απόστασή του από την ευθεία είναι το πολύ η απόσταση του από αυτήν, δηλαδή (υποτείνουσα). Το ζεύγος είναι επιτρεπτό και έχει μικρότερη απόσταση: άτοπο.
Λήμμα 9 (μέγιστη διασπορά δίνει δίκτυο). Έστω φραγμένο και . Ένα σύνολο σημείων του με ανά δύο αποστάσεις έχει φραγμένο πλήθος: οι μπάλες ακτίνας γύρω τους είναι ξένες και βρίσκονται σε φραγμένο σύνολο. Πάρε ένα τέτοιο σύνολο με μέγιστο πλήθος. Τότε κάθε σημείο του απέχει λιγότερο από από κάποιο σημείο του συνόλου, αλλιώς θα το προσθέταμε.
Τυπικά κόλπα
- Διάλεξε την αρχή των αξόνων. Στο κέντρο βάρους (), σε μια κορυφή ή σε ένα δοσμένο εσωτερικό σημείο. Μετά κάθε συνθήκη για αποστάσεις ή γωνίες γίνεται συνθήκη για τα .
- Πέρασε σε πίνακα Gram. Όταν οι αποστάσεις ανά δύο είναι γνωστές, τα εσωτερικά γινόμενα των καθορίζονται πλήρως. Η θετική ημιοριστότητα και το δίνουν φράγματα για το πλήθος των σημείων.
- Ορίζουσα για συνευθειακότητα και φορά. Το πρόσημο του λέει από ποια πλευρά της είναι το · αλλάζει πρόσημο μόνο όταν το περάσει την ευθεία.
- Γραμμικό συναρτησοειδές. Για πεπερασμένο και γενικό , το σημείο που μεγιστοποιεί το είναι κορυφή της . Είναι η πιο γρήγορη αρχή του ακραίου.
- Τομές. Εμβαδόν ή όγκος ως ολοκλήρωμα των μηκών ή εμβαδών των τομών (Cavalieri). Αν κάθε τομή είναι τουλάχιστον κάτι, ολοκληρώνεις το φράγμα.
- Ισοτιμίες στο πλέγμα. Ανάμεσα σε πέντε σημεία του δύο έχουν το ίδιο ζεύγος , άρα το μέσο τους είναι σημείο του πλέγματος.
- Μέσος όρος πάνω σε συμμετρική διάταξη. Αν μια ποσότητα έχει άθροισμα πάνω σε δύο συμμετρικά σημεία, ένα από τα δύο δίνει .
- Ύπαρξη πρώτα. Πριν πάρεις «το μέγιστο τρίγωνο» ή «το πλησιέστερο ζεύγος», δείξε ότι υπάρχει: πεπερασμένο σύνολο, ή συνεχής συνάρτηση σε συμπαγές (Weierstrass). Σε ανοιχτό δίσκο δεν υπάρχει εγγεγραμμένο τρίγωνο μέγιστου εμβαδού, αφού το supremum δεν πιάνεται.
- Συμπάγεια για όρια διατάξεων. Μια ακολουθία από -άδες σημείων ενός συμπαγούς έχει συγκλίνουσα υπακολουθία (Bolzano–Weierstrass), οπότε μια ελαχιστοποιούσα ακολουθία δίνει ελαχιστοποιό όταν η ποσότητα είναι συνεχής. Και: αν σε οικογένεια συμπαγών συνόλων κάθε πεπερασμένη υποοικογένεια τέμνεται, τέμνεται όλη, γι' αυτό το Helly περνά σε άπειρες οικογένειες συμπαγών κυρτών.
- Παγίδες. Το Helly θέλει κυρτότητα και «κάθε τρία», όχι «κάθε δύο». Ο Pick θέλει απλό πολύγωνο χωρίς τρύπες με κορυφές στο πλέγμα. Το προσημασμένο εμβαδόν δεν είναι εμβαδόν όταν το πολύγωνο αυτοτέμνεται.
Πώς εμφανίζονται στο IMC
- IMC 2001, 2η μέρα, πρόβλημα 3: σημεία σε σφαίρα με μεγάλες ανά δύο αποστάσεις. Η συνθήκη για τις αποστάσεις γίνεται συνθήκη για το πρόσημο των εσωτερικών γινομένων.
- IMC 2008, 2η μέρα, πρόβλημα 6: ισαπέχοντα σημεία σε χώρο Hilbert. Εσωτερικά γινόμενα και επιλογή κατάλληλου κέντρου.
- IMC 2015, 1η μέρα, πρόβλημα 5: σημείο στο εσωτερικό ενός simplex και αμβλείες γωνίες. Το σημείο γράφεται ως κυρτός συνδυασμός των κορυφών και οι γωνίες γίνονται πρόσημα εσωτερικών γινομένων.
- IMC 2004, 2η μέρα, πρόβλημα 3: άθροισμα αποστάσεων μέσα στον μοναδιαίο δίσκο. Ύπαρξη σημείου με επιλογή ακραίων ή συμμετρικών θέσεων.
- IMC 2009, 2η μέρα, πρόβλημα 1: όγκος συνόλου που ορίζεται από ανισότητα αποστάσεων. Συντεταγμένες και τομές.
- IMC 2024, 1η μέρα, πρόβλημα 5: κυρτή θήκη τυχαίων σημείων. Το « δεν ανήκει στη θήκη» περιγράφεται με υπερεπίπεδο από το που αφήνει όλα τα σημεία από τη μία πλευρά.
- IMC 2023, 2η μέρα, πρόβλημα 9: κυρτά υποσύνολα του κύβου με ξένες προβολές. Κυρτότητα και όγκοι.
- IMC 2026, 2η μέρα, πρόβλημα 7: εμβαδόν ένωσης ευθύγραμμων τμημάτων. Οριζόντιες τομές για το κάτω φράγμα και μια ακραία διάταξη που το πιάνει.
- IMC 2025, 2η μέρα, πρόβλημα 7: σύνολα ακεραίων κλειστά ως προς διπλασιασμό και μέσο όρο. Δεν είναι γεωμετρία, αλλά η λύση στηρίζεται στην αρχή του ακραίου: το μικρότερο στοιχείο, και το μεγαλύτερο στοιχείο κάτω από ένα δοσμένο.
Θέματα διαγωνισμών με αυτά τα εργαλεία
Δεν υπάρχουν ακόμα θέματα με αυτά τα εργαλεία.