Consider fractions $\frac{a}{b}$ where $a$ and $b$ are positive integers. (a) Prove that for every positive integer $n$, there exists such a fraction $\frac{a}{b}$ such that $\sqrt{n} \le \frac{a}{b} \le \sqrt{n+1}$ and $b \le \sqrt{n}+1$. (b) Show that there are infinitely many positive integers $n$ such that no such fraction $\frac{a}{b}$ satisfies $\sqrt{n} \le \frac{a}{b} \le \sqrt{n+1}$ and $b \le \sqrt{n}$.
Problem
Source: 2016 IMO Shortlist A5
Tags: IMO Shortlist, algebra, Fractions, Hi
19.07.2017 20:34
19.07.2017 20:34
Write the main inequality as $nb^2 \le a^2 \le (n+1)b^2$. We first solve part (b) by claiming that $n = x^2+1$ always fails. For concreteness we start by giving an example with $x=10$: $b=1$ gives $101 \le a^2 \le 102$. $b=2$ gives $404 \le a^2 \le 408$. $b=3$ gives $909 \le a^2 \le 918$. \dots $b=10$ gives $10100 \le a^2 \le 10200$. None of these intervals contain squares, by just a little bit. In general, for any $b \le x$ we have \[ (bx)^2 < b^2(x^2+1) \le b^2(x^2+2) < (bx+1)^2 \]and so the interval $[b^2(x^2+1), b^2(x^2+2)]$ contains no squares. As for part (a), write $n = x^2+r$ where $x = \left\lfloor \sqrt n \right\rfloor$. Intuitively want to select $b$ such that $(x^2+r)b^2 \approx (xb)^2$ is just slightly larger than a square; but we want $b$ to be large (close to $x$) to give room to $a$. Letting $a = xb+k$, a good guess is $(x^2+r)b^2 \approx (xb+k)^2$ with $k$ not too big, meaning $b^2r \approx 2bxk$, or $b \approx \frac{2kx}{r}$. Here is the construction: For $r$ even, set $k=r/2$, hence $b = x$. This works, with $a = x^2 + r/2$. For $r$ odd, set $k=\frac{1}{2}(r+1)$, hence $b = x+1$. This works (and is even motivated by (b)), with $a = b^2+b + \frac{1}{2}(r+1)$. We leave the verification of these to the reader.
22.07.2017 05:09
My favorite problem among the algebra problems of this year's shortlist, though it is not hard if you have some knowledge of Farey sequences. For (a), suppose $\sqrt{n}$ and $\sqrt{n+1}$ are irrational and let $t = \left [ \sqrt{n} \right ] = \left [ \sqrt{n+1} \right ] \geq 2$ ($t=1$ case is trivial). The problem statement is equivalent to the fact that there is a element $q$ of $F_{t+1}$ (Farey sequence of order $t+1$) such that $\left \{ \sqrt{n} \right \} < q < \left \{ \sqrt{n+1} \right \}$. Suppose this is not true. Then there exist two consecutive elements $q_1, q_2$ of $F_{t+1}$ such that $\left \{ \sqrt{n} \right \}$ and $\left \{ \sqrt{n+1} \right \}$ are both included in the interval $(q_1, q_2)$. Let $q_1 = \frac{a}{b}$, $q_2 = \frac{c}{d}$ in their irreducible forms. Then $q_2 - q_1 =\frac{1}{bd}$ and hence $\frac{1}{bd} > \sqrt{n+1} - \sqrt{n} = \frac{1}{\sqrt{n+1} + \sqrt{n}} > \frac{1}{2t+2}$. So $bd \leq 2t+1$ but since $b+d > t+1$, there are only four possibilities $(b, d) = (1, t+1), (t+1, 1), (t, 2), (2, t)$ which are equivalent to $\left (q_1, q_2 \right ) = \left (0, \frac{1}{t+1} \right ), \left (\frac{t}{t+1}, 1 \right ), \left (\frac{t-1}{2t}, \frac{1}{2} \right ), \left (\frac{1}{2}, \frac{t+1}{2t} \right )$ respectively. It is easy to check that each of these cases is impossible. For (b), $n=t^2+1$ for any positive integer $t$ works since $\sqrt{n}$ and $\sqrt{n+1}$ both belong in interval $\left (0, \frac{1}{t} \right )$, where $0$ and $\frac{1}{t}$ are consecutive elements of $F_t$.
31.07.2017 03:07
We tackle part (a) first by dealing with all integers $n$ from $s^2 + 1$ to $(s + 1)^2$ inclusive. Obviously $a = b = 1$ works for $n = 1$. We'll split into cases. Case 1: $n = s^2 + 2k$ where $s$ is a positive integer and $1 \le k \le s$ is an integer. We claim that $a = s^2 + k$, $b = s$ works. Squaring both sides of the given inequality yields $$s^2 + 2k \le \left(\frac{s^2 + k}{s}\right)^2 \le s^2 + 2k + 1 \rightarrow \frac{s^2 + 2k}{s^2 + k} \le \frac{s^2 + k}{s^2} \le \frac{s^2 + 2k + 1}{s^2 + k}.$$This inequality boils down to $\frac{k}{s^2 + k} \le \frac{k}{s^2} \le \frac{k + 1}{s^2 + k}$. The left inequality is obvious, while the right inequality becomes $ks^2 + k^2 \le ks^2 + s^2$ $\rightarrow k^2 \le s^2$, which is true because $1 \le k \le s$. Hence, this choice for $a$, $b$ works. Case 2: $n = s^2 + 2k + 1$ where $s$ is a positive integer and $0 \le k \le s$ is an integer. We claim that $a = s(s + 1) + k + 1$, $b = s + 1$ works. Likewise, we square both sides of the given inequality, leaving us with $$s^2 + 2k + 1 \le \left(\frac{s^2 + s + k + 1}{s + 1}\right)^2 \le s^2 + 2k + 2 \rightarrow \frac{s^2 + 2k + 1}{s^2 + s + k + 1} \le \frac{s^2 + s + k + 1}{s^2 + 2s + 1} \le \frac{s^2 + 2k + 2}{s^2 + s + k + 1}.$$This inequality is messier than the previous one we dealt with, but we'll use some more algebraic manipulations to verify it. The left inequality boils down to $\frac{k - s}{s^2 + s + k + 1} \le \frac{k - s}{s^2 + 2s + 1}$. If $k = s$, we get $0 = 0$, which leaves us to check $s^2 + 2s + 1 \ge s^2 + s + k + 1 \rightarrow 2s \ge s + k$ since $k - s$ is negative from $k < s$. But $2s \ge s + k$ is obvious. The right inequality boils down to $\frac{k - s}{s^2 + 2s + 1} \le \frac{k - s + 1}{s^2 + s + k + 1}$. Cross-multiplying and subtracting $(k - s)(s^2 + 2s + 1)$ from both sides yields $(k - s)^2 \le s^2 + 2s + 1$. This becomes $k^2 - 1 = (k - 1)(k + 1) \le 2s(k + 1)$. Since $k - 1 \le 2s$, the inequality is true. So, this choice of $a$ and $b$ works, solving part (a). For part (b) we can just show that $n = s^2 + 1$ fails. In part (a) we have established that choosing $a = s^2 + 1$, $b = s$ yields that $\frac{a}{b}$ is greater than or equal to $\sqrt{s^2 + 2} = \sqrt{n + 1}$. However, since $s$ is a positive integer, $\sqrt{n + 1}$ is irrational, and since $\frac{a}{b}$ is rational, it must be greater than $\sqrt{n + 1}$. But then, $\frac{a}{b} = \frac{s^2 + 1}{s}$ is the smallest possible value of $\frac{a}{b}$ we can have given that $1 \le b \le \sqrt{n}$. So no choices of integers $a$, $b$ work if $n = s^2 + 1$, and we're done.
02.09.2017 16:23
I hope this gives a somewhat "less messy" solution to part (a) (without knowledge of Farey sequence). Suppose $k\leq\sqrt{n} < k+1$ and write $n = k^2+r$ with $0\leq r\leq 2k$. Observe that $$ \sqrt{n} - k = \frac{n-k^2}{\sqrt{n}+k} = \frac{r}{\sqrt{n}+k}\leq \frac{r}{k+k} = \frac{r}{2k} $$and $$ \sqrt{n+1} - k = \frac{n-k^2+1}{\sqrt{n+1}+k} = \frac{r+1}{\sqrt{n+1}+k}\geq \frac{r+1}{(k+1)+k} = \frac{r+1}{2k+1}. $$Recall the fact that $\frac{x+z}{y+z}\geq\frac{x}{y}$ whenever $y\geq x > 0$ and $z\geq 0$, which tells us that $$ \sqrt{n}\leq k+\frac{r}{2k}\leq k + \frac{r+1}{2k+1}\leq \sqrt{n+1} $$If $r$ is even, then we can cancel a common factor in the fraction $\frac{r}{2k}$, so we can take the fraction $\frac{a}{b} = k + \frac{r}{2k}$. If $r$ is odd, consider $s := (k+1)^2 - n = 2k-r+1$ (which is even whenever $r$ is odd), and observe that $$ (k+1) - \sqrt{n} = \frac{(k+1)^2-n}{(k+1)+\sqrt{n}} = \frac{s}{(k+1)+\sqrt{n}} \geq \frac{s}{(k+1) + (k+1)} = \frac{s}{2(k+1)} $$and $$ (k+1) - \sqrt{n+1} = \frac{(k+1)^2-n-1}{(k+1)+\sqrt{n+1}} = \frac{s-1}{(k+1)+\sqrt{n+1}}\leq \frac{s-1}{(k+1)+k} = \frac{s-1}{2k+1}. $$Again, we get $$ \sqrt{n}\leq (k+1)-\frac{s}{2(k+1)}\leq (k+1)-\frac{s-1}{2k+1}\leq\sqrt{n+1}, $$so we can pick the fraction $\frac{a}{b} = (k+1) - \frac{s}{2(k+1)}$.
09.12.2017 05:06
a) Let $m = \left\lfloor \sqrt n \right\rfloor$. So $m+1 = \left\lceil \sqrt {n+1} \right\rceil$. Notice that $2|n-m^2$ or $2|n-(m+1)^2$. WLOG, let $2|n-m^2$ and $k=\frac{n-m^2}{2}$. We know that $\frac{k}{m+1}\le \frac{2k}{2m+1} \le \sqrt{n}-m=\frac{2k}{m+\sqrt{n}} \le \frac{2k}{2m}=\frac{k}{m}$. Similarly for all other n, if $p=\frac{(m+1)^2-n}{2}$ then $\frac{p}{m+1}= \frac{2p}{2m+2} \le (m+1)-\sqrt{n}=\frac{2p}{(m+1)+\sqrt{n}} \le \frac{2p}{2m+1} \le \frac{p}{m}$. Hence the fractions $\{\frac{m^2}{m}, \frac{m^2+1}{m}, \frac{m^2+2}{m} ,\dots ,\frac{m^2+m}{m}, \frac{m^2+m}{m+1}, \frac{m^2+m+1}{m+1}, \frac{m^2+m+2}{m+1} ,\dots ,\frac{(m+1)^2}{m} \}$ 'partition' the squareroot of the integers $\{m^2,m^2+1,\dots ,(m+1)^2\}$ in the order of sizes. The conclusion follow, with $b=m$ or $m+1$ b) We claim that all $n=m^2+1$ for some integer m doesn't satisfy the given condition. Suppose otherwise. We must have $\sqrt{m^2+2} \ge \frac{a}{b} >m$. But $\frac{a}{b}-m\le\sqrt{m^2+2}-m=\frac{2}{\sqrt{m^2+2}+m} < \frac{2}{2m}=\frac{1}{m}$ so we must have $b>m$ for the inequality to hold. Done
01.04.2020 12:16
My solution for part (b) is same as of @above , so won't repeat mathwizard888 wrote: Consider fractions $\frac{a}{b}$ where $a$ and $b$ are positive integers. (a) Prove that for every positive integer $n$, there exists such a fraction $\frac{a}{b}$ such that $\sqrt{n} \le \frac{a}{b} \le \sqrt{n+1}$ and $b \le \sqrt{n}+1$. (b) Show that there are infinitely many positive integers $n$ such that no such fraction $\frac{a}{b}$ satisfies $\sqrt{n} \le \frac{a}{b} \le \sqrt{n+1}$ and $b \le \sqrt{n}$. Very nice problem , the main idea here is to write down many many examples Solution- Part (a)- Let $S$ denote the set of all $n$ for which such $a,b$ exist , we will show that $S=\mathbb{N}$, by adding numbers one by one Claim 1 - $1,2,3,4,5,6,7,8,9 \in S$ This can easily be shown by directly taking values of $a,b$ , this is here just to remove complications later , so hereafter we assume all values are greater than $9$. Claim 2 - $n^2\in S$ This is also trivial by taking $a=n,b=1$ Claim 3 - $n^2-1\in S$ Again take $a=n,b=1$ Now we come to the non-trivial part Claim 4 - For given $b$ and $1\leq i\leq 2b-1 $ , we have $(b-1)^2+2i-1\in S$ Proof- The proof is easy in the sense that we will directly give $a,b$ ( $b$ is obviously $b$) Let $a_i=b^2-b+i$ where $1\leq i\leq 2b-1$ and define $x_i=\lfloor\frac{a_i^2}{b^2}\rfloor$ First we show that $x_i=(b-1)^2+2i-1$ It is easy to check that $x_1=(b-1)^2+1, x_{b}=b^2$ and $x_{2b-1}=(b-1)^2+2(2b-1)-1$ Now if we show that $x_t$ is an AP then we will get the required result Note that $\frac{a_{i+1}^2}{b^2}-\frac{a_i^2}{b^2}=2+\frac{2i+1-2b}{b^2}$ So for $1\leq i< b$ we have $\frac{a_{i+1}^2}{b^2}-\frac{a_i^2}{b^2}\leq 2 \implies x_{i+1}-x_{i}\leq 2$ Now we simply add everything to get $2b-2=x_{b}-x_1=(x_{b}-x_{b-1})+\cdots+(x_2-x_1)\leq 2(b-1) = 2b-2$ Hence equality must hold everywhere and similarly we do for $b\leq i\leq 2b-1$ but with the sign flipped to get that $x_i$ is an AP. And as there is only one AP of given lenght and fixed endpoints we get that $x_i=(b-1)^2+2i-1$ Now if we show that all $x_i\in S$ then we will be done First note that $\sqrt{x_i}\leq\frac{a_i}{b}\leq\sqrt{x_i+1} $ So its enough to show that $b\leq \sqrt{x_i}+1$ but note that $x_i$ is increasing and $b=b-1+1 < \sqrt{(b-1)^2+1}+1= \sqrt{x_1}+1$ and hence we are done. Main Proof- Now we show that we have covered all natural numbers. Let $n\in\mathbb{N}$ be given , if $n$ is a perfect square we are done by claim 2. So let $k^2<n<(k+1)^2$ , now we make two casses- Case I - $n$ and $k$ have same parity Let $n-(k-1)^2=2i-1$ we have $2i-1< (k+1)^2-(k-1)^2 \implies i\leq 2k$ If $i= 2k$ then $n=(k+1)^2-1$ and we use claim 3 If $i\leq 2k-1$ we use claim 4 with $b=k$ Case II - $n$ and $k$ have different parity Let $n-k^2=2i-1$ then $2i-1< 2k+1\implies i<k+1< 2(k+1)-1$ Hence we are done using claim 4 with $m=k+1$. Hence proved!!!!!!!
18.07.2020 23:46
Let $k=\lfloor \sqrt{n} \rfloor$. We claim that for any $0\le q\le k$, \begin{align*} k+\tfrac{q}{k+1} &\in \big[\sqrt{k^2+2q-1}, \sqrt{k^2+2q}\big],\\ k+\tfrac{q}{k} &\in \big[\sqrt{k^2+2q}, \sqrt{k^2+2q+1}\big], \end{align*}which would solve part (a). Both follow by squaring: for the latter, we want to show $k^2+2q \le \left(k+\tfrac{q}{k}\right)^2 \le k^2+2q+1$, which is clear since the middle expression is $k^2+2q+\tfrac{q^2}{k^2}$. For the former, we want to show $k^2+2q-1 \le \left(k+\tfrac{q}{k+1}\right)^2 \le k^2+2q$, which is also easy to verify by expansion. For part (b), we claim we can choose $n=k^2+1$ for any $k\ge 1$. Suppose there exists some $\tfrac{a}{b}$ with $b \le k$ such that $\sqrt{k^2+1}\le \tfrac{a}{b} \le \sqrt{k^2+2}$. But $k+\tfrac{1}{k} \ge \sqrt{k^2+2}$ (which follows directly from squaring), contradiction.
11.09.2020 00:14
Part a) Solution: Call a number $n$ $\textit{hot}$ if there exists a fraction $\tfrac{a}{b}$ satisfying the problem. Partition the positive integers into intervals of the form $[k^2, (k+1)^2 - 1]$ as $k$ ranges from $1 \to \infty$. We will prove that for any arbitrary interval $[k^2, (k+1)^2 - 1]$, all numbers in it are $\textit{hot}$. Notice that in this range, we require $b \leq k + 1$. For $n$ of the form $k^2 + 2i$, where $i : 0 \to k$, we may select $\tfrac{a}{b} = k + \tfrac{i}{k}$. Indeed, we may check that\[k^2 + 2i \leq \left(k + \frac{i}{k}\right)^2 = k^2 + 2i + \frac{i^2}{k^2} \leq k^2 + 2i + 1\]as desired. For $n$ of the form $k^2 + 2i - 1$, where $i : 1 \to k$, we may select $\tfrac{a}{b} = k + \tfrac{i}{k + 1}$. Indeed, we may check that\[k^2 + 2i - 1 \leq k^2 + 2i - \left(\frac{2i}{k + 1} - \frac{i^2}{(k + 1)^2}\right) = \left(k + \frac{i}{k+1}\right)^2 \leq k^2 + 2i\]as desired. Hence all $n$ in each interval $[k^2, (k+1)^2 - 1]$ are $\textit{hot}$, and considering all intervals, we are done. $\blacksquare$ Part b) Solution: I claim that all $n = k^2 + 1$ work for large enough $k$. Let $x$ be an integer and suppose\[\sqrt{x^2 + 1} \leq \frac{a}{b} \leq \sqrt{x^2 + 2}\]for some rational $\tfrac{a}{b}$ with $b \leq x$. Squaring and multiplying by $b^2$, we get $b^2(x^2 + 1) \leq a^2 \leq b^2(x^2 + 2)$. Clearly, the LHS of this bound satisfies $b^2(x^2 + 1) > (bx)^2$. Less clearly, the RHS of the bound satisfies\[b^2(x^2 + 2) = b^2x^2 + 2b^2 \leq b^2x^2 + 2bx < (bx + 1)^2\]so in fact, the perfect square $a^2$ is strictly bounded between two consecutive squares, a contradiction. $\blacksquare$
07.12.2020 03:45
Beautiful problem. The key idea is to consider blocks $m^2,m^2+1,\dots,m^2+2m$ for positive integers $m$ in which any $n$ falls. The following diagram reveals what is going on. $\begin{pmatrix} 0&&&1/3&1/2&1/3&&&1\\ 0&&1/4&1/3&2/4&2/3&3/4&&1\\ 0&1/5&1/4&2/5&2/4&3/5&3/4&4/5&1\\\end{pmatrix}.$ For $n=m^2$ take $a/b=m/1$. For $n=m^2+2m$ take $a/b=(m+1)/1$. For $n=m^2+1,\dots,m^2+2m-1$, let $c=((m+1)^2-n)/2$. Then \[\left(m+1-\frac{c}{m+1}\right)^2=m^2+2m+1-2c+\frac{c^2}{(m+1)^2},\]so $a/b=m+1-c/(m+1)$ works. For $n=m^2+2,\dots,m^2+2m-2$, let $c=(n-m^2)/2$. Then \[\left(m+\frac{c}{m}\right)^2=m^2+2c+\frac{c^2}{m^2},\]so $a/b=m+c/m$ works. This resolves part a. For part b, note that $m^2+1$ must be one such example because $(m+1/m)^2>m^2+2$, so for any $b\le m$, $a^2/b^2>m^2+2$ or $a^2/b^2\le m^2$.
23.02.2021 00:57
We first solve (a). Let $n=m^2+k$ where $0\le k\le 2m$. If $k$ is even, select $b=m$ and $a=m^2+\tfrac{k}{2}$. Note that \begin{align*} \sqrt{n}\le\tfrac{a}{b}\le \sqrt{n+1} &\iff b^2n\le a^2\le b^2(n+1) \\ &\iff m^2(m^2+k)\le m^2+m^2k+\tfrac{k^2}{4}\le m^2(m^2+k+1) \\ &\iff 0\le k^2\le 4m^2 \\ &\iff 0\le k\le 2m, \end{align*}which is true. If $k$ is odd, let $b=m+1$ and $a=m(m+1)+\tfrac{k+1}{2}$. In that case, we have \begin{align*} \sqrt{n}\le\tfrac{a}{b}\le \sqrt{n+1} &\iff b^2n\le a^2\le b^2(n+1) \\ &\iff (m+1)^2(m^2+k)\le m^2(m+1)^2 + m(m+1)(k+1) + \tfrac{(k+1)^2}{4}\le (m+1)^2(m^2+k+1) \\ &\iff k(m+1)^2 \le m(m+1)(k+1)+\tfrac{(k+1)^2}{4}\le (k+1)(m+1)^2 \\ &\iff (k-m)(m+1) \le \tfrac{(k+1)^2}{4}\le (k+1)(m+1). \end{align*}Both of these are easy to verify, so we're done. For $(b)$, let $n=m^2+1$. Then, we need to show that \[[b\sqrt{m^2+1},b\sqrt{m^2+2}]\]contains no integers. It is enough to show that $b\sqrt{m^2+2}<bm+1$. Note that \begin{align*} b\sqrt{m^2+2}<bm+1 &\iff b^2m^2 + 2b^2 < b^2m^2 + 2bm + 1\\ &\iff 2b(m-b)+1>0, \end{align*}which is true as $b\le m$. This completes the solution.
01.06.2021 10:02
dame dame
05.01.2022 05:21
Write $n$ as $k^2 + m$ where $k=\lfloor \sqrt{n}\rfloor$. Then, note that in $(a)$ we can select any $b\leq k+1$ . Case 1: $k^2+2x$, note that $x\leq k$. Then, the selection of $\frac{a}{b}=k+\frac1k$ works because \[(k+\frac{x}{k})^2 = k^2+2x+\frac{x^2}{k^2} \in [k^2+2x,k^2+2x+1]\] Case 2: $k^2+2x-1$. Note that $1\leq x\leq k$. Then, \[(k+\frac{x}{k+1})^2 = k^2 + \frac{2xk^2+2xk+x^2}{(k+1)^2}\]AFTSOC that $2xk^2+2xk+x^2> 2x(k+1)^2 = 2xk^2+4xk+2x\Longrightarrow x^2-2x> 2xk\geq 2x^2$ which is clearly absurd.Thus $\frac{a}{b}^2 \leq k^2+2x$. Next, note that $\frac{2kx}{k+1}\geq \frac{2x^2}{x+1}\geq 2x-1$, so $\frac{a}{b}^2 \geq k^2 + \frac{2kx}{x+1}+ \frac{x^2}{(k+1)^2}\geq k^2+2k-1+\frac{x^2}{(k+1)^2}$. Thus, we have shown that $\frac{a}{b}\in [k^2+2x-1,k^2+2x]$ and we are done with part $a$. For part $b$, note that $n=k^2+1$ works. Since $b\leq k$, if $\frac{a}{b}\geq k$, then $\frac{a}{b}\geq k+\frac{1}{k}$, but $(k+\frac{1}{k})^2 = k^2 + 2+ \frac{1}{k^2}> k^2+2=n+1$, a failure. Thus, all $n$ of the form $k^2+1$ fail, and we clearly have infinitely many valid choices of $n$ and part $(b)$ is done.
02.02.2022 17:40
First we solve part (a). Fix $n$ and assume contrary. Let $\lfloor n \rfloor = k$. Case $k=1$ is easy. Assume $k \ge 2$. Let $S$ be set of all fractions with denominator $\le k+1$. Choose $\frac{a}{b},\frac{c}{d} \in S$ such that $$\frac{a}{b} < \sqrt{n} \le \sqrt{n+1} < \frac{c}{d} \qquad \qquad (1) $$and the interval $\left( \frac{a}{b}, \frac{c}{d} \right)$ contains no fraction of $S$. As $\frac{a+c}{b+d} \in \left( \frac{a}{b}, \frac{c}{d} \right)$, thus $b+d \ge k+2$. Claim: $bc - ad = 1$. Proof: Our Claim just follows by Farey sequences.$\square$ Using our claim we obtain \begin{align*} \frac{1}{2(k+1)} &< \frac{1}{\sqrt{n+1} + \sqrt{n}} = \sqrt{n+1} - \sqrt{n} < \frac{c}{d} - \frac{a}{b} = \frac{bc - ad}{bd} = \frac{1}{bd} \\ &\implies bd \le 2k + 1 \qquad \qquad (2) \end{align*}Now recall that $b+d \ge k+2$. Claim: $\min(b,d) \le 2$. Proof: Assume contrary that $b,d \ge 3$. Then $(b-3)(d-3) \ge 0 \implies bd \ge 3(k-1)$. So $k \le 4$. Now if $b+d \ge k+3$, then $bd \ge 3k$, giving $k \le 1$, contradiction. If $b+d = k+2$, then that forces $b=d=3,k=4$. But that contradicts $\gcd(b,d) = 1$ (which follows from $bc - ad = 1$). $\square$ Now we have several cases. Main idea in each of them is to bound $\frac{c}{d} - \frac{a}{b}$. Case 1.1: $b=2$. Then $(2)$ forces $d=k$ and $(1)$ forces $a= 2k+1$. Then $n > k^2+ k$ forcing $\sqrt{n+1} \ge \sqrt{k^2 + k + 2}$. Then, \begin{align*} \frac{1}{2k} = \frac{1}{bd} = \frac{c}{d} - \frac{a}{b} > \sqrt{n+1} - \frac{a}{b} \ge \sqrt{k^2 + k +2} - \frac{2k+1}{2} = \frac{\frac{7}{4}}{ \sqrt{k^2 + k + 2} + \frac{2k+1}{2}} \\ \implies \sqrt{k^2 + k + 2} + \frac{2k + 1}{2} \ge \frac{7}{2} \cdot k \implies \sqrt{k^2 +k + 1} \ge k + 1 \end{align*}Case 1.2: $d=2$. Then $2$ forces $b = k$ and $(1)$ forces $c=2k+1$. Now $n+1 \le k^2 + k$ forcing $\sqrt{n} \le k^2 + k -1$. Then, \begin{align*} \frac{1}{2k} = \frac{1}{bd} = \frac{c}{d} - \frac{a}{b} > \frac{c}{d} - \sqrt{n} \ge \frac{2k + 1}{2} - \sqrt{k^2 + k -1} = \frac{ \frac{5}{4}}{ \frac{2k + 1}{2} + \sqrt{k^2 + k -1}} \\ \implies \frac{2k+1}{2} + \sqrt{k^2 + k - 1} \ge \frac{5}{2} \cdot k \implies \sqrt{k^2 + k -1} \ge k + \frac{1}{2} \end{align*}Case 2.1: $b=1$. Then $d \le k+1$ and $b +d \ge k+2$ forces $d = k+1$. Also $(1)$ gives $a=k$. Now $n > k$ forcing $\sqrt{n+1} \ge \sqrt{k^2+2}$. Thus, \begin{align*} \frac{1}{k+1} = \frac{1}{bd} = \frac{c}{d} - \frac{a}{b} > \sqrt{n+1} - \frac{a}{b} \ge \sqrt{k^2 + 2} - k = \frac{2}{\sqrt{k^2 + 2} + k } \\ \implies \sqrt{k^2 + 2} + k \ge 2(k+1) \implies \sqrt{k^2 + 2} \ge k + 2 \end{align*}Case 2.2: $d=1$. Then $b \le k+1$ and $b+d \ge k+2$ forces $b = 2k+1$. Also $(1)$ gives $c=k+1$. Now $n+1 < k+1$ forcing $\sqrt{n} \le \sqrt{k^2 - 2}$. Thus, \begin{align*} \frac{1}{k+1} = \frac{1}{bd} = \frac{c}{d} - \frac{a}{b} > k + 1 - \sqrt{(k+1)^2 - 2} = \frac{2}{k + 1 + \sqrt{(k+1)^2 - 2}} \\ \implies k+1 + \sqrt{(k+1)^2 - 2} \ge 2(k+1) \implies \sqrt{(k+1)^2 - 2} \ge k+1 \end{align*}In each case, we obtain a contradiction. This solves (a). Now we solve (b). Take $n = t^2 - 2$ for any $t \ge 2$. We will prove no such $\frac{a}{b}$ exists. Suppose not and write $$ \sqrt{t^2 - 2} \le \frac{a}{b} \le \sqrt{t^2 - 1} $$By assumption $b \le t-1$. Now $\frac{a}{b} < t$ gives $$\frac{a}{b} \le \frac{tb - 1}{b} = t - \frac{1}{b} \le t - \frac{1}{t-1} $$Using $\sqrt{t^2 - 2} \le \frac{a}{b}$ we obtain \begin{align*} \frac{1}{t-1} \le t - \sqrt{t^2-2} = \frac{2}{t + \sqrt{t^2 - 2} } \end{align*}This is a contradiction, completing the proof. $\blacksquare$
12.05.2023 22:30
24.05.2023 23:14
Let $n=x^2+y$ where $0\le y\le 2x$. Note that $\lfloor \sqrt{n} \rfloor = x$. Note that $0 \le \tfrac{y^2}{(2x)^2} \le 1$. Thus, if $y$ is even then we have \[\sqrt{n} = \sqrt{x^2+y}\le \sqrt{x^2+y+\frac{y^2}{(2x)^2}} = \sqrt{\left(x+\frac{y}{2x}\right)^2} = \frac{x^2+\frac{y}{2}}{x} \le \sqrt{x^2+y+1} = \sqrt{n+1}\]If $y$ is odd then pick $a=x(x+1)+y+1$ and $b=x+1$. The calculations work out and are long to type out so I'll omit them. We prove that we cannot find $b\le \sqrt{n}$ for $n=x^2+1$. Note that if a rational number exists, it must be between $x$ and $x+1$ exclusive. The smallest such number is $\tfrac{x^2+1}{x}$ which is still too big.
10.08.2023 02:04
We are essentially being asked to prove that there always exists an integer in the range $[b\sqrt{n},b\sqrt{n+1}]$, or equivalently in the range $[b\{\sqrt{n}\},b\{\sqrt{n+1}\}]$, or equivalently a square in the range $[b^2n,b^2(n+1)]$, for some $b \leq \sqrt{n}+1$, but not always for some $b \leq \sqrt{n}$. For part (a), write $n=p^2+q$ where $p$ is maximal. Then, If $q$ is even, take $b=p$. Then $$p^2(p^2+q)\leq\left(p+\frac{q}{2}\right)^2 \leq p^2(p^2+q+1),$$where the first inequality is obvious, and the second inequality is equivalent to $2p \geq q$, which is true. If $q$ is odd, take $b=p+1$. Then note that $$(p^2+2p+1)(p^2+q)=\left(p^2+p+\frac{q+1}{2}\right)^2-\left(p+\frac{1-q}{2}\right)^2\leq \left(p^2+p+\frac{q+1}{2}\right)^2,$$and therefore $$(p^2+2p+1)(p^2+q)=\left(p^2+p+\frac{q+1}{2}\right)^2-\left(p+\frac{1-q}{2}\right)^2+(p+1)^2 \geq \left(p^2+p+\frac{q+1}{2}\right)^2,$$which is true since $0 \leq p+\tfrac{1-q}{2} \leq p+1$. For part (b), I claim that $n=k^2+2$ fails where $k$ is a large positive integer. We have $$\{\sqrt{n+1}\}=\sqrt{k^2+2}-k=\frac{2}{k^2+\sqrt{k^2+2}}<\frac{1}{k},$$hence the interval $[b\{\sqrt{n}\},b\{\sqrt{n+1}\}]$, which is always positive, is also always less than $1$ for $b \leq \sqrt{n}$, hence it never contains an integer when $b \leq \sqrt{n}$.
27.12.2023 20:37
We rephrase the problem as follows: given a fixed integer $m$, there must exist fractions $\frac ab$ with $b \leq m + 1$ such that $$\frac k{m+\sqrt{m^2+k}} \leq \frac ab \leq \frac{k+1}{m+\sqrt{m^2+(k+1)}}.$$This is equivalent to the original problem through setting $m = \lfloor \sqrt n \rfloor$. The key claim is the following: Claim. For every $k \leq m$, we have $$\frac{2k-1}{m+\sqrt{m^2+2k-1}} \leq \frac k{m+1} \leq \frac{2k}{m+\sqrt{m^2+2k}} \leq \frac km \leq \frac{2k+1}{m+\sqrt{m^2+2k+1}}.$$ Proof. The middle two inequalities follow easily by noting $m < \sqrt{m^2+2k} < m+1$. The right inequality rewrites as \begin{align*} k\sqrt{2k+km+1} &\leq km + m \\ \iff 2k^3+k^2+m^2+k^2 &\leq k^2m^2+m^2+2km^2 \\ \iff (m^2-k^2)(2k+1) &\geq 0. \end{align*}This is clear as we always have $k \leq m$. The left inequality rewrites as \begin{align*} km +k\sqrt{m^2+2k-1} &\geq 2km - m + 2k - 1\\ k^2m^2+2k^3-k^2 &\geq (km-m+2k-1)^2 \\ (2k-1)(k-m-1)^2 &\geq 0 \end{align*}which is obviously true. Hence the claim is proved. $\blacksquare$ This implies that we can satisfy all the constraints by only picking fractions with $b = m$ or $b = m+1$, which finishes the first part. For the second part, taking $n = m^2+1$, notice that $\frac 1m > \frac 2{m+\sqrt{m^2+2}}$, so there is no fraction with $b \leq m$ in the range $[\sqrt n, \sqrt{n+1}]$, so the bound is tight.
19.02.2024 13:30
Nice and straightforward. $(a)$ Suppose for contradiction that there is a positive integer $n$ for which there doesn't exist a fraction satisfying our condition. It is easy to check the cases where $n < 9$, so assume that $n \geq 9$. We may assume that $\sqrt{n}$ is irrational since otherwise, we can simply pick $a=n$ and $b=1$. Let $\frac{a}{b}$ be the largest fraction (in irreducible form) not exceeding $\sqrt{n}$ such that $b \leq \sqrt{n}+1$. Choose the largest positive integer $y$ such that $ay \equiv -1 \pmod{b}$ and $y \leq \sqrt{n}+1$, and let $x = \frac{ay+1}{b}$. Note that $b+y \geq \sqrt{n}+1$, which implies that $b+y \geq \lfloor \sqrt{n} \rfloor + 2$. We have $\frac{x}{y}-\frac{a}{b}=\frac{xb-ay}{by} = \frac{1}{by}$. Therefore, by assumption we must have $\frac{1}{by} \geq \sqrt{n+1} - \sqrt{n} = \frac{1}{\sqrt{n}+\sqrt{n+1}}$ which implies that $by \leq \sqrt{n}+\sqrt{n+1} < 2\lfloor \sqrt{n} \rfloor+2$. Suppose that $b \geq 3$. Then by AM-GM we get $by \geq 3 (\lfloor \sqrt{n} \rfloor-1) \geq 2 \lfloor \sqrt{n} \rfloor + 2$, a contradiction. Let $n = x^2 + c$. Case 1: $b=1$. Since $\frac{a}{1}$ is the largest rational number with $b \leq \sqrt{n}+1$ not exceeding $\sqrt{n}$, we must have $\sqrt{n} \leq x + \frac{1}{x+1} \implies n \leq x^2 + \frac{2x}{x+1}+\frac{1}{x^2+2x+1}< x^2+2 \implies c = 1$. Then it is not hard to check that $\sqrt{x^2+1} \leq \frac{x^2+x+1}{x+1} \leq \sqrt{x^2+2}$ always holds. $\square$ Case 2: $b=2$. Since $\frac{a}{2}$ is the largest rational number with $b \leq \sqrt{n}+1$ not exceeding $\sqrt{n}$, we must have $x + \frac{1}{2} \leq \sqrt{x^2+c} \leq x + \frac{1}{2} + \frac{1}{2x}$. Squaring this inequality we get $x^2+x < (x + \frac{1}{2})^2 \leq x^2+c \leq (x+\frac{1}{2} + \frac{1}{2x})^2 < x^2+x+2$. This implies that $c=x+1$. Then it is not hard to check $\sqrt{x^2+x+1} \leq x + \frac{x+2}{2(x+1)} \leq x + \frac{x+1}{2x} \leq \sqrt{x^2+x+2}$ always holds. $\blacksquare$ $(b)$ Looking at Case 1 from part $(a)$, we observe that our bound barely holds. So we may presume that $x^2+1$ works. Indeed, it is very simple to show that we have $x + \frac{a}{b} \geq \sqrt{x^2+2}$ for all fractions with $b \leq \sqrt{n}$. $\blacksquare$
03.05.2024 11:38
Woah, one of the coolest algebra problems ever For part a, let $k = \left\lfloor \sqrt n \right\rfloor$. Then, we can manually check the cases $k < 5$. for $k \geq 5$, the cases where $n$ or $n+1$ are perfect squares are clear. Also, if $n = k^2+k$, then, $k+\frac{1}{2}$ lies between $\sqrt{n}$ and $\sqrt{n+1}$. Consider the Farey sequence of order $k+2$. So, now it is a well known property of Farey sequences that if $\frac{a_i}{b_i}$ and $\frac{a_{i+1}}{b_{i+1}}$, then $a_{i+1}b_i-a_ib_{i+1} = 1$ and $b_i+b_{i+1} \geq k+2$. Now, it is clear that no fraction with denominator $1$ or $2$ lies between $\sqrt{n}$ and $\sqrt{n+1}$ (as we already handled such cases in the last paragraph). But, $$\sqrt{n+1}-\sqrt{n} = \frac{1}{\sqrt{n+1}+\sqrt{n}} > \frac{1}{2k+2}$$Also, $$\frac{a_{i+1}}{b_{i+1}}-\frac{a_i}{b_i} = \frac{a_{i+1}b_i-a_ib_{i+1}}{b_ib_{i+1}} = \frac{1}{b_ib_{i+1}} \leq \frac{1}{3k-3}$$For $k > 5$, the difference between $\sqrt{n+1}$ and $\sqrt{n}$ is more than that of consecutive terms of the Farey sequence, so one term of the sequence lies between the radicals, and we are done For the second part, if $n = k^2+1$, then, note that $\sqrt{n}-k \leq \frac{a}{b}-k \leq \sqrt{n+1}-k$ and the fraction in the middle is between $0$ and $1$, so it is atleast $\frac{1}{k}$, but we can see $$\sqrt{k^2+2}-k = \frac{2}{\sqrt{k^2+2}+k} < \frac{1}{k}$$, so we are done.
06.12.2024 22:56
(a) We consider two cases: If \(n = x^2 + 2k\), where \(x = \lfloor \sqrt{n} \rfloor\), it follows that \[ n = x^2 + k \leq x^2 + k +\left( \frac{k}{x} \right)^2 \leq x^2 + k + 1 = n + 1. \]Thus, \[ \sqrt{n} \leq \frac{x^2+k}{x} \leq \sqrt{n+1}. \] If \(n = x^2 + 2k + 1\), where \(x = \lfloor \sqrt{n} \rfloor\), it follows that \[ n = x^2 + 2k = (x+1)^2 - 2(x-k) < (x+1)^2 - 2(x-k) + \left( \frac{x-k}{x+1} \right)^2. \]\[ < (x+1)^2 - 2(x-k) + 1 = x^2 + 2k + 1 = n+1. \]Thus, \[ \sqrt{n} < \frac{(x+1)^2 + (x-k)}{x+1} < \sqrt{n+1}. \] (b) Suppose \(n = x^2 + 1\) and that there exist \(a, b\) satisfying the problem. It follows that \[ (bx)^2<b^2(x^2 + 1) \leq a^2 \leq b^2(x^2 + 2) < bx^2 + 2bx < (bx+1)^2 \]This leads to a contradiction.