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.

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

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.

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

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

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

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.

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$

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

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.

dame dame

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.

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$

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.

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

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.

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$

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.

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