Problem 1710

Solution:

We bewijzen dit met inductie naar $n$. Voor $n=0$ werkt de permutatie $(0)$, want $0+0$ is een kwadraat.

Zij nu $l \geq 0$ en neem aan dat er voor elke $n \leq l$ een kwadratische permutatie bestaat (de inductiehypothese). We bekijken $n=l+1$. Zij $m$ zodat $m^{2}$ het kleinste kwadraat groter dan of gelijk aan $l+1$ is. Nu geldt $l \geq (m-1)^{2} = m^{2} - 2m + 1$, dus $2(l+1) \geq 2m^{2} - 4m + 4 = m^{2} + (m-2)^{2} \geq m^{2}$.

Dit betekent dat we een gehele $p$ met $0 \leq p \leq l+1$ kunnen vinden zodat $(l+1)+p = m^{2}$. Nu definiëren we onze permutatie als volgt.

Als $p \geq 1$, nemen we voor $\left(a_{0}, a_{1}, \ldots, a_{p-1}\right)$ een kwadratische permutatie van $\{0,1, \ldots, p-1\}$; deze bestaat volgens de inductiehypothese omdat $p-1 \leq l$. Voor $p \leq i \leq l+1$ definiëren we $a_{i} = m^{2} - i$. (Merk op dat we voor $p=0$ nu ook een volledige permutatie hebben gedefinieerd.)

Het rijtje $\left(a_{p}, a_{p+1}, \ldots, a_{l+1}\right)$ is nu precies $(l+1, l, \ldots, p)$, zodat we samen met het beginstuk nu alle waarden van $0$ tot en met $l+1$ gebruikt hebben. Verder is $a_{i} + i$ een kwadraat voor alle $i$. Dus $\left(a_{0}, a_{1}, \ldots, a_{l+1}\right)$ is een kwadratische permutatie van $\{0,1, \ldots, l+1\}$.