Olympiad Maths Prep

Library / /12 of 14

Geometry Difficulty 8.2 Shortlist Prove it Romania

A set S={s1,,sk}S = \{s_1, \dots, s_k\} of positive real numbers is *polygonal* if k3k \ge 3 and there is a non-degenerate planar kk-gon whose side lengths are exactly s1,,sks_1, \dots, s_k; the set SS is *multipolygonal* if in every partition of SS into two subsets, each of which has at least three elements, exactly one of these two subsets is polygonal. Fix an integer n7n \ge 7.

a) Does there exist an nn-element multipolygonal set, removal of whose maximal element leaves a multipolygonal set?

Solution

Recall that a necessary and sufficient condition for k3k \ge 3 positive real numbers s1,,sks_1, \dots, s_k to be the side lengths of a non-degenerate planar kk-gon is that a maximal sis_i be less than the sum of the other sjs_j.

a) The answer is in the affirmative. Given pairwise distinct positive real numbers ε1,ε2,ε3\varepsilon_1, \varepsilon_2, \varepsilon_3 less than 1/21/2, we show that the sets S={1,2,4,,2n5,2n4+ε1,2n4+ε2,2n4+ε3,2n31/2}S = \{1, 2, 4, \dots, 2^{n-5}, 2^{n-4} + \varepsilon_1, 2^{n-4} + \varepsilon_2, 2^{n-4} + \varepsilon_3, 2^{n-3} - 1/2\} and S{2n31/2}S \setminus \{2^{n-3} - 1/2\} are both multipolygonal.

Split any of the two sets into two subsets each of which has at least three elements, let AA be the part containing at least two of the 2n4+εi2^{n-4} + \varepsilon_i, and let BB be the other part.
The set AA is polygonal since its maximal element is either one of the 2n4+εi2^{n-4} + \varepsilon_i or 2n31/22^{n-3} - 1/2, each of which is smaller than the sum of other elements in AA.
To prove that BB is not polygonal, notice that its maximal element is either 2n31/22^{n-3} - 1/2, or one of the 2n4+εi2^{n-4} + \varepsilon_i, or some 2k2^k, kn5k \le n-5. In the first case, the sum of all other elements in BB is less than 1+2++2n5+2n4+εi=2n31+εi<2n31/21+2+\dots+2^{n-5}+2^{n-4}+\varepsilon_i = 2^{n-3}-1+\varepsilon_i < 2^{n-3}-1/2; in the second case, this sum does not exceed 1+2++2n5=2n41<2n4+εi1+2+\dots+2^{n-5} = 2^{n-4}-1 < 2^{n-4}+\varepsilon_i; and in the third case, this sum is at most 1+2++2k1=2k1<2k1+2+\dots+2^{k-1} = 2^k - 1 < 2^k. Consequently, BB is not polygonal.

Looking for a route rather than 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.