Với mỗi số nguyên dương $n$, ta gọi một hoán vị $(a_0,a_1,\dots ,a_{n-1})$ của các số $0$, $1$, $\dots$, $n-1$ là tốt nếu $a_i+i$ là số chính phương với mọi $i=0,1,\dots ,n-1$.
a) Chứng minh rằng với $n=2026$, trong một hoán vị tốt $(a_0,a_1,\dots ,a_{2025})$, luôn tồn tại ít nhất một chỉ số $i$ sao cho $a_i+i$ chia hết cho 9.
b) Chứng minh rằng với mọi số nguyên dương $n$, luôn tồn tại ít nhất một hoán vị tốt.

Lời giải (Lim Olympic - Lào Cai TST - P3):

a) Giả sử ngược lại rằng không có $a_i+i$ nào chia hết cho 9. Vì $a_i+i$ là số chính phương, nếu nó chia hết cho 3 thì nó phải chia hết cho 9. Do đó mọi $a_i+i$ đều không chia hết cho 3, nên $a_i+i\equiv 1(\mathrm{mod}3)$. Suy ra
$$\sum _{i=0}^{2025}(a_i+i)\equiv 2026\equiv 1(\mathrm{mod}3).$$
Nhưng $(a_0,\dots ,a_{2025})$ là một hoán vị của $(0,\dots ,2025)$, nên
$$\sum _{i=0}^{2025}(a_i+i)=2\sum _{i=0}^{2025}i=2025\cdot 2026\equiv 0(\mathrm{mod}3),$$
mâu thuẫn. Vậy chỉ số cần tìm luôn tồn tại.

b) Ta xây dựng bằng quy nạp theo $n$. Với $n=1$, lấy $a_0=0$.
Giả sử $n\ge 2$. Chọn $s$ là số chính phương nhỏ nhất không nhỏ hơn $n-1$ và đặt
$$l=s-(n-1).$$
Ta có $0\le l\le n-1$. Thật vậy, nếu $k^2<n-1<(k+1{)}^2$ thì
$$s=(k+1{)}^2\le 2(k^2+1)\le 2(n-1);$$
còn trường hợp $n-1$ thì hiển nhiên.
Trên đoạn chỉ số $l\le i\le n-1$, đặt $a_i=s-i$. Khi $i$ chạy từ $l$ đến $n-1$, các giá trị $a_i$ chạy qua đúng các số từ $n-1$ xuống $l$, và cũng có được
$$a_i+i=s$$
là số chính phương. Theo giả thiết quy nạp, trên các chỉ số $0,1,\dots ,l-1$ tồn tại một hoán vị tốt của các số $0,1,\dots ,l-1$. Ghép hai phần lại, ta thu được một hoán vị tốt của $0,1,\dots ,n-1$.
Vậy hoán vị tốt tồn tại với mọi $n\in {\mathbb{N}}^{\ast }$.