orl wrote: Prove that for every positive integer $n,$ the set $\{2,3,4,\ldots,3n+1\}$ can be partitioned into $n$ triples in such a way that the numbers from each triple are the lengths of the sides of some obtuse triangle. http://www.artofproblemsolving.com/Forum/viewtopic.php?f=36&t=480457

So our friend gold46 (from remote Mongolia), not only was (s)he in possession of the 2011 Shortlist, but also made part of it public by May 20, 2012, while everybody else tried to keep its secrecy until disclosure time July 12, 2012. Way to go ...

That happens sometimes. Some countries use these problems as their TSTs and after the TST is done, problems may be posted on AoPS. This is the main reason they don't reveal Shortlist before IMO. However, I don't know why we should wait till the IMO is held. But I guess that's because different countries hold Team Selections in different times, and even some of them choose the students going to IMO in a short while before IMO.

Maybe i made a mistake in my proof.Please tell me if i'm wrong. Denote $A=\{2,3,...2n+1\}, B=\{2n+2,...3n+1\}$. The triples will have the form $\{2n+1+i, 2i, 2i+1\}, i\in \{1,...n\}$. The condition for a triangle to be obtuse is( from cosine law) $a^2>b^2+c^2$, and in our case, it means $4n^2+i^2+1+4ni+4n+2i> 8i^2+1+4i$, which is equivalent to $4n^2+4ni+4n> 7i^2+2i$, but $n\ge i$, so $4n^2+4ni>7i^2, 4n>2i$.

MariusBocanu wrote: The triples will have the form $\{2n+1+i, 2i, 2i+1\}$, $i\in \{1,\ldots,n\}$. But for small values of $i$ (like for example $i=1$) we have $ 2i + (2i+1) < 2n+1+i$, so the triangle inequality is not satisfied. Trying to get the obtuse condition, you lost the ball out of your eyesight; it happens And what for are the notations $A$ and $B$ if they're not used later?

Proof by induction. For any $(a,b,c)$, (all triplets used here assume $a < b < c$), define $S(a,b,c)=a+b-c$ and $T(a,b,c)=c^2-b^2-a^2$, then the problem is to divide $(2,3,...3n+1)$ into triplets, each ascending, where $S(a,b,c),T(a,b,c) > 0$. Call $(a,b,c)$ good if $S(a,b,c),T(a,b,c) >0$. Note that if $(a,b,c)$ is good, so is $(a,b+k,c+k)$, for any integral k. The inductive hypothesis is that $(2,3,...3k+1)$ can be partitioned into $k$ good triplets, the $ith$ triplet having first element $i+1$. For $k=1$, it is clearly true since $(2,3,4)$ is good. Assume this is true for $k=1,2,...n-1$. Now let $x= \lfloor 5n/2 \rfloor +1$. Calculation shows that $(n+1,x,3n+1)$ is good, as are $(n,x-1,3n),(n-1,x-2,3n-1),...(x-2n+1,2x-3n,x+1)$. In total, these comprise all the elements of $(2,3,...3n+1)$, except for $(2,3,...x-2n)$ and $(n+2,n+3,...,2x-3n-1)$. To construct the missing triplets, take the solution triplets $(i+1,b_i,c_i)$ for $k=x-2n-1$, and create the triplets $(i+1,b_i+(3n+1-x),c_i+(3n+1-x))$, all of which are good. The partition is now complete.

Lemma: Triangle with sides $x,x+r-1,r$ is obtuse for positive integers $x,r$ with $x>r>1$. Proof: It is equivalent to $(x+r-1)^2>x^2+r^2$ which becomes $2(x-1)(r-1)>1$ which is true. Now for $n=2k$ construct these triplets. $2k+1-2i,2k+2+i,4k+2-i$ $ i=0,..,k$ and $2k-2-2i,6k+1-i,4k+4+i$ for $i=0,..,k-2$(these are all of the form as in the lemma which means they are sides of obtuse triangles) and the triplet $2k,3k+2,4k+4$ which are also sides of an obtuse triangle for $k\ge 2$ Similar construction is for $n=2k+1$ Only left case is $n=1$ which is obvious.

pplay around with small values of $ n $, it is not hard at all to come up with a solution

Here is one of many possible constructions. We will prove one can form such a partition such that $\{2,3,\dots,n+1\}$ are in different triples; let $P(n)$ denote this statement. We make the following observation: If $a<b<c$ is an obtuse triple, then so is $(a,b+x,c+x)$ for any $x > 0$. Observe $P(1)$ is obviously true. Claim: We have $P(n) \implies P(2n)$ for all $n \ge 1$. Proof. Take the partition for $P(n)$ and use the observation to get a construction for $\{2, \dots, n+1\} \sqcup \{2n+2, \dots, 4n+1\}$. Now consider the following table: \[ \left[ \begin{array}{cccc|cccc} 2 & 3 & \dots & n+1 & n+2 & n+3 & \dots & 2n+1 \\ \hline \multicolumn{4}{c|}{\text{Induction}} & 4n+2 & 4n+3 & \dots & 5n+1 \\ \multicolumn{4}{c|}{\text{hypothesis}} & 5n+2 & 5n+3 & \dots & 6n+1 \end{array} \right] \]We claim all the column are obtuse. Indeed, they are obviously the sides of a triangle; now let $2 \le k \le n+1$ and note that \[ k^2 < 8n^2 \implies (n+k)^2 + (4n+k)^2 < (5n+k)^2 \]as desired. $\blacksquare$ Claim: We have $P(n) \implies P(2n-1)$ for all $n \ge 2$. Proof. Take the partition for $P(n)$ and use the observation to get a construction for $\{2, \dots, n+1\} \sqcup \{2n+1, \dots, 4n+1\}$. Now consider the following table: \[ \left[ \begin{array}{cccc|cccc} 2 & 3 & \dots & n+1 & n+2 & n+3 & \dots & 2n \\ \hline \multicolumn{4}{c|}{\text{Induction}} & 4n+1 & 4n+2 & \dots & 5n-1 \\ \multicolumn{4}{c|}{\text{hypothesis}} & 5n & 5n+1 & \dots & 6n-2 \end{array} \right] \]We claim all the columns are obtuse again. Indeed, they are obviously the sides of a triangle; now let $1 \le k \le n-1$ and note that \[ (k-2)^2 < 8n^2-12n+4 \implies (n+1+k)^2 + (4n+k)^2 < (5n+k-1)^2 \]as desired. $\blacksquare$ Together with the base case $P(1)$, we obtain $P(n)$ for all $n$.

Lemma: The numbers $\{d+1,n,n+d\}$ are the sides of an obtuse triangle for positive integers $d$ and $n\ge d+1$. Proof of Lemma: The triangle inequality is clearly satisfied. Furthermore, \[(n+d)^2-n^2-(d+1)^2=2nd-2d-1\ge 2d^2-1>0,\]so the triangle is obtuse. $\blacksquare$ We split into cases based on the parity of $n$. Case 1: $n$ is even. We claim that we can partition $[2n]\setminus\{3n/2,2n\}$ into $n-1$ pairs with differences ranging from $1$ to $n-1$. To do this, we pair up $\{n/2-k,n/2+k+1\}$ for $k=0,\ldots,n/2-1$, and $\{3n/2-k,3n/2+k\}$ for $k=1,\ldots,n/2-1$. Let the pair with difference $d$ be $\{a_d,b_d\}$, so $b_d-a_d=d$. Make the triples $\{2,a_1+n+1,b_1+n+1\},\{3,a_2+n+1,b_2+n+1\},\ldots,\{n,a_{n-1}+n+1,b_{n-1}+n+1\},\{n+1,3n/2+n+1,3n+1\}$. By our lemma, the first $n-1$ triples work. It suffices to check that the last one works. The triangle inequality is clearly satisfied, and \[(3n+1)^2-(n+1)^2-(5n/2+1)^2=7n^2/4-n-1>0\]for $n\ge 2$, as desired. Case 2: $n$ is odd. We claim we can partition $[2n]\setminus\{3n/2-1/2,2n\}$ into $n-1$ pairs with differences ranging from $1$ to $n-1$. Pair up $\{(n-1)/2-k,(n-1)/2+k+1\}$ for $k=0,\ldots,(n-1)/2-1$ and $\{(3n-1)/2-k,(3n-1)/2+k\}$ for $k=1,\ldots,(n-1)/2$. Let the pair with difference $d$ be $\{a_d,b_d\}$, so $b_d-a_d=d$. Make the triples $\{2,a_1+n+1,b_1+n+1\},\{3,a_2+n+1,b_2+n+1\},\ldots,\{n,a_{n-1}+n+1,b_{n-1}+n+1\},\{n+1,(3n-1)/2+n+1,3n+1\}$. By our lemma, the first $n-1$ triples work. It suffices to check that the last one works. The triangle inequality is clearly satisfied, and \[(3n+1)^2-(n+1)^2-(5n/2+1/2)^2=7n^2/4+3n/2-1/4>0\]for $n\ge 1$, as desired. So we have a construction for all $n\ge 1$.

Here's a different way for the inductive approach: Call a triple of naturals $(i,j,k)$ a nice triple if $i<j<k$ are sides of an obtuse triangle, i.e. $i+j>k$ and $i^2+j^2<k^2$. We wish to show that $S(n)=\{2,3, \dots ,3n+1\}$ can be partitioned into $n$ nice triples. Call such a set $S(n)$ a nice set. We apply prefix induction (look at the variants of induction given here) on $n$, i.e. we try to prove that if $S(n)$ is nice, then so is $S(2n)$ and $S(2n+1)$, in which case we will be done. The base case $(n=1)$ is trivial (Take $(2,3,4)$ as the required nice triple). So now assume that the result is true for some $n \geq 2$. First consider the set $S(2n)=\{2,4, \dots ,6n\} \cup \{3,5, \dots ,6n+1\}$. Now, if $(i,j,k)$ is a nice triple, then so are $(2i,2j,2k)$ and $(i-1,j-1,k-1)$. The first triple is easily seen to be nice, while the second one is nice using the following- $$(i-1)^2+(j-1)^2-(k-1)^2=(i^2+j^2-k^2)+2(k-i-j)+1 \leq -1+2(-1)+1<0$$This gives that if $A$ is a nice subset, then so is $2A$ and $A-1$. Using this fact, we get that, as $S(n)$ is nice, so $2(S(n)-1)=\{2,4, \dots ,6n\}$ and $2S(n)-1=\{3,5, \dots ,6n+1\}$ are also nice. Since the union of two disjoint nice sets is also nice, so we get that $S(2n)$ is a nice set. Now, we take up the set $S(2n+1)$, which can be thought of as a union of the three sets of triples given below- $$\{(2n-2a+4,2n+a+2,4n-a+5):a=1,2, \dots ,n+1\} \cup \{(2n-2a+1,4n+a+5,6n-a+5):a=1,2, \dots ,n-1\} \cup (2n+1,4n+5,5n+5)$$It is easy to see that all of these triples are distinct and nice (Too lazy to show the calculations ). This gives that $S(2n+1)$ is also a nice set, as desired. Hence, done. $\blacksquare$ REMARK: While trying this problem, I easily proved that $S(2n)$ is nice (Luckily the first thing I tried was induction; and when the normal induction didn't seem to work, it made sense to use prefix induction). However, proving that $S(2n+1)$ is also nice if $S(n)$ is nice came out as a difficult task, which I wasn't able to do even after trying for nearly an hour and a half (which is why I finally turned to finding out a construction, which is easy and doable in around an hour or so ). So overall, I think this problem was a really nice one (pun intended ), in its formation, as well as in the risk of getting stuck on it for a long time.

For each $n$, inductively construct a sequence of numbers in the following manner: Write $\lceil n/2\rceil$, and then repeat the process for $\lfloor n/2\rfloor$, until we get to $1$. For example, the sequence we construct for $19$ is: $10, 5, 2, 1, 1$. Now, if our sequence is $a_1,a_2,\ldots, a_i$ backwards, we split $[n+2,3n+1]$ into the following $i$ groups: $[2(a_1+\ldots + a_{i-1})+n+2, 2(a_1+\ldots+a_{i})+n+2)$, and in a group of size $2s$, we pair its first element with the $s+1$st element, etc.. In this way, we split the largest $2n$ numbers into $n$ pairs. Now, pair the pair with the $i$th smallest smaller element with $i$, to create $n$ triplets. We claim that each triplet forms an obtuse triangle. Denote the $i$th triplet as $(i,y_i,z_i)$ such that $y_i,z_i$ are in the $k$th group formed by the $a_j$. In our construction for $\{a_j\}$, we have $a_1+\ldots+a_{j-1}\ge a_j-1$, meaning that if $y_i,z_i$ are in the $k$th group, we have that $i>a_k$, meaning triangle inequality is satisfied. Furthermore, we have $i<a_1+\ldots + a_k\le 2a_k$, so $z_i^2-y_i^2=(y_i+z_i)*2a_k>4a_k^2>i^2$, so the triangle is obtuse. So, this is a valid construction, as desired.

Call a triple $(a,b,c)$ stupid if $a<b<c$ and $a,b,c$ form an obtuse triangle, so we wish to partition $\{2,\ldots,3n+1\}$ into $n$ stupid triples. We begin with the following key lemma. Lemma: If $(a,b,c)$ is stupid, then so is $(a,b+r,c+r)$ for any $r>0$. Proof: Clearly the triangle inequality is satisfied. Furthermore, we have $a^2+b^2<c^2 \implies a^2+(b+r)^2<(c+r)^2$ for $r>0$, so combining these gives the desired. $\blacksquare$ Now we use strong downwards induction, with the base case of $n=1$ being trivial (the only option of $(2,3,4)$, which works). We will add the additional condition that our $n$ stupid triples should "separate" $2,\ldots,n+1$, i.e. each of these numbers is present (obviously as the least element) in a different stupid triple. If $n=2m$ is even, then form the stupid triples $(2m+1,5m+1,6m+1),(2m,5m,6m),\ldots,(m+2,4m+2,3m+2)$. Note that we are left with the numbers $\{2,\ldots,m+1,2m+2,\ldots,4m+1\}$. Evidently, each of these triples satisfies the triangle inequality. Further, for any triple $(a,b,c)$ listed, we have $$c^2-b^2\geq (5m+2)^2-(4m+2)^2=9m^2+4m>4m^2+4m+1=(2m+1)^2\geq a^2,$$so all these triangles are in fact obtuse. On the other hand, by inductive hypothesis we can form $m$ stupid triples with least parts $2,\ldots,m+1$ from the set $\{2,\ldots,m+1,m+2,\ldots,3m+1\}$, so by our lemma we should also be able to do this for $\{2,\ldots,m+1,2m+2,\ldots,4m+1\}$, completing the inductive step. Otherwise, if $n=2m-1$ is odd, then form the stupid triples $(2m,5m-2,6m-2),(2m-1,5m-3,4m-3),\ldots,(m+1,4m-1,5m-1)$. Note that we are left with the numbers $\{2,\ldots,m,2m+1,\ldots,4m-2\}$. As before, each of these triples $(a,b,c)$ satisfies the triangle inequality, and also $$c^2-b^2 \geq (5m-1)^2-(4m-1)^2=9m^2-2m>4m^2=(2m)^2\geq a^2,$$hence these triples are actually stupid. By inductive hypothesis, we can form $m-1$ stupid triples with least parts $2,\ldots,m$ from $\{2,\ldots,m,m+1,\ldots,3m-2\}$, so we can also do this for $\{2,\ldots,m,2m+1,\ldots,4m-2\}$ by the lemma. This again completes the inductive step. Since these cases cover all possible $n$, we are done. It is also possible to view this triple-generating process as an algorithm in the same way. In this case, the triples generated for $n=5$ would be $(6,13,16),(5,12,15),(4,11,14),(3,9,10),(2,7,8)$. Remark: Why does this feel like it would have 1800 rating on codeforces? Actual Remark (motivation): After looking at the $n=2$ case it seemed highly likely to me that some construction where we take $2,\ldots,n+1$ as the smallest elements and throw together the other elements (at the very least, it's worth a try). The most obvious way to do this would be to take $(n+1,6n,6n+1),(n,6n-1,6n-2)$, and so on, which is what's suggested by the $n=2$ construction, but when $n$ gets bigger the difference of $1$ between the squares isn't enough. On the other hand, if we make the differences really big to the point where the triangle is obtuse if it exists, the triangle inequality might not be satisfied. To overcome these "extreme issues" we probably want to do something in the middle. Looking at numbers near the top, we would probably like to get $(n+1,6n+1,6n-k)$ all the way to $(n+1-k,6n-k+1,6n-2k)$ for some suitable (approximate) choice of $k$. It turns out that $k \approx n/2$ works nicely, since the triangle inequality should just barely hold at the lower end and the obtuse condition should also hold. The rest is just correctly choosing boundary conditions.

Let $S(a,b,k)$ be $k$ triples of the following form: \[(a-k+1,b-2k+1,b-k+1), (a-k+2,b-2k+2,b-k+2), \dots, (a,b-k, b)\]We impose the precondition that all of those triangles are non-degenerate and obtuse. Call $(a,b,c)$ an obtuse triple if $a<b<c$, $a+b>c$ and $a^2+b^2<c^2$. Then, if $(a,b,c)$ is obtuse then $a<b+k<c+k$, $a+(b+k)>(c+k)$ and \[a^2+(b+k)^2=a^2+b^2+2kb+k^2 < c^2+2kb+k^2 < c^2+ 2kc + k^2 = (c+k)^2\]so $(a,b+k,c+k)$ is also obtuse. Note that if $a^2+b^2<c^2$ and $a+b>c$ then \[(a-1)^2+(b-1)^2 = a^2+b^2-2(a+b)+1<a^2+b^2-2c+1<c^2-2c+1=(c-1)^2\]so if $(a,b,c)$ is obtuse and $a+b>c+1$ then so is $(a-1,b-1,c-1)$. Note that since $-7n^2+2n+1<0$ for all $n\ge 1$, we have $(2n+1)^2+(5n+1)^2 < (6n+1)^2$ and we have $n+2+4n+2>5n+2$, so $S(2n+1,6n+1,n)$ are all obtuse. It also uses every number like $\{n+2,n+3,\dots, 2n+1, 4n+2, 4n+3, \dots, 6n+1\}$. Now, if you can partition $\{2,3,\dots 3n+1\}$ in a way that separates $\{2,3,\dots, n+1\}$ then if you add $n$ to each $b$ and $c$ in the obtuse triples, they stay obtuse and take up $\{2,3,\dots, n+1,2n+2,\dots, 4n+1\}$. Together with $S(2n+1,6n+1,n)$ we completed the partition. Thus, if the claim is true for $n$ then it is true for $2n$. For $n$ implying $2n-1$ we can simply use $S(2n,6n-2,n-1)$ for the same effect and we will not go into detail.

We prove a stronger statement: Prove that for every positive integer $n,$ the set $\{2,3,4,\ldots,3n+1\}$ can be partitioned into $n$ triples in such a way that the numbers from each triple are the lengths of the sides of some obtuse triangle and none of the triangles have two side lengths less than or equal to $n+1$. Call $(x,y,z)$ good if they are the length of the sides of an obtuse triangle. Notice that $(x,y,z)$ is good iff (WLOG $x<y<z$) $x^2 + y^2 < z^2$ and $x + y >z $. We want to split $\{2, 3, \ldots, 3n + 1\}$ into $n$ good triples. Claim 1: If $(a,b,c)$ is good with $a < b < c$, then $(a, b + k, c + k)$ is also good for any positive integer $k$. Proof: If $(a,b,c)$ was good, then $a^2 + b^2 < c^2$ and $a + b > c$. It suffices to show that $a^2 + (b+k)^2 < (c+k)^2$ and $a + b + k > c + k$. The second inequality holds true obviously since $a + b > c $ and the first inequality holds true because $a^2 + b^2 < c^2$ and $2bk < 2ck$. $\square$ Claim 2: If $(a,b,c)$ is good, $a<b<c$, and $a + b >c + 1$, then $(a-1, b-1, c-1)$ is also good. Proof: Suppose $(a,b,c)$ was good. Clearly\[(a-1)^2 + (b-1)^2 = a^2 + b^2 - 2(a+b) + 2 < c^2 - 2(c + 1) + 2 < (c-1)^2\]and $(a-1) + (b-1) = a + b - 2 > c - 1$, so $(a-1, b-1, c-1)$ is also good. $\square$ Claim 3: For any $n \ge 2$, if the statement is true, then the statement is true for $2n$ also. Proof: We partition $\{2,3,4,\ldots, 6n + 1\}$ in the following way: We partition the numbers in the interval $[n+2, 4n + 1]$ as\[\{n + 2, 2n + 2, 3n + 2\}, \{n + 3, 2n + 3, 3n + 3\}, \ldots, \{2n+1, 3n+1, 4n+1\}\]Obviously no two of these sets intersect. To see they are good, notice that $(2n+1)^2 + (3n+1)^2 < (4n+1)^2$, and then applying claim 2 gives the desired result. Note that each $2\le r\le n + 1 $ was matched with two other numbers from $n+2$ to $3n + 1$ in the original partition of $\{2, 3, 4, \ldots, 3n + 1\}$. In our new partition, match it with those two same numbers except each added by $3n$. These two numbers will be each at least $n + 2$ originally, so when added by $3n$, they will at least $4n+2$, so they cannot intersect in the interval $[n + 2, 4n + 1]$. Furthermore, each of these triplets are good by claim 1, and cannot intersect each other. Therefore this partition works, so the claim is proven. $\square$ Claim 4: For any $n\ge 4$ if the statement is true, then the statement is true for $2n-1$ also. Proof: We partition $\{2,3,4,\ldots, 6n - 2\}$ in the following way: We partition the numbers in the interval $[n+2, 4n -2]$ as\[\{n+2, 2n+1, 3n\}, \{n+3, 2n+2, 3n+1\}, \ldots, \{2n , 3n - 1, 4n - 2\}\]Obviously no two of these sets intersect. To see they are good, notice $(2n)^2 + (3n-1)^2 < (4n-2)^2$, and then applying claim $2$ gives the desired result. Note that each $2\le r\le n + 1$ was matched with two other numbers from $n + 2$ to $3n + 1$ in the original partition of $\{2,3,4,\ldots, 3n +1\}$. In our new partition, match it with those two same numbers except added by $3n - 3$. These two numbers will be originally at least $n + 2$, so when added by $3n - 3$, at least $4n - 1$ so they cannot intersect in the interval $[n + 2, 4n - 2]$. Furthermore, each of these triplets are good by claim $1$, and cannot intersect each other. Therefore, this partition works, so the claim is proven. $\square$ Now, we clearly see that the statement is true for $1, 2, 3, $ and $5$, by\begin{align*} \{2,3,4\} \\ \{2,4,5\} ,\{3,6,7\} \\ \{2,9,10\}, \{3,6,7\}, \{4,5,8\}, \\ \{5,7,9\}, \{4,12,14\}, \{2,10,11\}, \{3,15,16\}, \{6,8,13\} \\ \end{align*}respectively. Now we may induct on $n$ to show it is true for all $n$. Note it is true for $n = 1,2,3,5$. Now suppose it was true for everything less than $k$ for some $k \ne \{1,2,3,5\}$. If $k$ is even, the statement is true for $\frac{k}{2}$, so using claim $3$, it is true for $k$. If $k$ is odd, the statement is true for $\frac{k + 1}{2} \ge 4$, so using claim $4$, it is true for $k$. Therefore, the induction is complete, so we are done.

Note that for $n = 2$ we have the base case of $(2, 3, 4)$. We now induct on the hypothesis that for a given $n$, the elements $\{2, \dots, n + 1\}$ are paired with two elements each from $\{n+2, 3n+1\}$. Claim: A construction for $n$ gives us one for $2n$. Proof. Suppose we have such a working example. Now consider $\{2, 3, 4, \dots, 6n + 1\}$. We can shift the latter two elements of the earlier triplets to get obtuse triangles on $\{2, 3, 4, \dots, n+1\}$ with $\{2n+2, \dots, 4n+1\}$. It remains to match $\{n+2, \dots, 2n+1\}$ with $\{4n+2, \dots, 6n+1\}$. We can do this by having triplets $(n+1+i, 4n+1+i, 5n+1+i)$ for $1 \le i \le n$ which satisfies the triangle condition and are obtuse. $\blacksquare$ Claim: This also works for $2n + 1$. Proof. Same idea but match $\{n+2, \dots, 2n+2\}$ with $\{4n+3, \dots, 6n+4\}$. This can be done by taking triplets $(n+1+i, 4n+2+i, 5n+3+i)$. $\blacksquare$