Maths Olympiad Prep

Library / /218 of 520

Combinatorics Difficulty 6.3 National olympiad Prove it

Prove that for every positive integer nn, the set {2,3,4,,3n+1}\{2,3,4, \ldots, 3 n+1\} can be partitioned into nn triples in such a way that the numbers from each triple are the lengths of the sides of some obtuse triangle.

Solution

Throughout the solution, we denote by [a,b][a, b] the set {a,a+1,,b}\{a, a+1, \ldots, b\}. We say that {a,b,c}\{a, b, c\} is an obtuse triple if a,b,ca, b, c are the sides of some obtuse triangle. We prove by induction on nn that there exists a partition of [2,3n+1][2,3n+1] into nn obtuse triples AiA_i (2in+1)(2 \leq i \leq n+1) having the form Ai={i,ai,bi}A_i=\{i, a_i, b_i\}. For the base case n=1n=1, one can simply set A2={2,3,4}A_2=\{2,3,4\}. For the induction step, we need the following simple lemma.

Lemma. Suppose that the numbers a(cb)(c+b)>a2a(c-b)(c+b)>a^2.

Now we turn to the induction step. Let n>1n>1 and put t=n/2n29n2(n+1)2i2t=\lfloor n / 2\rfloor \cdot \frac{n}{2} \cdot \frac{9n}{2} \geq (n+1)^2 \geq i^2, so this triangle is obtuse. The proof is completed.

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