IMO Shortlist 2011, Algebra 5

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

w

16 users

TOPICS

No tags match your search

M

No tags match your search

M

IMO Shortlist 2011, Algebra 5

G H J

Reveal topic tags

triangle inequality

L

G H BBookmark kLocked kLocked NReply

Source: IMO Shortlist 2011, Algebra 5

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3647 posts

orl

#1 h Jul 11, 2012, 10:23 PM • 6 Y

Y by Davi-8191, tenplusten, ApraTrip, Adventure10, Mango247, and 1 other user

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.

Proposed by Canada

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

23450 posts

pco

#2 h Jul 12, 2012, 2:09 PM • 2 Y

Y by Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

15142 posts

#3 h Jul 12, 2012, 2:17 PM • 8 Y

Y by AlastorMoody, David-Vieta, Adventure10, Mango247, and 4 other users

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 ...

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5452 posts

#4 h Jul 12, 2012, 2:21 PM • 2 Y

Y by Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

429 posts

#5 h Jul 17, 2012, 5:41 AM • 2 Y

Y by Adventure10, Mango247

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$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

15142 posts

#6 h Jul 17, 2012, 7:15 AM • 4 Y

Y by AlastorMoody, Adventure10, Mango247, and 1 other user

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?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

105 posts

#7 h Jul 18, 2012, 5:34 PM • 1 Y

Y by Adventure10

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

339 posts

leader

#8 h Apr 20, 2014, 2:57 PM • 1 Y

Y by Adventure10

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

366 posts

#9 h Jan 18, 2015, 11:35 PM • 2 Y

Y by Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6862 posts

#10 h Dec 19, 2017, 12:17 AM • 5 Y

Y by InCtrl, Amir Hossein, Lcz, v4913, Adventure10

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$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1614 posts

yayups

#11 h Jan 24, 2019, 9:19 AM • 2 Y

Y by Amir Hossein, Adventure10

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$ .

This post has been edited 1 time. Last edited by yayups, Jan 24, 2019, 9:20 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1218 posts

#12 h Jan 25, 2019, 2:30 PM • 3 Y

Y by Amir Hossein, Adventure10, Mango247

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.

This post has been edited 5 times. Last edited by math_pi_rate, Mar 3, 2020, 6:49 AM
Reason: (j-1)^2- instead of (j-1)^-

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

894 posts

#13 h Feb 8, 2019, 10:59 PM • 2 Y

Y by Adventure10, Mango247

Not an induction

This post has been edited 2 times. Last edited by stroller, Feb 8, 2019, 11:09 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1576 posts

#14 h Apr 10, 2020, 11:39 PM • 1 Y

Y by TechnoLenzer

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5000 posts

#15 h Dec 1, 2022, 3:10 AM • 3 Y

Y by Mango247, Mango247, Mango247

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.

This post has been edited 2 times. Last edited by IAmTheHazard, Dec 4, 2022, 6:32 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

awesomeming327.

1665 posts

awesomeming327.

#16 h Apr 13, 2023, 6:02 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5537 posts

#17 h Jun 24, 2023, 2:43 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1492 posts

#18 h Apr 8, 2024, 5:24 PM

Y by

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

32 posts

#19 h Mar 17, 2025, 12:24 AM

Y by

Sketch (no induction):

The motivation is firstly that it would be nice constructively if we had every triplet begin with a small number from $[2,n+1]$ <l and secondly that for the pair each of these distinct numbers is associated with, we want to choose a pair from $[n+2,3n+1]$ where the pair is as spread out as possible and its size corresponds to the size of the small number it is associated with.

We claim we can split them into triples each with a distinct number from $[2,n+1]$ . The main idea is we basically want to partition $[n+2,3n+1]$ into intervals of length $2k$ , where then we can choose pairs from that interval with the same difference. For example, for $n=3$ , we have the distinct numbers $2,3,4$ , and we partition $[5,10]$ into $[5,6]$ and $[7,10]$ which would give triples $(2,5,6), (3,7,9), (4,8,10)$ .

Mark $n+2$ with a dot, and continue recursively marking $\lceil k/2 \rceil$ until $2$ is marked (e.g. for $n=3$ , we mark $5, 3, 2$ ). Then label all these marks in ascending order, $s_1, \dots s_N, s_{N+1}$ where $s_1 = 2, s_{N+1} = n+2$ . We have that for $1\leq i \leq N$ that $s_{i+1} = 2s_i -1$ or $2s_i - 2$ , except in case $n=2$ where $s_2 = 3$ .

Now we form the triples by splitting into the aforementioned intervals: Let $1 \leq i \leq N$ , and let $0 \leq j < s_{i+1} - s_{i}$ . For each $j$ we form:
$(s_i + j, n + 2s_i - 2 + j, n + s_{i+1} + s_i - 2 + j)$ We can verify that every single number is used distinctly in this construction of triples, then by some algebraic bash ( $n \geq s_i$ by the way) we can prove every triple satisfies the inequalities for obtuse triangles.

This post has been edited 2 times. Last edited by mathfun07, Mar 17, 2025, 12:28 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a