Problem 1828

The idea is to approximate the numbers $\sqrt{1}, \sqrt{2}, \ldots, \sqrt{N}$ by the nearest integer with errors $<0.5$. This gives the following sequence
$$1,1,2,2,2,2,3,3,3,3,3,3,4, \ldots .$$
More precisely, for each $k \geqslant 1$, we round $\sqrt{k^{2}-k+1}, \ldots, \sqrt{k^{2}+k}$ to $k$, so that there are $2 k$ copies of $k$.

Step 1. We first consider the easier case when $N$ has the form
$$N=m(m+1) .$$
In this case, the numbers $\sqrt{1}, \sqrt{2}, \ldots, \sqrt{N}$ are approximated by the elements of the multiset $\left\{1_{\times 2}, 2_{\times 4}, 3_{\times 6}, \ldots, m_{\times 2 m}\right\}$. Let $T_{m}$ denote "half of" the multiset, i.e.
$$T_{m}:=\left\{1_{\times 1}, 2_{\times 2}, 3_{\times 3}, \ldots, m_{\times m}\right\} .$$
We will prove by induction that there exists three permutations $\left(u_{k}\right),\left(v_{k}\right)$, and $\left(w_{k}\right)$ of the elements in the multiset $T_{m}$ such that $u_{k}+v_{k}+w_{k}=2 m+1$ is constant for $k=1,2, \ldots, \frac{m(m+1)}{2}$.

When $m=1$, take $1+1+1=3$. When $m=2$, take $(1,2,2)+(2,1,2)+(2,2,1)=(5,5,5)$. Suppose that we have constructed three permutations $\left(u_{k}\right),\left(v_{k}\right)$, and $\left(w_{k}\right)$ of $T_{m-1}$ satisfying $u_{k}+v_{k}+w_{k}=2 m-1$ for every $k=1,2, \ldots, \frac{m(m-1)}{2}$. For $T_{m}$, we note that
$$T_{m}=T_{m-1} \sqcup\left\{m_{\times m}\right\}$$
and also
$$\begin{equation*} T_{m}=\left(T_{m-1}+1\right) \sqcup\{1,2, \ldots, m\} \tag{1} \end{equation*}$$
Here $T_{m-1}+1$ means to add 1 to all elements in $T_{m-1}$. We construct the permutations $\left(u_{k}^{\prime}\right)$, ( $v_{k}^{\prime}$ ), and ( $w_{k}^{\prime}$ ) of $T_{m}$ as follows:
- For $k=1,2, \ldots, \frac{m(m-1)}{2}$, we set $u_{k}^{\prime}=u_{k}, v_{k}^{\prime}=v_{k}+1, w_{k}^{\prime}=w_{k}+1$.
- For $k=\frac{m(m-1)}{2}+r$ with $r=1,2, \ldots, m$, we set $u_{k}^{\prime}=m, v_{k}^{\prime}=r, w_{k}^{\prime}=m+1-r$.
It is clear from (1) that $\left(u_{k}^{\prime}\right),\left(v_{k}^{\prime}\right)$, and $\left(w_{k}^{\prime}\right)$ give three permutations of $T_{m}$, and that they satisfy $u_{k}^{\prime}+v_{k}^{\prime}+w_{k}^{\prime}=2 m+1$ for every $k=1,2, \ldots, \frac{m(m+1)}{2}$.

The inductive construction can be visualised by the $3 \times \frac{m(m+1)}{2}$ matrix
$$\left[\begin{array}{cccccc} u_{1} & \ldots & u_{m(m-1) / 2} & m & \ldots & m \ v_{1}+1 & \ldots & v_{m(m-1) / 2}+1 & 1 & \ldots & m \ w_{1}+1 & \ldots & w_{m(m-1) / 2}+1 & m & \ldots & 1 \end{array}\right],$$
in which the three rows represent the permutations $\left(u_{k}^{\prime}\right),\left(v_{k}^{\prime}\right),\left(w_{k}^{\prime}\right)$, and the sum of the three entries of each column is $2 m+1$.

Thus, when $N=m^{2}+m$, we can construct permutations $\left(a_{k}\right),\left(b_{k}\right)$, and $\left(c_{k}\right)$ of $1,2, \ldots, N$ such that
$$\begin{equation*} 2 m+1-1.5<\sqrt{a_{k}}+\sqrt{b_{k}}+\sqrt{c_{k}}<2 m+1+1.5 . \tag{2} \end{equation*}$$
This gives
$$\left|\sqrt{a_{k}}+\sqrt{b_{k}}+\sqrt{c_{k}}-2 \sqrt{N}\right|<2.5<2023$$
where we used that $-1<2 m-2 \sqrt{m^{2}+m}<0$ for positive $m$.

Step 2. We now proceed to the general case. Let $m$ be such that
$$m(m+1) \leqslant N<(m+1)(m+2)$$
Write $N=m(m+1)+t$ for some $t \in\{0,1, \ldots, 2 m+1\}$ and let
$$L:=\left\lfloor\frac{4}{9} N\right\rfloor$$
We will make use of the following inequalities below:
$$N>m^{2}, \quad N<(m+2)^{2}, \quad t \leqslant 2 m+1, \quad L+1>4 N / 9, \quad L \leqslant 4 N / 9$$
As above, we construct three permutations $\left(a_{k}\right),\left(b_{k}\right)$, and $\left(c_{k}\right)$ of $1,2, \ldots, m(m+1)$ satisfying (2). Now we construct the three required permutations $\left(A_{k}\right),\left(B_{k}\right)$, and $\left(C_{k}\right)$ of $1,2, \ldots, N$ as follows:
For $k=1,2, \ldots, m(m+1)$, if $a_{k} \leqslant L$, take $A_{k}=a_{k}$, and if $a_{k}>L$, take $A_{k}=a_{k}+t$. For $k=m(m+1)+r$ with $r=1,2, \ldots, t$, set $A_{k}=L+r$. Define the permutations ( $B_{k}$ ) and ( $C_{k}$ ) similarly. Now for $k=1,2, \ldots, m(m+1)$, we show $0 \leqslant \sqrt{A_{k}}-\sqrt{a_{k}} \leqslant 2$. The lower bound is obvious. If $m \leqslant 1$, then $N \leqslant 5$ and hence $\sqrt{A_{k}}-\sqrt{a_{k}} \leqslant \sqrt{5}-\sqrt{1} \leqslant 2$. If $m \geqslant 2$, then
$$\sqrt{A_{k}}-\sqrt{a_{k}}=\frac{A_{k}-a_{k}}{\sqrt{A_{k}}+\sqrt{a_{k}}} \leqslant \frac{t}{2 \sqrt{L+1}} \leqslant \frac{2 m+1}{\frac{4}{3} m} \leqslant 2$$
We have similar inequalities for ( $B_{k}$ ) and ( $C_{k}$ ). Thus
$$2 \sqrt{N}-4.5<2 m+1-1.5 \leqslant \sqrt{A_{k}}+\sqrt{B_{k}}+\sqrt{C_{k}} \leqslant 2 m+1+1.5+6<2 \sqrt{N}+8.5$$
For $k=m^{2}+m+1, \ldots, m^{2}+m+t$, we have
$$2 \sqrt{N}<3 \sqrt{L+1} \leqslant \sqrt{A_{k}}+\sqrt{B_{k}}+\sqrt{C_{k}} \leqslant 3 \sqrt{L+t} \leqslant \sqrt{4 N+9 t}<2 \sqrt{N}+8.5$$
To sum up, we have defined three permutations $\left(A_{k}\right),\left(B_{k}\right)$, and $\left(C_{k}\right)$ of $1,2, \ldots, N$, such that
$$\left|\sqrt{A_{k}}+\sqrt{B_{k}}+\sqrt{C_{k}}-2 \sqrt{N}\right|<8.5<2023$$
holds for every $k=1,2, \ldots, N$.

This is a variation of Solution 1 that uses induction for Step 2.
Let $n$ be an integer satisfying $0 \leqslant n \leqslant m+1$ and define the multiset $T_{m, n}$ by
$$T_{m, n}:=\left\{1_{\times 1}, 2_{\times 2}, 3_{\times 3}, \ldots, m_{\times m},(m+1)_{\times n}\right\}$$
In other words, $T_{m, 0}=T_{m}, T_{m, n}=T_{m} \sqcup\left\{(m+1)_{\times n}\right\}$ and $T_{m, m+1}=T_{m+1}$, where $T_{m}$ is the set defined in Solution 1.

Claim. There exist three permutations $\left(u_{k}\right),\left(v_{k}\right),\left(w_{k}\right)$ of $T_{m, n}$ such that
$$\begin{cases}u_{k}+v_{k}+w_{k}=2 m+1 & (n=0), \\ u_{k}+v_{k}+w_{k} \in\{2 m+1,2 m+2,2 m+3\} & (1 \leqslant n \leqslant m), \\ u_{k}+v_{k}+w_{k}=2 m+3 & (n=m+1) .\end{cases}$$
Proof. We proceed by induction on $m$. If $n=0$ or $n=m+1$, the assertion can be proved as in Solution 1. If $1 \leqslant n \leqslant m$, we note that
$$T_{m, n}=T_{m-1, n} \sqcup\left\{m_{\times(m-n)},(m+1)_{\times n}\right\}=\left(T_{m-1, n}+1\right) \sqcup\{1,2, \ldots, m\}$$
From the hypothesis of induction, it follows that we have three permutations $\left(u_{k}\right),\left(v_{k}\right),\left(w_{k}\right)$ of $T_{m-1, n}$ satisfying $u_{k}+v_{k}+w_{k} \in\{2 m-1,2 m, 2 m+1\}$ for every $k$. We construct the permutations $\left(u_{k}^{\prime}\right),\left(v_{k}^{\prime}\right)$, and $\left(w_{k}^{\prime}\right)$ of $T_{m, n}$ as follows:
- For $k=1,2, \ldots, \frac{m(m-1)}{2}+n$, we set $u_{k}^{\prime}=u_{k}, v_{k}^{\prime}=v_{k}+1$, and $w_{k}^{\prime}=w_{k}+1$.
- For $k=\frac{m(m-1)}{2}+n+r$ with $r=1,2, \ldots, m$, we set $u_{k}^{\prime}=m$ if $1 \leqslant r \leqslant m-n$ while $u_{k}^{\prime}=m+1$ if $m-n+1 \leqslant r \leqslant m, v_{k}^{\prime}=r$, and $w_{k}^{\prime}=m+1-r$.
It is clear from the construction that $\left(u_{k}^{\prime}\right),\left(v_{k}^{\prime}\right)$, and $\left(w_{k}^{\prime}\right)$ give three permutations of $T_{m, n}$, and they satisfy $u_{k}^{\prime}+v_{k}^{\prime}+w_{k}^{\prime} \in\{2 m+1,2 m+2,2 m+3\}$ for every $k=1,2, \ldots, \frac{m(m+1)}{2}+n$.

Again, we can visualise the construction using the matrix
$$\left[\begin{array}{ccccccccc} u_{1} & \ldots & u_{m(m-1) / 2+n} & m & \ldots & m & m+1 & \ldots & m+1 \\v_{1}+1 & \ldots & v_{m(m-1) / 2+n}+1 & 1 & \ldots & \ldots & \ldots & \ldots & m \\w_{1}+1 & \ldots & w_{m(m-1) / 2+n}+1 & m & \ldots & \ldots & \ldots & \ldots & 1 \end{array}\right] .$$

In general, we have $m(m+1) \leqslant N<(m+1)(m+2)$ for some $m \geqslant 0$. Set $N=m(m+1)+t$ for some $t \in\{0,1, \ldots, 2 m+1\}$. Then the approximation of $\{\sqrt{1}, \sqrt{2}, \ldots, \sqrt{N}\}$ by the nearest integer with errors $<0.5$ is a multiset
$$\left\{1_{\times 2}, 2_{\times 4}, \ldots, m_{\times 2 m},(m+1)_{\times t}\right\}=T_{m, n_{1}} \sqcup T_{m, n_{2}}$$
with $n_{1}=\lfloor t / 2\rfloor$ and $n_{2}=\lceil t / 2\rceil$.
Since $0 \leqslant n_{1} \leqslant n_{2} \leqslant m+1$, by using the Claim we can construct permutations ( $a_{k}$ ), ( $b_{k}$ ), and $\left(c_{k}\right)$ to satisfy the following inequality:
$$2 m+1-1.5<\sqrt{a_{k}}+\sqrt{b_{k}}+\sqrt{c_{k}}<2 m+3+1.5 .$$
Since $m<\sqrt{N}<m+2$, it follows that
$$2 \sqrt{N}-4.5<2 m+1-1.5<\sqrt{a_{k}}+\sqrt{b_{k}}+\sqrt{c_{k}}<2 m+3+1.5<2 \sqrt{N}+4.5$$
and so
$$\left|\sqrt{A_{k}}+\sqrt{B_{k}}+\sqrt{C_{k}}-2 \sqrt{N}\right|<4.5<2023$$

This solution is based on the geometrical insight of equilateral triangles.

Step 1. We first consider the easier case of triangle numbers
$$N=\frac{m(m+1)}{2} .$$
As shown in the following picture, consider the triangular shaped lattice points inside an equilateral triangle $A B C$ with a total of $N$ points. The lattice is built in a way that the $\ell^{\text {th }}$ row has exactly $\ell$ points for each $\ell=1,2, \ldots, m$. Rows are numbered in three different ways, one for each vertex.

Each point $P_{k}$ in the triangular lattice is labelled with a triple of integers $\left(a_{k}, b_{k}, c_{k}\right)$ as follows. The first coordinate is called the $A$-coordinate, and so on for $B, C$. To define the $A$-coordinate, denoted $W_{a}(\bullet)$, first label the lattice points by $1,2,3, \ldots$ starting with the point closest to $A$ and then going down the rows with the rule that within a row, the labelling is from left to right (see right picture). The $B$-coordinate, denoted $W_{b}(\bullet)$, is defined by rotating the $A$-coordinate counterclockwise by $120^{\circ}$. The $C$-coordinate, denoted $W_{c}(\bullet)$, similarly, by rotating the $A$-coordinate counterclockwise by $240^{\circ}$.

Assume that a point $P$ lies in the $\ell_{a}{ }^{\text {th }}$ row from the vertex $A$, in the $\ell_{b}{ }^{\text {th }}$ row from the vertex $B$, and in the $\ell_{c}{ }^{\text {th }}$ row from the vertex $C$. Note that $\ell_{a}$ is proportional to the height of $A$ in the triangle, minus the height of $P$. Since inside an equilateral triangle, the sum of the lengths of the heights from a point to the three sides is independent of the point, we must have
$$\ell_{a}+\ell_{b}+\ell_{c}=2 m+1=\sqrt{8 N+1} .$$
Since there are exactly $1+2+\cdots+\ell=\frac{\ell(\ell+1)}{2}$ points in the first $\ell$ rows, the $A$-labeling $W_{a}(P)$ of the point $P$ satisfies
$$\frac{\ell_{a}(\ell_{a}-1)}{2}+1 \leqslant W_{a}(P) \leqslant \frac{\ell_{a}(\ell_{a}+1)}{2} .$$
In paticular,
$$\left(\ell_{a}-\frac{1}{2}\right)^{2}<2 W_{a}(P)<\left(\ell_{a}+\frac{1}{2}\right)^{2} .$$
Taking the cyclic sum gives
$$\left|\sqrt{2 W_{a}(P)}+\sqrt{2 W_{b}(P)}+\sqrt{2 W_{c}(P)}-\left(\ell_{a}+\ell_{b}+\ell_{c}\right)\right|<\frac{3}{2}$$
and thus
$$\left|\sqrt{W_{a}(P)}+\sqrt{W_{b}(P)}+\sqrt{W_{c}(P)}-2 \sqrt{N+\frac{1}{8}}\right|<\frac{3}{2} \cdot \frac{1}{\sqrt{2}}=\frac{3 \sqrt{2}}{4} .$$

Step 2. Now, for a general positive integer $N$, there exists a positive integer $m$ such that
$$\frac{m(m-1)}{2}+1 \leqslant N \leqslant \frac{m(m+1)}{2} .$$
Write $N=\frac{m(m+1)}{2}-t$ with $t \in\{0,1, \ldots, m-1\}$. We modify the above construction for $\frac{m(m+1)}{2}$ points into a construction for $N$ points as follows. We remove $t$ arbitrary points from the $m^{\text {th }}$ row (namely the bottom row) of the triangular lattice. The remaining triangular lattice has $\frac{m(m+1)}{2}-t=N$ points, and we assign their $A-, B$-, and $C$-coordinates as before (in the same order, yet skipping over the points that are removed so that the coordinates exactly form permutations of $1,2, \ldots, N$ ).

For each point $P$ in the triangular lattice (that was not removed earlier), suppose that it is in the $\ell_{a}{ }^{\text {th }}, \ell_{b}{ }^{\text {th }}$, and $\ell_{c}{ }^{\text {th }}$ row when viewed from $A, B$, and $C$, respectively. Now the $A$-coordinates $W_{a}(P)$ still satisfies
$$\frac{\ell_{a}(\ell_{a}-1)}{2}+1 \leqslant W_{a}(P) \leqslant \frac{\ell_{a}(\ell_{a}+1)}{2} .$$
The $B$-coordinate $W_{b}(P)$ satisfies
$$\frac{(\ell_{b}-1)(\ell_{b}-2)}{2}+1 \leqslant W_{b}(P) \leqslant \frac{\ell_{b}(\ell_{b}+1)}{2}$$
because, viewing from point $B$, we have removed either 0 or 1 point from each row, and the first $\ell_{b}-1$ rows have at least $0+1+\cdots+(\ell_{b}-2)=\frac{(\ell_{b}-1)(\ell_{b}-2)}{2}$ points left. For the same reason, the $C$-labeling $W_{c}(P)$ satisfies
$$\frac{(\ell_{c}-1)(\ell_{c}-2)}{2}+1 \leqslant W_{c}(P) \leqslant \frac{\ell_{c}(\ell_{c}+1)}{2} .$$
From this, we deduce that
$$\begin{aligned} \ell_{a}-\frac{1}{2} & <\sqrt{2 W_{a}(P)}<\ell_{a}+\frac{1}{2}, \\ \ell_{b}-\frac{3}{2} & <\sqrt{2 W_{b}(P)}<\ell_{b}+\frac{1}{2}, \\ \ell_{c}-\frac{3}{2} & <\sqrt{2 W_{c}(P)}<\ell_{c}+\frac{1}{2} . \end{aligned}$$
Combining all above with the inequalities $2 m-1<2 \sqrt{2 N}<2 m+1$ and $\ell_{a}+\ell_{b}+\ell_{c}=2 m+1$, we deduce that
$$\begin{aligned} 2 \sqrt{2 N}-\frac{7}{2}<(2 m+1)-\frac{7}{2}<\sqrt{2 W_{a}(P)} & +\sqrt{2 W_{b}(P)}+\sqrt{2 W_{c}(P)} \\ & <(2 m+1)+\frac{3}{2}<2 \sqrt{2 N}+\frac{7}{2} \end{aligned}$$
Therefore, for each point $P$, we have
$$\left|\sqrt{W_{a}(P)}+\sqrt{W_{b}(P)}+\sqrt{W_{c}(P)}-2 \sqrt{N}\right|<\frac{7}{2} \cdot \frac{1}{\sqrt{2}}<2.5<2013 .$$
We may finally order of the $N$ points in an arbitrary way. Then the $A$-labelings $W_{a}(\bullet)$ give the permutation $a_{1}, \ldots, a_{N}$, the $B$-labelings $W_{b}(\bullet)$ give $b_{1}, \ldots, b_{N}$, and the $C$-labelings $W_{c}(\bullet)$ give $c_{1}, \ldots, c_{N}$.

For each $k=1,2, \ldots, N$, we have
$$\left|\sqrt{a_{k}}+\sqrt{b_{k}}+\sqrt{c_{k}}-2 \sqrt{N}\right|<2.5<2023$$