Maths Olympiad Prep

Library / /35 of 35

Geometry Difficulty 7.6 National olympiad, round 2 Prove it Belarus

Given two finite sets AA and BB of pairs of real numbers. For any three pairs (a1,b1)(a_1, b_1), (a2,b2)(a_2, b_2) and (a3,b3)(a_3, b_3) from AA there exists a pair (c,d)(c, d) from BB such that
a1c+b1d0,a2c+b2d0anda3c+b3d0. a_1c + b_1d \ge 0, \quad a_2c + b_2d \ge 0 \quad \text{and} \quad a_3c + b_3d \ge 0.
Prove that the BB contains a pair (γ,δ)(\gamma, \delta) such that αγ+βδ0\alpha\gamma + \beta\delta \ge 0 for each pair (α,β)(\alpha, \beta) from AA.

Solution

Consider each pair (a,b)(a, b) as the vector with the coordinates (a,b)(a, b) on the Cartesian plane. The inequality ac+bd0ac+bd \ge 0 is equivalent to the non-negativity of the scalar product, i.e. it states that the angle between the vectors is not greater than π/2\pi/2. Also note that the lengths of the vectors don't matter, so without loss of generality assume that all these vectors are unit and their endpoints lie on the unit circle. Then for each fixed vector (a,b)(a, b) of the first set the inequality ac+bd0ac+bd \ge 0 means that the endpoint of the vector (c,d)(c, d) of the second set lies on the semicircle with the midpoint at the end of the vector (a,b)(a, b).

Thereby we can formulate the statement of the problem in the following equivalent form: Given the finite set AA of semicircles and the finite set BB of points on the unit circle such that every three semicircles from AA have a common point from BB. Then all given semicircles from AA have a common point from BB.

Let's prove the latter statement. We will identify each point on the unit circle with the oriented angle between the vector (0,1)\overrightarrow{(0,1)} and the radius-vector of the point, in particular this angle belongs to [0,2π)[0, 2\pi). And fix the positive (anticlockwise) direction on the unit circle so that all semicircles from AA have unique starting point. Without loss of generality assume that one of the semicircles from AA starts at 00 and ends at π\pi. Consider the set of all semicircles from AA such that their starting point is greater than π\pi, and let [1,r1][\ell_1, r_1] be the semicircle in this set with the smallest r1r_1, 1>π>r1\ell_1 > \pi > r_1. Similarly consider the set of all semicircles from AA such that their starting point is less than π\pi, and let [2,r2][\ell_2, r_2] be the semicircle in this set with the biggest 2\ell_2, 2<π<r2\ell_2 < \pi < r_2. Since the semicircles [0,π][0, \pi], [1,r1][\ell_1, r_1] and [2,r2][\ell_2, r_2] have a common point from BB, there exists a given point vBv \in B such that r1v2r_1 \ge v \ge \ell_2. Clearly, vv satisfies the statement conditions.

For the completeness of the proof let's make a few clarifications. Firstly, without loss of generality we assumed all semicircles in AA to be pairwise distinct, as well as all points BB. Secondly, it could happen that it is impossible to find [1,r1][\ell_1, r_1] or [2,r2][\ell_2, r_2] since the corresponding set is empty. However, in these cases the assertion is obvious, since in them the desired point is π\pi or 00, respectively. Finally, we ignore the semicircle [π,0][\pi, 0]; if such semicircle is given then the point vv cannot exist since otherwise the given semicircles [π,0][\pi, 0], [1,r1][\ell_1, r_1] and [2,r2][\ell_2, r_2] don't have a common point from BB; therefore the existence of [π,0][\pi, 0] reduces to the previous case, and in this case it also contains a point common to all the others.

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.