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)

Bảng có tổng cộng 10 cặp ô chung cạnh chia làm hai loại:

Loại 1: $AB,BC,CD,DH,HG,GF,FE,EA$.

Loại 2: $BF,CG$.

Nhận xét: Giả sử ta đã tô màu đúng cho hai ô kề nhau theo chiều dọc (ví dụ ô $B$ và $F$) bằng 2 màu khác nhau. Nếu ta ghép thêm một cột mới gồm 2 ô kề nhau (ví dụ cột gồm $C$ và $G$) vào cạnh $BF$, số cách tô màu cho $C$ và $G$ là 7 cách. Thật vậy, giả sử màu của $B$ là màu 1, màu của $F$ là màu 2. Cần tô cho $C$ (kề $B$, kề $G$) và $G$ (kề $F$, kề $C$).

- Nếu $C$ mang màu 2 (giống $F$), thì $G$ chỉ cần khác màu 2, tức là $G$ có 3 cách chọn.
- Nếu $C$ mang màu khác cả 1 và 2 (có 2 cách chọn). Khi đó $G$ phải khác màu 2 và khác màu $C$, nên $G$ có 2 cách chọn. Số cách trong trường hợp này là $2\cdot 2=4$ cách.

Tổng cộng ta có $3+4=7$ cách tô cho mỗi khối ghép thêm, khi đó ta chia làm 2 trường hợp:

Trường hợp 1: Cặp ô cùng màu là loại 1 (có 8 cách chọn cặp). Giả sử ta chọn $A$ và $B$ cùng màu.

- Lúc này, ($A$ và $B$) kề cả $E$ và $F$, mà $E$ và $F$ cũng kề nhau, nên số cách chọn là: $4\cdot 3\cdot 2=24$ cách.
- Cột thứ ba ($C$ và $G$) được ghép vào cạnh của ($A$ và $B$). Theo nhận xét, có 7 cách tô.
- Cột thứ tư ($D$ và $H$) được ghép vào cạnh ($C$ và $G$). Theo nhận xét, có thêm 7 cách tô.

Số cách tô màu cho mỗi cặp trong trường hợp này là:
$$24\cdot 7\cdot 7=1176\text{ (caˊch)}.$$

Trường hợp 2: Cặp ô cùng màu là loại 2 (có 2 cách chọn cặp). Giả sử ta chọn $B$ và $F$ cùng màu.

- ($B$ và $F$) sẽ kề với $A,E$ (ở cột trái) và kề với $C,G$ (ở cột phải).
- Chọn màu cho ($B$ và $F$): có 4 cách.
- Cột trái ($A$ và $E$) phải chọn cho $A$ và $E$ hai màu khác nhau nên có $3\cdot 2=6$ cách.
- Cột phải ($C$ và $G$) tương tự cũng có 6 cách.
- Cột ngoài cùng ($D$ và $H$), thì theo nhận xét, có 7 cách tô.

Số cách tô màu cho mỗi cặp trong trường hợp này là:
$$4\cdot 6\cdot 6\cdot 7=1008\text{ (caˊch)}.$$

Vậy tổng số cách tô cần tính là: $8\cdot 1176+2\cdot 1008=11424$.

Đáp án chính thức (nguồn trang lời giải, trang 5, được đóng khung trong đề): $\boxed{11424}$.

Đầu tiên ta có bổ đề sau:

Bổ đề: Với mọi số nguyên không âm $a$ và mọi số nguyên dương $n$, ta có
$$\sum _{i=0}^{n-1}S(a+i)\ge \sum _{i=0}^{n-1}S(i).$$

Chứng minh bổ đề: Với mỗi số nguyên không âm $m$, gọi $d_r(m)$ là chữ số của $m$ tại hàng $10^r$. Khi đó
$$d_r(m)=\lfloor \frac{m}{10^r}\rfloor -10\lfloor \frac{m}{10^{r+1}}\rfloor ,S(m)=\sum _{r\ge 0}{d}_r(m).$$

Ta sẽ chứng minh rằng tại mỗi hàng thập phân, tổng các chữ số của đoạn $a,a+1,\dots ,a+n-1$ không nhỏ hơn tổng tương ứng của đoạn $0,1,\dots ,n-1$. Cố định $r\ge 0$, đặt $q=10^r$ và $P=10q=10^{r+1}$. Dãy các chữ số tại hàng $10^r$ là một dãy tuần hoàn có chu kì $P$. Trong một chu kì, dãy này có dạng

$$\underset{q\text{ soˆˊ}}{\underbrace{0,\dots ,0}},\underset{q\text{ soˆˊ}}{\underbrace{1,\dots ,1}},\dots ,\underset{q\text{ soˆˊ}}{\underbrace{9,\dots ,9}}.$$

Kí hiệu một chu kì trên bởi $c_0,c_1,\dots ,c_{P-1}$. Ta có $c_0\le c_1\le \cdots \le c_{P-1}$ và tổng của một chu kì là

$$C=\sum _{j=0}^{P-1}{c}_j=q(0+1+\cdots +9)=45q.$$

Viết $n=kP+t$, trong đó $k\ge 0$ và $0\le t<P$. Do dãy đang xét có chu kì $P$, bất kì $kP$ số hàng liên tiếp nào cũng gồm đúng $k$ chu kì đầy đủ, nên có tổng bằng $kC$. Vì vậy, khi xét một đoạn gồm $n$ số hàng liên tiếp, ta chỉ cần so sánh tổng của $t$ số hàng còn lại.

Nếu $t=0$ thì tổng tại hàng $10^r$ của mọi đoạn gồm $n$ số hàng liên tiếp đều bằng $kC$, nên khẳng định hiển nhiên đúng. Xét $t>0$. Gọi $u$ là vị trí bắt đầu của $t$ số hàng còn lại trong chu kì, với $0\le u<P$.

Nếu $u+t\le P$, đoạn này không đi qua chỗ chuyển từ 9 về 0 và gồm

$$c_u,c_{u+1},\dots ,c_{u+t-1}.$$

Do dãy $c_0,c_1,\dots ,c_{P-1}$ không giảm, với mọi $0\le j<t$ ta có $c_{u+j}\ge c_j$. Bởi vậy

$$c_u+c_{u+1}+\cdots +c_{u+t-1}\ge c_0+c_1+\cdots +c_{t-1}.$$

Nếu $u+t>P$, đoạn này đi qua chỗ chuyển từ 9 về 0 và gồm

$$c_u,c_{u+1},\dots ,c_{P-1},c_0,c_1,\dots ,c_{u+t-P-1}.$$

Đặt $v=u+t-P$. Phần bù của đoạn trên trong cả chu kì là

$$c_v,c_{v+1},\dots ,c_{u-1},$$

gồm đúng $P-t$ số hàng. Do $u<P$ nên $v<t$. Dễ thấy với mọi $0\le j<P-t$ ta có $c_{v+j}\le c_{t+j}$. Suy ra

$$c_v+c_{v+1}+\cdots +c_{u-1}\le c_t+c_{t+1}+\cdots +c_{P-1}.$$

Lấy tổng cả chu kì trừ hai vế, ta được

$$c_u+\cdots +c_{P-1}+c_0+\cdots +c_{v-1}\ge c_0+c_1+\cdots +c_{t-1}.$$

Như vậy, trong cả hai trường hợp, tổng của $t$ số hàng liên tiếp bất kì trong chu kì đều không nhỏ hơn tổng của $t$ số hàng đầu tiên. Do đó

$$\sum _{i=0}^{n-1}{d}_r(a+i)\ge \sum _{i=0}^{n-1}{d}_r(i).$$

Bất đẳng thức này đúng với mọi $r\ge 0$. Chọn $R$ đủ lớn để $a+n-1<10^{R+1}$. Khi đó tất cả các chữ số ở những hàng cao hơn $10^R$ đều bằng 0. Vì vậy bổ đề được chứng minh do

$$\sum _{i=0}^{n-1}S(a+i)=\sum _{r=0}^R\sum _{i=0}^{n-1}{d}_r(a+i)\ge \sum _{r=0}^R\sum _{i=0}^{n-1}{d}_r(i)=\sum _{i=0}^{n-1}S(i).$$

Áp dụng bổ đề với $n=2026$, tổng chữ số của bất kì 2026 số nguyên không âm liên tiếp nào cũng không nhỏ hơn ${\sum }_{i=0}^{2025}S(i)={\sum }_{i=0}^{999}S(i)+{\sum }_{i=1000}^{1999}S(i)+{\sum }_{i=2000}^{2009}S(i)+{\sum }_{i=2010}^{2019}S(i)+{\sum }_{i=2020}^{2025}S(i)=13500+14500+65+75+39=28179$, vì thế ta suy ra được nên $N_{\min }=28179$, và dấu bằng khi lấy 2026 số tự nhiên đầu tiên.

a) Chọn một bộ ba Đông Bắc $A,B,C$ của tập hợp và viết

$$B-A=(u,v),C-B=(p,q).$$

Khi đó $u,v,p,q$ đều là các số nguyên dương. Vì thế

$$A{C}^2-A{B}^2-B{C}^2=(u+p{)}^2+(v+q{)}^2-(u^2+v^2)-(p^2+q^2)=2(up+vq)\ge 4.$$

b) Vì không có đường thẳng qua hai điểm nào song song với một trục tọa độ nên các hoành độ đôi một khác nhau và các tung độ đôi một khác nhau. Vì tập hợp có 20 điểm nên sau khi sắp xếp các điểm theo hoành độ tăng dần, tập hợp bao gồm các điểm dạng

$$P_i=(i,{\pi }_i),1\le i\le 20,$$

trong đó $({\pi }_1,{\pi }_2,\dots ,{\pi }_{20})$ là một hoán vị của $(1,2,\dots ,20)$.

Ba điểm $P_i,P_j,P_k$ với $i<j<k$ tạo thành một bộ ba Đông Bắc khi và chỉ khi ${\pi }_i<{\pi }_j<{\pi }_k$.

Ta có kết quả sau về số Catalan:

Bổ đề: Số hoán vị $({\pi }_1,\dots ,{\pi }_n)$ của $(1,2,\dots ,n)$ sao cho không tồn tại ba chỉ số $i<j<k$ thoả mãn điều kiện ${\pi }_i<{\pi }_j<{\pi }_k$ bằng $\frac{1}{n+1}{C}_{2n}^n$.

Chứng minh bổ đề: Gọi $C_n$ là số lượng hoán vị như trên của tập hợp $(1,2,\dots ,n)$.

Trước hết, ta sẽ đưa bài toán về việc đếm các hoán vị không tồn tại ba chỉ số $i<j<k$ sao cho ${\pi }_i<{\pi }_k<{\pi }_j$. Ta gọi ${\pi }_i$ là một LIM nếu ${\pi }_i<{\pi }_j$ với mọi $j<i$.

Xét một hoán vị $\pi$ không tồn tại ba chỉ số $i<j<k$ sao cho ${\pi }_i<{\pi }_j<{\pi }_k$. Ta có nhận xét rằng các phần tử không phải LIM phải xuất hiện theo thứ tự giảm dần.

Thật vậy, giả sử có hai vị trí $i<j$ sao cho ${\pi }_i,{\pi }_j$ đều không phải LIM và ${\pi }_i<{\pi }_j$. Vì ${\pi }_i$ không phải LIM nên tồn tại $h<i$ sao cho ${\pi }_h<{\pi }_i$. Khi đó $h<i<j$ và ${\pi }_h<{\pi }_i<{\pi }_j$, vô lý.

Do đó, một hoán vị không tồn tại ba chỉ số $i<j<k$ sao cho ${\pi }_i<{\pi }_j<{\pi }_k$ được xác định duy nhất nếu biết vị trí và giá trị của các LIM: các số còn lại chỉ cần được điền vào các vị trí còn trống theo thứ tự giảm dần.

Bây giờ, vẫn giữ nguyên vị trí và giá trị của các LIM. Ta đi từ trái sang phải qua các vị trí còn trống; tại mỗi vị trí, nếu $m$ là LIM gần nhất ở bên trái, ta điền số nhỏ nhất chưa được sử dụng và lớn hơn $m$.

Hoán vị thu được không tồn tại ba chỉ số $i<j<k$ sao cho ${\pi }_i<{\pi }_k<{\pi }_j$. Thật vậy, giả sử tồn tại $i<j<k$ sao cho ${\pi }_i<{\pi }_k<{\pi }_j$. Gọi $m$ là LIM gần nhất đứng trước vị trí $j$. Khi đó $m\le {\pi }_i<{\pi }_k<{\pi }_j$. Nhưng tại thời điểm điền vào vị trí $j$, số ${\pi }_k$ vẫn chưa được sử dụng và lớn hơn $m$, trái với cách chọn ${\pi }_j$ là số nhỏ nhất chưa được sử dụng và lớn hơn $m$.

Ngược lại, từ một hoán vị không tồn tại ba chỉ số $i<j<k$ sao cho ${\pi }_i<{\pi }_k<{\pi }_j$, ta giữ nguyên các LIM và điền các số còn lại theo thứ tự giảm dần. Theo nhận xét trên, ta thu được duy nhất một hoán vị không tồn tại ba chỉ số $i<j<k$ sao cho ${\pi }_i<{\pi }_j<{\pi }_k$.

Như vậy, tồn tại một song ánh giữa hai tập hoán vị trên. Do đó, ta chỉ cần đếm số hoán vị không tồn tại ba chỉ số $i<j<k$ sao cho ${\pi }_i<{\pi }_k<{\pi }_j$, và vẫn ký hiệu số lượng này là $C_n$.

Xét một hoán vị $\pi =({\pi }_1,{\pi }_2,\dots ,{\pi }_n)$ thỏa mãn điều kiện trên. Giả sử ${\pi }_k=n$. Khi đó, hoán vị được chia thành hai phần:

- Phần bên trái $L$ gồm $k-1$ phần tử đứng trước $n$: $({\pi }_1,{\pi }_2,\dots ,{\pi }_{k-1})$.
- Phần bên phải $R$ gồm $n-k$ phần tử đứng sau $n$: $({\pi }_{k+1},\dots ,{\pi }_n)$.

Từ đây ta suy ra được:

- Mọi phần tử nằm ở bên trái $n$ trong $L$ bắt buộc phải lớn hơn mọi phần tử nằm ở bên phải $n$ trong $R$. Thật vậy, nếu tồn tại $l\in L$ và $r\in R$ sao cho $l<r$, thì do $r<n$, ta có ba phần tử $l,n,r$ xuất hiện theo thứ tự từ trái sang phải và thỏa mãn $l<r<n$. Khi đó tồn tại ba chỉ số $i<j<k$ sao cho ${\pi }_i<{\pi }_k<{\pi }_j$, vô lý. Do đó, tập hợp các giá trị của $L$ là $\{n-k+1,\dots ,n-1\}$, còn tập hợp các giá trị của $R$ là $\{1,\dots ,n-k\}$.
- Cả hai phần $L$ và $R$ cũng không tồn tại ba chỉ số $i<j<k$ sao cho phần tử thứ $i$ nhỏ hơn phần tử thứ $k$ và phần tử thứ $k$ nhỏ hơn phần tử thứ $j$.

Để ý số cách chọn phần bên trái $L$ có độ dài $k-1$ là $C_{k-1}$ và số cách chọn phần bên phải $R$ có độ dài $n-k$ là $C_{n-k}$. Suy ra $C_n={\sum }_{k=1}^n{C}_{k-1}{C}_{n-k}={\sum }_{i=0}^{n-1}{C}_i{C}_{n-1-i}$, và vì $C_0=1$ nên đây là dãy Catalan hay $C_n=\frac{1}{n+1}{C}_{2n}^n$, bổ đề được chứng minh.

Do đó, trong $20!$ hoán vị của $(1,2,\dots ,20)$, có đúng $\frac{1}{21}{C}_{40}^{20}$ hoán vị không tạo ra bộ ba Đông Bắc.

Vậy số tập hợp Lam Sơn là $20!-\frac{1}{21}{C}_{40}^{20}$.

Trong mỗi tiết có nhiều hơn 15 học sinh vắng mặt, nên có nhiều nhất 14 học sinh đi học. Do đó tổng số lượt đi học của cả 30 học sinh trong 100 tiết không vượt quá
$$100\cdot 14=1400.$$
Gọi $t$ là số học sinh được dự thi cuối khóa. Mỗi học sinh trong số đó đi học ít nhất 56 tiết, nên
$$56t⩽1400.$$
Suy ra $t⩽25$. Vì có 30 học sinh nên có ít nhất $30-25=5$ học sinh không được dự thi. Do đó $N\ge 5$.
Ta dựng một cách điểm danh có đúng 5 học sinh không được dự thi.
Đánh số 25 học sinh đầu tiên bởi các số $0,1,2,\dots ,24$. Chia 100 tiết thành 4 vòng, mỗi vòng gồm 25 tiết. Trong tiết thứ $j$ của mỗi vòng, cho đúng 14 học sinh
$$j,j+1,\dots ,j+13(\mathrm{mod}25)$$
di học, 5 học sinh còn lại luôn vắng mặt. Trong mỗi vòng, mỗi học sinh thuộc nhóm đầu đi học đúng 14 tiết, nên sau 4 vòng mỗi em đi học đúng 56 tiết và được dự thi. Chỉ có 5 học sinh cuối không được dự thi. Vậy $N=5$.

Gọi $r_i$ là số quân cờ trên hàng $i$ và $c_j$ là số quân cờ trên cột $j$. Vì ô $(i,j)$ đang trống nên tổng số quân trên các ô cùng hàng hoặc cùng cột với nó bằng $r_i+c_j$. Do đó
$$(i,j)\text{ hợp lệ }⟺r_i+c_j\equiv 0(\mathrm{mod}2),$$
Gọi $u$ là số hàng chứa lẻ quân và $v$ là số cột chứa lẻ quân. Ban đầu $u=v=0$. Mỗi nước đi hợp lệ có đúng một trong hai dạng:
- Đặt tại giao của một hàng chẵn và một cột chẵn, khi đó $u,v$ cùng tăng 1;
- Đặt tại giao của một hàng lẻ và một cột lẻ, khi đó $u,v$ cùng giảm 1.
Vì thế, trong suốt trò chơi ta luôn có bất biến là $u=v$.

a) Gọi $M_0$ là các ô màu xanh nước biển, $M_1$ là các ô màu xanh lá cây, $M_2$ là các ô màu cam, $M_3$ là các ô màu đỏ. An lần lượt đặt hết các quân trong $M_0,M_1,M_2,M_3$ và để ý mọi bước đều hợp lệ.



b) Giả sử An bị kẹt sau khi đã đặt $m$ quân. Khi đó không còn ô trống hợp lệ. Theo bất biến, có cùng $u$ hàng lẻ và $u$ cột lẻ. Do không còn ô hợp lệ nên mọi giao điểm của hai cột với hàng cùng tính chẵn lẻ đều đã có quân. Vì vậy
$$m⩾u^2+(8-u{)}^2=2(u-4{)}^2+32⩾32.$$
Suy ra trước khi đặt đủ 32 quân, An không thể bị kẹt, ta có điều phải chứng minh.

c) Câu trả lời là không. Ban đầu An điền các ô như sau:



Sau khi điền xong, An đã đặt 25 quân. Ba hàng và ba cột của khối $3\times 3$ đều lẻ; bốn hàng và bốn cột còn lại đều chẵn. Vì thế mọi ô trống đều nối một hàng lẻ với một cột chẵn hoặc ngược lại, nên không hợp lệ. An bị kẹt và còn thừa 7 quân; do đó câu trả lời là không.

Nhận xét. Ngoài ra với bảng $n\times n$ tổng quát, An có thể luôn đặt được tối đa $\frac{n^2+1}{2}$ quân với $n$ lẻ, và $\frac{n^2+2n}{2}$ quân với $n$ chẵn. Bạn đọc có thể thử sức để chỉ ra điều này.

Nhận xét: Với mọi $x\in {\mathbb{N}}^{\ast }$, ta luôn viết được dưới dạng $x=3^k\cdot m$ (trong đó $k\in \mathbb{N}$, $m\in {\mathbb{N}}^{\ast }$ và $\gcd (m,3)=1$).

Ta gọi nhóm các số có cùng giá trị $m$: $\{m,3m,9m,27m,\dots \}$ là một chuỗi.

Dễ dàng thấy rằng với 2 số bất kỳ trong cùng một chuỗi thì luôn có 1 số chia hết cho 3 lần số còn lại.

Số lượng chuỗi chính là số lượng các số đại diện $m\le 210n$ thỏa mãn:

$$\{\begin{array}{l}\gcd (m,14)=1\\ \gcd (m,3)=1\end{array}⟹\gcd (m,42)=1$$

Áp dụng công thức phi hàm Euler, số lượng các số $m$ thỏa mãn trên đoạn $[1,210n]$ là:

$$210n\cdot \left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)\left(1-\frac{1}{7}\right)=210n\cdot \frac{1}{2}\cdot \frac{2}{3}\cdot \frac{6}{7}=60n$$

Vậy có tất cả $60n$ chuỗi. Mà tập hợp $A$ gồm có $60n+1$ phần tử.

Theo nguyên lý Dirichlet, tồn tại ít nhất 1 chuỗi chứa từ 2 phần tử trở lên thuộc tập $A$.

Từ đó, ta có điều phải chứng minh (đpcm).

a) Gọi khoảng cách từ vị trí đèn led $P$ bất kì đến ba cạnh $AB,AC,BC$ lần lượt là $d_{AB}(P),d_{AC}(P),d_{BC}(P)$.
*) Chứng minh chiều thuận:
Giả sử ba đường thẳng $X_i,Y_j,Z_k$ cùng đi qua một đèn led $P$. Ta có
$$d_{BC}(P)=\frac{\sqrt{3}}{2}(n+1-i);d_{AB}(P)=\frac{\sqrt{3}}{2}(n+1-j);d_{AC}(P)=\frac{\sqrt{3}}{2}(n+1-k).$$
Mà tổng khoảng cách từ một điểm nằm trên lưới tới ba cạnh của tam giác luôn bằng $n\frac{\sqrt{3}}{2}$. Từ đó suy ra
$$\frac{\sqrt{3}}{2}(n+1-i)+\frac{\sqrt{3}}{2}(n+1-j)+\frac{\sqrt{3}}{2}(n+1-k)=n\frac{\sqrt{3}}{2}\iff i+j+k=2n+3$$
*) Chứng minh chiều đảo:
Giả sử có ba chỉ số $i,j,k\in \{1,2,\dots ,n+1\}$ thỏa mãn $i+j+k=2n+3$.
Xét hai đường thẳng $X_i$ và $Y_j$ cắt nhau tại duy nhất một điểm $P$.
$$d_{BC}(P)=(n+1-i)\frac{\sqrt{3}}{2};d_{AB}(P)=(n+1-j)\frac{\sqrt{3}}{2}$$
$$k\le n+1\Rightarrow (i+j)\ge n+2\Rightarrow d_{BC}(P)+d_{AB}(P)=\left(2n+2-(i+j)\right)\frac{\sqrt{3}}{2}\le n\frac{\sqrt{3}}{2}$$
Suy ra điểm $P$ nằm trên lưới tam giác đều. Khi đó:
$$d_{AC}(P)=n\frac{\sqrt{3}}{2}-(n+1-i)\frac{\sqrt{3}}{2}-(n+1-j)\frac{\sqrt{3}}{2}=(i+j-n-2)\frac{\sqrt{3}}{2}$$
$$=\left[(2n+3-k)-n-2\right]\frac{\sqrt{3}}{2}=(n+1-k)\frac{\sqrt{3}}{2}.$$
Suy ra $P$ nằm trên đường thẳng $Z_k$. Do đó, $X_i,Y_j,Z_k$ đồng quy tại đúng một đèn led $P$.

b) Ta chỉ ra một dãy thao tác thỏa mãn là tác động vào tất cả các đường $X_{2m},Y_{2m},Z_{2m}$ với $1\le 2m\le n+1$ và không tác động vào các đường còn lại.
Khi đó với mỗi đèn $P$ bất kì tồn tại duy nhất bộ ba đường thẳng $X_i,Y_j,Z_k$ cùng đi qua $P$ thỏa mãn $i+j+k=2n+3$. Do $2n+3$ là số lẻ, nên trong ba số $i,j,k$ có 2 số chẵn, 1 số lẻ hoặc 3 số lẻ. Theo cách thao tác ở trên, thì đèn $P$ được tác động đúng hai lần hoặc không được tác động lần nào. Do đó trạng thái đèn $P$ vẫn là tắt.

c) Do ta cần tìm số lần tác động ít nhất và nếu ta tác động hai lần trên cùng một đường thẳng thì trạng thái của các đèn không thay đổi nên ta có thể biểu diễn tất cả các tổ hợp thao tác dưới dạng bộ
$$\left(a_1,a_2,\dots ,a_{n+1},b_1,b_2,\dots ,b_{n+1},c_1,c_2,\dots ,c_{n+1}\right),$$
trong đó mỗi phần tử $a_i,b_i,c_i$ tương ứng với thao tác được thực hiện trên các đường thẳng $X_i,Y_i,Z_i$; nhận giá trị 0 (không được tác động) hoặc 1 (được tác động).
Gọi $A$ là tập hợp tất cả các bộ $\left(a_1,a_2,\dots ,a_{n+1},b_1,b_2,\dots ,b_{n+1},c_1,c_2,\dots ,c_{n+1}\right)$. Khi đó $|A|=2^{3n+3}$.
Gọi $B$ là tập hợp tất cả các trạng thái của dàn đèn LED, trong đó mỗi trạng thái của dàn đèn LED trong $B$ được mô tả bằng một bộ $N=\frac{(n+1)(n+2)}{2}$ phần tử $\left(d_1,d_2,\dots ,d_N\right)$, trong đó mỗi phần tử bằng 0 hoặc 1 (tương ứng đèn tắt hoặc bật).
Xét ánh xạ $f:A\to B$ với $f(x)$ là phần tử thuộc $B$ thu được sau khi thực hiện $x$. Từ đây, ta quy ước phép cộng hai phần tử trong $A$ hoặc trong $B$ được tính trên từng cặp số ở vị trí tương ứng của hai phần tử đó và được tính theo modulo 2 (tức là $1+1=0+0=0$, $0+1=1+0=1$).
Ta thấy $f(x+x^{\prime })=f(x)+f(x^{\prime })$ với mọi $x,x^{\prime }\in A$.
*) Gọi $K$ là tập hợp tất cả các $x\in A$ sao cho $f(x)$ là trạng thái tất cả các đèn đều tắt. Dễ thấy tám phần tử sau đây thuộc $K$:
$$((0,0,\dots ,0),(0,0,\dots ,0),(0,0,\dots ,0))=\mathrm{id}$$
$$((0,0,\dots ,0),(1,1,\dots ,1),(1,1,\dots ,1))=a$$
$$((1,1,\dots ,1),(1,1,\dots ,1),(0,0,\dots ,0))=b$$
$$((1,1,\dots ,1),(0,0,\dots ,0),(1,1,\dots ,1))=a+b$$
$$((0,1,0,1,\dots ),(0,1,0,1,\dots ),(0,1,0,1,\dots ))=c$$
$$((0,1,0,1,\dots ),(1,0,1,0,\dots ),(1,0,1,0,\dots ))=a+c$$
$$((1,0,1,0,\dots ),(1,0,1,0,\dots ),(0,1,0,1,\dots ))=b+c$$
$$((1,0,1,0,\dots ),(0,1,0,1,\dots ),(1,0,1,0,\dots ))=a+b+c$$
Ta sẽ chứng minh tập $K$ có đúng 8 phần tử.
Giả sử $L=((a_1,a_2,\dots ,a_{n+1}),(b_1,b_2,\dots ,b_{n+1}),(c_1,c_2,\dots ,c_{n+1}))$ thuộc $K$.
Khi đó $a_i+b_j+c_k=0$ với $i+j+k=2n+3$. Bằng cách cộng thêm $a$ hoặc $b$ nếu cần thiết, ta có thể giả sử rằng $b_{n+1}=c_{n+1}=0$. Vì $a_2+b_n+c_{n+1}=a_2+b_{n+1}+c_n=0$, ta có $b_n=c_n$. Có hai trường hợp:
(a) $b_n=c_n=0$. Khi đó từ $a_3+b_{n-1}+c_{n+1}=a_3+b_n+c_n=a_3+b_{n+1}+c_{n-1}$, suy ra $b_{n-1}=c_{n-1}=0$. Tương tự ta thấy tất cả các phần tử $b_i$ và $c_i$ đều bằng 0, từ đó suy ra $L=\mathrm{id}$.
(b) $b_n=c_n=1$. Khi đó từ $a_3+b_{n-1}+c_{n+1}=a_3+b_n+c_n=a_3+b_{n+1}+c_{n-1}$, suy ra $b_{n-1}=c_{n-1}=0$. Làm tương tự ta thu được $(b_1,b_2,\dots ,b_{n+1})=(c_1,c_2,\dots ,c_{n+1})=(\dots ,1,0,1,0)$, từ đó suy ra $L=c$ hoặc $L=a+c$.
Do đó $L$ là một trong tám phần tử được liệt kê ở trên.
Như vậy, với mỗi $x\in A$ tồn tại đúng 7 phần tử $x^{\prime }$ khác thuộc tập $A$ thỏa mãn $f(x)=f(x^{\prime })$. Do đó, ta có thể phân hoạch $2^{3(n+1)}$ phần tử của $A$ thành $2^{3n}$ tập con, mỗi tập tương ứng duy nhất với một phần tử của $B$.
*) Xét mỗi tập con $S$ chứa 8 phần tử như trên:
Với mỗi phần tử $x\in S$, gọi $x_1$ là số lượng các phần tử $a_1,a_3,\dots$ bằng 1, và gọi $x_2$ là số lượng các phần tử $a_2,a_4,\dots$ bằng 1. Định nghĩa tương tự $y_1,y_2,z_1,z_2$ cho dãy $b_i$ và $c_i$. Khi đó, số thao tác tương ứng $x$ là
$$T(x)=x_1+x_2+y_1+y_2+z_1+z_2.$$
Đặt $n=4k$. Xét $x\in S$ để $T(x)$ đạt giá trị nhỏ nhất.
Dễ thấy $x+a,x+b,x+c,x+(a+b),x+(a+c),x+(b+c),x+(a+b+c)\in S$.
Ta có:
$$T(x+a)=x_1+x_2+(n+1-y_1-y_2)+(n+1-z_1-z_2)\ge T(x)=x_1+x_2+y_1+y_2+z_1+z_2$$
$$\Rightarrow n+1\ge y_1+y_2+z_1+z_2.$$
Làm tương tự ta có: $x_1+x_2+z_1+z_2\le n+1$; $x_1+x_2+y_1+y_2\le n+1$;
$$x_2+y_2+z_2\le 3k;(1)$$
$$x_1+y_1+z_2\le 3k+1;x_2+y_1+z_1\le 3k+1;x_1+y_2+z_1\le 3k+1(2)$$
Cộng vế với vế của bốn bất đẳng thức trong (1), (2) rồi chia cho 4, ta được $T\le 6k+1$.
Dấu "=" xảy ra khi $x_1=x_2=y_1=y_2=z_2=k$ và $z_1=k+1$.

Lời giải (Lim Olympic - Quảng Ngãi TST - P5):

a) Ta sẽ giải bài toán trong trường hợp tổng quát là $k=2$ và $N$ là số lẻ.

Đặt $N=2m+1$. Giả sử phản chứng rằng trò chơi không bao giờ dừng.

Hai thẻ mang số $N$ đứng yên tại hai người khác nhau. Sau đó, hai thẻ mang số $N-1$ sẽ được chuyển qua những người đang giữ thẻ $N$ cho tới khi chúng đến những người không giữ thẻ có số lớn hơn. Khi ấy chúng đứng yên. Nếu chúng cùng đứng yên tại một người thì trò chơi đã dừng, nên chúng phải nằm tại hai người mới khác nhau.

Tiếp tục như vậy, sau hữu hạn lượt, tất cả thẻ mang các số $m+2,m+3,\dots ,2m+1$ đều đứng yên. Có $m$ số như vậy, nên $2m=N-1$ thẻ trên nằm tại $N-1$ người khác nhau.

Gọi $A$ là người duy nhất còn lại.

Xét hai thẻ mang số $m+1$. Tại bất cứ người nào trong $N-1$ người trên, thẻ $m+1$ đều nhỏ hơn một thẻ đang được giữ cố định, nên nó phải được chuyển tiếp.

Vì thế cả hai thẻ $m+1$ cuối cùng đều đi tới $A$.

Khi thẻ thứ nhất tới $A$, nó được giữ lại. Sau đó thẻ thứ hai cũng tới $A$, nên $A$ giữ hai thẻ cùng mang số $m+1$. Trò chơi dừng, mâu thuẫn.

Vậy nếu $k=2$ và $N$ lẻ thì trò chơi luôn dừng.

b) Ta sẽ chứng minh ngoại trừ trường hợp $k=2$ và $N$ lẻ, thì trò chơi đều không dừng lại.

◇ Trường hợp 1: $N$ chẵn.

Đặt $N=2m$. Chia $N$ người thành $m$ nhóm, mỗi nhóm gồm hai người.
Ta dùng $m$ số lớn nhất là $m+1,m+2,\dots ,2m$.

Với mỗi số $r\in \{m+1,m+2,\dots ,2m\}$, lấy $k$ thẻ mang số $r$ và phát cho hai người trong một nhóm: một người nhận $1$ thẻ, người kia nhận $k-1$ thẻ.

Như vậy mỗi người đều có ít nhất một thẻ mang số lớn hơn $m$, nhưng không ai có đủ $k$ thẻ cùng số. Các vị trí còn thiếu được điền bằng toàn bộ các thẻ mang các số $1,2,\dots ,m$.

Trong quá trình chơi, các thẻ mang số lớn hơn $m$ luôn là những thẻ có số lớn nhất tại người đang giữ chúng, nên chúng đứng yên mãi mãi. Mọi thẻ mang số không vượt quá $m$ đều nhỏ hơn các thẻ cố định này, nên sau mỗi lượt chúng đều được chuyển sang người bên trái.

Do đó, phần các thẻ nhỏ mà mỗi người đang giữ chỉ chuyển nguyên sang người bên trái sau mỗi lượt. Ban đầu mỗi người có ít nhất một thẻ lớn, nên có nhiều nhất $k-1$ thẻ nhỏ. Vì vậy không bao giờ có người nào nhận được $k$ thẻ nhỏ cùng số.

Mặt khác, với mỗi số lớn, $k$ thẻ của số đó được chia cho ít nhất hai người và luôn đứng yên, nên cũng không thể có người nào giữ đủ $k$ thẻ cùng số.

Vậy với cách chia ban đầu này, trò chơi không bao giờ dừng.

◇ Trường hợp 2: $N$ lẻ và $k\ge 3$.

Viết $N=2m+3$.

Chia $N$ người thành một nhóm gồm ba người và $m$ nhóm, mỗi nhóm gồm hai người.

Có tất cả $m+1$ nhóm, lấy $m+1$ số lớn nhất trong $\{1,2,\dots ,N\}$ và gán mỗi số cho một nhóm.

☆ Với mỗi nhóm gồm hai người, chia $k$ thẻ mang số tương ứng thành hai phần $1$ và $k-1$.
☆ Với nhóm gồm ba người, chia $k$ thẻ mang số tương ứng thành ba phần $1,1,k-2$. Do $k\ge 3$, cả ba phần đều khác rỗng và mỗi phần đều có ít hơn $k$ thẻ.

Như vậy mỗi người đều giữ ít nhất một thẻ mang một trong $m+1$ số lớn nhất, nhưng không ai giữ đủ $k$ thẻ cùng số. Ta điền các vị trí còn lại bằng tất cả các thẻ mang những số nhỏ hơn.
Hoàn toàn tương tự trường hợp trên, các thẻ mang $m+1$ số lớn nhất đứng yên mãi mãi, còn các thẻ nhỏ hơn chỉ chuyển vòng quanh bàn từ người này sang người bên trái.

Mỗi người có ít nhất một thẻ lớn, nên tại mọi thời điểm phần thẻ nhỏ chuyển tới một người có không quá $k-1$ thẻ. Do đó không thể xuất hiện $k$ thẻ nhỏ cùng số tại một người. Các thẻ lớn cũng đã được chia cho ít nhất hai người nên không thể tạo ra $k$ thẻ cùng số tại một người.

Vì vậy tồn tại cách chia ban đầu để trò chơi không bao giờ dừng.

Từ đây ta suy ra được tất cả các giá trị cần tìm là $k=2$ và $N$ lẻ.

Điều kiện để diện tích là số lẻ: Mỗi hình chữ nhật được tạo thành có kích thước $p\times q$ với $p,q$ nguyên dương, diện tích bằng $pq$. Tích $pq$ là số lẻ khi và chỉ khi cả $p$ và $q$ đều lẻ. Đếm theo từng kích thước: Bảng gồm 8 ô theo một chiều và 6 ô theo chiều còn lại. Một hình chữ nhật kích thước $p\times q$ (với $p$ ô theo chiều có 8 ô, $q$ ô theo chiều có 6 ô) có đúng $(9-p)(7-q)$ vị trí đặt trong Bảng. Do đó $$n(S)=\sum _{p\le 8,p\text{lẻ}}(9-p)\cdot \sum _{q\le 6,q\text{lẻ}}(7-q).$$ Tính hai tổng: $$\sum _{p\in \{1;3;5;7\}}(9-p)=8+6+4+2=20,\sum _{q\in \{1;3;5\}}(7-q)=6+4+2=12.$$ Vậy $n(S)=20\cdot 12=240$. Đáp số: Tập hợp $S$ có 240 phần tử. Nhận xét: Kết quả không phụ thuộc vào quy ước gọi chiều nào là chiều dài của Bảng: nếu đổi vai trò hai chiều thì $n(S)=(8+6+4+2)\cdot (6+4+2)$ vẫn bằng 240.

a) Ta giải bài toán tổng quát cho bảng $n\times n$.

Gọi $a_{i,j}\in \{-1,0,1\}$ là số được điền vào ô thuộc hàng $i$, cột $j$.

Điều kiện đề bài cho $a_{i,j}+a_{i+1,j}+a_{i,j+1}+a_{i+1,j+1}=0$, hay $a_{i+1,j+1}=-a_{i,j}-a_{i+1,j}-a_{i,j+1}$.

Do đó, nếu đã biết hàng đầu tiên và cột đầu tiên thì ta lần lượt xác định được tất cả các ô còn lại của bảng. Đặt $x_i=(-1{)}^{i+1}{a}_{i,1}$ và $y_j=(-1{)}^{j+1}{a}_{1,j}$.

Ta có $x_1=y_1=a_{1,1}$. Từ điều kiện trên, bằng quy nạp theo $i+j$, ta thu được

$$a_{i,j}=(-1{)}^{i+j}(x_i+y_j-a_{1,1}).$$

bởi công thức đúng tại các ô $(i,j)$, $(i+1,j)$, $(i,j+1)$ thì công thức cũng đúng tại $(i+1,j+1)$ do

$$a_{i+1,j+1}=-a_{i,j}-a_{i+1,j}-a_{i,j+1}=(-1{)}^{i+j}(x_{i+1}+y_{j+1}-a_{1,1}).$$

Vì $a_{i,j}\in \{-1,0,1\}$ nên ta có điều kiện cần và đủ là $x_i+y_j-x_1\in \{-1,0,1\}$ với mọi $i,j$.

Giờ ta đếm số cách điền theo giá trị của $x_1=y_1$.

Trường hợp 1. $x_1=y_1=0$.

Khi đó điều kiện trở thành $x_i+y_j\in \{-1,0,1\}$. Ta xét dãy $x_2,\dots ,x_n$.

- Nếu $x_2=\cdots =x_n=0$ thì dãy $y_2,\dots ,y_n$ được chọn tùy ý trong $\{-1,0,1\}$, nên có $3^{n-1}$ cách.
- Nếu các $x_i$ chỉ nhận các giá trị $0,1$ và có ít nhất một giá trị bằng 1, thì có $2^{n-1}-1$ cách chọn dãy $(x_i)$. Khi đó mọi $y_j$ phải thuộc $\{-1,0\}$, nên có $2^{n-1}$ cách chọn dãy $(y_j)$.
- Tương tự, nếu các $x_i$ chỉ nhận các giá trị $-1,0$ và có ít nhất một giá trị bằng $-1$, ta cũng có $(2^{n-1}-1)2^{n-1}$ cách.
- Cuối cùng, nếu dãy $(x_i)$ chứa cả $1$ và $-1$, thì trong tổng số $3^{n-1}$ dãy, ta loại đi dãy toàn 0, các dãy chỉ chứa $0,1$ và có ít nhất một số 1, cùng các dãy chỉ chứa $-1,0$ và có ít nhất một số $-1$. Do đó số cách chọn là $3^{n-1}-1-2(2^{n-1}-1)=3^{n-1}-2^n+1$, và mọi $y_j$ buộc phải bằng 0.

Vậy số cách trong trường hợp này là

$$A=3^{n-1}+2(2^{n-1}-1)2^{n-1}+3^{n-1}-2^n+1=2\cdot 3^{n-1}+2\cdot 4^{n-1}-2^{n+1}+1$$

Trường hợp 2. $x_1=y_1=1$.

Điều kiện trở thành $x_i+y_j-1\in \{-1,0,1\}$, hay tương đương với $x_i+y_j\ge 0$.

- Nếu $x_2=\cdots =x_n=1$ thì dãy $y_2,\dots ,y_n$ được chọn tùy ý, nên có $3^{n-1}$ cách.
- Nếu các $x_i$ chỉ nhận các giá trị $0,1$ và có ít nhất một giá trị bằng $0$, thì có $2^{n-1}-1$ cách chọn dãy $(x_i)$. Khi đó mọi $y_j$ phải thuộc $\{0,1\}$, nên có $2^{n-1}$ cách chọn dãy $(y_j)$.
- Nếu dãy $(x_i)$ có ít nhất một giá trị bằng $-1$, thì có $3^{n-1}-2^{n-1}$ cách chọn. Khi đó tất cả $y_j$ đều phải bằng $1$.

Vậy số cách trong trường hợp này là
$$B=3^{n-1}+(2^{n-1}-1)2^{n-1}+3^{n-1}-2^{n-1}=2\cdot 3^{n-1}+4^{n-1}-2^n.$$

Trường hợp $x_1=y_1=-1$ hoàn toàn tương tự trường hợp trên, nên cũng có $B$ cách.

Vậy tổng số cách điền cần tính là
$$S_n=A+2B=4\cdot 4^{n-1}+6\cdot 3^{n-1}-2^{n+2}+1=4^n+2\cdot 3^n-4\cdot 2^n+1.$$

Với $n=2026$, số cách cần tính là $4^{2026}+2\cdot 3^{2026}-4\cdot 2^{2026}+1$.

b) Để ý 2 điểm $A(x_A,y_A)$ và $B(x_B,y_B)$ liên kết khi và chỉ khi $x_A\equiv x_B(\mathrm{mod}3)$ và $y_A\equiv y_B(\mathrm{mod}3)$.

Chia 62 điểm của $S$ vào 9 bộ theo cặp số dư $(x\mathrm{mod}3,y\mathrm{mod}3)$.

Theo nguyên lý Dirichlet, tồn tại một bộ chứa ít nhất $\lceil \frac{62}{9}\rceil =7$ điểm, giả sử là $A_1,\dots ,A_7$.

Khi đó mọi bộ hai điểm trong số này đều liên kết.

Giả sử các điểm trên có dạng $A_i=(3X_i+r,3Y_i+s)$ với $X_i,Y_i\in \mathbb{Z}$.

Với ba điểm $A_1(x_1,y_1)$, $A_2(x_2,y_2)$, $A_3(x_3,y_3)$, diện tích tam giác $A_1{A}_2{A}_3$ là
$$S_{A_1{A}_2{A}_3}=\frac{1}{2}\left|(x_2-x_1)(y_3-y_1)-(x_3-x_1)(y_2-y_1)\right|$$
$$=\frac{9}{2}\left|(X_2-X_1)(Y_3-Y_1)-(X_3-X_1)(Y_2-Y_1)\right|.$$

Xét 7 cặp $(X_i,Y_i)$ theo modulo 2, để ý tồn tại hai điểm, chẳng hạn $A_1,A_2$, sao cho $X_1\equiv X_2(\mathrm{mod}2)$ và $Y_1\equiv Y_2(\mathrm{mod}2)$. Chọn $A_3$ bất kỳ trong 5 điểm còn lại. Khi đó cả $X_2-X_1$ và $Y_2-Y_1$ đều chẵn, suy ra
$$(X_2-X_1)(Y_3-Y_1)-(X_3-X_1)(Y_2-Y_1)$$
là số chẵn. Vì thế diện tích tam giác $A_1{A}_2{A}_3$ là một số nguyên chia hết cho 9.

Nhận xét: Thậm chí ta chỉ cần tập $S$ gồm 37 điểm là đủ, và đây là giá trị tối ưu nhất có thể.