uniolympiads English

Γεωμετρία και αρχή του ακραίου

Εσωτερικά γινόμενα για αποστάσεις και γωνίες, ορίζουσες Gram, εμβαδά με ορίζουσες και τύπο του κορδονιού, κυρτά σύνολα, Helly και διαχωρισμός, Pick, και η αρχή του ακραίου με συμπάγεια.

Τι πρέπει να ξέρεις απέξω

Εσωτερικό γινόμενο. Για x,y∈Rnx, y \in \R^n:

∣x−y∣2=∣x∣2+∣y∣2−2 x⋅y,cos⁡∠(x,y)=x⋅y∣x∣ ∣y∣.|x - y|^2 = |x|^2 + |y|^2 - 2\, x \cdot y, \qquad \cos \angle(x, y) = \frac{x \cdot y}{|x|\,|y|} .

Η γωνία ∠AOB\angle AOB είναι αμβλεία ακριβώς όταν (A−O)⋅(B−O)<0(A - O) \cdot (B - O) < 0, και ορθή ακριβώς όταν το γινόμενο είναι 00. Μια συνθήκη για αποστάσεις γίνεται έτσι συνθήκη για πρόσημα εσωτερικών γινομένων.

Ορίζουσες, εμβαδά, όγκοι. Το προσημασμένο εμβαδόν του τριγώνου με κορυφές a,b,c∈R2a, b, c \in \R^2 είναι

12det⁡(b1−a1c1−a1b2−a2c2−a2),\frac12 \det \begin{pmatrix} b_1 - a_1 & c_1 - a_1 \\ b_2 - a_2 & c_2 - a_2 \end{pmatrix},

θετικό όταν οι κορυφές είναι σε αντιωρολογιακή φορά και μηδέν ακριβώς όταν είναι συνευθειακές. Το nn-διάστατο simplex με κορυφές a0,…,ana_0, \dots, a_n έχει όγκο 1n!∣det⁡(a1−a0,…,an−a0)∣\frac{1}{n!} \left| \det(a_1 - a_0, \dots, a_n - a_0) \right|.

Τύπος του κορδονιού (shoelace). Για απλό πολύγωνο P1P2…PmP_1 P_2 \dots P_m με Pi=(xi,yi)P_i = (x_i, y_i) και δείκτες modulo mm:

area⁡=12∣∑i=1m(xiyi+1−xi+1yi)∣.\operatorname{area} = \frac12 \left| \sum_{i=1}^{m} (x_i y_{i+1} - x_{i+1} y_i) \right| .

Ορίζουσα Gram. Για v1,…,vk∈Rnv_1, \dots, v_k \in \R^n ο πίνακας G=(vi⋅vj)i,j=1kG = (v_i \cdot v_j)_{i,j=1}^{k} είναι θετικά ημιορισμένος, rank⁡G=dim⁡span⁡(v1,…,vk)≤n\operatorname{rank} G = \dim \operatorname{span}(v_1, \dots, v_k) \le n, και det⁡G\det G είναι το τετράγωνο του kk-διάστατου όγκου του παραλληλεπιπέδου που παράγουν τα viv_i.

Κυρτά σύνολα. Η κυρτή θήκη conv⁡S\operatorname{conv} S είναι το σύνολο των κυρτών συνδυασμών ∑λixi\sum \lambda_i x_i με xi∈Sx_i \in S, λi≥0\lambda_i \ge 0, ∑λi=1\sum \lambda_i = 1. Στο Rn\R^n αρκούν n+1n + 1 σημεία (Carathéodory)· στο επίπεδο, κάθε σημείο της θήκης ανήκει σε τρίγωνο με κορυφές από το SS.

Helly στο επίπεδο. Αν C1,…,Cm⊂R2C_1, \dots, C_m \subset \R^2 (m≥3m \ge 3) είναι κυρτά και κάθε τρία έχουν κοινό σημείο, τότε όλα έχουν κοινό σημείο. Για άπειρη οικογένεια χρειάζεται επιπλέον τα σύνολα να είναι συμπαγή.

Διαχωρισμός. Δύο ξένα, μη κενά, συμπαγή κυρτά σύνολα του Rn\R^n χωρίζονται γνησίως από υπερεπίπεδο.

Pick. Για απλό πολύγωνο με κορυφές στο Z2\Z^2, με II εσωτερικά και BB συνοριακά σημεία του πλέγματος:

area⁡=I+B2−1.\operatorname{area} = I + \frac{B}{2} - 1 .

Το ευθύγραμμο τμήμα από το p∈Z2p \in \Z^2 στο q∈Z2q \in \Z^2 περιέχει gcd⁡(∣q1−p1∣,∣q2−p2∣)+1\gcd(|q_1 - p_1|, |q_2 - p_2|) + 1 σημεία του πλέγματος (μαζί με τα άκρα).

Ισοπεριμετρική ανισότητα. Κλειστή καμπύλη μήκους LL που περικλείει εμβαδόν AA ικανοποιεί 4πA≤L24 \pi A \le L^2, με ισότητα μόνο για τον κύκλο. Ανάμεσα στα nn-γωνα με δοσμένη περίμετρο, το κανονικό έχει το μέγιστο εμβαδόν.

Αρχή του ακραίου. Σε πεπερασμένο (ή συμπαγές) σύνολο κάθε πραγματική ποσότητα (συνεχής, στη συμπαγή περίπτωση) παίρνει μέγιστο και ελάχιστο. Διάλεξε το αντικείμενο που κάνει μια καλά διαλεγμένη ποσότητα ακραία, υπόθεσε ότι ο ισχυρισμός αποτυγχάνει, και φτιάξε αντικείμενο ακόμα πιο ακραίο: άτοπο.

Τα βασικά λήμματα

Λήμμα 1 (τέσσερα σημεία). Για κάθε a,b,c,d∈Rna, b, c, d \in \R^n:

∣a−b∣2+∣b−c∣2+∣c−d∣2+∣d−a∣2−∣a−c∣2−∣b−d∣2=∣a−b+c−d∣2≥0,|a - b|^2 + |b - c|^2 + |c - d|^2 + |d - a|^2 - |a - c|^2 - |b - d|^2 = |a - b + c - d|^2 \ge 0 ,

με ισότητα ακριβώς όταν a+c=b+da + c = b + d, δηλαδή όταν το abcdabcd είναι (ίσως εκφυλισμένο) παραλληλόγραμμο.

Απόδειξη. Αναπτύσσουμε κάθε ∣x−y∣2|x - y|^2 όπως παραπάνω. Το αριστερό μέλος γίνεται ∣a∣2+∣b∣2+∣c∣2+∣d∣2−2(a⋅b+b⋅c+c⋅d+d⋅a)+2(a⋅c+b⋅d)|a|^2 + |b|^2 + |c|^2 + |d|^2 - 2(a \cdot b + b \cdot c + c \cdot d + d \cdot a) + 2(a \cdot c + b \cdot d), και το ίδιο ακριβώς δίνει το ανάπτυγμα του ∣a−b+c−d∣2|a - b + c - d|^2.

Λήμμα 2 (Gram). Έστω VV ο n×kn \times k πίνακας με στήλες τα v1,…,vkv_1, \dots, v_k, οπότε G=V⊤VG = V^\top V.

  • x⊤Gx=∣Vx∣2≥0x^\top G x = |V x|^2 \ge 0, άρα ο GG είναι θετικά ημιορισμένος, και Gx=0G x = 0 ακριβώς όταν Vx=0V x = 0. Άρα det⁡G=0\det G = 0 ακριβώς όταν τα viv_i είναι γραμμικά εξαρτημένα.
  • Αν είναι ανεξάρτητα, η Gram–Schmidt δίνει V=QRV = Q R, όπου ο QQ έχει ορθοκανονικές στήλες (Q⊤Q=IkQ^\top Q = I_k) και ο RR είναι k×kk \times k άνω τριγωνικός με rii>0r_{ii} > 0 την απόσταση του viv_i από το span⁡(v1,…,vi−1)\operatorname{span}(v_1, \dots, v_{i-1}). Τότε G=R⊤RG = R^\top R και det⁡G=∏irii2\det G = \prod_i r_{ii}^2. Το γινόμενο «βάση επί ύψος» επαναλαμβανόμενο είναι ακριβώς ο όγκος του παραλληλεπιπέδου.

Για k=2k = 2: το τρίγωνο abcabc στο Rn\R^n έχει εμβαδόν 12∣u∣2∣v∣2−(u⋅v)2\frac12 \sqrt{|u|^2 |v|^2 - (u \cdot v)^2} με u=b−au = b - a, v=c−av = c - a. Αντίστροφα, κάθε θετικά ημιορισμένος GG με rank⁡G≤n\operatorname{rank} G \le n είναι πίνακας Gram διανυσμάτων του Rn\R^n: από τη φασματική ανάλυση G=UDU⊤G = U D U^\top παίρνουμε G=W⊤WG = W^\top W με W=D1/2U⊤W = D^{1/2} U^\top, και ο WW έχει το πολύ nn μη μηδενικές γραμμές.

Λήμμα 3 (τύπος του κορδονιού). Από το θεώρημα του Green, το εμβαδόν ενός χωρίου με θετικά προσανατολισμένο σύνορο είναι ∮x dy\oint x\,dy. Στην πλευρά από το PiP_i στο Pi+1P_{i+1}, με x=xi+t(xi+1−xi)x = x_i + t(x_{i+1} - x_i) και dy=(yi+1−yi) dtdy = (y_{i+1} - y_i)\,dt, το ολοκλήρωμα είναι 12(xi+xi+1)(yi+1−yi)\frac12 (x_i + x_{i+1})(y_{i+1} - y_i). Αθροίζοντας, οι όροι xi+1yi+1−xiyix_{i+1} y_{i+1} - x_i y_i τηλεσκοπούνται κυκλικά σε 00 και μένει 12∑i(xiyi+1−xi+1yi)\frac12 \sum_i (x_i y_{i+1} - x_{i+1} y_i). Η απόλυτη τιμή καλύπτει την ωρολογιακή φορά.

Ανάγνωση με τρίγωνα: κάθε όρος 12(xiyi+1−xi+1yi)\frac12 (x_i y_{i+1} - x_{i+1} y_i) είναι, από τον τύπο της ορίζουσας με a=Oa = O, το προσημασμένο εμβαδόν του τριγώνου OPiPi+1O P_i P_{i+1}. Ο τύπος αθροίζει λοιπόν τα τρίγωνα από την αρχή προς κάθε πλευρά· όσα διατρέχονται ωρολογιακά μετρούν αρνητικά και αφαιρούν ακριβώς ό,τι περισσεύει έξω από το πολύγωνο.

Τα τρίγωνα OPiPi+1O P_i P_{i+1} με πρόσημο: τα αρνητικά ακυρώνουν το κομμάτι έξω από το πολύγωνο

Συνέπεια: κάθε πολύγωνο με κορυφές στο Z2\Z^2 έχει εμβαδόν στο 12Z\frac12 \Z.

Λήμμα 4 (Radon και Helly στο επίπεδο). Radon: τέσσερα σημεία x1,…,x4∈R2x_1, \dots, x_4 \in \R^2 χωρίζονται σε δύο ομάδες με τεμνόμενες κυρτές θήκες.

Απόδειξη. Τα τρία διανύσματα x2−x1,x3−x1,x4−x1x_2 - x_1, x_3 - x_1, x_4 - x_1 του R2\R^2 είναι εξαρτημένα, άρα υπάρχουν λ1,…,λ4\lambda_1, \dots, \lambda_4, όχι όλα μηδέν, με ∑λixi=0\sum \lambda_i x_i = 0 και ∑λi=0\sum \lambda_i = 0. Έστω P={i:λi>0}P = \{i : \lambda_i > 0\}, NN τα υπόλοιπα, και s=∑i∈Pλi=−∑i∈Nλi>0s = \sum_{i \in P} \lambda_i = -\sum_{i \in N} \lambda_i > 0. Το σημείο

p=∑i∈Pλisxi=∑i∈N−λisxip = \sum_{i \in P} \frac{\lambda_i}{s} x_i = \sum_{i \in N} \frac{-\lambda_i}{s} x_i

ανήκει και στις δύο θήκες.

Helly για m=4m = 4. Πάρε pi∈⋂j≠iCjp_i \in \bigcap_{j \ne i} C_j και χώρισε τα p1,…,p4p_1, \dots, p_4 κατά Radon σε PP, NN με κοινό σημείο pp. Για κάθε jj: αν j∉Pj \notin P, όλα τα pip_i με i∈Pi \in P ανήκουν στο CjC_j, οπότε p∈conv⁡{pi:i∈P}⊆Cjp \in \operatorname{conv}\{p_i : i \in P\} \subseteq C_j· αν j∈Pj \in P, τότε j∉Nj \notin N και με τον ίδιο τρόπο p∈Cjp \in C_j. Για m>4m > 4: αντικατάστησε τα Cm−1,CmC_{m-1}, C_m με το Cm−1∩CmC_{m-1} \cap C_m. Από την περίπτωση m=4m = 4 κάθε τρία από τα νέα m−1m - 1 σύνολα τέμνονται, και εφαρμόζεται επαγωγή.

Λήμμα 5 (διαχωρισμός μέσω πλησιέστερου ζεύγους). Έστω A,BA, B ξένα, μη κενά, συμπαγή κυρτά. Η (x,y)↦∣x−y∣(x, y) \mapsto |x - y| είναι συνεχής στο συμπαγές A×BA \times B, άρα παίρνει ελάχιστο σε κάποιο (a,b)(a, b), με a≠ba \ne b. Θέτουμε u=b−au = b - a. Αν για κάποιο x∈Ax \in A ήταν u⋅(x−a)>0u \cdot (x - a) > 0, τότε για at=a+t(x−a)∈Aa_t = a + t(x - a) \in A:

∣b−at∣2=∣u∣2−2t u⋅(x−a)+t2∣x−a∣2<∣u∣2|b - a_t|^2 = |u|^2 - 2t\, u \cdot (x - a) + t^2 |x - a|^2 < |u|^2

για μικρό t>0t > 0, άτοπο. Άρα u⋅x≤u⋅au \cdot x \le u \cdot a στο AA και, συμμετρικά, u⋅y≥u⋅bu \cdot y \ge u \cdot b στο BB. Αφού u⋅b−u⋅a=∣u∣2>0u \cdot b - u \cdot a = |u|^2 > 0, το υπερεπίπεδο u⋅z=u⋅a+b2u \cdot z = u \cdot \frac{a + b}{2} χωρίζει γνησίως.

Λήμμα 6 (Pick, σκιαγράφηση). Η ποσότητα I+B2−1I + \frac{B}{2} - 1 είναι προσθετική όταν κολλάμε δύο πολύγωνα του πλέγματος κατά μήκος κοινής πλευράς (τα σημεία της κοινής πλευράς γίνονται εσωτερικά, και το −1-1 διορθώνει τα δύο άκρα). Ο τύπος ισχύει για ορθογώνια με πλευρές στους άξονες (μέτρηση), άρα για τα ορθογώνια τρίγωνά τους, άρα για κάθε τρίγωνο (αφαιρώντας ορθογώνια τρίγωνα από ένα ορθογώνιο), άρα για κάθε απλό πολύγωνο (τριγωνοποίηση). Συνέπεια: ένα τρίγωνο του πλέγματος χωρίς άλλα σημεία του πλέγματος έχει εμβαδόν 12\frac12.

Δύο πολύγωνα του πλέγματος κολλάνε: η ποσότητα I+B/2−1I + B/2 - 1 προστίθεται όπως το εμβαδόν

Λήμμα 7 (το πιο απομακρυσμένο ζεύγος). Αν A,BA, B είναι δύο σημεία πεπερασμένου S⊂RnS \subset \R^n σε μέγιστη απόσταση, τότε όλο το SS βρίσκεται ανάμεσα στα δύο υπερεπίπεδα που περνούν από τα AA και BB κάθετα στο ABAB. Πράγματι, αν (X−B)⋅(B−A)>0(X - B) \cdot (B - A) > 0, τότε

∣X−A∣2=∣X−B∣2+∣B−A∣2+2(X−B)⋅(B−A)>∣B−A∣2.|X - A|^2 = |X - B|^2 + |B - A|^2 + 2 (X - B) \cdot (B - A) > |B - A|^2 .

Ειδικά τα A,BA, B είναι κορυφές της conv⁡S\operatorname{conv} S.

Λήμμα 8 (Sylvester–Gallai). Αν πεπερασμένο S⊂R2S \subset \R^2 δεν είναι όλο πάνω σε μια ευθεία, υπάρχει ευθεία που περιέχει ακριβώς δύο σημεία του SS.

Απόδειξη. Ανάμεσα στα ζεύγη (P,ℓ)(P, \ell) με ℓ\ell ευθεία από τουλάχιστον δύο σημεία του SS και P∈S∖ℓP \in S \setminus \ell (πεπερασμένα και τουλάχιστον ένα), διάλεξε αυτό με την ελάχιστη απόσταση ∣PQ∣>0|PQ| > 0, όπου QQ η προβολή του PP στην ℓ\ell. Αν η ℓ\ell είχε τρία σημεία του SS, δύο από αυτά, BB και CC, θα ήταν στην ίδια κλειστή ημιευθεία της ℓ\ell με αρχή το QQ, με ∣QB∣<∣QC∣|QB| < |QC|. Το BB είναι πάνω στο τμήμα QCQC, οπότε η απόστασή του από την ευθεία PCPC είναι το πολύ η απόσταση του QQ από αυτήν, δηλαδή ∣PQ∣ ∣QC∣∣PC∣<∣PQ∣\frac{|PQ|\,|QC|}{|PC|} < |PQ| (υποτείνουσα). Το ζεύγος (B,PC)(B, PC) είναι επιτρεπτό και έχει μικρότερη απόσταση: άτοπο.

Λήμμα 9 (μέγιστη διασπορά δίνει δίκτυο). Έστω K⊂RnK \subset \R^n φραγμένο και r>0r > 0. Ένα σύνολο σημείων του KK με ανά δύο αποστάσεις ≥r\ge r έχει φραγμένο πλήθος: οι μπάλες ακτίνας r/2r/2 γύρω τους είναι ξένες και βρίσκονται σε φραγμένο σύνολο. Πάρε ένα τέτοιο σύνολο με μέγιστο πλήθος. Τότε κάθε σημείο του KK απέχει λιγότερο από rr από κάποιο σημείο του συνόλου, αλλιώς θα το προσθέταμε.

Τυπικά κόλπα

  • Διάλεξε την αρχή των αξόνων. Στο κέντρο βάρους (∑xi=0\sum x_i = 0), σε μια κορυφή ή σε ένα δοσμένο εσωτερικό σημείο. Μετά κάθε συνθήκη για αποστάσεις ή γωνίες γίνεται συνθήκη για τα xi⋅xjx_i \cdot x_j.
  • Πέρασε σε πίνακα Gram. Όταν οι αποστάσεις ανά δύο είναι γνωστές, τα εσωτερικά γινόμενα των xi−x1x_i - x_1 καθορίζονται πλήρως. Η θετική ημιοριστότητα και το rank⁡G≤n\operatorname{rank} G \le n δίνουν φράγματα για το πλήθος των σημείων.
  • Ορίζουσα για συνευθειακότητα και φορά. Το πρόσημο του det⁡(b−a,c−a)\det(b - a, c - a) λέει από ποια πλευρά της abab είναι το cc· αλλάζει πρόσημο μόνο όταν το cc περάσει την ευθεία.
  • Γραμμικό συναρτησοειδές. Για πεπερασμένο SS και γενικό uu, το σημείο που μεγιστοποιεί το u⋅xu \cdot x είναι κορυφή της conv⁡S\operatorname{conv} S. Είναι η πιο γρήγορη αρχή του ακραίου.
  • Τομές. Εμβαδόν ή όγκος ως ολοκλήρωμα των μηκών ή εμβαδών των τομών (Cavalieri). Αν κάθε τομή είναι τουλάχιστον κάτι, ολοκληρώνεις το φράγμα.
  • Ισοτιμίες στο πλέγμα. Ανάμεσα σε πέντε σημεία του Z2\Z^2 δύο έχουν το ίδιο ζεύγος (x mod 2,y mod 2)(x \bmod 2, y \bmod 2), άρα το μέσο τους είναι σημείο του πλέγματος.
  • Μέσος όρος πάνω σε συμμετρική διάταξη. Αν μια ποσότητα έχει άθροισμα ≥2c\ge 2c πάνω σε δύο συμμετρικά σημεία, ένα από τα δύο δίνει ≥c\ge c.
  • Ύπαρξη πρώτα. Πριν πάρεις «το μέγιστο τρίγωνο» ή «το πλησιέστερο ζεύγος», δείξε ότι υπάρχει: πεπερασμένο σύνολο, ή συνεχής συνάρτηση σε συμπαγές (Weierstrass). Σε ανοιχτό δίσκο δεν υπάρχει εγγεγραμμένο τρίγωνο μέγιστου εμβαδού, αφού το supremum δεν πιάνεται.
  • Συμπάγεια για όρια διατάξεων. Μια ακολουθία από nn-άδες σημείων ενός συμπαγούς έχει συγκλίνουσα υπακολουθία (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: κυρτή θήκη τυχαίων σημείων. Το «pp δεν ανήκει στη θήκη» περιγράφεται με υπερεπίπεδο από το pp που αφήνει όλα τα σημεία από τη μία πλευρά.
  • IMC 2023, 2η μέρα, πρόβλημα 9: κυρτά υποσύνολα του κύβου με ξένες προβολές. Κυρτότητα και όγκοι.
  • IMC 2026, 2η μέρα, πρόβλημα 7: εμβαδόν ένωσης ευθύγραμμων τμημάτων. Οριζόντιες τομές για το κάτω φράγμα και μια ακραία διάταξη που το πιάνει.
  • IMC 2025, 2η μέρα, πρόβλημα 7: σύνολα ακεραίων κλειστά ως προς διπλασιασμό και μέσο όρο. Δεν είναι γεωμετρία, αλλά η λύση στηρίζεται στην αρχή του ακραίου: το μικρότερο στοιχείο, και το μεγαλύτερο στοιχείο κάτω από ένα δοσμένο.

Θέματα διαγωνισμών με αυτά τα εργαλεία

Δεν υπάρχουν ακόμα θέματα με αυτά τα εργαλεία.