3. Find all natural numbers $n$ for which there exists a permutation $\sigma$ of the numbers $1,2, \ldots, n$ such that the number

$$
\sqrt{\sigma(1)+\sqrt{\sigma(2)+\sqrt{\cdots+\sqrt{\sigma(n)}}}}
$$

is rational.

(Serbia)
3. Let $a_{i}=\sqrt{\sigma(i)+\sqrt{\cdots+\sqrt{\sigma(n)}}}$ for $1 \leqslant i \leqslant n$ and $a_{n+1}=0$. If $a_{1}$ is rational, repeated squaring shows that $a_{2}, \ldots, a_{n}$ are also rational. Furthermore, $a_{n}$ must be an integer, and thus $a_{n-1}, \ldots, a_{1}$ are also integers. Further, from $a_{n}k$, we have $a_{j}=$ $\sqrt{k^{2}+1+a_{j+1}} \geqslant k+1$, i.e., $a_{j+1} \geqslant 2 k$. However, $a_{j+1}<\sqrt{n}+1$, from which we get $2 k<$ $\sqrt{(k+1)^{2}+1}$, which gives $3 k^{2}<2 k+2$, so $k \leqslant 1$, i.e., $n \leqslant 4$.

If $n=4$, then $\sigma(4)=1$ or $\sigma(4)=4$. In the first case, $\sigma(3)=3$ and $\sigma(2)=2$ must hold, leaving $\sigma(1)=4$, which is not a solution; in the second case, $\sigma(3)=\sigma(2)=2$, which is also impossible. Similarly, there is no solution for $n=2$. For $n=1$ and $n=3$, the solutions are $\sqrt{1}=1$ and $\sqrt{2+\sqrt{3+\sqrt{1}}}=2$. Therefore, the answer is $n \in\{1,3\}$.