Let $n$ be a positive integer number. If $S$ is a finite set of vectors in the plane, let $N(S)$ denote the number of two-element subsets $\{\mathbf{v}, \mathbf{v'}\}$ of $S$ such that \[4\,(\mathbf{v} \cdot \mathbf{v'}) + (|\mathbf{v}|^2 - 1)(|\mathbf{v'}|^2 - 1) < 0. \] Determine the maximum of $N(S)$ when $S$ runs through all $n$-element sets of vectors in the plane. ***
Problem
Source: Romania TST 6 2010, Problem 3
Tags: inequalities, vector, algebra proposed, algebra
22.06.2016 12:39
Sorry to dig out such an old topic. But this is very interesting,I am wondering if someone can add a solution?
24.06.2016 04:17
Let $k$ be the largest number such that there exist $k$ vectors in the plane in which every pair $v, v'$ satisfies the desired inequality. Then by Erdos-Turan we have $N(S) \leq f(k, n)$, which is the maximum number of edges in a complete $k$-partite graph on $n$ vertices (since the adjacency graph does not contain $K_{k+1}$). On the other hand, $f(k, n)$ is achievable by choosing appropriate copies of the $k$ vectors. Thus it remains to find $k$. We will show $k = 4$. In fact, $k = 4$ works because $v_1 = (1+\epsilon, 0), v_2 = (0, 1-\epsilon), v_3 = (-1-\epsilon, 0), v_4 = (0, -1 + \epsilon)$ do satisfy the desired condition. On the other hand, suppose for contradiction that we are given 5 vectors in which every pair satisfies the inequality. First, there must be at most 3 vectors with length $\geq 1$. Otherwise among the four vectors with length $\geq 1$ we can find a pair $v, v'$ whose angles differ by at most $90^{\circ}$. For this pair we have $v \cdot v'$ and $(|v|^2-1)(|v'|^2-1)$ are both non-negative, contradicting the inequality! In a similar way there must be at most 3 vectors with length $\leq 1$. Since we have a total of five vectors, we have exactly 3 vectors of length $\geq 1$ and 2 vectors of length $\leq 1$ or vice versa. Our argument below applies to either case equally well, so we will assume the former scenario. Let us state a crucial lemma that facilitates future analysis: Lemma. Suppose $u_1, v_1, v_2, u_2$ are four vectors in clockwise position such that $|u_i| \geq 1 \geq |v_i|$. Suppose further that the desired inequality holds for every pair of these vectors. Let $\alpha, \beta, \gamma$ be the angles between $u_1$ and $v_1$, between $v_1$ and $v_2$ and between $v_2$ and $u_2$ respectively. Then either $\alpha + \beta > 180^{\circ}$ or $\beta + \gamma > 180^{\circ}$, but not both. Proof. Let $l_1, s_1, s_2, l_2$ denote the length of $u_1, v_1, v_2, u_2$. Applying the condition to $u_1, v_1$, we have $(l_1^2 - 1)(1-s_1^2) > 4l_1s_1 \cos \alpha$. Similarly we have $(l_2^2-1)(1-s_2^2) > 4l_2s_2 \cos \gamma$. Now apply the condition to $v_1, v_2$, we have $(1-s_1^2)(1-s_2^2) < -4s_1s_2 \cos \beta$. The condition applied to $u_1, u_2$ gives $(l_1^2-1)(l_2^2-1) < -4l_1l_2 \cos (\alpha + \beta + \gamma)$. We can multiply the first two inequalities here and compare it to the product of the last two inequalities. This way all factors of the form $1-x^2$ drop out, and we obtain $$ \cos \alpha \cdot \cos \gamma < \cos \beta \cdot \cos(\alpha + \beta + \gamma).$$Basic trigonometric manipulation gives $\cos(\alpha-\gamma) < \cos (\alpha + 2\beta + \gamma)$, which in turn yields $\sin(\alpha + \beta) \cdot \sin(\beta + \gamma) < 0$, hence the result. Back to the original problem. We have three vectors $u_1, u_2, u_3$ (in clockwise position) that have length $\geq 1$ and two vectors $v_1, v_2$ that have length $\leq 1$. By condition, the angles between $u_i$ and $u_j$ are greater than $90^{\circ}$. Thus the clockwise angle from $u_i$ to $u_{i+1}$ is less than $180^{\circ}$. Thus by lemma, $v_1$ and $v_2$ cannot both lie between $u_i$ and $u_{i+1}$. Thus without loss we can assume $v_1$ lies between $u_2$ and $u_3$, while $v_2$ lies between $u_3$ and $u_1$. By lemma, either the clockwise angle from $u_2$ to $v_2$ or the clockwise angle from $v_1$ to $u_1$ is less than $180^{\circ}$. Without loss assume the latter, then we have four vectors $v_1, u_3, v_2, u_1$ in clockwise position and also contained in a half-plane. This situation can be ruled out following the proof of the lemma -- specifically let $\alpha, \beta, \gamma$ be the clockwise angles, then the condition implies $\cos \alpha \cdot \cos \gamma < \cos (\alpha + \beta) \cdot \cos (\beta + \gamma)$, $\Leftrightarrow$ $\cos(\alpha + \gamma) < \cos (\alpha + 2\beta + \gamma)$, $\Leftrightarrow$ $\sin\beta \cdot \sin(\alpha + \beta + \gamma) < 0$. This contradicts our observation that $\alpha + \beta + \gamma < 180^\circ$. The proof is complete.