Find, in terms of $\epsilon$, the smallest positive integer $n$ such that $|\sqrt{n}-\lfloor{\sqrt{n}}\rfloor-\frac12|<\epsilon$ where $0<\epsilon<\frac12$.
Numerical experimentation suggests that the answer is $\lfloor\left(\lfloor\frac{1}{8\epsilon}+\frac{1}{2}\rfloor+\frac{1}{2}\right)^2\rfloor$ but I don't know how to prove this.
My attempt:
I set $\sqrt{n}=k+\frac12\pm\delta$ where $k\in\mathbb{Z}$ and $0<\delta<\epsilon$, which leads to $n=k^2+k+\frac14+\delta^2+(2k\pm1)\delta$, but I don't know if this helps.
Context:
I came up with this question after thinking about the decimal expansion of square roots.