Problem 1761

Solution:

If $n$ is an even number, the claim is trivial: in that case there do not even exist two consecutive beautiful numbers, since even numbers are not beautiful. From now on we assume that $n$ is odd.

Since numbers divisible by $n$ are not beautiful, we may restrict ourselves to numbers $x \in \{1, \ldots, n-1\}$. Suppose that the numbers $x$ and $x+1$ are beautiful. The remainders of $x^{2}$ and $(x+1)^{2}$ upon division by $n$, which are odd, are equal to $x^{2}-n\left[\frac{x^{2}}{n}\right]$ and $(x+1)^{2}-n\left[\frac{(x+1)^{2}}{n}\right]$ respectively, so $\left[\frac{x^{2}}{n}\right]$ and $\left[\frac{(x+1)^{2}}{n}\right]$ have different parities. Since $0<(x+1)^{2}-x^{2}<2 n$ implies $0 \leqslant\left[\frac{(x+1)^{2}}{n}\right]-\left[\frac{x^{2}}{n}\right] \leqslant 2$, it follows that $\left[\frac{(x+1)^{2}}{n}\right]=\left[\frac{x^{2}}{n}\right]+1$.

Therefore, if the numbers $x, x+1, \ldots, x+k$ are beautiful, then
$$m=y-\left[\frac{y^{2}}{n}\right] \quad \text{is constant for all} \quad y=x, x+1, \ldots, x+k$$
Since the equality $y-\left[\frac{y^{2}}{n}\right]=m$ is equivalent to $y-m \leqslant \frac{y^{2}}{n}<y-m+1$, i.e. to $n\left(\frac{n}{4}-m\right) \leqslant\left(y-\frac{n}{2}\right)^{2}<n\left(\frac{n}{4}-m+1\right)$, the number of consecutive numbers $y$ with this property is not greater than $\left[\sqrt{n\left(\frac{n}{4}-m+1\right)}-\sqrt{n\left(\frac{n}{4}-m\right)}\right]+1 \leqslant[\sqrt{n}]+1$ if $m \leqslant\left[\frac{n}{4}\right]$, and is not greater than $2\left[\sqrt{n\left\{\frac{n}{4}\right\}}+\frac{1}{2}\right] \leqslant[\sqrt{3 n}]+1$ for $m=\left[\frac{n}{4}\right]+1$.