Find all integers $n \geq 3$ such that among any $n$ positive real numbers $a_1, a_2, \hdots, a_n$ with $\text{max}(a_1,a_2,\hdots,a_n) \leq n \cdot \text{min}(a_1,a_2,\hdots,a_n)$, there exist three that are the side lengths of an acute triangle.
Problem
Source: Also USAMO problem 1
Tags: USA(J)MO, USAMO, 2012 USAJMO, 2012 USAMO, geometry, Fibonacci, xtimmyGgettingflamed
25.04.2012 00:59
I got n>11, probably did it wrong.
25.04.2012 00:59
25.04.2012 01:00
Remark that the problem an acute triangle exists iff for each $i,j,k \in \{1,2,...,n\}$ where $i < j < k$, then $a_i^2 + a_j^2 \ge a_k^2$ where WLOG $a_1 \le a_2 \le ... \le a_n$. Suppose there does not exist an acute triangle for $n$. Denote $a_1 = a, a_2 = b$. Then we need $a_3 \ge \sqrt{a^2 + b^2}$. Now, we need $a_4 \ge \sqrt{a^2 + 2b^2}$ and by induction it is trivial to prove we need $a_n \ge \sqrt{F_{n-2}a^2 + F_{n-1}b^2} \ge a\sqrt{F_n}$. Then as $F_{13} = 233 > 13^2$ and furthermore for all $n \ge 13$ we have $F_n > n^2$, we have $F_n > na$ for $n \ge 13$. This violates the problem condition, so the problem holds for all $n \ge 13$. To show all lower $n$ fail, consider $(a_i) = (\sqrt{F_1}, \sqrt{F_2},...,\sqrt{F_n})$. Remark that $(\sqrt{F_i},\sqrt{F_j},\sqrt{F_k})$ work where $i < j < k$ requires $F_i + F_j > F_k$ for it to be an acute triangle. But $F_i + F_j \le F_{k-2} + F_{k-1} = F_k$, hence the statement clearly fails for $n \le 12$ as no triangles can even be formed, and hence we are done. EDIT : ninja'd.
25.04.2012 01:03
I, along with several of my friends, got $n>12$ for integer n. Assume that there exists a sequence $(a_1,\hdots,a_n)$ satisfying the conditions and no 3 of which form the side lengths of an acute triangle. WLOG, assume that $a_1 \leq a_2 \leq \hdots \leq a_n$. Thus, $a_3^2 \geq a_2^2+a_1^2$ $a_4^2 \geq a_3^2+a_2^2$ $\hdots$ $a_n^2 \geq a_{n-1}^2+a_{n-2}^2$ Thus, $a_n^2 \geq F_{n-1}a_2^2+F_{n-2}a_1^2$, where $F_n$ is the Fibbonacci sequence with $F_1=F_2=1$. The condition is equivalent to $a_n \leq na_1$, and thus $na_1 \geq \sqrt{F_{n-1}a_2^2+F_{n-2}a_1^2} \implies n^2a_1^2 \geq F_{n-1}a_2^2+F_{n-2}a_1^2$. Note that since $a_2\geq a_1$, we have $F_{n-1}a_2^2+F_{n-2}a_1^2 \geq F_na_1^2$. Thus, $n^2a_1^2 \geq F_na_1^2$, and $n^2 \geq F_n$. It's easy to verify that $n \leq 12$ satisfies this, and $n>12$ doesn't. EDIT: ninjaed several times xD
25.04.2012 01:05
This was also USAMO #1.
25.04.2012 01:10
Guys, can anyone tell me whats wrong with my solution? assume a1<a2<a3...<a_n If n is odd, a_n - a1 < (n-1)*a1 Telescoping, (a_n - a_(n-2)) + (a_(n-2) - a_(n-4)) + ... + (a3-a1) < (n-1) * a1 Let n = 2k+1, there are k differences which sum to less than 2*k*a1 By pigeonhole, at least one difference must be less than or equal to 2*a1 Suppose that a_i = m*a1, a_(i+2) = (m+2)*a1, so a_(i+1) is at least m*a1 We want (a_i)^2 + (a_(i+1))^2 > (a_(i+2))^2, or 2* m^2 > m^2 + 4m + 4, or (m-2)^2 > 8, which leads to m>=5. Since m+2 must be less than n, n>=7. Then I found with a similar method the same for the even case. I got n>=7, and I'm sure that it's >=13 now, but I'm not sure where I went wrong...
25.04.2012 01:16
lol, this was pretty easy. Just take the Fibonacci sequence, and do some bounding. I used Binet's formula in my proof to rigorously show F_n increased faster, but apparently that was way overkill (you just had to use induction).
25.04.2012 01:17
I got an answer of $n \ge 13$ as well I basically constructed the minimum valued (and therefore maximum lengthed) sequence $a_i$ such that there are NO acute triangles WLOG $a_1 \le a_2 \le ... \le a_n, a_1=1$ then minimum $a_2=1$, and our constraint is $a_n \le n$ then acute if and only if $a_i^2 < a_{i-1}^2 + a_{i-2}^2$, so to construct the minimumvalued sequence with no acute, $a_i^2=a_{i-1}^2+a_{i-2}^2$ then let $b_i=a_i^2$ By definition, $b$ is the fibonacci sequence Furthermore, our constraint becomes $b_n \le n^2$ If $3 \le n \le 12$, then $b_n \le n^2$, so it is possible to have a sequence meet the constraint but not have acute triangles If $n \ge 13$, then $b_n > n^2$, so a sequence of $n \ge 13$ integers that meets the constraint $a_n \le n$ must have acute triangles (because our minimum valued sequence does NOT meet the constraint)
25.04.2012 01:20
Bleh, I'll post this. Note that $F_{13}>13^2$ and $F_{14}>14^2$ by direct calculation. Now assume that $F_n>n^2$ and $F_{n+1}>(n+1)^2$ for some $n>12$. Adding gives $F_{n+2}>2n^2+2n+1$. Since $n^2>2n+3$ for $n>12$, we have $F_{n+2}>2n^2+2n+1>n^2+4n+4=(n+2)^2$. Thus, when $(n,n+1)$ works, so does $(n+1,n+2)$, and the induction is complete.
25.04.2012 01:22
Lol I wrote three pages because I tried to explain why if each consecutive triplet made a right triangle and that there exists a contradiction then we have our $n$ that work. Haha hopefully they don't get upset with all the wordiness Sidenote: Would they dock points if I said: "By computation we see that for $n$ from $3$ to $12$, $n^2 \geq F_n$"?
25.04.2012 01:23
Doubtfully. I said the same thing, although I put a table at the end to be sure.
25.04.2012 01:28
25.04.2012 01:29
The question reads "positive real numbers"
25.04.2012 01:31
Hm. I solved $F_{n-2}>n^2$ and thus got $n\geq15$. So close. I wonder how many points they'll take off. I did everything else right...
25.04.2012 01:32
pr0likethis wrote: I got an answer of $n \ge 13$ as well I basically constructed the minimum valued (and therefore maximum lengthed) sequence $a_i$ such that there are NO acute triangles WLOG $a_1 \le a_2 \le ... \le a_n, a_1=1$ then minimum $a_2=1$, and our constraint is $a_n \le n$ then acute if and only if $a_i^2 < a_{i-1}^2 + a_{i-2}^2$, so to construct the minimumvalued sequence with no acute, $a_i^2=a_{i-1}^2+a_{i-2}^2$ then let $b_i=a_i^2$ By definition, $b$ is the fibonacci sequence Furthermore, our constraint becomes $b_n \le n^2$ If $3 \le n \le 12$, then $b_n \le n^2$, so it is possible to have a sequence meet the constraint but not have acute triangles If $n \ge 13$, then $b_n > n^2$, so a sequence of $n \ge 13$ integers that meets the constraint $a_n \le n$ must have acute triangles (because our minimum valued sequence does NOT meet the constraint) That was almost exactly the solution I had. I felt the need to define the Fibonacci sequence in the beginning for some weird reason.
25.04.2012 02:51
dinoboy wrote: Remark that the problem an acute triangle exists iff for each $i,j,k \in \{1,2,...,n\}$ where $i < j < k$, then $a_i^2 + a_j^2 \ge a_k^2$ where WLOG $a_1 \le a_2 \le ... \le a_n$. Suppose there does not exist an acute triangle for $n$. Denote $a_1 = a, a_2 = b$. Then we need $a_3 \ge \sqrt{a^2 + b^2}$. Now, we need $a_4 \ge \sqrt{a^2 + 2b^2}$ and by induction it is trivial to prove we need $a_n \ge \sqrt{F_{n-2}a^2 + F_{n-1}b^2} \ge a\sqrt{F_n}$. Then as $F_{13} = 233 > 13^2$ and furthermore for all $n \ge 13$ we have $F_n > n^2$, we have $F_n > na$ for $n \ge 13$. This violates the problem condition, so the problem holds for all $n \ge 13$. To show all lower $n$ fail, consider $(a_i) = (\sqrt{F_1}, \sqrt{F_2},...,\sqrt{F_n})$. Remark that $(\sqrt{F_i},\sqrt{F_j},\sqrt{F_k})$ work where $i < j < k$ requires $F_i + F_j > F_k$ for it to be an acute triangle. But $F_i + F_j \le F_{k-2} + F_{k-1} = F_k$, hence the statement clearly fails for $n \le 12$ as no triangles can even be formed, and hence we are done. EDIT : ninja'd. This is basically exactly what I did. I didn't bother to prove that the Fibonacci sequence increases faster than $x^2$ though... hope that's okay...
25.04.2012 03:17
If the actual answer was a subset of the answer I got, do you think I have a chance at a point
25.04.2012 03:36
I was too lazy to use square roots, so I just defined the new sequence $\{b_i\} = \{a_i^2\}$. But otherwise my solution is basically the same as most above.
25.04.2012 03:43
sparkle123 wrote: dinoboy wrote: Remark that the problem an acute triangle exists iff for each $i,j,k \in \{1,2,...,n\}$ where $i < j < k$, then $a_i^2 + a_j^2 \ge a_k^2$ where WLOG $a_1 \le a_2 \le ... \le a_n$. Suppose there does not exist an acute triangle for $n$. Denote $a_1 = a, a_2 = b$. Then we need $a_3 \ge \sqrt{a^2 + b^2}$. Now, we need $a_4 \ge \sqrt{a^2 + 2b^2}$ and by induction it is trivial to prove we need $a_n \ge \sqrt{F_{n-2}a^2 + F_{n-1}b^2} \ge a\sqrt{F_n}$. Then as $F_{13} = 233 > 13^2$ and furthermore for all $n \ge 13$ we have $F_n > n^2$, we have $F_n > na$ for $n \ge 13$. This violates the problem condition, so the problem holds for all $n \ge 13$. To show all lower $n$ fail, consider $(a_i) = (\sqrt{F_1}, \sqrt{F_2},...,\sqrt{F_n})$. Remark that $(\sqrt{F_i},\sqrt{F_j},\sqrt{F_k})$ work where $i < j < k$ requires $F_i + F_j > F_k$ for it to be an acute triangle. But $F_i + F_j \le F_{k-2} + F_{k-1} = F_k$, hence the statement clearly fails for $n \le 12$ as no triangles can even be formed, and hence we are done. EDIT : ninja'd. This is basically exactly what I did. I didn't bother to prove that the Fibonacci sequence increases faster than $x^2$ though... hope that's okay... I feel like one needs to show that.
12.09.2022 23:05
We claim that the answer is $n>12$ for integer $n$. Step one: Showing $n \leq 12$ don't work To do this, we will first prove that $F_n > n^2$ for $n > 12$. The base case, at $n = 13$, obviously works, and for the inductive step, it suffices to show that $F_{n-1} > 2n + 1$ when $n > 12$, which is obviously true. Now note that the best configuration for this to not work should have as many 'right triangle triples' as possible, while still minimizing the terms; so it should look like $\sqrt{1}, \sqrt{1}, \sqrt{2}, \sqrt{3}, \sqrt{5}, \sqrt{8}, \ldots \sqrt{F_p}$ which will work up to (and including) $F_{12} = 144$, since for larger $p$ we'll have $\sqrt{F_p} > p$. There are $12$ terms in the sequence $1, 1, 2, 3, 5, \ldots, 144$, so this means that $n \leq 12$ cannot work - just remove the rightmost term! Step two: Showing $n > 12$ work We can use contradiction for this part. If some $n$ for $n>12$ didn't work, then the sequence $\sqrt{1}, \sqrt{1}, \sqrt{2}, \sqrt{3}, \sqrt{5}, \sqrt{8}, \ldots \sqrt{F_p}$ would be the not-working sequence, and we'd have to have $p > 12$. But as shown above this doesn't work, contradiction. Combining these two parts, only $n>12$ for integer $n$ works. $\blacksquare$
26.09.2022 16:01
We claim that the answer is $ n>12$ for integer $n$ WLOG let: $a_{1} \leq a_{2} \leq a_{3}$ ...... $a_{n-2} \leq a_{n-1} \leq a_{n}$ With a little bit of induction and minimization we see that for there to have to exist an acute triangle we need $n>\sqrt{F_{n}}$ Where $F_{n}$ denotes the nth fibonacci number we find that this works for all integer $n > 12$ $\blacksquare$ Remarks: Nice beginner oly problem cool how fibonaaci likes to so up in triangle inequalities Couldn't solve when awake yesterday I just woke up and knew how to solve it lol
20.03.2023 04:21
This was in an email I got from MAA for practice problems. WLOG, let $a_1=1,$ because we can always scale up the set. Also, let $a_i\geq a_j$ for all $i>j$ Let us first try not for acute triangles, but nondegenerate triangles. To find a set which does not work, we have $a_n=a_{n-1}+a_{n-2}$ We end up getting $1, 1, 2, 3, 5, 8, \cdots$ However, we have a limit for $a_n,$ so for $n>5,$ there exists a triangle. Now on to the slightly harder part, the acute triangle. By the Pythagorean Inequalities, $c^2<a^2+b^2$ for sides $a, b, $ and $c$ of an acute triangle. Using this, we can try constructing a set which does not work with the recursive formula being $a_n=\sqrt{a^2_{n-1}+a^2_{n-2}}.$ We get the set $1, 1, \sqrt{2}, \sqrt{3}, \sqrt{5}, \cdots$ Every $a_n$ is the square root of the next Fibonacci number. The first time where $a_n>n$ is when $n=13,$ as $a_{12}=\sqrt{144}=12.$ We can inductively show that all square roots of Fibonacci numbers for $n>13$ are greater than their respective $n.$ The answer is all integers $\boxed{n\geq13}$
09.08.2023 01:30
First assume WLOG $a_1=1$ Then we prove by induction that $a_n\geq\sqrt{F_n}$ where $F_n$ is the nth Fibonacci number. Then by induction again we see that $F_n>n^2$ if $n>12$ That violate condition $a_n<n$, so $n>12$ impossible Full proof here: https://infinityintegral.substack.com/p/usajmo-2012-contest-review
30.11.2023 05:04
funny Define the Fibonacci numbers as follows: $F_1 = 1, F_2 = 1$, and $F_n = F_{n-1} + F_{n-2}$ for $n\ge 3$. WLOG, let $a_1\le a_2\le \cdots \le a_n$ We claim that if it is impossible to choose three numbers in a sequence of $n$ positive real numbers $a_1, a_2, \ldots, a_n$ such that the three numbers can be the side lengths of an acute triangle, then $a_i \ge a_1\sqrt{F_i}$ for all $i = 3, 4, \ldots ,n$. We will prove this using induction. The base case, $i = 3$ is easy to see; we have $a_3^2 \ge a_1^2 + a_2^2 \ge 2a_1^2\implies a_3 \ge \sqrt{2} a_1$. Now, assume $a_i\ge a_1\sqrt{F_i}$ for all $i = 4, 5, \ldots, n$. Notice that $a_{i-1} \ge a_1\sqrt{F_{i-1}}\implies a_{i-1}^2 \ge a_1^2\cdot F_{i-1}$ and similarly $a_i^2\ge a_1^2\cdot F_i$. Thus, we know that $a_i^2 + a_{i-1}^2 \ge a_1^2\cdot F_{i+1}$. Because we want the triangle with side lengths $a_{i+1}, a_i, a_{i-1}$ to not be acute, we have $a_{i+1}^2 \ge a_i^2 + a_{i-1}^2$, so $a_{i+1}^2 \ge a_1^2 \cdot F_{i+1}\implies a_{i+1} \ge a_1 \sqrt{F_{i+1}}$, as desired. Note that for $n\ge 13$, we have that $\sqrt{F_n} > n$. We again prove this using induction; the base case is trivial to see. We have $F_n > n^2$ and $F_{n-1} > (n-1)^2 = n^2-2n+1$ from the inductive hypothesis. Thus, $F_{n+1} = F_n + F_{n-1} > (n+1)^2 + n^2-4n > (n+1)^2\implies \sqrt{F_{n+1}} > n+1$. AFTSOC that all $n\ge 13$ fail. This tells us that $a_n \ge a_1\sqrt{F_n}>a_1n$, contradiction, so all $n\ge 13$ work. All $n < 13$ fail by taking the construction $a_1, \sqrt{F_2}a_1, \sqrt{F_3} a_1,\ldots, \sqrt{F_n} a_n$. Thus, our answer is all $n\ge 13$. $\blacksquare$
04.01.2024 15:47
Answer: $n \geq 13$ Define the sequence $F_1 = 1, F_2 = 1$ and $F_n = F_{n-1} + F_{n-2}$ for $n \geq 3$. Now for $n \leq 12$, $F_n \leq n^2$ and if $n \geq 13$, then $F_n > n^2$ So if we have $n \leq 12$ real numbers $a_1, a_2, a_3 \dots a_{n}$, then the following construction of numbers allows there to be no acute triangles while obeying $\max(a_1, a_2, a_3 \dots a_{n}) \leq n\min(a_1, a_2, a_3 \dots a_{n})$: We set $a_i = \sqrt{F_i}$. For $k \geq 3$, there exist no two indices $i, j < k$ such that $a_i^2 + a_j^2 > a_k^2$ since $a_i^2 + a_j^2 \leq a_{k-2}^2 + a_{k-1}^2 = F_{k-2} + F_{k-1} = F_{k}$. Now suppose $n \geq 13$. Without loss of the generality, let $a_1 \leq a_2 \leq a_3 \leq \dots a_n$. For the sake of contradiction say there exist no three side lengths forming an acute triangle. Then it must be true that $a_3^2 \geq a_2^2 + a_1^2 \geq 2a_1^2 \implies a_4^2 \geq a_3^2 + a_2^2 \geq 3a_1^2 \implies a_5^2 \geq a_4^2 + a_3^2 \geq 3a_1^2 + 2a_1^2 = 5a_1^2$. Continuing this chain, we see that $a_n^2 \geq F_na_1^2 \implies a_n \geq \sqrt{F_n}a_1 > na_1$ which is a contradiction.
10.03.2024 03:49
The answer is all $n \ge 13$. Note that positive reals $x < y < z$ can be the sides of an acute triangle iff $x^2 + y^2 > z^2$ by the law of cosines. Define the Fibonacci sequence $F_{k \{k \ge 0\}}$ such that $F_0 = 0, F_1 = 1$, and $F_k = F_{k - 1} + F_{k - 2}$ for $k \ge 2$. For $n \le 12$, we can set $a_i = \sqrt{F_i}$ for $1 \le i \le n$. Then for $1 \le i < j < k \le n$, we have $a_i^2 + a_j^2 \le F_{j - 1} + F_j = F_{j + 1} \le a_k^2$, so $(a_i, a_j, a_k)$ cannot be the sides of an acute triangle. Now, we will show that all $n \ge 13$ satisfy the problem condition. Assume WLOG that $a_1 \le a_2 \cdots \le a_n$ and suppose ftsoc no three $a_i$ form an acute triangle. Claim: For $1 \le k \le n$, we have $a_k^2 \ge F_ka_1^2$. Proof: We prove this by strong induction on $k$. For the base cases of $k = 1, 2$ this is evident as $F_1 = F_2 = 1$. Then, for the inductive step, suppose that it holds the claim holds for $a_1, a_2, \ldots, a_k$. For $k + 1$, we note that $a_{k + 1}^2 \ge a_k^2 + a_{k - 1}^2 \ge F_ka_1^2 + F_{k - 1}a_1^2 = F_{k + 1}a_1^2$, so the claim is proven. Now, we note by the claim that $a_n^2 \ge F_na_1^2$. But by an inductive argument, we have $F_n > n^2$ for $n \ge 13$, so $a_n^2 > n^2a_1^2$, which violates the condition that $na_1\ge a_n$. This gives the desired contradiction.
11.03.2024 18:14
WLOG $a_1 \le a_2 \le ... \le a_n$. Note that for a triangle with sides $a \le b \le c$ to be acute, $a^2+b^2 > c^2$ must be true. Let's proceed by finding all $n$ such that there exists a sequence $a_1,a_2,...,a_n$ that does not include three elements that form the side lengths of an acute triangle. Note that if $a_{i-a},a_i,a_{i+b}$ form an acute triangle, then $a_{i-a+1},a_i,a_{i+b-1}$ is also an acute triangle if $a,b > 1$. This condition reduces to for every $i$ in $1 \le i \le n-2$, $$a_i^2+a_{i+1}^2 \le a_{i+2}^2$$is true. Setting $a_i=k_i*a_1$, we get $1=k_1 \le k_2 \le k_3 ... \le k_n \le n$. We have \begin{align*} 1+k_2^2 \le k_3^2 \\ k_2^2+k_3^2 \le k_4^2 \\ . . . k_{n-2}^2+k_{n-1}^2 \le k_n^2 \\ \end{align*} From this, we get that \begin{align*} k_1^2 = 1 \\ k_2^2 \ge 1 \\ k_3^2 \ge 2 \\ k_4^2 \ge 3 \\ . . . k_n^2 \ge F_{n-1} \\ \end{align*} Where $F_a$ denotes the $a$th term of the Fibonacci sequence with $F_0=F_1=1$. We see that at $k_{12}^2 \ge 144$ and $k_{13}^2 \ge 233$. We claim that for all $3 \ge n \ge 12$, there exists a sequence $a_1,a_2,...,a_n$ satisfying problem conditions and have not distinct elements that form the sides lengths of an acute triangle. Indeed this is true because for $F_{i-1} \ge k_i \ge i^2$ for all $i$ in the range. Now we have to prove that for all $n \ge 13$, $F_{n-1} > n^2$. We will proceed by Proof by Induction. Assume $F_{n-2} > (n-1)^2$. Then $F_{n-2}+2n-1 > n^2$ and hence showing $F_{n-1} \ge F_{n-2}+2n-1$ or $F_{n-3} \ge 2n-1$ would be sufficient. This is true for all $n \ge 13$ via Proof by Induction as follows: Let $F_{n-4} \ge 2(2n-1)-1$. Then for $F_{n-3} \ge 2n-1$ to be true, $F_{n-5} \ge 2$, both the assumption and the condition are true for all $n \ge 13$, and we are done.
12.03.2024 01:13
Lemma: Define $F_0 = 0$ and $F_1 = 1$, with $F_n = F_{n-1} + F_{n-2}$ for $n \geq 2$. Then, for all $n \geq 13$, $F_n > n^2$. We can easily verify this holds for $n = 13$ and $n = 14$. Suppose $n' \geq 15$ and assume it holds for $n = n'-1$ and $n = n'-2$. Then, $F_{n'} = F_{n'-1} + F_{n'-2} > (n' - 1)^2 + (n' - 2)^2 = 2n'^2 - 6n' + 5 = n'^2 + (n' - 1)(n' - 5)$. Clearly, the RHS expression is greater than $n'^2$, which finishes our proof by induction. Claim: All $n \geq 13$ satisfy the problem condition. Suppose $n \geq 13$. We assume to the contrary that there do not exist three numbers $a_i, a_j, a_k$ that are the side lengths of an acute triangle. For three numbers $a_i, a_j, a_k$ to be the side lengths of an acute triangle, we must have: 1. Triangle inequality: \begin{align*} a_i + a_j &> a_k \\ a_j + a_k &> a_i \\ a_i + a_k &> a_j \\ \end{align*} 2. Acute condition (derived from Law of Cosines): \begin{align*} a_i^2 + a_j^2 &> a_k^2 \\ a_j^2 + a_k^2 &> a_i^2 \\ a_i^2 + a_k^2 &> a_j^2. \\ \end{align*} If we WLOG $a_i \leq a_j \leq a_k$, then we find that the single condition $a_i^2 + a_j^2 > a_k^2$ is enough to imply the other conditions. So, we re-index $a_1, a_2, \ldots, a_n$ such that $a_1 \leq a_2 \leq \cdots \leq a_n$. According to our initial assumption to the contrary, \begin{align*} a_1^2 + a_2^2 &\leq a_3^2 \\ a_2^2 + a_3^2 &\leq a_4^2 \\ &\vdots \end{align*}and so on. Then, \begin{align*} a_4^2 &\geq a_2^2 + a_3^2 \geq 2a_2^2 + a_1^2 \geq 3a_1^2, \\ a_5^2 &\geq a_3^2 + a_4^2 \geq 5a_1^2, \\ \ldots a_{n}^2 &\geq F_n a_1^2 \implies a_{n} \geq \sqrt{F_n} a_1 > na_1. \end{align*} And since $\max(a_1, a_2, \ldots, a_n) = a_n$ and $\min(a_1, a_2, \ldots, a_n) = a_1$, we have a contradiction. Next, we show that all $n \leq 12$ doesn't work. Consider sequences satisfying $a_i = \sqrt{F_i}$ for all $1 \leq i \leq n$. We can check that the min max condition is satisfied as long as $n \leq 12$. Then, if $i<j<k$, we have $a_k^2 = F_k = F_{k-1} + F_{k-2} \geq F_{i} + F{j} = a_i^2 + a_j^2$, so $a_i, a_j, a_k$ do not form an acute triangle. Thus, the sequence does not work and we have shown that only $n \geq 13$ work.
12.05.2024 15:37
This took me 12 hours, ironic. Let's say we have integer $n$ and sequence $(a_1,a_2,\hdots,a_n)$ that does not satisfy the condition. WLOG let $a_1 \leq a_2 \leq \hdots \leq a_n$. From the law of cosines, we can see that if triangle has sides with lengths $a\leq b\leq c$ and $a^2 + b^2 \leq c^2$, it is not acute. By our assumption, we have $a_3^2 \geq a_2^2+a_1^2$ $a_4^2 \geq a_3^2+a_2^2$ ..... $a_n^2 \geq a_{n-1}^2+a_{n-2}^2$. Then we have $a_n^2 \geq F_{n-1}a_2^2+F_{n-2}a_1^2$. Since, $a_n \leq na_1$ and $a_1 \leq a_2 $, we get $n^2 \geq F_n$. To satisfy this, we need to have $n \leq 12 $.
20.05.2024 00:35
assume the first number is 1 then, to make sure there are no acute triangles, it goes like 1 a >=sqrt(1+a^2) >=sqrt(1+2a^2) >=sqrt(2+3a^2) >=sqrt(3+5a^2) ... >=sqrt(F(n-3)+F(n-2)a^2)<=n where F(0)=F(1)=1 and F(n)=F(n-1)+F(n-2) F(n-3)+F(n-2)a^2<=n^2 a^2<=(n^2-F(n-3))/F(n-2)>=1 Note that $F$ grows exponentially, so once it becomes less than $1$ it will remain less than $1$ Get that when $n=12$ it equals $1$ and past that, it is less than $1$ so there must be an acute and the answer is $\boxed{n \ge 13}$
29.10.2024 16:01
I think the the answer is n≥12, because they need ti be "DIFFERENT" so 12 is also OK.
22.11.2024 05:47
ryanbear wrote: assume the first number is 1 then, to make sure there are no acute triangles, it goes like 1 a >=sqrt(1+a^2) >=sqrt(1+2a^2) >=sqrt(2+3a^2) >=sqrt(3+5a^2) ... >=sqrt(F(n-3)+F(n-2)a^2)<=n where F(0)=F(1)=1 and F(n)=F(n-1)+F(n-2) F(n-3)+F(n-2)a^2<=n^2 a^2<=(n^2-F(n-3))/F(n-2)>=1 Note that $F$ grows exponentially, so once it becomes less than $1$ it will remain less than $1$ Get that when $n=12$ it equals $1$ and past that, it is less than $1$ so there must be an acute and the answer is $\boxed{n \ge 13}$ Yeah the answer is right but I don’t really understand the reasoning
23.12.2024 06:24
problem dies to eq nuke, brief sketch of sol Recall that positive reals $x \le y \le z$ are lengths of an acute triangle if and only if $x^2 + y^2 > z^2$. Also let $F_n$ be the $n$-th Fibonacci number. We claim the answer is all $n \ge 13$. To show the condition is not met for $n \le 12$, consider the set \[ \{ \sqrt{F_1}, \sqrt{F_2}, \dots, \sqrt{F_n} \}. \]Clearly, no triples can form lengths of an acute triangle, and $\sqrt{F_n} \le n \cdot 1$ subject to the range. Now to show all $n \ge 13$ must work, for the sake of contradiction assume some set does not contain any triple that can be lengths of an acute triangle. WLOG $a_1 \le a_2 \le \dots \le a_n$. From $a_1 \le a_2$, it is easy to induct upwards the relation $F_n a_1^2 \le a_n^2$, but we also have $a_n^2 \le n^2 a_1^2$ then $F_n \le n^2$. This fails when $n \ge 13$ (this is trivial to prove) hence contradiction. We are done.
01.01.2025 06:26
The answer is all $n\ge 13$. WLOG, let $1=a_1 \le a_2 \le \cdots \le a_n \le n$. Recall that a triangle with side lengths $x\ge y\ge z$ is acute if and only if $x^2 < y^2+z^2$; we will use this fact throughout our proof. Also, let $F_n$ denote the $n^\text{th}$ Fibonacci number, where $F_1=F_2=1$ and $F_{n} = F_{k-1}+F_{k-2}$ for all valid $k\ge 3$. Crucially, note that if $n < 13$, then $F_n \le n^2$, and if $n\ge 13$, then $F_n > n^2$. If $n< 13$, consider $a_n = \sqrt{F_n}$, which satisfies $1=a_1 \le a_2 \le \cdots \le a_n \le n$. Then, if $1\le i < j < k \le n$ are indices, we have $a_i^2 + a_j^2 \le a_{k-2}^2 + a_{k-1}^2 = a_k^2$, and hence $a_i$, $a_j$, and $a_k$ are not the side lengths of an acute triangle. Now, we show that if $n\ge 13$, there exist $a_i$, $a_j$, and $a_k$ that are the side lengths of an acute triangle. Assume the contrary, and let $a_2 = r\ge 1$. Then, we must have \begin{align*} a_3^2 &\ge r^2 +1 \\ a_4^2 &\ge a_3^2 + a_2^2 \ge 2r^2+1 \\ a_5^2 &\ge a_4^2+a_3^2 \ge 3r^2+2 \\ &\vdots \\ a_n^2 &\ge a_{n-1}^2 + a_{n-2}^2 \ge F_{n-1}r^2+F_{n-2} \ge F_n > n^2.\end{align*}This gives us a contradiction and completes the proof. $\blacksquare$