Let $\ell>\delta$ be any two positive reals. Take $b_i=r_i=\ell+(i-1)\delta$, $w_i=2\ell+2(i-1)\delta$ for $i=1,2,\dots,2008$, and $b_{2009}=w_{2009}=2\ell+4016\delta$, $r_{2009}=\ell+2008\delta$. Note that we may construct triangles with sides $b_i,r_{i+1},w_i$ for $i=1,2,\dots,2008$, and a triangle with sides $b_{2009},r_1,w_{2009}$, thus the proposed values indeed satisfy the condition of the problem; indeed, $b_{2009}=w_{2009}>r_1>0$, yielding an isosceles triangle, while $b_i+r_{i+1}-w_i=\delta$ with $w_i-r_{i+1}=\ell+(i-2)\delta>0$ and $w_i-b_i=\ell+(i-1)\delta>0$, or $w_i$ is the largest of the three sides, but smaller than the sum of the other two $b_i+r_{i+1}$, for $i=1,2,\dots,2008$. Note also that $w_i=b_i+r_i$ for all $i=1,2,\dots,2008$, hence at most one non-degenerate triangle with sides $b_i,r_i,w_i$ may be obtained in this case. Note finally that at least one non-degenerate triangle will always exist with sides $b_{2009},r_{2009},w_{2009}$, because $b_{2009}$ is a side of a certain triangle with other two sides $r_j$ and $w_k$, and $b_{2009}<r_j+w_k\leq r_{2009}+w_{2009}$, and similarly for $r_{2009}$ and $w_{2009}$.

In my opinion, this problem is terrible. If the problem said to prove k=1, it would be trivial. However, requiring the one solving the problem to find k just makes it a luck-based "guess-and-check" problem. According to a grader at MOP, half of black did not get this problem, while quite a few in red and green did, which is a pretty bad sign.

As an author of the problem let me defend it . I certainly dont think that it is luck based. Intuition tells you that the conditions are not very bounding. I also think that this problem distunguishes the people who just learn stuff from the people who are truly insightful and full of inspiration. And that is exactly the kind of thing you want to do at IMO.

Kenny_cz wrote: As an author of the problem let me defend it . I certainly dont think that it is luck based. Intuition tells you that the conditions are not very bounding. I also think that this problem distunguishes the people who just learn stuff from the people who are truly insightful and full of inspiration. And that is exactly the kind of thing you want to do at IMO. Although I do not think this problem is "wonderful", I mostly agree with Kenny, and think that although other problems may be better problems 1 at IMO, this is a perfectly legitimate candidate. Good job Kenny!

Can we take all triangles as equilateral traiangles then we get that $k=2009$?

arberiii wrote: Can we take all triangles as equilateral traiangles then we get that $k=2009$? No, because it has to hold for any set of 2009 triangles.

Hmm, just one solution till now. The problem was a bit confusing at first but actually not as difficult as expected and quite fun. We'll prove $k=1$. Call a triple $(a,b,c)$ good, if we can form a non-degenerated triangle with side lengths $a,b,c$. We'll show that $(b_{2009},r_{2009},w_{2009})$ is good. As $b_{2009}, r_{2009}$ and $w_{2009}$ are side lengths in some triangle, let $(b_{2009},r_b,w_b), (b_r,r_{2009},w_r)$ and $(b_w,r_w,w_{2009})$ be those triangles. Then we'll easily get \begin{align*} b_{2009}+r_{2009} &\geq b_w,r_w > w_{2009}, \\ r_{2009}+w_{2009} &\geq r_b+w_b > b_{2009}, \\ w_{2009}+b_{2009} &\geq w_r+b_r > r_{2009}. \end{align*}Thus, $(b_{2009},r_{2009},w_{2009})$ is good, indeed. Now, it suffices to construct $2009$ triangles, such that $(b_i,r_i,w_i)$ isn't good for all $1 \leq i \leq 2008$. Let the triangles have side lengths \[ (b_1,r_1,w_2), (b_2,r_2,w_3), \dots, (b_{2008},r_{2008},w_{2009}), (b_{2009},r_{2009},w_1). \]Take $b_1=b_2=\dots=b_{2008}=1$ and $b_{2009}=2009$. Then $r_1=\tfrac32, r_n=n+1$ for $2 \leq n \leq 2008$ and $r_{2009}=2009$. Also at last $w_1=\tfrac25$ and $w_n=n$ for $2 \leq n \leq 2009$. It is easy to see that $(b_1,r_1,w_1)= \left(1,\tfrac32,2 \right)$ is good. It is also easy to see that $(b_i,r_i,w_{i+1})=(1,i+1,i+1)$ for $2 \leq i \leq 2008$ is good. And of course the triple $(b_{2009},r_{2009},w_{2009})= \left(2009,2009, \tfrac25 \right)$ is good. But \[ b_1+w_1 = 1+\tfrac25 < \tfrac32 = r_1, \]so $(b_1,r_1,w_1)$ is not good. Also \[ b_i+w_i=1+i=r_i \]for $2 \leq i \leq 2008$, so $(b_i,r_i,w_i)$ is not good either. Therefore, $k=1$, as claimed.

Obviously $w_{2009},b_{2009},r_{2009}$ must form a non-degenerated triangle. If not, suppose $w_{2009}>=b_{2009}+r_{2009}$, then $w_{2009}>=b_{2009}+r_{2009}>=r_i+b_j>w_{2009}$(Let $r_i,b_j,w_{2009}$ be one of the 2009 given triangles) which is a contradiction. We can show that k is exactly 1 with the construction: Triangle's 1 through 2008 have side lengths $x+2,x+4,2x+5$ triangle 2009 has side lengths $6000,4,6000$ where the first number is blue, second is red, third is white. Thus the triple $(b_k,r_k,w_k)=(k+2,k+3,2k+5)$ is degenerate for $k<2009$. b:3,4,5,...,2010,6000 r:4,5,6,7,...,2012 w:7,9,11,...,4021,6000

Solution from Twitch Solves ISL: The answer is $k=1$. To see at least one triangle must be formed, simply note that the longest sides $b_{2009}$, $r_{2009}$, $w_{2009}$ of each color necessarily form a triangle; for if $w_{2009} > b_{2009} + r_{2009}$ (say) then no triangle can have side $w_{2009}$. Conversely, we give a construction where only $j=2009$ works: \[ \begin{array}{rrrr r rr} \triangle_1 \hspace*{2ex} & \triangle_2 \hspace*{2ex} & \triangle_3 \hspace*{2ex} & \triangle_4 \hspace*{2ex} & \dots & \triangle_{2008} \hspace*{2ex} & \triangle_{2009} \hspace*{2ex} \\ \hline b_1 = 10000 & b_2 = 10001 & b_3 = 10002 & b_4 = 10003 & \dots & b_{2008} = 12007 & b_{2009} = 12008 \\ w_{2009} = 14200 & w_1 = 10000 & w_2 = 10001 & w_3 = 10002 & \dots & w_{2007} = 12006 & w_{2008} = 12007 \\ r_{2009} = 24199 & r_1 = 20000 & r_2 = 20002 & r_3 = 20004 & \dots & r_{2007} = 24012 & r_{2008} = 24014 \end{array} \]This counterexample shows $k=1$ is the largest integer for which the statement is true.

How about the following construction: \[ \begin{array}{rrrr r rr} 1 \hspace*{2ex} & 2 \hspace*{2ex} & 3 \hspace*{2ex} & 4 \hspace*{2ex} & \dots & 2008 \hspace*{2ex} & 2009 \hspace*{2ex} \\ \hline b_1 = 1 & b_2 = 2 & b_3 = 3 & b_4 = 4 & \dots & b_{2008} = 2008 & b_{2009} = 2009 \\ r_1 = 1 & r_2 = 2 & r_3 = 3 & r_4 = 4 & \dots & r_{2008} = 2008 & r_{2009} = 4017.5 \\ w_1 = 2 & w_2 = 4 & w_3 = 6 & w_4 = 8 & \dots & w_{2008} = 4016 & w_{2009} = 4018 \end{array} \] We have triangles $(b_2,r_1,w_1), (b_3,r_2,w_2), (b_4,r_3,w_3) \dots (b_{2009},r_{2008},w_{2008}), (b_1,r_{2009},w_{2009})$

We claim that the maximal value of $k$ is $1$. Let $(a,b,c)$ be a triangle with sides $a,b,c$ and with $a,b,c$ being red, blue, and white, respectively. Then the triples $(10(1+i(i+1)), 10(i^2+1)+1, 10i),1\le i\le 2008$ and $(10,10^{100},10^{100})$ produce $k=1$. Now we prove that $k=0$ is impossible. WLOG let $r_{2009}\ge w_{2009},b_{2009}$. We claim that $r_{2009},w_{2009},b_{2009}$ are the side lengths of a nondegenerate triangle. Suppose $r_{2009}$ is in a triangle with $w_m,s_n$. Then $r_{2009}< w_m+s_n\le w_{2009}+b_{2009}$, proving the claim.

dame dame

We claim the answer is... what the heck? It's $1$? ok IMO PSC, very cool. This following construction works for $6$ and readily generalizes. We have triangles $(19999, 10000, 10000)$ all the way up to $(20003, 10002, 10002)$ (to generalize to $2009$, just put more padding diagonals in between). Then, the other triangles are $(5001, 25000, 30000)$, $(1001, 49000, 50000)$, $(5002, 50000, 55000)$, and we arrange them as such: \begin{align*} &5001, 5002, 10000, 10001, 10002, 49000& \\ &1001, 10000, 10001, 10002, 30000, 50000& \\ &19999, 20001, 20003, 25000, 50000, 55000.& \end{align*} Assume WLOG that the biggest out of $w_{2009}, r_{2009}, b_{2009}$ is $w_{2009}$. Then, since everything's sorted, this implies that $w_{2009}$ is the biggest value of them all. Assume for sake of contradiction that there are $0$ working indices, or in other words $r_{2009} + b_{2009} < w_{2009}$. However, if we let $r_i$ and $b_k$ be the corresponding indices that matched up with $w_{2009}$ in a non-degenerate triangle, then we get \begin{align*} r_i + b_k \leq r_{2009} + b_{2009} < w_{2009} < r_i + b_k, \end{align*}which is a contradiction. Thus we are done.

.........

Consider the following, easily generalized so that there are $2009$ columns (extend the middle with the same pattern) \[ \begin{tabular}{ c c c c c c c } {\color{red}3} & {\color{blue}30} & {\color{yellow}300}& {\color{green}3000}& l & m &a \\ x & {\color{red}5} & {\color{blue}50}& {\color{yellow}500}& {\color{green}5000}& n &b\\ y & z & {\color{red}7} & {\color{blue}70} & {\color{yellow}700}& {\color{green}7000} &c \end{tabular} \]Let the 9 variables be grouped into the 3 triangles as follows: $(x,l,c),(y,m,b),(z,n,a)$. So each triple has the three elements in three different rows, as the problem requires. Let \begin{align*} \ell=10^{100}, \quad m=10^{100}+1, \quad a &= 10^{100}+2 \\ n=10^{100}+7001, \quad b&=10^{100}+7002 \\ c&=10^{100}, \end{align*}and let $x=0.1, y=1, z=2.1$. Then $x<5$ and $y<z<7$ and $3000<l<m<a$ and $5000<n<b$ and $7000<c$. Also, $(3,x,y)$ is not a triangle, $(30,5,z)$ is not a triangle, $(l,5000,700)$ is not a triangle, $(m,n,7000)$ is not a triangle (this part DOES NOT work). The 2009 triangles are the sets of 3 numbers with the same color (the bottom left 3 and top right 3 are separate). Also, we can now assign the white,red,blue shades as in the problem to the elements, without two of the same shade in the same row -- that's why we need the whole a,b,c,x,y,z,l,m,n thing, to make this work for the boundary cases. No column forms a triangle except the last. Hence, $k\le 1$. To prove $k\ge 1$, note that the last column must always form a triangle, since if $b_{2009}+r_{2009} \le w_{2009}$, then $w_{2009}$ can't be in a triangle with lower values.

The answer is $k=1$. Take $b_i=2^i$, $r_i=2^i$ for $1\le i<2009$ and $r_{2009}=2^{2010}$, and $w_i=2^{i+1}$. Then our triangles may be formed by $b_{i+1}$, $r_i$, and $w_i$ for $1\le i<2009$ while the last triangle is formed by $b_1$, $r_{2009}$, $w_{2009}$. It is easy to see that this works. Now suppose that none of the indices form a non-degenerate triangle. Then WLOG suppose that $w_{2009}\ge b_{2009}+r_{2009}$. Clearly $w_{2009}$ cannot form a non-degenerate triangle with any pair of blue and red sides, a clear contradiction. $\blacksquare$

Just in case I messed up the sequence, it looks like this: 2 4 8 16 32 2 4 8 16 64 4 8 16 32 64

We claim that $k=1.$ We provide such a construction that proves $k\ge 2$ will not work. $b_i=2^i$, $r_i=2^i$ when $1\le i\le 2008$ but $r_{2009}=2^{2010}$ and $w_{i}=2^{i+1}.$ The triangles are $b_{i+1},r_{i+1},w_i$ when $1\le i\le 2007$, $b_1,r_{2009},w_{2009}$ and $b_{2009},r_1,w_{2008}.$ Now, if $k=0$ then $b_1+b_2+\dots+b_{2009}+r_1+r_2+\dots+r_{2009}\le w_1+w_2+\dots+w_{2009}$ so by pigeonhole, no matter how we permute the $b,r,w$ into $b'$, $r'$ and $w'$ there will be $b_i'+r_i'\le w_i'.$

We claim that the answer is $1$. Note that $b_{2009}$, $r_{2009}$, and $w_{2009}$ form a triangle since $b_{2009} < r_i + w_j \le r_{2009}+w_{2009}$ and similarly for the other values. We now provide a construction. Take $b_i=3^{i-1}$, $r_i=3^{i}$, and $w_i=3^{i-1}$ if $i \neq 2009$ and $w_{2009} = 3^{2009}$. If $2009$ was replaced by $4$ this would be $$1 \text{ } 3 \text{ } 9 \text{ } 27$$$$3 \text{ } 9 \text{ } 27 \text{ } 81$$$$1 \text{ } 3 \text{ } 9 \text{ } 81$$Note that $b_{i+1}$, $r_i$, and $w_i$ form a triangle for $i \le 2008$ and $b_1$, $r_{2009}$, and $w_{2009}$ form a triangle. Note that for $i \le 2008$, we have that $b_i + w_i = 2 \cdot 3^{i-1} < 3^i = r_i$, which means that none of these form a triangle. This means that there is at most one triangle in the desired form so we are done.

why is this such a troll problem The answer is $k=1$. We first claim that the longest side of each color must form a triangle. WLOG that $b_{2009}$ is the largest. Then, consider the triangle with a blue side of length $b_{2009}$. It must be paired with some two other red and white sides that add up to more than the blue side. Since there exists a red side and a white side that add up to more than the longest blue side, the longest red side and the longest white side must add to more than the blue side, which shows that $k\geq 1$. We will now present a construction where only 1 index $j$ exists. Suppose we had $$b_1=10,b_2=10^{10},b_3=10^{10^{10}}\cdots b_{2008}=b_{2009}=10\uparrow\uparrow 2008,$$$$r_1=1,r_2=10,r_3=10^{10}\cdots r_{2009}=10\uparrow\uparrow 2008,$$$$w_1=1,w_2=10,w_3=10^{10}\cdots w_{2009}=10\uparrow\uparrow 2008,$$Clearly, the only index for which $b_j,r_j,w_j$ makes a triangle is $j=2009$. However, we can create the following matchings of triangles: $$(b_{2008},r_1,w_{2009})$$$$(b_{2009},r_{2009},w_{1})$$ For the remaining triangles, we can then just make the equilateral triangles $(b_1,r_2,w_2)=(10,10,10)$, $(b_2,r_3,w_3)=(10^{10},10^{10},10^{10})$ and so on until $(b_{2007},r_{2008},w_{2008})$. Hence the answer is $k=1$ and we are done.

We claim the answer is 1, that being the triangle $b_{2009},r_{2009},w_{2009}$, which always works since $b_{2009} < r_i + w_j \le r_{2009}+w_{2009}$. Now, take sufficiently large values of them, with $1\le k\le 2008$ always: $\{b_k,r_k,w_k\}=143466569420^{\{k-1,k,k-1\}},\{b_{2009},r_{2009},w_{2009}\}=143466569420^{\{2008,2009,2009\}}$, respectively in the sets; it's obvious that the original triangles (isosceles) were $b_{k+1},r_k,w_k$, as well as b_1,r_2009,w_2009. Finally, note that $b_k+w_k=2(143466569420)^{k-1}<143466569420^{k}=r_k$, so there are no other triangles.

I claim the answer is $k = 1$. Proof we cannot get $k > 1$: Consider the triangles $(b,r,w) = (5 \cdot 2^i,4 \cdot 2^i,2 \cdot 2^i)$ for $0 \le i \le 2007$, and $(10^{2007}, 10^{2007}, 1 )$. Sorting then gives $b_i =(5 \cdot 1, 5 \cdot 2, \cdots 5 \cdot 2^{2007}, 10^{2007}), r_i = (4 \cdot 1, 4 \cdot 2, \cdots 4 \cdot 2^{2007}, 10^{2007}), w_i = (1, 2, \cdots 2^{2008}) $. Clearly for the first $2008$ indices there is no triangle formed since $5 \cdot 2^i = 4 \cdot 2^i + 2^i$, and since the last index has two equal values a triangle is formed. Proof we cannot get $k = 0$: Assume we can. Then for the last index, one of the sides must be at least the sum of the other two. WLOG let this be $w_{2009}$, then we have $w_{2009} \ge b_{2009} + r_{2009} \ge b_i + r_j$ for any $i,j$, but since there exists some triangle $w_{2009}, b_i, r_j$ we have a contradiction.

We claim that the answer is $1.$ Note that $b_{2009} <r_i+w_j \leq r_{2009}+w_{2009},$ and cyclic variations hold so $b_{2009}, r_{2009}, w_{2009}$ form a non-degenerate triangle. Now, we provide a construction to prove the bound. Consider the sequences $1, 3, 3^2, \cdots, 3^{2007}, 3^{2008}$ $1, 3, 3^2, \cdots, 3^{2007}, 3^{2009}$ $3, 3^2, 3^3, \cdots, 3^{2008}, 3^{2009}$ which represent $b_i, r_i, w_i$ respectively. Letting the triangles have sides $(b_2, r_1, w_1), (b_3, r_2, w_2), \cdots, (b_{i+1}, r_i, w_i), \cdots, (b_{2009}, r_{2008}, w_{2008}), (b_1, r_{2008}, w_{2008})$ gives valid triangles, and clearly in this construction only $3^{2008}, 3^{2009}, 3^{2009}$ gives a valid triangle, so the bound is proven. Hence the answer is $1,$ as claimed.