For each positive integer $n \ge 3$, define $A_n$ and $B_n$ as \[A_n = \sqrt{n^2 + 1} + \sqrt{n^2 + 3} + \cdots + \sqrt{n^2+2n-1}\]\[B_n = \sqrt{n^2 + 2} + \sqrt{n^2 + 4} + \cdots + \sqrt{n^2 + 2n}.\]Determine all positive integers $n\ge 3$ for which $\lfloor A_n \rfloor = \lfloor B_n \rfloor$. Note. For any real number $x$, $\lfloor x\rfloor$ denotes the largest integer $N\le x$. Anant Mudgal and Navilarekallu Tejaswi
Problem
Source: INMO 2024/6
Tags: floor function, INMO 2024, INMO
21.01.2024 15:23
The answer is odd $n$. Use binomial approximation.
21.01.2024 15:53
Proposed by Anant Mudgal and Navilarekallu Tejaswi
21.01.2024 18:27
$ (n+\frac{k-1}{n})^2<n^2+2k-1<(n+\frac{2k-1}{2n})^2$ for $1 \leq k \leq n$ So $ n^2+\frac{n-1}{2}<A_n< n^2+\frac{n}{2}$ $(n+\frac{2k-1}{2n})^2<n^2+2k<(n+\frac{k}{n})^2$ for $1 \leq k \leq n$ So $ n^2+\frac{n}{2}<B_n<n^2+\frac{n+1}{2}$ If $n$ is even, then $ [A_n]=n^2+\frac{n}{2}-1$ and $[B_n]=n^2+\frac{n}{2}$ If $n$ is odd then $[A_n]=[B_n]=n^2+\frac{n-1}{2}$
21.01.2024 19:05
RagvaloD wrote: $ (n+\frac{k-1}{n})^2<n^2+2k-1<(n+\frac{2k-1}{2n})^2$ for $1 \leq k \leq n$ So $ n^2+\frac{n-1}{2}<A_n< n^2+\frac{n}{2}$ $(n+\frac{2k-1}{2n})^2<n^2+2k<(n+\frac{k}{n})^2$ for $1 \leq k \leq n$ So $ n^2+\frac{n}{2}<B_n<n^2+\frac{n+1}{2}$ If $n$ is even, then $ [A_n]=n^2+\frac{n}{2}-1$ and $[B_n]=n^2+\frac{n}{2}$ If $n$ is odd then $[A_n]=[B_n]=n^2+\frac{n-1}{2}$ wow! solution!
22.01.2024 07:06
Probably my most cursed solve in exam.
22.01.2024 07:12
hellomath010118 wrote: Probably my most cursed solve in exam.
Did you write this solution in the test ors ors ors
22.01.2024 10:39
Using integral. We assume $n\ge 3$ is throughout. Define the function $f(x) = x^{\frac{1}{2}}$ on the domain $\mathbb{R}_{>0}$. Let $ I = \int_{n^2}^{(n+1)^2}f(x)dx = \left[\frac{2}{3}x^{\frac{3}{2}}\right]_{n^2}^{(n+1)^2} = 2n^2+2n+\frac{2}{3}$. Since $f(x)$ is concave, the tangents lie above the graph of $f$. Therefore, $\int_{y-1}^{y+1}f(x)dx < 2f(y)$ for any $y>1$. Summing over $y = n^2 +2i-1$, where $i$ varies from $1$ to $n$, we get, $ A_n > \frac{1}{2}\int_{n^2}^{n^2+2n}f(x)dx > \frac{1}{2}\left(I - f((n+1)^2)\right) = n^2 + \frac{n}{2} - \frac{1}{6}$ Summing over $y = n^2 +2i$, where $i$ varies from $1$ to $n$, we get, $ B_n > \frac{1}{2}\int_{n^2+1}^{(n+1)^2}f(x)dx > \frac{1}{2}\left(I - f(n^2+1)\right) = n^2 + n +\frac{1}{3} - \frac{\sqrt{n^2+1}}{2}$ Also, secants lie below the graph of $f$. Therefore, $f(y-1)+f(y+1) < \int_{y-1}^{y+1}f(x)dx$ for all $y>1$. Summing over $y = n^2 +2i$, where $i$ varies from $1$ to $n$, we get, $ 2 A_n - f(n^2 +1) + f((n+1)^2) < \int_{n^2 + 1}^{(n+1)^2}f(x)dx < I - f(n^2) = I - n \implies A_n < \frac{1}{2}\left( I +\sqrt{n^2+1} - 2n -1\right) = n^2 + \frac{\sqrt{n^2 + 1}}{2} -\frac{1}{6}$ Summing over $y = n^2 +2i-1$, where $i$ varies from $1$ to $n$, we get, $ 2 B_n - f(n^2 +2n) + f(n^2) < \int_{n^2 }^{n^2 + 2n}f(x)dx < I - f(n^2+2n) \implies B_n < \frac{1}{2}\left( I - n \right) = n^2 + \frac{n}{2} +\frac{1}{3}$ Using the four inequalities obtained above, we get $n^2 + \frac{n-1}{2} < A_n < n^2 +\frac{n}{2}$ and $n^2 + \frac{n+1}{2} > B_n > n^2 + \frac{n}{2}$. ( Since $\sqrt{n^2+1} < n + \frac{1}{3}$) Therefore $\lfloor A_n \rfloor = \lfloor B_n \rfloor$ if and only if $n$ is odd. Hope I did not make any calculation errors.
22.01.2024 11:31
@above I do remember getting $1/3$ and $1/6$ in my final expressions so it is probably correct.
22.01.2024 11:50
Observe : $\quad n^2<n^2+k<(n+1)^2,\quad \Rightarrow \lfloor \sqrt{n^2+k} \rfloor = n.$ Claim : We claim that the following holds : $$ \frac{k-1}{2 n}<\left\{\sqrt{n^2+k}\right\}<\frac{k}{2n} . \quad \forall \, n \geq 3 , \quad k \in \{1, 2, ... 2n\}$$ Proof: Observe: $\{\sqrt{n+k}\} > \frac{k-1}{2n}$ $$ \Leftrightarrow \left\lfloor\sqrt{n^2+k}\right\rfloor + \{\sqrt{n^2+k}\} > \left\lfloor\sqrt{n^2+k}\right\rfloor + \frac{k-1}{2n} $$ $$ \Leftrightarrow \sqrt{n^2+k} > n + \frac{k-1}{2n} $$ Squaring both sides, we have: $$ \Leftrightarrow n^2+k > n^2 + \frac{(k-1)^2}{4n^2} + k-1 \Leftrightarrow \frac{(2n)^2}{(k-1)^2} > 1 $$ which is obvious Now, For the other inequality notice that the inequality is equivalent to proving that $$\sqrt{n^{2}+k}<n+\frac{k}{2n}$$which is again obvious by squaring. Now getting back to our problem, $\begin{aligned} & \left\lfloor A_n \right\rfloor = \left\lfloor \sqrt{n^2+1} + \sqrt{n^2+3} + \cdots + \sqrt{n^2+2n-1} \right\rfloor \\ & = \left\lfloor \left\lfloor \sqrt{n^2+1} \right\rfloor + \left\lfloor \sqrt{n^2+3} \right\rfloor + \cdots + \left\lfloor \sqrt{n^2+2n-1} \right\rfloor + \left\{ \sqrt{n^2+1} \right\} + \cdots + \left\{ \sqrt{n^2+2n-1} \right\} \right\rfloor \\ & = \lfloor \underbrace{n + n + \cdots + n}_{n \text{ times}} + \{ \sqrt{n+1} \} + \cdots + \{ \sqrt{n^2+2n-1} \} \rfloor \\ & = n^2 + \underbrace{\left\lfloor \left\{ \sqrt{n^2+1} \right\} + \cdots + \left\{ \sqrt{n^2+2n-1} \right\} \right\rfloor}_{\lfloor X \rfloor} \\ & =n^2 + \lfloor X \rfloor \end{aligned}$ Similarly : $$ \left\lfloor B_n\right\rfloor=n^2+\underbrace{\left.\left.\left\lfloor\sqrt{n^2+2}\right\}+\ldots \sqrt{n^2+2 n}\right\}\right\rfloor}_{\lfloor Y \rfloor} \Rightarrow\quad \left\lfloor B_n\right\rfloor=n^2 + \lfloor Y \rfloor $$Now $A_n$=$B_n$. $ \Leftrightarrow\lfloor X \rfloor=\lfloor Y \rfloor $. Now $\begin{aligned} & \frac{1}{2 n} \sum_{k=o d d} k-1<X<\frac{1}{2 n} \sum_{k=\text { odd }} k . \\ & \frac{1}{2 n}(0+2+\cdots+2 n-2)<X<\frac{1}{2 n}(1+3 \cdots+2 n-1) . \\ \Rightarrow & \frac{1}{n} \frac{(n-1) \cdot n}{2}<X<\frac{n^2}{2 n} \\ \Rightarrow & \frac{n-1}{2}<X<\frac{n}{2} . \cdots(1)\\\text{again}\\ & \frac{1}{2 n} \sum_{k=\text { even }} k-1<Y<\frac{1}{2 n} \sum_{k=\text { even }} k \\ = & \frac{1}{2 n} 2\left(1+3 \cdots+2 n-1\right)<Y<\frac{1}{2 n} 2(1+\cdots+n) . \\ = & \frac{n}{2}<y<\frac{n+1}{2}\cdots(2) . \end{aligned}$ Now if $n=$ even say $n=2 k$. $$ \begin{aligned} & \frac{2 k-1}{2}<X<\frac{2 k}{2} \Rightarrow\lfloor X\rfloor=k-1 \\ & \frac{2 k}{2}<Y<\frac{2 k+1}{2} \Rightarrow\lfloor Y\rfloor=k . \end{aligned} $$so not possible. if $n=$ odd say $n=2 k+1$ $$ \begin{aligned} & \frac{2 k}{2}<X<\frac{2 k-1}{2} \Rightarrow\lfloor X\rfloor=k . \\ & \frac{2 k+1}{2}<Y<\frac{2 k+2}{2} \Rightarrow\lfloor Y\rfloor=k . \end{aligned} $$Since all these are if and only if statements so the equality $\left\lfloor A_n\right\rfloor=\left\lfloor B_n\right\rfloor$ holds for all odd numbers $\geqslant 3$. $\blacksquare$
23.01.2024 02:49
Claim: $ \frac{1}{2(x+1)} <\sqrt{x^2+n+1} - \sqrt{x^2 +n}< \frac{1}{2x}$ for $x \geq 3$ and $n \leq 2x$ Proof: $(\sqrt{x^2+n+1} + \sqrt{x^2 +n} )(\sqrt{x^2+n+1} - \sqrt{x^2 +n} ) = 1$ $\implies \frac{1}{2(x+1)} < \frac{1}{\sqrt{x^2+n+1} + \sqrt{x^2 +n}} < \frac{1}{2x}$ Now $ \frac{1}{2(x+1)} < \sqrt{x^2+n+1} - \sqrt{x^2 +n} < \frac{1}{2x} \implies \frac{1}{2(n+1)} < \sqrt{n^2+2k+2} - \sqrt{n^2 +2k+1} < \frac{1}{2n} $ $\implies \frac{n}{2(n+1)} < B_n - A_n <\frac{1}{2} $ Now for $k < 2n+1$ we have $ 2n+ 1 < \sqrt{n^2+k} + \sqrt{n^2+2n+1-k} < 2\sqrt{n^2+n+\frac{1}{2}} $ $\implies 2n\sqrt{n^2+n+\frac{1}{2}} > B_n +A_n > n(2n+1)$ Simplifying these two inequalities we get $ n \sqrt{n^2+n+\frac{1}{2}} + \frac{1}{4} > B_n > n(n+\frac{1}{2}) +\frac{n}{4(n+1)}$ ,and $ n \sqrt{n^2+n+\frac{1}{2}} + \frac{1}{4} - \frac{n}{2(n+1)} > A_n > n(n+\frac{1}{2}) +\frac{n}{4(n+1)} - \frac{1}{2}$ Now, $\sqrt{n^2+n+\frac{1}{2}} < n + \frac{1}{2}+ \frac{1}{8n}$ Putting this in our equations $n(n+\frac{1}{2})+\frac{3}{8} > B_n > n(n+\frac{1}{2}) +\frac{n}{4(n+1)}$ $n(n+\frac{1}{2}) + \frac{1}{2(n+1)} - \frac{1}{8} > A_n >n(n+\frac{1}{2}) +\frac{n}{4(n+1)} - \frac{1}{2} $ Now for even $n$ , $[B_n]=n^2+\frac{n}{2}$ and $ [A_n]=n^2+\frac{n}{2}-1$ and for odd $n$, $[A_n]=[B_n]=n^2+\frac{n-1}{2}$
30.03.2024 23:29
We claim that all odd $n$ work and no even $n$ work. It is clear that $B_n>A_n$ for all $n$. Claim: \[\frac{n^2}{2n+1}<A_n-n^2<\frac n2, \ \ \ (\spadesuit)\]\[\frac{n(n+1)}{2n+1}<B_n-n^2<\frac {n+1}2. \ \ \ (\clubsuit)\] Proof. Note that \[A_n-n^2=\sum_{i=1}^{n}\sqrt{n^2+2i-1}-n=\sum_{i=1}^{n}\frac{2i-1}{n+\sqrt{n^2+2i-1}}\]Also, $\frac{2i-1}{2n+1}<\frac{2i-1}{n+\sqrt{n^2+2i-1}}<\frac{2i-1}{2n}$, which gives \[\frac{n^2}{2n+1}=\frac1{2n+1}\sum_{i=1}^{n}(2i-1)<A_n-n^2=\sum_{i=1}^{n}\frac{2i-1}{n+\sqrt{n^2+2i-1}}<\frac1{2n}\sum_{i=1}^{n}(2i-1)=\frac{n^2}{2n}=\frac n2,\]which proves $(\spadesuit)$. Similarly, we have \[\frac{n(n+1)}{2n+1}=\frac1{2n+1}\sum_{i=1}^{n}2i<B_n-n^2=\sum_{i=1}^{n}\frac{2i}{n+\sqrt{n^2+2i}}<\frac1{2n}\sum_{i=1}^{n}2i=\frac{n(n+1)}{2n}=\frac{n+1}2,\]which proves $(\clubsuit)$. Hence, the claim is true. $\blacksquare$ Note that since $n>0$, $\frac{n^2}{2n+1}>\frac{n-1}2$ and using $(\spadesuit)$ gives $\frac{n-1}2<A_n-n^2$. Similarly, we have $\frac{n(n+1)}{2n+1}>\frac n2$ and using $(\clubsuit)$ gives $\frac n2<B_n-n^2$. Combining, we have \[\frac n2-1<\frac{n-1}2<\frac{n^2}{2n+1}<A_n-n^2<\frac n2<\frac{n(n+1)}{2n+1}<B_n-n^2<\frac{n+1}2<\frac n2+1. \ \ \ (\star)\]Hence, if $n$ is even, then $\frac n2$ is an integer, and $(\star)$ gives \[\lfloor A_n\rfloor=n^2+\frac n2-1\neq \lfloor B_n\rfloor=n^2+\frac n2,\]while if $n$ is odd, then \[\lfloor A_n\rfloor=n^2+\frac{n-1}2=\lfloor B_n\rfloor,\]as required. The proof is complete. $\blacksquare$
04.06.2024 01:38
Revenge!
01.01.2025 23:53
Lemma 1 : B_n - A_n < 1/2 Proof: B_n - A_n = 1/root(n^2 +2) + root(n^2 +1) +................ + 1/root(n^2 + 2n) +1/root(n^2 + 2n + 1) < 1/2n +...... +1/2n n times, or = 1/2 Lemma 2 A_n < n^2 + n/2 < B_n Proof: A_n - n^2 = 1/root(n^2+1) + n + ......................2n-1/root(n^2 + 2n -1) + n (because n^2 can be written as n+n...+n ,n times and then distribute and rationalise) < 1+3+....+2n-1/2n = n^2/2n = 1/2 * n, so A_n < n^2 + 1/2*n B_n - n^2 = 2/root(n^2) + n +................2n/root(n^2 + 2n) +n > 2+4+....6/2n+1 = n(n+1)/2n+1 > n/2(n+1)/(n+1)= 1/2*n or Bn > n^2 + 1/2n, done Now combing lemma 1 and 2 with pinch of common sense (namely considering two cases when n is even so there's an integer n^2 + 1/2*n separating so no solution for even n, and for odd n its done by some trivial floor and ceiling bounds) gives the final solution