Given two finite collections of pairs of real numbers It turned out that for any three pairs $(a_1, b_1)$, $(a_2, b_2)$ and $(a_3, b_3)$ from the first collection there is a pair $(c, d)$ from the second collection, such that the following three inequalities hold: \[ a_1c + b_1d \geq 0,a_2c + b_2c \geq 0 \text{ and } a_3c + b_3d \geq 0 \]Prove that there is a pair $(\gamma, \delta)$ in the second collection, such that for any pair $(\alpha, \beta)$ from the first collection inequality $\alpha \gamma + \beta \delta \geq 0$ holds.
Problem
Source: Belarus - Iran Competition 2022
Tags: algebra, combinatorics
18.09.2024 17:01
Define the open half-planes \(H_i = \{(x, y)\ |\ a_ix + b_iy > 0\}\subset \mathbb R^2\) for all \(i\in I\) where \(I\) is the index set of the first collection of real pairs. Then \(H_i\) are convex and by Helly the intersection \(A = \displaystyle \bigcap_{i\in I} H_i\) is a nonempty open angle. Let \(S\) be the second collection of real pairs. We are left to show that \(A\cap S\ne \varnothing\). Consider the case when \(I\) is finite. Then there are distinct \(i, j\in I\) such that the border lines of \(A\) are perpendicular to \((a_i, b_i)\) and \((a_j, b_j)\) and \(A\subset H_i\cap H_j\). Take any \(k\in I\setminus\{i, j\}\). Then by the condition there exists a point \((\gamma, \delta)\in S\) such that \((\gamma, \delta)\in H_i\cap H_j\cap H_k\). But then \((\gamma, \delta) \in A\) so we are done. For the case when \(I\) is not finite we just assume WLOG that all \((a_i, b_i)\) lie on the unit circle and add a small limiting argument in the second sentence of the last paragraph.
18.09.2024 21:00
kiyoras_2001 wrote: Then \(H_i\) are convex and by Helly the intersection \(A = \displaystyle \bigcap_{i\in I} H_i\) is a nonempty open angle. How do you use Helly here? The inequalities in the problem statement are not strict, so you do not have a guarantee that a point that satisfies the condition for indices $i,j,k$ lies in $H_i\cap H_j\cap H_k$. Imagine two open half-planes face in opposite directions. Then a point on their common border can satisfy the conditions, however these half-planes do not intersect at all! kiyoras_2001 wrote: \(A\subset H_i\cap H_j\) I believe your idea is $A = H_i\cap H_j$ kiyoras_2001 wrote: \((\gamma, \delta)\in H_i\cap H_j\cap H_k\) Same thing as in the first paragraph kiyoras_2001 wrote: For the case when \(I\) is not finite That is my fault. The original problem statement says collections are finite. I edited the post