Maths Olympiad Prep

Library / /18 of 18

Combinatorics Difficulty 8.9 Shortlist Prove it Romania

Let nn be a positive integer number. If SS is a finite set of vectors in the plane, let N(S)N(S) denote the number of two-element subsets {v,v}\{\mathbf{v}, \mathbf{v}'\} of SS such that
4(vv)+(v21)(v21)<0. 4 (\mathbf{v} \cdot \mathbf{v}') + (|\mathbf{v}|^2 - 1)(|\mathbf{v}'|^2 - 1) < 0.

Determine the maximum of N(S)N(S) when SS runs through all nn-element sets of vectors in the plane.

Solution

Without loss of generality, we may (and will) assume all vectors anchored at the origin. Assigning to each vector v=(x,y)\mathbf{v} = (x, y) in R2\mathbb{R}^2 the unit vector
u=(2xx2+y2+1,2yx2+y2+1,x2+y21x2+y2+1) \mathbf{u} = \left( \frac{2x}{x^2 + y^2 + 1}, \frac{2y}{x^2 + y^2 + 1}, \frac{x^2 + y^2 - 1}{x^2 + y^2 + 1} \right)
in R3\mathbb{R}^3 defines a bijection between all vectors in R2\mathbb{R}^2 and all unit vectors in R3\mathbb{R}^3 different from (0,0,1)(0, 0, 1); its inverse sends a unit vector u=(x,y,z)(0,0,1)\mathbf{u} = (x, y, z) \neq (0, 0, 1) to the vector v=(x/(1z),y/(1z))\mathbf{v} = (x/(1-z), y/(1-z)). Clearly, the condition
4(vv)+(v21)(v21)<0 4 (\mathbf{v} \cdot \mathbf{v}') + (|\mathbf{v}|^2 - 1)(|\mathbf{v}'|^2 - 1) < 0
for vectors in R2\mathbb{R}^2 is equivalent to uu<0\mathbf{u} \cdot \mathbf{u}' < 0 for the corresponding unit vectors in R3\mathbb{R}^3. Now let S={v1,v2,,vn}S = \{\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_n\}, let {u1,u2,,un}\{\mathbf{u}_1, \mathbf{u}_2, \dots, \mathbf{u}_n\} be the set of corresponding unit vectors in R3\mathbb{R}^3 and consider the graph GG on nn vertices labelled 1,2,,n1, 2, \dots, n, with an edge joining vertex ii to vertex jj if and only if uiuj<0\mathbf{u}_i \cdot \mathbf{u}_j < 0. Since the largest size of a set of vectors in R3\mathbb{R}^3 with negative mutual dot-products is 44, it follows that GG is K5K_5-free. Hence, by Turán's theorem, GG has at most the following number of edges
(1151)n22=3n2/8, \lfloor \left(1 - \frac{1}{5-1}\right) \cdot \frac{n^2}{2} \rfloor = \lfloor 3n^2/8 \rfloor,
the upper bound being achieved by Turán's extremal graph T(n,5)=Kn1,n2,n3,n4T(n, 5) = K_{n_1, n_2, n_3, n_4}, where n1+n2+n3+n4=nn_1 + n_2 + n_3 + n_4 = n and ninj1|n_i - n_j| \le 1. Geometrically, this can be achieved in R3\mathbb{R}^3 by considering four tight bundles of nin_i unit vectors each, around the vectors (1,0,0)(1, 0, 0), (1,2,0)(-1, 2, 0), (1,1,3)(-1, -1, 3) and (1,1,1)(-1, -1, -1), respectively. Consequently, the required maximum is 3n2/8\lfloor 3n^2/8 \rfloor.

Alternatively, notice that no five vertices of the complement Gˉ\bar{G} of GG are independent, so the independence number α(Gˉ)4\alpha(\bar{G}) \le 4, and apply the Caro-Wei theorem to get
4α(Gˉ)i=1n11+degin1+1ni=1ndegi=n2n+2E(Gˉ). 4 \ge \alpha(\bar{G}) \ge \sum_{i=1}^{n} \frac{1}{1 + \deg i} \ge \frac{n}{1 + \frac{1}{n} \sum_{i=1}^{n} \deg i} = \frac{n^2}{n + 2|E(\bar{G})|}.
Consequently, E(Gˉ)n(n4)/8|E(\bar{G})| \ge n(n-4)/8, so E(G)=n(n1)/2E(Gˉ)3n2/8|E(G)| = n(n-1)/2 - |E(\bar{G})| \le 3n^2/8.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.