Bài Tập Trắc Nghiệm Chuyên Đề: Quy tắc đếm, hoán vị/chỉnh hợp/tổ hợp (Toán học Lớp 10)

Gọi một hàng hoặc một cột là tím mộng mơ nếu nó chứa quân cờ của cả hai màu.
Giả sử có $R$ hàng tím, $C$ cột tím và có tất cả $N$ quân cờ.
Trước hết, mỗi hàng tím chứa không quá 5 quân đỏ và không quá 5 quân xanh. Thật vậy, nếu một hàng tím chứa nhiều hơn 5 quân đỏ thì một quân xanh trên hàng đó đã nhìn thấy nhiều hơn 5 quân khác màu, trái với giả thiết. Tương tự đối với các cột tím.
Do đó, mỗi hàng tím hoặc cột tím chứa không quá 10 quân cờ.
Mặt khác, mỗi quân cờ phải nằm trên ít nhất một hàng tím hoặc một cột tím, vì nó nhìn thấy 5 quân khác màu. Bởi vậy ta có được $N\le 10R+10C$.
Nếu $R+C\le 379$ thì $N\le 3790<3800$.
Xét trường hợp $R+C\ge 380$. Không mất tính tổng quát, giả sử $R\ge C$, khi đó $R\ge 190$.
Trong $R$ hàng tím có nhiều nhất $10R$ quân. Mỗi quân nằm ngoài các hàng tím phải thuộc một trong $C$ cột tím, nên số quân như vậy không vượt quá $(200-R)C$. Do đó với $190\le R\le 200$ ta có:
$$N\le 10R+(200-R)C\le 10R+(200-R)R=210R-R^2\le 210\cdot 190-190^2=3800$$



Dấu bằng đạt được trong cách xây dựng ở trên, ứng với $R=C=190$.
Vậy số quân cờ lớn nhất có thể đặt là 3800.

Nếu hai ước $x,y$ được ghép thành một cặp thì $x+y=3^k$, khi đó $v_3(x)=v_3(y)$.
Mọi lũy thừa của 3 xuất hiện ở đây đều lẻ, nên mỗi cặp gồm đúng một ước lẻ và một ước chẵn.
Viết $n=3^{a}m=2^s{3}^{a}u$ với $a$ là số tự nhiên và $m$ nguyên dương không chia hết cho 3, $u$ lẻ và $\gcd (u,3)=1$.
Số ước lẻ của $n$ là $(a+1)\tau (u)$ còn số ước chẵn của $n$ là $s(a+1)\tau (u)$ nên $s=1$.
Do đó $m=2u$ với $\gcd (u,6)=1$.
Vì hai ước được ghép với nhau có cùng $v_3$ nên tập các ước của $n$ không chia hết cho 3 được ghép cặp bên trong chính nó, và các ước này chính là của $2u$.
Các ước lẻ của $2u$ có dạng $d$ với $d\mid u$, còn các ước chẵn có dạng $2e$ với $e\mid u$, do đó tồn tại một hoán vị $f$ của tập các ước dương của $u$ sao cho $d+2f(d)$ là lũy thừa của 3 với mọi $d\mid u$.
Ta sẽ chứng minh $u$ là số square-free.
Lấy một số nguyên tố $p\mid u$. Trong các ước của $u$, số ước chia hết cho $p$ là $\frac{v_p(u)}{v_p(u)+1}\tau (u)$.
Trong một cặp $(d,2f(d))$, không thể đồng thời có $p\mid d$ và $p\mid f(d)$, vì khi đó $p\mid d+2f(d)=3^k$, trái với $p\ne 3$. Khi $d$ đi qua tất cả các ước của $u$, cả $d$ và $f(d)$ đều xuất hiện trong tập này đúng 1 lần. Do đó
$$2\cdot \frac{v_p(u)}{v_p(u)+1}\tau (u)\le \tau (u),$$
suy ra $v_p(u)\le 1$. Từ đó $u$ là số square-free.
Dấu bằng xảy ra nên $(d,2f(d))$ có đúng một trong hai số chia hết cho $p$ nên buộc $f(d)=\frac{u}{d}$ với mọi $d\mid u$.
Cho $d=1$ và $d=u$ suy ra $1+2u$ và $u+2$ đều phải là lũy thừa của 3.
Đặt $1+2u=3^r$, $u+2=3^s$ với $r,s$ nguyên dương thì $3^r=2\cdot 3^s-3=3\left(2\cdot 3^{s-1}-1\right)$.
Nếu $s\ge 2$ thì $2\cdot 3^{s-1}-1$ không chia hết cho 3, do đó $s=1$ nên $u=1$, từ đó $m=2$ hay $n=3^a\cdot 2$ với mọi số tự nhiên $a$, thử lại bằng cách ghép cặp $(3^i,2\cdot 3^i)$ với $0\le i\le a$ thấy thỏa mãn.
Vậy tất cả số nguyên dương $n$ cần tìm là $n=3^a\cdot 2$ với $a$ tự nhiên.

Giả sử các lũy thừa cơ số $p$ biểu diễn được là $p^{a_1}<p^{a_2}<\cdots <p^{a_t}$, ta cần tìm giá trị lớn nhất của $t$.

Gọi $A_i$ là tập gồm 3 phần tử sao cho tổng các phần tử trong $A_i$ bằng $p^{a_i}$, với $i=1,2,\dots t$.

Ta có $|A_1\cup A_2\cup \cdots \cup A_t|\le n$.

Nhận xét: Với mỗi $i\ge 2$, ta có $A_i\setminus (A_1\cup A_2\cup \cdots \cup A_{i-1})\ne \varnothing$.

Giả sử phản chứng, tức $(A_1\cup A_2\cup \cdots \cup A_{i-1})\subset A_i$.

Khi đó cứ với $x\in A_i$ thì tồn tại $j<i$ sao cho $x\in A_j$ thì $x<{\sum }_{a\in A_j}a=p^j\le p^{i-1}$.

Từ đó tổng các phần tử của $A_i$ bé hơn $3p^{i-1}<p^i$, vô lý. Nhận xét được chứng minh.

Từ nhận xét trên ta có $|A_1|=3$, $|A_2\setminus A_1|\ge 1$, $|A_3\setminus (A_1\cup A_2)|\ge 1,\dots$

Do đó $n\ge |A_1\cup A_2\cup \cdots \cup A_t|\ge 3+1+1+\cdots +1=3+(t-1)=t+2$.

Vậy $t\le n-2$. Dấu bằng xảy ra chẳng hạn với tập

$$S=\{1,2,p^2-3,p^3-3,\dots p^{n-2}-3\}$$

Vậy giá trị lớn nhất của $l_p(S)$ bằng $n-2$.

Với mỗi $i=0,1,\dots ,n$, đặt $d_i=c_A(i)-c_B(i)$. Ta xem $(d_i{)}_{i=0}^n$ như một quỹ đạo xuất phát từ $d_0=0$.

Ở mỗi lượt, quỹ đạo có một trong bốn loại bước:



Điều kiện để $A$ đạt giải đặc biệt tương đương với

$$d_i\ge -1(1\le i\le n),d_n>0.$$

Gọi $U_n(r)$ là số quỹ đạo không bị ràng buộc, có độ dài $n$, xuất phát từ $0$ và kết thúc tại $r$.

Ta biến mỗi bước của quỹ đạo thành hai bước lên hoặc xuống như sau:



Đây là một song ánh giữa các quỹ đạo độ dài $n$ kết thúc tại $r$ và các quỹ đạo gồm $2n$ bước lên, xuống, kết thúc tại độ cao $2r$. Nếu quỹ đạo mới có $a$ bước lên và $2n-a$ bước xuống thì

$$a-(2n-a)=2r,$$

suy ra $a=n+r$, do đó $U_n(r)=C_{2n}^{n+r}$.

Bây giờ cố định $r\ge 1$. Xét một quỹ đạo kết thúc tại $r$ nhưng vi phạm điều kiện $d_i\ge -1$.

Gọi $t$ là thời điểm đầu tiên quỹ đạo đạt tới $-2$.

Ta xét phần quỹ đạo từ thời điểm 0 đến thời điểm $t$: đổi mỗi bước 1 thành $-1$, mỗi bước $-1$ thành 1, còn hai loại bước 0 được giữ nguyên. Khi đó, phần quỹ đạo này kết thúc tại 2 thay vì $-2$.

Phần quỹ đạo sau thời điểm $t$ có tổng độ thay đổi bằng $r-(-2)=r+2$.

Vì thế quỹ đạo mới kết thúc tại $2+(r+2)=r+4$.

Ngược lại, mọi quỹ đạo kết thúc tại $r+4$ đều phải đi qua 2. Phần quỹ đạo mới từ đầu đến lần đầu tiên đạt 2, ta thu được một quỹ đạo kết thúc tại $r$ và vi phạm điều kiện $d_i\ge -1$.

Do đó, số quỹ đạo vi phạm kết thúc tại $r$ bằng $U_n(r+4)$.

Bởi vậy, số quỹ đạo hợp lệ kết thúc tại $r$ là $U_n(r)-U_n(r+4)=C_{2n}^{n+r}-C_{2n}^{n+r+4}$.

Cộng theo $r=1,2,\dots ,n$, ta được

$$\sum _{r=1}^n\left(C_{2n}^{n+r}-C_{2n}^{n+r+4}\right)=\sum _{r=1}^{\min \{4,n\}}{C}_{2n}^{n+r}.$$

Vậy số kịch bản cần tính bằng $\sum _{r=1}^{\min \{4,n\}}{C}_{2n}^{n+r}$.

Nhận xét: Bài toán trên liên quan tới bài toán quỹ đạo nổi tiếng sau:

Bài toán bỏ phiếu bầu cử: Cho hai ứng cử viên $A$ và $B$, biết rằng $A$ nhận $a$ phiếu bầu cử, $B$ nhận $b$ phiếu bầu cử và $a>b$. Hỏi có bao nhiêu cách kiểm phiếu sao cho trong suốt quá trình thì số phiếu của $A$ luôn lớn hơn số phiếu $B$? Đáp số: $\frac{a-b}{a+b}{C}_{a+b}^a$.

(AI giải đề cho tôi)
Gọi $a_i$ là số công nhân hoàn thành nhiệm vụ $i$ ($i=1,2,3,4,5$). Theo giả thiết $a_i\ge 170$, nên số công nhân KHÔNG hoàn thành nhiệm vụ $i$ là $250-a_i\le 80$. Xét tất cả các cặp công nhân: có $\left(\genfrac{}{}{0ex}{}{250}{2}\right)=\frac{250\cdot 249}{2}=31125$ cặp. Giả sử phản chứng: với mọi cặp công nhân, tồn tại ít nhất một nhiệm vụ mà cả hai người đều không hoàn thành (tức cặp đó 'hụt' nhiệm vụ nào đó). Với nhiệm vụ $i$, số cặp mà cả hai cùng không hoàn thành nhiệm vụ $i$ nhiều nhất là $\left(\genfrac{}{}{0ex}{}{250-a_i}{2}\right)\le \left(\genfrac{}{}{0ex}{}{80}{2}\right)=3160$. Do đó tổng số cặp 'bị hụt' tính trên cả 5 nhiệm vụ không vượt quá $5\cdot 3160=15800$. Nhưng $15800<31125$, mâu thuẫn với giả thiết phản chứng rằng mọi cặp đều bị hụt ít nhất một nhiệm vụ. Vậy tồn tại một cặp công nhân mà xét chung cả hai người, cả 5 nhiệm vụ đều có ít nhất một người hoàn thành. Đpcm.

(AI giải đề cho tôi)
Số tự nhiên có 4 chữ số khác nhau từ các chữ số 0,1,2,3,4: chữ số đầu tiên không được là 0 nên có 4 cách chọn; chữ số thứ hai có 4 cách (còn 4 chữ số trong đó có 0); chữ số thứ ba có 3 cách; chữ số thứ tư có 2 cách. Tổng: $4\cdot 4\cdot 3\cdot 2=96$ số. Vậy đáp án B.

(AI giải đề cho tôi)
a) Số có 4 chữ số khác nhau từ S={1,...,6}: $A_6^4=6\cdot 5\cdot 4\cdot 3=360\ne 120$ → Sai. b) Số chẵn có 2 chữ số khác nhau: chữ số hàng đơn vị thuộc {2,4,6} (3 cách), hàng chục thuộc 5 số còn lại → $3\cdot 5=15$ → Đúng. c) Số chính phương hai chữ số được tạo từ chữ số của S: 16, 25, 36, 64 (49 loại vì 9∉S) → chỉ 4 số, không phải 5 → Sai. d) $P\cap S=\{1,2,3,4\}$, tổng bình phương $=1+4+9+16=30\ne 31$ → Sai.
a) (AI giải đề cho tôi)
$A_6^4=360\ne 120$
b) (AI giải đề cho tôi)
3 cách chọn chữ số đơn vị (2,4,6) × 5 cách chọn chữ số chục = 15
c) (AI giải đề cho tôi)
Chỉ có 4 số: 16, 25, 36, 64 (49 loại vì 9∉S)
d) (AI giải đề cho tôi)
$P\cap S=\{1,2,3,4\}$, tổng bình phương $=30\ne 31$

Gọi $(I)$ là đường tròn nội tiếp đa giác $P$, ta thu được $2n$ tiếp điểm của $P$ với $(I)$.

Chọn ba cạnh của $P$ và gọi $A,B,C$ lần lượt là các tiếp điểm tương ứng theo chiều kim đồng hồ.

Gọi $x,y,z$ lần lượt là số khoảng giữa hai tiếp điểm liên tiếp khi đi từ $A$ đến $B$, $B$ đến $C$, $C$ đến $A$.

Khi đó $x,y,z$ là các số nguyên dương và $x+y+z=2n$.

Bây giờ ta cần điều kiện để ba đường thẳng đã chọn tạo thành một tam giác phủ $P$.

Giả sử hai tiếp tuyến tại $A,B$ cắt nhau tại $T$ thì $AIBT$ nội tiếp, khi đó từ việc tam giác phủ $P$ ta suy ra được $0<\angle ATB=180^{\circ }-\angle AIB=180^{\circ }-\frac{180^{\circ }x}{n}$ nên $x<n$. Tương tự ta có $y<n$ và $z<n$.

Ngược lại, giả sử $x,y,z<n$ thì tạo thành tam giác phủ $P$ vì khi đó 3 góc của tam giác đó là

$$180^{\circ }-\frac{180^{\circ }x}{n},180^{\circ }-\frac{180^{\circ }y}{n},180^{\circ }-\frac{180^{\circ }z}{n}$$

Vậy điều kiện cần và đủ là $x,y,z<n$.

Như thế, ta chỉ còn phải đếm các bộ số nguyên dương $(x,y,z)$ sao cho $x+y+z=2n$ và $x,y,z<n$.

Đặt $x^{\prime }=n-x$, $y^{\prime }=n-y$, $z^{\prime }=n-z$ thì $x^{\prime },y^{\prime },z^{\prime }>0$ và $x^{\prime }+y^{\prime }+z^{\prime }=n$.

Ngược lại, mỗi bộ số nguyên dương $(x,y,z)$ thỏa mãn $x+y+z=n$ xác định duy nhất một bộ $(x^{\prime },y^{\prime },z^{\prime })$ thỏa mãn các điều kiện trên nên theo bài toán chia kẹo Euler, số cách là $C_{n-1}^2$.

Với một bộ có thứ tự $(x,y,z)$ cố định, có $2n$ cách chọn tiếp điểm đầu tiên $A$. Sau khi $A$ và $(x,y,z)$ đã được chọn thì $B,C$ hoàn toàn được xác định. Vì thế ta có $2n{C}_{n-1}^2$ cách chọn.

Trong cách chọn này, mỗi bộ xuất hiện đúng 3 lần nên số tam giác cần tìm là

$$\frac{2n{C}_{n-1}^2}{3}=\frac{2n}{3}\cdot \frac{(n-1)(n-2)}{2}=\frac{n(n-1)(n-2)}{3}.$$

a) (2,0 điểm) Ta gọi một hàng là "xanh" nếu trên đó có ít nhất 2 ô tô xanh. Nếu trên hàng đó có ô tô màu đỏ thì xét điều kiện (i) cho ô màu đỏ này, ta có ngay điều vô lý vì trên hàng đó có nhiều hơn 1 ô xanh là khác màu với nó. Như thế, trên hàng xanh sẽ không có ô đỏ nào, và tương tự cũng không có ô vàng nào. (1,0 điểm)

Định nghĩa tương tự với cột "xanh" và hàng/cột "vàng", "đỏ". Như thế, các hàng xanh, đỏ, vàng là đôi một rời nhau nên $x_1+d_1+v_1\le 21$. Tương tự, ta cũng có $x_2+d_2+v_2\le 24$ và cộng lại thì được $x_1+x_2+d_1+d_2+v_1+v_2\le 21+24=45$. (1,0 điểm)

b) (3,0 điểm) Đặt $X=x_1+x_2$, $D=d_1+d_2$, $V=v_1+v_2$ và $a$ là tổng số hàng/cột còn lại, không thuộc các nhóm trên, gọi là hàng/cột "thường". Ta có $X+D+V+a=45$. (0,5 điểm)

Ta thấy rằng một ô được tô xanh thì có thể thuộc về một hàng xanh, một cột xanh hoặc hàng/cột thường (mỗi hàng/cột thường cũng chỉ chứa không quá 1 ô xanh). Do có $x_1$ hàng xanh, $x_2$ cột xanh nên chúng giao nhau tại $x_1{x}_2$ ô, kéo theo số ô được tô xanh tối đa là $x_1{x}_2+a$. (1,0 điểm)

Theo bất đẳng thức AM-GM, $x\le x_1{x}_2+a\le \frac{(x_1+x_2{)}^2}{4}+a=\frac{X^2}{4}+a$. Không mất tính tổng quát, giả sử $X=\min \{X,D,V\}$ thì $45-a=X+D+V\ge 3X$. Suy ra
$$\frac{X^2}{4}+a\le \frac{(45-a{)}^2}{4\cdot 9}+a=56+\frac{a(a-54)+9}{36}\le 56+\frac{9}{36}=56+\frac{1}{4},$$
đánh giá cuối đúng vì $0\le a\le 45$. (1,0 điểm)

Vì thế nên $m\le x\le \frac{X^2}{4}+a\le 56+\frac{1}{4}$. Giá trị lớn nhất cần tìm là 56.

Ta xét ví dụ xây dựng trong hình bên dưới (theo thứ tự xanh, đỏ, vàng):

[Hình cần kiểm tra lại: p7_f1] (0,5 điểm)

Lưu ý. Các bài toán ở trên đây có thể có nhiều cách giải. Ban giám khảo căn cứ tình hình cụ thể để cho điểm nếu thí sinh làm khác cách giải của hướng dẫn chấm thi.

a) (2,0 điểm) Tổng số lượt tham gia là $26\cdot 20=520$. Vì mỗi học sinh tham gia không quá 2 buổi nên số lượt tham gia sẽ không quá $2n$. Do đó, ta có $2n\ge 520$, giải ra được $n\ge 260$. Giá trị nhỏ nhất cần tìm là 260. (1,0)

Xây dựng cho $n=260$; mỗi học sinh sẽ tham gia đúng 2 buổi. Coi mỗi buổi như 1 đỉnh của đồ thị đơn và học sinh tương ứng với cạnh. Xếp các đỉnh của đồ thị lên vòng tròn và mỗi đỉnh sẽ nối với 10 đỉnh liền trước và 10 đỉnh liền sau. Như thế, bậc mỗi đỉnh là 20, ứng với mỗi buổi có 20 học sinh và vì đây là đồ thị đơn nên 2 buổi bất kỳ có chung không quá 1 học sinh. Số học sinh là $n=\frac{26\cdot 20}{2}=260$. (1,0)

b) (3,0 điểm) Nhận xét: “2 học sinh bất kỳ tham gia chung không quá 1 buổi” tương đương với “2 buổi bất kỳ có chung không quá 1 học sinh tham gia”.
Gọi $x_1,x_2,\dots ,x_n$ là số buổi mà các học sinh $1,2,\dots ,n$ tham gia. Ta có ngay
$$x_1+x_2+\cdots +x_n=26\cdot 20=520.$$
Gọi $S$ là số bộ $(\{A,B\},C)$ mà học sinh $C$ có tham gia vào cặp buổi $\{A,B\}$.
• Đếm theo cặp buổi: $S\le C_{26}^2\cdot 1=325$.
• Đếm theo học sinh $C$: $S=C_{x_1}^2+C_{x_2}^2+\cdots +C_{x_n}^2=\frac{1}{2}\left({\sum }_{i=1}^n{x}_i^2-{\sum }_{i=1}^n{x}_i\right)$. (1,0)

Vì $x_i\in \mathbb{Z}$ nên đánh giá $(x_i-2)(x_i-3)\ge 0$ luôn đúng, do đó $x_i^2\ge 5x_i-6$. Do đó ${\sum }_{i=1}^n{x}_i^2\ge 5{\sum }_{i=1}^n{x}_i-6n$. Thay vào đánh giá $S$, ta có $S\ge 2{\sum }_{i=1}^n{x}_i-3n=1040-3n$.
Vì thế $325\ge 1040-3n$, giải ra được $n\ge 239$. Giá trị nhỏ nhất cần tìm là 239. (1,0)

Xây dựng cho $n=239$: gọi $a,b$ lần lượt là số học sinh tham gia 2, 3 buổi. Ta có hệ sau: $a+b=239$, $2a+3b=520\iff a=197$, $b=42$.
Ta coi 26 buổi ứng với 26 đỉnh của một đồ thị đầy đủ $K_{26}$. Mỗi học sinh tham gia 2 buổi sẽ ứng với 1 cạnh nối 2 đỉnh biểu diễn buổi tương ứng. Mỗi học sinh tham gia 3 buổi sẽ ứng với 1 tam giác lấy từ 3 đỉnh của đồ thị. Như vậy cần chọn các tam giác và các cạnh hợp lý sao cho không có 2 cạnh nào bị trùng nhau.
Ta đánh số 26 buổi bởi $A_0,A_1,\dots ,A_{25}$. Ta chọn các tam giác (số thứ tự mod 26):
$${\mathcal{T}}_1=\{\{A_i,A_{i+1},A_{i+3}\}\mid i=0,1,\dots ,25\},{\mathcal{T}}_2=\{\{A_{2i},A_{2i+4},A_{2i+9}\}\mid i=0,1,\dots ,12\},$$
$${\mathcal{T}}_3=\{\{A_1,A_5,A_9\},\{A_7,A_{11},A_{15}\},\{A_{13},A_{17},A_{21}\}\}.$$
Số lượng các bộ ba là $26+13+3=42$. Trong nhóm ${\mathcal{T}}_1$, các cặp đỉnh có số thứ tự cách 1, 2, 3 (mod 26), trong nhóm ${\mathcal{T}}_2$, các cặp đỉnh số thứ tự cách 4, 5, 9 (mod 26), đồng thời với khoảng cách là 4 thì hai đầu đều chẵn; trong nhóm ${\mathcal{T}}_3$, các khoảng cách là 4, 8 (mod 26) và hai đầu đều lẻ. Vì thế không có cạnh nào bị lặp lại.
Tiếp theo, trong ${\mathcal{T}}_1$, mỗi đỉnh thuộc đúng 3 tam giác; trong ${\mathcal{T}}_2$, có mỗi đỉnh chẵn thuộc 2 tam giác và mỗi đỉnh lẻ thuộc 1 tam giác, trong ${\mathcal{T}}_3$, có 9 đỉnh lẻ (trừ các đỉnh 3, 19, 23, 25). Vì thế nên có 22 đỉnh thuộc 5 tam giác và 4 đỉnh thuộc 4 tam giác. Bỏ đi 2 cạnh $A_3{A}_{25},A_{19}{A}_{23}$ và chọn tất cả $C_{26}^2-3\cdot 42-2=197$ cạnh còn lại của đồ thị, mỗi cạnh ứng với 197 học sinh tham gia 2 buổi.
Tiếp theo ta kiểm tra bậc của mỗi đỉnh, ta xét 22 đỉnh thuộc 5 tam giác khi đó mỗi đỉnh loại này có bậc là $26-5-1=20$. Còn bốn đỉnh 3, 19, 23, 25 có mỗi đỉnh thuộc 4 tam giác và do bỏ đi cạnh $A_3{A}_{25},A_{19}{A}_{23}$ từ đồ thị $K_{26}$ ta được mỗi đỉnh loại này có bậc là $26-4-1-1=20$. Do đó ta có 26 đỉnh với mỗi đỉnh có bậc là 20 hay mỗi buổi có đúng 20 học sinh tham gia. (1,0)

Lưu ý. Các bài toán ở trên đây có thể có nhiều cách giải. Ban giám khảo cần cứ tình hình cụ thể để cho điểm nếu thí sinh làm khác cách giải của hướng dẫn chấm thi.

Với mỗi hàng hoặc cột $L$, đặt $d(L)=\gcd \{\text{caˊc soˆˊ na˘ˋm treˆn }L\}$ và gọi $d(L)$ là chỉ số của $L$.
Theo giả thiết, $2n$ chỉ số của $n$ hàng và $n$ cột đôi một khác nhau, ta có các nhận xét:
- Nếu $L$ có chỉ số $d$, thì $n$ số trên $L$ là $n$ bội dương phân biệt của $d$. Vì thế số lớn nhất trên $L$ không nhỏ hơn $nd$.
- Nếu một ô là giao của hàng có chỉ số $a$ và cột có chỉ số $b$, thì số trong ô đó chia hết cho cả $a$ và $b$, do đó chia hết cho $\mathrm{lcm}(a,b)$.

a) Có $2n$ chỉ số là $2n$ số nguyên dương đôi một khác nhau. Bởi vậy, trong các chỉ số ấy phải có một chỉ số $d\ge 2n$. Hàng hoặc cột có chỉ số $d$ chứa $n$ bội dương phân biệt của $d$.
Theo nhận xét trên, số lớn nhất trên hàng hoặc cột này không nhỏ hơn
$$nd\ge n\cdot 2n=2n^2.$$
Vậy trong mọi bảng tốt luôn có một ô chứa số không nhỏ hơn $2n^2$.

b) Giả sử tồn tại một bảng tốt tối tiểu. Nếu một hàng hoặc cột có chỉ số $d$, thì nó chứa một số không nhỏ hơn $nd$. Mặt khác, mọi số trong bảng đều không vượt quá $2n^2$, nên $nd\le 2n^2$, suy ra $d\le 2n$.
Như vậy, $2n$ chỉ số là $2n$ số nguyên dương phân biệt, đều không vượt quá $2n$.
Do đó tập hợp các chỉ số phải chính xác là
$$\{1,2,\dots ,2n\}.\text{\hspace{1em}(1)}$$
Không mất tính tổng quát giả sử chỉ số $2n$ thuộc về một cột, kí hiệu cột đó là $C_{2n}$.
Các số trên $C_{2n}$ là $n$ bội dương phân biệt của $2n$, đồng thời không vượt quá $2n^2$.
Chỉ có đúng $n$ bội như vậy, nên các số trên $C_{2n}$ là
$$2n,4n,6n,\dots ,2n^2.\text{\hspace{1em}(2)}$$

Ta tiếp tục chứng minh các chỉ số $2n-1$ và $2n-2$ cũng thuộc về các cột.

Nếu $2n-1$ là chỉ số của một hàng, thì ô giao của hàng đó với $C_{2n}$ phải chia hết cho
$$\mathrm{lcm}(2n-1,2n)=2n(2n-1)>2n^2,$$
mâu thuẫn với tính tối tiểu. Vậy $2n-1$ là chỉ số của một cột, kí hiệu là $C_{2n-1}$.

Nếu $2n-2$ là chỉ số của một hàng, thì tại giao điểm của hàng đó với $C_{2n-1}$, số trong ô phải chia hết cho $(2n-2)(2n-1)$ vì hai số này nguyên tố cùng nhau. Với $n\ge 3$,
$$(2n-2)(2n-1)-2n^2=2n(n-3)+2>0.$$
Suy ra số trong ô lớn hơn $2n^2$, vô lí. Do đó $2n-2$ cũng là chỉ số của một cột, kí hiệu là $C_{2n-2}$.

Bây giờ giả sử $n$ lẻ. Khi đó $n\ge 3$. Xét hàng hoặc cột $A$ có chỉ số $n$.

Trường hợp 1: $A$ là một cột.
Các số trên $A$ đều là bội của $n$. Theo (2), tất cả các bội chẵn của $n$ không vượt quá $2n^2$, tức là
$$2n,4n,\dots ,2n^2,$$
đều đã nằm trên $C_{2n}$. Vì các số trong bảng đôi một khác nhau, cột $A$ chỉ có thể chứa các bội lẻ của $n$:
$$n,3n,5n,\dots ,(2n-1)n.$$
Có đúng $n$ số như vậy, nên đây chính là các số nằm trên $A$.
Vì $n$ lẻ nên tất cả các số này đều lẻ. Mỗi hàng cắt $A$ tại một số lẻ, do đó chỉ số của mỗi hàng, là ước của số ấy, cũng phải lẻ. Vậy $n$ chỉ số của các hàng chính là $n$ số lẻ trong tập (1):
$$1,3,5,\dots ,2n-1.$$
Đặc biệt, $2n-1$ phải là chỉ số của một hàng. Điều này mâu thuẫn với việc $2n-1$ đã là chỉ số của cột $C_{2n-1}$ nên trường hợp này không xảy ra.

Trường hợp 2: $A$ là một hàng.
Hàng $A$ cắt $C_{2n}$ tại một ô. Ngoài ô này, $n-1$ ô còn lại trên $A$ chứa các bội của $n$ không nằm trên $C_{2n}$. Bởi (2), chúng phải là các bội lẻ của $n$, nên đều là số lẻ.
Do đó $n-1$ cột khác $C_{2n}$ đều có chỉ số lẻ. Như vậy, trong tất cả các cột, cột duy nhất có thể có chỉ số chẵn là $C_{2n}$. Nhưng $C_{2n-2}$ cũng có chỉ số chẵn, mâu thuẫn.
Cả hai trường hợp đều vô lí. Vậy không tồn tại bảng tốt tối tiểu khi $n$ lẻ.

c) Để ý ta chỉ cần xét $n$ chẵn.
Giả sử $n\ge 8$ chẵn và tồn tại một bảng tốt tối tiểu. Ta đã biết rằng các chỉ số $2n$, $2n-1$, $2n-2$ đều thuộc về các cột. Với $n\ge 8$, ta có
$$(2n-4)(2n-3)-2n^2=2(n-1)(n-6)>0.\text{\hspace{1em}(3)}$$
Nếu $2n-3$ là chỉ số của một hàng, thì hàng đó cắt cột $C_{2n-2}$ tại một số chia hết cho
$$(2n-3)(2n-2)>(2n-4)(2n-3)>2n^2,$$
vô lí. Do đó $2n-3$ là chỉ số của một cột. Tương tự, nếu $2n-4$ là chỉ số của một hàng thì tại giao điểm với cột $C_{2n-3}$, số trong ô phải chia hết cho
$$(2n-4)(2n-3)>2n^2$$
và theo (3), cũng sẽ vô lí. Vì vậy $2n-4$ là chỉ số của một cột.

Xét cột $C_{2n-2}$. Số bội dương của $2n-2$ không vượt quá $2n^2$ là
$$\lfloor \frac{2n^2}{2n-2}\rfloor =\lfloor \frac{n^2}{n-1}\rfloor =n+1,$$
vì $n^2=(n-1)(n+1)+1$. Cột $C_{2n-2}$ đã chứa $n$ bội phân biệt của $2n-2$.
Vì vậy, trong toàn bộ phần còn lại của bảng, có nhiều nhất một số chia hết cho $2n-2$. (4)

Xét hàng hoặc cột $A$ có chỉ số $n-1$. Vì $n$ chẵn nên $n-1$ lẻ. Bởi vậy, một bội của $n-1$ là số chẵn khi và chỉ khi nó chia hết cho $2(n-1)=2n-2$. (5)

Trường hợp 1: $A$ là một cột.
Theo (4) và (5), $A$ chứa nhiều nhất một số chẵn. Do đó ít nhất $n-1$ hàng cắt $A$ tại một số lẻ, nên ít nhất $n-1$ hàng có chỉ số lẻ.
Trong tập $\{1,2,\dots ,2n\}$ chỉ có $n$ số lẻ. Vì thế các cột có nhiều nhất một chỉ số lẻ. Nhưng $2n-1$ và $2n-3$ là hai chỉ số lẻ cùng thuộc về các cột, mâu thuẫn.

Trường hợp 2: $A$ là một hàng.
Ngoài cột $C_{2n-2}$, theo (4), hàng $A$ có nhiều nhất một ô chứa số chẵn. Một cột có chỉ số chẵn thì mọi số trên cột ấy đều chẵn. Vì vậy, ngoài $C_{2n-2}$, có nhiều nhất một cột mang chỉ số chẵn.
Tuy nhiên, $C_{2n}$ và $C_{2n-4}$ là hai cột khác $C_{2n-2}$, đều có chỉ số chẵn. Lại mâu thuẫn.
Vậy không tồn tại bảng tốt tối tiểu với $n\ge 8$ chẵn.

Khi $n=6$, ta đã biết các chỉ số 12, 11, 10 thuộc về các cột.
Giả sử một trong các số 7, 8, 9 là chỉ số của một hàng. Hàng ấy cắt cột $C_{11}$ tại một số chia hết lần lượt cho $7.11=77$, $8.11=88$ và $9.11=99$.
Cả ba số đều lớn hơn $2n^2=72$. Do đó 7, 8, 9 đều phải là chỉ số của các cột.
Như vậy sáu cột có các chỉ số
$$7,8,9,10,11,12.$$
Suy ra chỉ số 5 thuộc về một hàng, gọi là $R_5$. Cột $C_{10}$ chứa 6 bội phân biệt của 10.
Trong khi đó, chỉ có
$$10,20,30,40,50,60,70$$
là các bội dương của 10 không vượt quá 72. Vì thế, ngoài $C_{10}$, toàn bảng chứa nhiều nhất một bội của 10. Các số trên $R_5$ đều là bội của 5. Một số như vậy chẵn khi và chỉ khi nó là bội của 10. Do đó, ngoài giao điểm với $C_{10}$, hàng $R_5$ có nhiều nhất một ô chứa số chẵn.
Suy ra trong năm cột khác $C_{10}$, nhiều nhất một cột có chỉ số chẵn. Nhưng $C_8$ và $C_{12}$ đều là các cột có chỉ số chẵn và đều khác $C_{10}$, mâu thuẫn. Vậy $n=6$ cũng không thỏa mãn.

Vậy $n=2$ và $n=4$ là tất cả giá trị thoả mãn yêu cầu bằng cách xét các bảng sau:

Đặt $R=3m$, $C=6n$. Gọi $w_i$ là số ô trắng ở hàng $i$ và $v_j$ là số ô trắng ở cột $j$.

Với mỗi ô đỏ $(i,j)$ được chọn làm $C_2$, có đúng $w_i$ cách chọn $C_1$ và $v_j$ cách chọn $C_3$. Vì thế
$$T=\sum _{(i,j)\text{ đỏ}}{w}_i{v}_j.$$

Theo bất đẳng thức Bunhiacopxki, ta có
$$T^2\le \left(\sum _{(i,j)\text{ đỏ}}{w}_i^2\right)\left(\sum _{(i,j)\text{ đỏ}}{v}_j^2\right)=\left(\sum _{i=1}^R(C-w_i)w_i^2\right)\left(\sum _{j=1}^C(R-v_j)v_j^2\right).$$

Với $0\le u\le C$ thì $(C-u)u^2\le \frac{4C^3}{27}$ và $(R-v)v^2\le \frac{4R^3}{27}$, do đó
$$T\le \sqrt{R\cdot \frac{4C^3}{27}C\cdot \frac{4R^3}{27}}=\frac{4}{27}{R}^2{C}^2=48m^2{n}^2.$$

Để đạt dấu bằng, chia $3m$ hàng thành ba nhóm, mỗi nhóm $m$ hàng; chia $6n$ cột thành ba nhóm, mỗi nhóm $2n$ cột. Tô đỏ ba khối nằm trên đường chéo tạo bởi các cặp nhóm cùng chỉ số và tô trắng các ô còn lại. Khi đó mỗi hàng có $2n$ ô đỏ, $4n$ ô trắng; mỗi cột có $m$ ô đỏ, $2m$ ô trắng. Có $6mn$ ô đỏ và mỗi ô đỏ đóng góp $(4n)(2m)=8mn$ bộ ba. Bởi vậy $T=6mn\cdot 8mn=48m^2{n}^2$.

Do đó giá trị lớn nhất cần tìm là $\boxed{48m^2{n}^2}$.

(AI giải đề cho tôi)
Gọi $E_A,E_B,E_C$ là biến cố 'hộp tương ứng chứa đủ 6 quả bóng và các bóng tăng dần từ trên xuống'. Các hộp được phân biệt bởi vị trí (như hình vẽ).

Ta có:
$$|E_A|=\left(\genfrac{}{}{0ex}{}{15}{6}\right)\cdot A_{12}^9=5005\cdot \frac{12!}{3!}=5005\cdot 79833600=399567168000.$$
(Giải thích: chọn 6 quả cho hộp $A$, thứ tự trong hộp bị ép buộc tăng dần; 9 quả còn lại đặt vào 12 ngăn của hai hộp kia: $12\cdot 11\cdots 4=\frac{12!}{3!}$.)

Hai hộp cùng vừa đầy vừa tăng dần:
$$|E_A\cap E_B|=\left(\genfrac{}{}{0ex}{}{15}{6}\right)\left(\genfrac{}{}{0ex}{}{9}{6}\right)\cdot A_6^3=5005\cdot 84\cdot 120=50450400,$$
tương tự cho các cặp khác; ba hộp cùng đầy là không thể.

Số cách để đúng một hộp thỏa mãn (bằng bao hàm – loại trừ):
$$N=3|E_A|-2\cdot 3|E_A\cap E_B|=1198701504000-302702400=1198398801600.$$

Do đó:
$$\frac{N}{20175064}=\frac{1198398801600}{20175064}=59400.$$

(AI giải đề cho tôi)
Góc nội tiếp $\hat{A}$ của tam giác nội tiếp bằng nửa số đo cung $BC$ không chứa $A$, nên $\hat{A}>100^{\circ }\iff$ cung $BC$ không chứa $A$ lớn hơn $200^{\circ }\iff$ cung $BC$ chứa $A$ nhỏ hơn $160^{\circ }$. Đa giác đều 2026 đỉnh nội tiếp đường tròn, mỗi cạnh chắn cung $\frac{360^{\circ }}{2026}$. Cố định đỉnh $A$; gọi $B$ cách $A$ $i$ đỉnh về một phía, $C$ cách $A$ $j$ đỉnh về phía kia ($i,j\ge 1$). Khi đó cung nhỏ $BC$ chứa $A$ gồm $i+j$ cạnh nên có số đo $\frac{(i+j)\cdot 360^{\circ }}{2026}<160^{\circ }\iff i+j<\frac{2026\cdot 160}{360}=\frac{8104}{9}\approx 900,44$, tức $i+j\le 900$. Số cặp $(i,j)$: ${\sum }_{s=2}^{900}(s-1)=\frac{899\cdot 900}{2}=C_{900}^2$. Vì tổng ba góc bằng $180^{\circ }$, mỗi tam giác có nhiều nhất một góc lớn hơn $100^{\circ }$ nên không bị đếm trùng. Vậy số tam giác cần tìm là $2026\cdot C_{900}^2$, trùng với đáp án A của đề.

Lời giải.

a) Trước hết xét một dãy gồm $m$ đỉnh thẳng hàng. Gọi $a_m$ là số cách tô đỏ, xanh các đỉnh sao cho không có hai đỉnh xanh liên tiếp.

Ta có $a_1=2$, $a_2=3$. Với $m\ge 3$, xét màu của đỉnh cuối cùng. Nếu đỉnh cuối màu đỏ thì $m-1$ đỉnh trước có $a_{m-1}$ cách tô. Nếu đỉnh cuối màu xanh thì đỉnh ngay trước nó bắt buộc màu đỏ, còn $m-2$ đỉnh đầu có $a_{m-2}$ cách tô. Do đó $a_m=a_{m-1}+a_{m-2}$.

Trở lại với đa giác 2026 đỉnh. Xét màu của $A_1$.

- Nếu $A_1$ màu đỏ thì $A_2,A_3,\dots ,A_{2026}$ là một dãy 2025 đỉnh, nên có $a_{2025}$ cách tô.
- Nếu $A_1$ màu xanh thì do $A_2$ và $A_{2026}$ đều kề $A_1$, hai đỉnh này bắt buộc màu đỏ. Khi đó chỉ còn dãy $A_3,A_4,\dots ,A_{2025}$ gồm 2023 đỉnh cần tô, nên có $a_{2023}$ cách.

Vì vậy số cách tô là $a_{2025}+a_{2023}={\left(\frac{\sqrt{5}+1}{2}\right)}^{2026}+{\left(\frac{\sqrt{5}-1}{2}\right)}^{2026}$.

b) Ta biểu diễn mỗi cách tô bằng một quỹ đạo trên lưới ô vuông, xuất phát từ $O=(0,0)$ như sau:

- Nếu $A_i$ được tô đỏ thì đi một bước sang phải.
- Nếu $A_i$ được tô xanh thì đi một bước lên trên.

Sau $k$ bước, hoành độ của điểm đang đứng bằng số đỉnh đỏ trong $A_1,A_2,\dots ,A_k$, còn tung độ bằng số đỉnh xanh. Vì vậy điều kiện của bài toán tương đương với việc quỹ đạo luôn nằm trên hoặc phía dưới đường thẳng $y=x$.

Giả sử có đúng $j$ đỉnh xanh, với $0\le j\le 1013$. Khi đó có $2026-j$ đỉnh đỏ, nên quỹ đạo đi từ $(0,0)$ đến $(2026-j,j)$ bằng $2026-j$ bước sang phải và $j$ bước lên.

Nếu bỏ qua điều kiện $y\le x$, số quỹ đạo là $C_{2026}^j$, và ta cần tính số quỹ đạo không thoả mãn.

Một quỹ đạo như vậy phải có lúc đi lên phía trên đường $y=x$. Xét điểm đầu tiên quỹ đạo chạm đường $y=x+1$, giả sử đó là $(t,t+1)$. Lúc lấy đối xứng quỹ đạo từ $(0,0)$ đến $(t,t+1)$ qua đường $y=x$, tức là đổi mỗi bước sang phải thành bước lên và mỗi bước lên thành bước sang phải. Khi đó điểm $(t,t+1)$ biến thành $(t+1,t)$, nên toàn bộ quỹ đạo biến thành một quỹ đạo từ $(0,0)$ đến $(2027-j,j-1)$.

Ngược lại, với một quỹ đạo bất kỳ từ $(0,0)$ đến $(2027-j,j-1)$, vì hoành độ cuối lớn hơn tung độ cuối nên quỹ đạo có một điểm đầu tiên nằm trên đường $x=y+1$. Đối xứng đoạn đầu đến điểm đó qua $y=x$ ta thu lại duy nhất một quỹ đạo từ $(0,0)$ đến $(2026-j,j)$ đã đi lên phía trên $y=x$. Do đó đây là một song ánh.

Vì quỹ đạo từ $(0,0)$ đến $(2027-j,j-1)$ có đúng $j-1$ bước lên trong tổng số 2026 bước, số quỹ đạo không thỏa mãn là $C_{2026}^{j-1}$. Vậy với đúng $j$ đỉnh xanh, số cách tô thỏa mãn là $C_{2026}^j-C_{2026}^{j-1}$, với quy ước $C_{2026}^{-1}=0$. Cộng $j$ từ 0 tới 1013, ta được số cách tô thoả mãn là
$$\sum _{j=0}^{1013}\left(C_{2026}^j-C_{2026}^{j-1}\right)=C_{2026}^{1013}.$$

Nhận xét. Bài toán trên sử dụng ý tưởng quỹ đạo tương tự với Hùng Yên TST 2026. Bài toán: Cho số nguyên dương $n$. Hai bạn $A$ và $B$ cùng tham gia một trò chơi gồm $n$ lượt. Mỗi lượt, họ độc lập giải cùng một câu đố và kết quả là mỗi người chơi hoặc giải được hoặc không giải được. Đặt $c_A(i),c_B(i)$ lần lượt là tổng số câu đố mà $A,B$ giải được trong $i$ lượt đầu tiên. Hỏi có bao nhiêu kịch bản có thể xảy để $A$ đạt giải đặc biệt, nghĩa là sau khi kết thúc toàn bộ $n$ lượt chơi, $A$ không chỉ giải được nhiều câu đố hơn $B$ ($c_A(n)>c_B(n)$), mà còn chưa bao giờ để $B$ bỏ xa quá một câu trong suốt quá trình ($\forall i=1,2,\dots ,n:c_B(i)-c_A(i)\le 1$)?

Lời giải.

Với mỗi học sinh $A$, ký hiệu $d_A$ là số học sinh quen $A$.

Trước hết chứng minh mọi học sinh đều có cùng số người quen.

Lấy hai học sinh phân biệt $A,B$ và ta sẽ đếm số dãy $A-X-Y-B$ mà hai học sinh liên tiếp quen nhau.

Nếu $A,B$ không quen nhau, trong số $d_A$ học sinh $X$ quen $A$ có đúng $2n$ học sinh cũng quen $B$. Do đó số dãy trên bằng $2n\cdot n+(d_A-2n)\cdot 2n=2n{d}_A-2n^2$. Tương tự cũng có số dãy trên bằng $2n{d}_B-2n^2$, suy ra $d_A=d_B$.

Nếu $A,B$ quen nhau, trường hợp $X=B$ cho $d_B$ cách chọn $Y$. Ngoài ra có $n$ học sinh $X$ quen cả $A,B$, và $d_A-n-1$ học sinh $X$ quen $A$ nhưng không quen $B$. Vì vậy số dãy là $d_B+n^2+2n(d_A-n-1)$, tương tự cũng bằng $d_A+n^2+2n(d_B-n-1)$. Suy ra $(2n-1)(d_A-d_B)=0$, nên $d_A=d_B$.

Vậy mọi học sinh đều có cùng số người quen, kí hiệu là $d$.

Cố định một học sinh $A$ và ta sẽ đếm số cặp có thứ tự $(B,C)$ sao cho $A$ quen $B$, $B$ quen $C$ và $C\ne A$. Dễ dàng tính được số cặp như trên bằng $d(d-1)$.

Mặt khác, nếu $C$ quen $A$ thì có $n$ cách chọn $B$, còn nếu $C$ không quen $A$ thì có $2n$ cách. Do đó
$$d(d-1)=dn+2n(3n-1-d)$$
Khi đó $(d-2n)(d+3n-1)=0$, và vì $d>0$ suy ra $d=2n$.

Do đó mỗi học sinh đều quen đúng $2n$ người khác.

a) Số cặp học sinh quen nhau là $\frac{3n\cdot 2n}{2}=3n^2$. Mỗi cặp quen nhau có đúng $n$ người quen chung, nên nằm trong đúng $n$ nhóm "Bạn bè". Mỗi nhóm "Bạn bè" có ba cặp học sinh quen nhau. Vì vậy số nhóm "Bạn bè" là
$$\frac{3n^2\cdot n}{3}=n^3.$$

b) Với mỗi học sinh $A$, gọi $T_A$ là tập gồm $A$ và tất cả những học sinh không quen $A$. Vì $A$ quen đúng $2n$ học sinh nên $|T_A|=n$.

Nếu $A$ không quen $B$, hai học sinh này có đúng $2n$ người quen chung. Mà cả $A$ và $B$ đều có đúng $2n$ người quen, nên tập những người quen của $A$ và của $B$ trùng nhau. Do đó $T_A=T_B$.

Suy ra các tập $T_A$ hoặc trùng nhau, hoặc rời nhau, và mỗi tập có đúng $n$ phần tử. Vì có $3n$ học sinh nên toàn bộ học sinh được chia thành đúng ba tập như vậy, gọi là $T_1,T_2,T_3$.

Hai học sinh thuộc hai tập khác nhau phải quen nhau; nếu không thì chúng phải thuộc cùng một tập. Vì thế, chọn một học sinh từ mỗi $T_1,T_2,T_3$ thì ba học sinh đó đôi một quen nhau.

Vậy ba tập $T_1,T_2,T_3$ là ba tổ cần tìm.

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 }$.