uniolympiads Ελληνικά

Geometry and the extremal principle

Inner products for distances and angles, Gram determinants, areas via determinants and the shoelace formula, convex sets, Helly and separation, Pick, and the extremal principle with compactness.

What to know by heart

Inner product. For 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|} .

The angle ∠AOB\angle AOB is obtuse exactly when (A−O)⋅(B−O)<0(A - O) \cdot (B - O) < 0, and right exactly when the product is 00. So a condition on distances becomes a condition on the signs of inner products.

Determinants, areas, volumes. The signed area of the triangle with vertices a,b,c∈R2a, b, c \in \R^2 is

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},

positive when the vertices are in counterclockwise order and zero exactly when they are collinear. The nn-dimensional simplex with vertices a0,…,ana_0, \dots, a_n has volume 1n!∣det⁡(a1−a0,…,an−a0)∣\frac{1}{n!} \left| \det(a_1 - a_0, \dots, a_n - a_0) \right|.

Shoelace formula. For a simple polygon P1P2…PmP_1 P_2 \dots P_m with Pi=(xi,yi)P_i = (x_i, y_i) and indices 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 determinant. For v1,…,vk∈Rnv_1, \dots, v_k \in \R^n the matrix G=(vi⋅vj)i,j=1kG = (v_i \cdot v_j)_{i,j=1}^{k} is positive semidefinite, rank⁡G=dim⁡span⁡(v1,…,vk)≤n\operatorname{rank} G = \dim \operatorname{span}(v_1, \dots, v_k) \le n, and det⁡G\det G is the square of the kk-dimensional volume of the parallelepiped spanned by the viv_i.

Convex sets. The convex hull conv⁡S\operatorname{conv} S is the set of convex combinations ∑λixi\sum \lambda_i x_i with xi∈Sx_i \in S, λi≥0\lambda_i \ge 0, ∑λi=1\sum \lambda_i = 1. In Rn\R^n, n+1n + 1 points suffice (Carathéodory); in the plane, every point of the hull lies in a triangle with vertices from SS.

Helly in the plane. If C1,…,Cm⊂R2C_1, \dots, C_m \subset \R^2 (m≥3m \ge 3) are convex and every three of them have a common point, then all of them have a common point. For an infinite family the sets must moreover be compact.

Separation. Two disjoint, nonempty, compact convex subsets of Rn\R^n are strictly separated by a hyperplane.

Pick. For a simple polygon with vertices in Z2\Z^2, with II interior and BB boundary lattice points:

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

The segment from p∈Z2p \in \Z^2 to q∈Z2q \in \Z^2 contains gcd⁡(∣q1−p1∣,∣q2−p2∣)+1\gcd(|q_1 - p_1|, |q_2 - p_2|) + 1 lattice points (endpoints included).

Isoperimetric inequality. A closed curve of length LL enclosing area AA satisfies 4πA≤L24 \pi A \le L^2, with equality only for the circle. Among nn-gons with given perimeter, the regular one has the largest area.

Extremal principle. On a finite (or compact) set every real quantity (continuous, in the compact case) has a maximum and a minimum. Choose the object that makes a well-chosen quantity extremal, assume the claim fails, and build an even more extreme object: contradiction.

The standard lemmas

Lemma 1 (four points). For all 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 ,

with equality exactly when a+c=b+da + c = b + d, that is when abcdabcd is a (possibly degenerate) parallelogram.

Proof. Expand every ∣x−y∣2|x - y|^2 as above. The left-hand side becomes ∣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), and the expansion of ∣a−b+c−d∣2|a - b + c - d|^2 gives exactly the same.

Lemma 2 (Gram). Let VV be the n×kn \times k matrix with columns v1,…,vkv_1, \dots, v_k, so G=V⊤VG = V^\top V.

  • x⊤Gx=∣Vx∣2≥0x^\top G x = |V x|^2 \ge 0, so GG is positive semidefinite, and Gx=0G x = 0 exactly when Vx=0V x = 0. Hence det⁡G=0\det G = 0 exactly when the viv_i are linearly dependent.
  • If they are independent, Gram–Schmidt gives V=QRV = Q R, where QQ has orthonormal columns (Q⊤Q=IkQ^\top Q = I_k) and RR is k×kk \times k upper triangular with rii>0r_{ii} > 0 the distance of viv_i from span⁡(v1,…,vi−1)\operatorname{span}(v_1, \dots, v_{i-1}). Then G=R⊤RG = R^\top R and det⁡G=∏irii2\det G = \prod_i r_{ii}^2. The repeated product "base times height" is exactly the volume of the parallelepiped.

For k=2k = 2: the triangle abcabc in Rn\R^n has area 12∣u∣2∣v∣2−(u⋅v)2\frac12 \sqrt{|u|^2 |v|^2 - (u \cdot v)^2} with u=b−au = b - a, v=c−av = c - a. Conversely, every positive semidefinite GG with rank⁡G≤n\operatorname{rank} G \le n is the Gram matrix of vectors in Rn\R^n: from the spectral decomposition G=UDU⊤G = U D U^\top we get G=W⊤WG = W^\top W with W=D1/2U⊤W = D^{1/2} U^\top, and WW has at most nn nonzero rows.

Lemma 3 (shoelace formula). By Green's theorem, the area of a region with positively oriented boundary is ∮x dy\oint x\,dy. On the side from PiP_i to Pi+1P_{i+1}, with x=xi+t(xi+1−xi)x = x_i + t(x_{i+1} - x_i) and dy=(yi+1−yi) dtdy = (y_{i+1} - y_i)\,dt, the integral is 12(xi+xi+1)(yi+1−yi)\frac12 (x_i + x_{i+1})(y_{i+1} - y_i). Summing, the terms xi+1yi+1−xiyix_{i+1} y_{i+1} - x_i y_i telescope cyclically to 00 and what remains is 12∑i(xiyi+1−xi+1yi)\frac12 \sum_i (x_i y_{i+1} - x_{i+1} y_i). The absolute value covers the clockwise order.

Reading with triangles: by the determinant formula with a=Oa = O, each term 12(xiyi+1−xi+1yi)\frac12 (x_i y_{i+1} - x_{i+1} y_i) is the signed area of the triangle OPiPi+1O P_i P_{i+1}. So the formula adds up the triangles from the origin to each side; those traversed clockwise count negatively and remove exactly what lies outside the polygon.

The triangles OPiPi+1O P_i P_{i+1} with sign: the negative ones cancel the part outside the polygon

Consequence: every polygon with vertices in Z2\Z^2 has area in 12Z\frac12 \Z.

Lemma 4 (Radon and Helly in the plane). Radon: four points x1,…,x4∈R2x_1, \dots, x_4 \in \R^2 can be split into two groups with intersecting convex hulls.

Proof. The three vectors x2−x1,x3−x1,x4−x1x_2 - x_1, x_3 - x_1, x_4 - x_1 of R2\R^2 are dependent, so there are λ1,…,λ4\lambda_1, \dots, \lambda_4, not all zero, with ∑λixi=0\sum \lambda_i x_i = 0 and ∑λi=0\sum \lambda_i = 0. Let P={i:λi>0}P = \{i : \lambda_i > 0\}, NN the rest, and s=∑i∈Pλi=−∑i∈Nλi>0s = \sum_{i \in P} \lambda_i = -\sum_{i \in N} \lambda_i > 0. The point

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

lies in both hulls.

Helly for m=4m = 4. Take pi∈⋂j≠iCjp_i \in \bigcap_{j \ne i} C_j and split p1,…,p4p_1, \dots, p_4 by Radon into PP, NN with a common point pp. For each jj: if j∉Pj \notin P, all pip_i with i∈Pi \in P lie in CjC_j, so p∈conv⁡{pi:i∈P}⊆Cjp \in \operatorname{conv}\{p_i : i \in P\} \subseteq C_j; if j∈Pj \in P, then j∉Nj \notin N and in the same way p∈Cjp \in C_j. For m>4m > 4: replace Cm−1,CmC_{m-1}, C_m by Cm−1∩CmC_{m-1} \cap C_m. By the case m=4m = 4, every three of the new m−1m - 1 sets intersect, and induction applies.

Lemma 5 (separation via the closest pair). Let A,BA, B be disjoint, nonempty, compact convex sets. The map (x,y)↦∣x−y∣(x, y) \mapsto |x - y| is continuous on the compact set A×BA \times B, so it attains a minimum at some (a,b)(a, b), with a≠ba \ne b. Put u=b−au = b - a. If u⋅(x−a)>0u \cdot (x - a) > 0 for some x∈Ax \in A, then for 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

for small t>0t > 0, a contradiction. So u⋅x≤u⋅au \cdot x \le u \cdot a on AA and, symmetrically, u⋅y≥u⋅bu \cdot y \ge u \cdot b on BB. Since u⋅b−u⋅a=∣u∣2>0u \cdot b - u \cdot a = |u|^2 > 0, the hyperplane u⋅z=u⋅a+b2u \cdot z = u \cdot \frac{a + b}{2} separates strictly.

Lemma 6 (Pick, sketch). The quantity I+B2−1I + \frac{B}{2} - 1 is additive when two lattice polygons are glued along a common side (the points of the common side become interior, and the −1-1 corrects the two endpoints). The formula holds for rectangles with sides on the axes (counting), hence for their right triangles, hence for every triangle (subtracting right triangles from a rectangle), hence for every simple polygon (triangulation). Consequence: a lattice triangle with no other lattice points has area 12\frac12.

Two lattice polygons glued together: the quantity I+B/2−1I + B/2 - 1 adds up like area

Lemma 7 (the farthest pair). If A,BA, B are two points of a finite S⊂RnS \subset \R^n at maximal distance, then all of SS lies between the two hyperplanes through AA and BB perpendicular to ABAB. Indeed, if (X−B)⋅(B−A)>0(X - B) \cdot (B - A) > 0, then

∣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 .

In particular A,BA, B are vertices of conv⁡S\operatorname{conv} S.

Lemma 8 (Sylvester–Gallai). If a finite S⊂R2S \subset \R^2 does not lie on a single line, some line contains exactly two points of SS.

Proof. Among the pairs (P,ℓ)(P, \ell) with ℓ\ell a line through at least two points of SS and P∈S∖ℓP \in S \setminus \ell (finitely many, and at least one), choose the one with the smallest distance ∣PQ∣>0|PQ| > 0, where QQ is the projection of PP onto ℓ\ell. If ℓ\ell had three points of SS, two of them, BB and CC, would lie on the same closed half-line of ℓ\ell starting at QQ, with ∣QB∣<∣QC∣|QB| < |QC|. The point BB is on the segment QCQC, so its distance from the line PCPC is at most that of QQ, namely ∣PQ∣ ∣QC∣∣PC∣<∣PQ∣\frac{|PQ|\,|QC|}{|PC|} < |PQ| (hypotenuse). The pair (B,PC)(B, PC) is admissible and has a smaller distance: contradiction.

Lemma 9 (a maximal packing is a net). Let K⊂RnK \subset \R^n be bounded and r>0r > 0. A set of points of KK with pairwise distances ≥r\ge r has bounded size: the balls of radius r/2r/2 around them are disjoint and lie in a bounded set. Take such a set of maximal size. Then every point of KK is at distance less than rr from some point of the set, otherwise we could add it.

Typical tricks

  • Choose the origin. At the centroid (∑xi=0\sum x_i = 0), at a vertex or at a given interior point. Then every condition on distances or angles becomes a condition on the xi⋅xjx_i \cdot x_j.
  • Pass to a Gram matrix. When the pairwise distances are known, the inner products of the xi−x1x_i - x_1 are completely determined. Positive semidefiniteness and rank⁡G≤n\operatorname{rank} G \le n bound the number of points.
  • Determinant for collinearity and orientation. The sign of det⁡(b−a,c−a)\det(b - a, c - a) tells on which side of abab the point cc lies; it changes sign only when cc crosses the line.
  • A linear functional. For finite SS and generic uu, the point maximizing u⋅xu \cdot x is a vertex of conv⁡S\operatorname{conv} S. It is the quickest extremal principle.
  • Sections. Area or volume as the integral of the lengths or areas of the sections (Cavalieri). If every section is at least something, integrate the bound.
  • Parities on the lattice. Among five points of Z2\Z^2, two have the same pair (x mod 2,y mod 2)(x \bmod 2, y \bmod 2), so their midpoint is a lattice point.
  • Averaging over a symmetric configuration. If a quantity has sum ≥2c\ge 2c over two symmetric points, one of the two gives ≥c\ge c.
  • Existence first. Before taking "the largest triangle" or "the closest pair", show it exists: a finite set, or a continuous function on a compact set (Weierstrass). In an open disk there is no inscribed triangle of maximal area, since the supremum is not attained.
  • Compactness for limits of configurations. A sequence of nn-tuples of points of a compact set has a convergent subsequence (Bolzano–Weierstrass), so a minimizing sequence gives a minimizer when the quantity is continuous. Also: if every finite subfamily of a family of compact sets intersects, the whole family intersects, which is why Helly extends to infinite families of compact convex sets.
  • Pitfalls. Helly needs convexity and "every three", not "every two". Pick needs a simple polygon without holes and with lattice vertices. The signed area is not the area when the polygon self-intersects.

How they appear in the IMC

  • IMC 2001, day 2, problem 3: points on a sphere with large pairwise distances. The condition on distances becomes a condition on the sign of inner products.
  • IMC 2008, day 2, problem 6: equidistant points in a Hilbert space. Inner products and the choice of a suitable centre.
  • IMC 2015, day 1, problem 5: a point inside a simplex and obtuse angles. The point is written as a convex combination of the vertices and the angles become signs of inner products.
  • IMC 2004, day 2, problem 3: sums of distances in the unit disk. Existence of a point by choosing extremal or symmetric positions.
  • IMC 2009, day 2, problem 1: the volume of a set defined by a distance inequality. Coordinates and sections.
  • IMC 2024, day 1, problem 5: the convex hull of random points. "pp is not in the hull" is described by a hyperplane through pp that leaves all points on one side.
  • IMC 2023, day 2, problem 9: convex subsets of the cube with disjoint projections. Convexity and volumes.
  • IMC 2026, day 2, problem 7: the area of a union of line segments. Horizontal sections for the lower bound and an extremal configuration that attains it.
  • IMC 2025, day 2, problem 7: sets of integers closed under doubling and averaging. Not geometry, but the solution rests on the extremal principle: the smallest element, and the largest element below a given one.

Contest problems using these tools

No problems with these tools yet.