Maths Olympiad Prep

Library / /144 of 144

Combinatorics Difficulty 9.1 IMO level Find the answer

Find the largest possible integer kk, such that the following statement is true:
Let 20092009 arbitrary non-degenerated triangles be given. In every triangle the three sides are coloured, such that one is blue, one is red and one is white. Now, for every colour separately, let us sort the lengths of the sides. We obtain
b1b2b2009the lengths of the blue sides r1r2r2009the lengths of the red sides and w1w2w2009the lengths of the white sides  \left. \begin{array}{rcl} & b_1 \leq b_2\leq\ldots\leq b_{2009} & \textrm{the lengths of the blue sides }\\ & r_1 \leq r_2\leq\ldots\leq r_{2009} & \textrm{the lengths of the red sides }\\ \textrm{and } & w_1 \leq w_2\leq\ldots\leq w_{2009} & \textrm{the lengths of the white sides }\\ \end{array}\right.
Then there exist kk indices jj such that we can form a non-degenerated triangle with side lengths bjb_j, rjr_j, wjw_j.

[i]

A number or a short expression. Spacing and $ signs are ignored.

Solution

To solve this problem, we need to find the largest possible integer k k such that for given sequences of side lengths b1b2b2009 b_1 \leq b_2 \leq \ldots \leq b_{2009} , r1r2r2009 r_1 \leq r_2 \leq \ldots \leq r_{2009} , and w1w2w2009 w_1 \leq w_2 \leq \ldots \leq w_{2009} , there are k k indices j j for which bj,rj,wj b_j, r_j, w_j can form a non-degenerated triangle.

A non-degenerated triangle requires that the sum of the lengths of any two sides is greater than the length of the remaining side. This is known as the triangle inequality, and we need:

bj+rj>wj,rj+wj>bj,wj+bj>rj. \begin{align*} b_j + r_j &> w_j, \\ r_j + w_j &> b_j, \\ w_j + b_j &> r_j. \end{align*}

Given that we sort each color's side lengths in non-decreasing order, the condition we must prove is that there exists at least one j j for which these inequalities hold true.

### Analysis

Consider a scenario where each set of lengths is from different triangles, the length bj,rj,wj b_j, r_j, w_j may or may not satisfy the triangle inequalities due to their independent selection. However, since they are sorted sequences, permutations of indices alone without verification with the original triangles cannot guarantee a valid triangle due to the sorting operation mixing lengths from distinct triangles.

### Approach

To ensure that at least one combination of (bj,rj,wj) (b_j, r_j, w_j) forms a valid triangle, let's consider the most restricted situation: the smallest non-trivial configuration is when k=1 k = 1 , meaning we can ensure that a valid triangle can be formed with at least one combination due to sheer number and randomness in initial selections. Among 2009 2009 triangles, even under the worst permutations, there will always be at least one j j due to pigeonhole principle or inherent randomness that keeps at least one triple in a potentially valid configuration for the triangle inequalities.

### Conclusion

Thus, the largest integer k k for which we can guarantee these side combinations form at least one valid non-degenerated triangle is:

1 \boxed{1}

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.