International Mathematics Competition
for University Students
2015

IMC2015: Day 1, Problem 5

5. Let $n\ge2$, let $A_1,A_2,\ldots,A_{n+1}$ be $n+1$ points in the $n$-dimensional Euclidean space, not lying on the same hyperplane, and let $B$ be a point strictly inside the convex hull of $A_1,A_2,\ldots,A_{n+1}$. Prove that $\angle A_iBA_j>90^\circ$ holds for at least $n$ pairs $(i,j)$ with $\displaystyle{1\le i<j\le n+1}$.

Proposed by Géza Kós, Eötvös University, Budapest

Solution. Let $\mathbf{v}_i=\overrightarrow{BA_i}$. The condition $\angle A_iBA_j>90^\circ$ is equivalent with $\mathbf{v}_i\cdot \mathbf{v}_j<0$. Since $B$ is an interior point of the simplex, there are some weights $w_1,\ldots,w_{n+1}>0$ with $\sum\limits_{i=1}^{n+1} w_i \mathbf{v}_i=\textbf0$.

Let us build a graph on the vertices $1,\ldots,n+1$. Let the vertices $i$ and $j$ be connected by an edge if $\mathbf{v}_i\cdot \mathbf{v}_j<0$. We show that this graph is connected. Since every connected graph on $n+1$ vertices has at least $n$ edges, this will prove the problem statement. Suppose the contrary that the graph is not connected; then the vertices can be split in two disjoint nonempty sets, say $V$ and $W$ such that $V\cup W=\{1,2,\ldots,n+1\}$. Since there is no edge between the two vertex sets, we have $\mathbf{v}_i\cdot \mathbf{v}_j\ge0$ for all $i\in V$ and $j\in W$.

Consider $$ 0 = \left(\sum_{i\in V\cup W} w_i \mathbf{v}_i \right)^2 = \left(\sum_{i\in V} w_i \mathbf{v}_i \right)^2 + \left(\sum_{i\in W} w_i \mathbf{v}_i \right)^2 + 2\sum_{i\in V}\sum_{i\in W} w_iw_j(\mathbf{v}_i\cdot \mathbf{v}_j). $$ Notice that all terms are nonnegative on the right-hand side. Moreover, $\sum\limits_{i\in V} w_i \mathbf{v}_i\ne\textbf0$ and $\sum\limits_{i\in W} w_i \mathbf{v}_i\ne\textbf0$, so there are at least two strictly nonzero terms, contradiction.

Remark 1. The number $n$ in the statement is sharp; if $\mathbf{v}_{n+1}=(1,1,\ldots,1)$ and $v_i=(\underbrace{0,\ldots,0}_{i-1},-1,\underbrace{0,\ldots,0}_{n-i})$ for $i=1,\ldots,n$ then $\mathbf{v}_i\cdot \mathbf{v}_j<0$ holds only when $i=n+1$ or $j=n+1$.

Remark 2. The origin of the problem is here.