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)

Lời giải (Lim Olympic - Nghệ An TST - P7).

Quy ước các chỉ số theo modulo $n$. Với mỗi cách bố trí $x=(x_1,x_2,\dots ,x_n)$, đặt $x_i=1$ nếu đèn thứ $i$ sáng và $x_i=0$ nếu đèn thứ $i$ tắt. Khi đó $s_i=x_i+x_{i+1}+\cdots +x_{i+k-1}$.

a) Ta chứng minh điều kiện cần và đủ là $\gcd (n,k)=1$.

Trước hết, giả sử $d=\gcd (n,k)>1$. Xét cấu hình $x$ trong đó đúng các đèn có chỉ số đồng dư 1 modulo $d$ sáng, và cấu hình $y$ trong đó đúng các đèn có chỉ số đồng dư 2 modulo $d$ sáng. Trong $k$ vị trí liên tiếp, mỗi lớp đồng dư modulo $d$ xuất hiện đúng $k/d$ lần. Vì thế cả hai cấu hình đều cho $s_i=k/d$ với mọi $i$. Hai cấu hình khác nhau nhưng có cùng bản ghi, nên ta loại trường hợp này.

Ngược lại, giả sử $\gcd (n,k)=1$. Từ bản ghi, ta có $s_{i+1}-s_i=x_{i+k}-x_i$. Do $\gcd (n,k)=1$, dãy chỉ số $1,1+k,1+2k,\dots ,1+(n-1)k$ modulo $n$ đi qua tất cả các vị trí. Bắt đầu từ $x_1$ và dùng liên tiếp các đẳng thức trên, ta biểu diễn được $x_i=x_1+C_i$ với mọi $i$, trong đó mỗi $C_i$ hoàn toàn được xác định bởi bản ghi.

Thay vào $s_1=x_1+x_2+\cdots +x_k$, ta được $k{x}_1+C=s_1$, trong đó $C=C_1+C_2+\cdots +C_k$ đã biết. Vì $k>0$, giá trị $x_1$ được xác định duy nhất nên $x_1,x_2,\dots ,x_n$ cũng được xác định duy nhất.

Vậy điều kiện cần và đủ là $\gcd (n,k)=1$.

b) Đặt $d=\gcd (n,k)$, viết $n=dm$ và $k=dq$. Xét hai cấu hình $x,y$ và đặt $c_i=x_i-y_i$. Hai cấu hình cho cùng bản ghi khi và chỉ khi $c_i+c_{i+1}+\cdots +c_{i+k-1}=0$ với mọi $i$. Trừ hai đẳng thức liên tiếp, ta được $c_{i+k}=c_i$ với mọi $i$. Do đó $c_i$ không đổi trên mỗi lớp đồng dư modulo $d$.

Gọi giá trị của hiệu trên lớp thứ $r$ là $c_r$. Vì mỗi đoạn gồm $k=dq$ vị trí liên tiếp chứa đúng $q$ phần tử thuộc mỗi lớp đồng dư modulo $d$, điều kiện tổng bằng 0 tương đương với $c_1+c_2+\cdots +c_d=0$. Ngược lại, điều kiện này cùng với việc hiệu không đổi trên mỗi lớp đồng dư cùng cho ta điều kiện đủ để hai cấu hình cho cùng bản ghi.

Giờ ta chia các ngọn đèn thành $d$ đường ray.

Với $1\le r\le d$, đặt $X_r=(x_r,x_{r+d},\dots ,x_{r+(m-1)d})\in \{0,1{\}}^m$ là đường ray thứ $r$. Nếu một đường ray của $x$ chứa cả 0 và 1 thì bắt buộc $c_r=0$, nên đường ray đó được giữ nguyên trong $y$. Một đường ray toàn 1 chỉ có thể được giữ nguyên hoặc đổi thành toàn 0; tương tự, một đường ray toàn 0 chỉ có thể được giữ nguyên hoặc đổi thành toàn 1.

Với mỗi cấu hình $x=(x_1,x_2,\dots ,x_n)$, gọi

$$\varphi (x)=\left\{y\in \{0,1{\}}^n:y\text{ cho cuˋng bản ghi với }x\right\}.$$

Như vậy, $\varphi (x)$ là lớp gồm tất cả các cấu hình cho cùng một bản ghi với $x$, còn $|\varphi (x)|$ là số cấu hình thuộc lớp đó. Giả sử $x$ có đúng $u$ đường ray toàn 1, $v$ đường ray toàn 0 và $d-u-v$ đường ray hỗn hợp (tức có cả 0 và 1). Để thu được một cấu hình $y\in \varphi (x)$, ta chọn $j$ trong $u$ đường ray toàn 1 để đổi thành toàn 0, đồng thời chọn đúng $j$ trong $v$ đường ray toàn 0 để đổi thành toàn 1. Các đường ray còn lại được giữ nguyên. Do đó theo Vandermonde ta có

$$|\varphi (x)|=\sum _{j=0}^{\min (u,v)}{C}_u^j{C}_v^j=C_{u+v}^u,$$

Ta gán cho mỗi cấu hình $x$ trọng số $\frac{1}{|\varphi (x)|}$. Xét một lớp $\mathcal{L}$ có đúng $h$ cấu hình. Với mọi $x\in \mathcal{L}$, ta có $\varphi (x)=\mathcal{L}$, nên $|\varphi (x)|=h$. Vì thế tổng trọng số của các cấu hình thuộc $\mathcal{L}$ bằng

$$\sum _{x\in \mathcal{L}}\frac{1}{|\varphi (x)|}=h\cdot \frac{1}{h}=1.$$

Do đó, khi cộng trên tất cả các cấu hình, mỗi lớp tương đương, hay mỗi bản ghi phân biệt, được tính đúng một lần. Bởi vậy $T=\sum _{x\in \{0,1{\}}^n}\frac{1}{|\varphi (x)|}$ là số bản ghi cần tính.

Số cấu hình $x$ đúng $u$ đường ray toàn 1 và $v$ đường ray toàn 0 là $\frac{d!}{u!v!(d-u-v)!}(2^m-2{)}^{d-u-v}$ nên

$$T=\sum _{\begin{array}{c}u,v\ge 0\\ u+v\le d\end{array}}\frac{d!}{u!v!(d-u-v)!}(2^m-2{)}^{d-u-v}\frac{u!v!}{(u+v)!}=\sum _{u+v=0}^d{C}_d^{u+v}(u+v+1)(2^m-2{)}^{d-u-v}$$

Kết hợp với việc $(u+v)C_d^{u+v}=d{C}_{d-1}^{u+v-1}$ ta suy ra được

$$T=(2^m-1{)}^d+d(2^m-1{)}^{d-1}=(2^m+d-1)(2^m-1{)}^{d-1},$$

trong đó $d=\gcd (n,k)$ và $m=n/d$.

Vậy số bản ghi phân biệt có thể thu được là $T=\left(2^{n/d}+d-1\right){\left(2^{n/d}-1\right)}^{d-1}$ với $d=\gcd (n,k)$.

Trước hết ta có bổ đề quen thuộc sau:

Bổ đề: Với $N$ là hợp số thì $\phi (N)\le N-\sqrt{N}$.

Chứng minh: Thật vậy, gọi $p$ là ước nguyên tố nhỏ nhất của $N$. Khi đó $p\le \sqrt{N}$.

Trong các số $1,2,\dots ,N$ có đúng $N/p$ bội của $p$, và chúng không nguyên tố cùng nhau với $N$. Vì thế
$$N-\phi (N)\ge \frac{N}{p}\ge \sqrt{N}$$

① Giả sử $n$ thỏa mãn $\phi (\phi (n)+k)=n-k$. Ta có $n>k$ và $\phi (n)+k\ge 2$ nên
$$n-k=\phi (\phi (n)+k)\le \phi (n)+k-1.$$
Vì vậy $n-\phi (n)\le 2k-1$. Nếu $n$ là hợp số thì $\sqrt{n}\le n-\phi (n)\le 2k-1$ nên $n\le (2k-1{)}^2$.

Từ đó có hữu hạn hợp số $n$ thoả mãn yêu cầu đề bài.

(2) Giả sử với $k$ nào đó, phương trình có vô số nghiệm nguyên dương $n$. Để ý chỉ có hữu hạn hợp số nên phải có vô số nghiệm $n$ là số nguyên tố, thì $\phi (n)=n-1$ nên
$$\phi (n+k-1)=n-k.$$
Đặt $M=n+k-1$ thì $M-\phi (M)=2k-1$. Nếu $M$ là hợp số thì $\sqrt{M}\le 2k-1$ nên chỉ có hữu hạn giá trị hợp số $M$. Do có vô số giá trị $M$ nên phải có ít nhất 1 giá trị $M$ là số nguyên tố và khi đó
$$M-\phi (M)=1$$
Do đó $2k-1=1$ nên $k=1$. Ngược lại với $k=1$ thì mọi số nguyên tố $n$ thoả mãn yêu cầu nên giá trị duy nhất thoả mãn là $k=1$.

1) Gọi $i$ là vị trí của số 2026.

Vì 2026 là số lớn nhất nên nếu $i<2026$ thì $a_i=2026>a_{i+1}$, tức 2026 là một điểm giảm.

Theo giả thiết đây là điểm giảm duy nhất, do đó $a_1<a_2<\cdots <a_{i-1}<a_i=2026$ và $a_{i+1}<a_{i+2}<\cdots <a_{2026}$. Vì thế, sau khi chọn tập $X=\{a_{i+1},a_{i+2},\dots ,a_{2026}\}\subset \{1,2,\dots ,2025\}$, hoán vị được xác định duy nhất: các phần tử của $\{1,2,\dots ,2025\}\setminus X$ đứng trước 2026 theo thứ tự tăng dần, còn các phần tử của $X$ đứng sau 2026 theo thứ tự tăng dần.

Trong $\{1,2,\dots ,2025\}$ có 1012 số chẵn và 1013 số lẻ. Điều kiện của đề bài tương đương với việc $X$ chọn ít nhất một số chẵn và ít nhất một số lẻ. Số cách chọn là $(2^{1012}-1)(2^{1013}-1)$.

Vậy số hoán vị cần tìm là $(2^{1012}-1)(2^{1013}-1)$.

2) Xét một hoán vị có duy nhất một điểm giảm, ở vị trí $i$.

Khi đó hai dãy $a_1<a_2<\cdots <a_i$ và $a_{i+1}<a_{i+2}<\cdots <a_{2026}$ đều tăng nghiêm ngặt.

Do đó, nếu đặt $B=\{a_1,a_2,\dots ,a_i\}$ thì hoán vị được xác định duy nhất bởi tập $B$: viết các phần tử của $B$ theo thứ tự tăng dần, sau đó viết các phần tử của phần bù $A\setminus B$ theo thứ tự tăng dần.

Tập $B$ phải khác rỗng và khác $A$, nên ban đầu có $2^{2026}-2$ cách chọn.

Hoán vị thu được không có điểm giảm khi và chỉ khi phần tử cuối của khối thứ nhất nhỏ hơn phần tử đầu của khối thứ hai. Điều này xảy ra khi và chỉ khi $B=\{1,2,\dots ,r\}$ với $r\in \{1,2,\dots ,2025\}$ nào đó, và có 2025 trường hợp như vậy.

Vì thế số hoán vị có đúng một điểm giảm là $(2^{2026}-2)-2025=2^{2026}-2027$.

Đặt $m=3n$. Ta đánh số các ô bởi $(i,j)$, trong đó $1\le i,j\le m$, chỉ số $i$ tăng từ trái sang phải và chỉ số $j$ tăng từ dưới lên trên và $L$ là số bước đi.
(1) Trong một hành trình khép kín, gọi $R,U,D$ lần lượt là số bước sang phải, đi lên và đi chéo xuống-sang trái. Để ý $R-D=U-D=0$ nên $R=U=D$ và số bước đi luôn là một bội của 3.
Ta chứng minh quân cờ không thể đi qua cả $m^2$ ô. Giả sử ngược lại. Nối tâm các ô liên tiếp trong hành trình, ta được một đa giác đơn nằm trong hình chữ nhật có bốn đỉnh là tâm của ô góc bảng.
Tại ô góc dưới bên phải $(m,1)$, bước đi vào duy nhất có thể là từ $(m-1,1)$ sang phải và bước đi ra duy nhất có thể là đi lên $(m,2)$. Vì thế, theo chiều đi của hành trình, đa giác quay ngược chiều kim đồng hồ tại đỉnh này. Trái lại, tại ô góc trên bên trái $(1,m)$, hành trình buộc phải đi vào từ $(1,m-1)$ rồi đi ra sang phải tới $(2,m)$, nên đa giác quay theo chiều kim đồng hồ.
Điều này là không thể, bởi tại các đỉnh thuộc bao lồi của một đa giác đơn, chiều quay phải thoả mãn việc tất cả đều ngược chiều kim đồng hồ nếu đa giác được định hướng dương, và tất cả đều theo chiều kim đồng hồ nếu đa giác được định hướng âm.
Vậy hành trình không thể đi qua toàn bộ $m^2$ ô.
Vì $m^2=9n^2$ chia hết cho 3 và số bước là một bội của 3, ta có số bước không vượt quá $m^2-3$.
(2) Trước hết, trong ba cột đầu tiên ta xét hành trình
$$(1,1)\to (2,1)\to (3,1)\to (3,2)\to \cdots \to (3,m)$$
$$\to (2,m-1)\to (1,m-2)\to (2,m-2)\to (1,m-3)\to (2,m-3)\to \cdots$$
$$\to (1,2)\to (2,2)\to (1,1).$$
Ở phần có dấu ba chấm trên dòng thứ hai, ta luân phiên một bước sang phải và một bước chéo xuống-sang trái. Chu trình này đi qua mọi ô trong ba cột đầu, trừ đúng ba ô $(1,m-1)$, $(1,m)$, $(2,m)$ và nó chứa cạnh đi lên $(3,m-2)\to (3,m-1)$.
Bây giờ giả sử ta đã có một chu trình đi qua các cột từ 1 đến $c$, trong đó $c=3t$, vẫn chỉ bỏ ba ô trống, đồng thời chu trình chứa cạnh $(c,m-2)\to (c,m-1)$, ta thay cạnh này bởi đường đi sau:
$$(c,m-2)\to (c+1,m-2)\to (c+2,m-2)$$
$$\to (c+1,m-3)\to (c+2,m-3)\to \cdots \to (c+1,1)\to (c+2,1)$$
$$\to (c+3,1)\to (c+3,2)\to \cdots \to (c+3,m)$$
$$\to (c+2,m-1)\to (c+2,m)\to (c+1,m-1)\to (c+1,m)\to (c,m-1).$$
Đường đi vừa viết đi qua mỗi ô của ba cột mới $c+1,c+2,c+3$ đúng một lần và chứa cạnh
$$(c+3,m-2)\to (c+3,m-1),$$
nên ta có thể tiếp tục lặp lại phép ghép. Bắt đầu từ $c=3$ và thực hiện $n-1$ lần, ta thu được một chu trình trên cả $m=3n$ cột, chỉ bỏ đúng ba ô trống, hành trình này có $m^2-3=9n^2-3$ bước.
Hình vẽ dưới đây minh họa quá trình trên với $n=2$ và $n=3$:



Vậy số bước đi lớn nhất mà quân cờ $T$ thực hiện là $9n^2-3$ bước.

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.

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