Bài Tập Trắc Nghiệm Chuyên Đề: Chứng minh tổ hợp (Toán học Lớp 10, 11, 12)

(AI giải đề cho tôi)
Biểu diễn bài toán bằng lý thuyết đồ thị: 20 vận động viên là 20 đỉnh; hai đỉnh kề nhau nếu hai người đã thi đấu với nhau. Mỗi vòng đấu là một ghép cặp hoàn hảo (perfect matching) gồm 10 cạnh; sau 4 vòng ta được đồ thị $G$ đều bậc 4 trên 20 đỉnh, là hợp của 4 ghép cặp hoàn hảo, không có cặp cạnh lặp. Cần tìm $k$ lớn nhất sao cho mọi đồ thị như vậy đều có tập độc lập (các đỉnh đôi một không kề) cỡ ít nhất $k$.

BƯỚC 1: Chứng minh mọi cách đấu đều cho phép chọn được 5 người đôi một chưa từng gặp nhau, tức $\alpha (G)\ge 5$.

Giả sử ngược lại $\alpha (G)\le 4$. Xét đồ thị bổ $H=\overline{G}$: $H$ là đồ thị 15-chuẩn trên 20 đỉnh nên có $\frac{20\cdot 15}{2}=150$ cạnh. Điều kiện $\alpha (G)\le 4$ tức $\omega (H)\le 4$, nghĩa là $H$ không chứa $K_5$. Theo định lý Turán, số cạnh lớn nhất của đồ thị trên 20 đỉnh không chứa $K_5$ là $$t_4(20)=\left(1-\frac{1}{4}\right)\cdot \frac{20^2}{2}=150.$$ Vậy $H$ đạt đúng số cạnh cực đại, suy ra $H$ chính là đồ thị Turán $T_4(20)$ (đa phần hoàn chỉnh với 4 phần, mỗi phần 5 đỉnh), do đó $G=\overline{H}$ là hợp rời của 4 đồ thị $K_5$.

Nhưng điều này vô lý: trong một vòng đấu, các cặp đấu nội bộ một nhóm $K_5$ (5 người) tạo thành một ghép cặp trên 5 đỉnh nên gồm tối đa 2 cạnh, luôn còn ít nhất 1 người của nhóm phải đấu với người ngoài nhóm; trong khi $G$ không có cạnh nối giữa các nhóm. Mỗi vòng chỉ có tối đa 2 cạnh nội nhóm nên 4 vòng có tối đa 8 cạnh, nhỏ hơn 10 cạnh của $K_5$. Mâu thuẫn. Vậy $\alpha (G)\ge 5$ với mọi cách chia cặp.

BƯỚC 2: Xây dựng một lịch đấu 4 vòng cụ thể sao cho không chọn được 6 người đôi một chưa từng gặp, tức tồn tại cách đấu với $\alpha (G)=5$.

Chia 20 người thành 5 nhóm $A,B,C,D,E$, mỗi nhóm 4 người đánh số $0,1,2,3$. Mỗi nhóm sẽ đấu đủ 6 cặp nội bộ (tạo thành một $K_4$); mỗi người còn đấu đúng 1 ván chéo với người của nhóm khác. Lịch cụ thể:

- Vòng 1 (A, B, C mỗi nhóm 2 ván nội bộ; D, E mỗi nhóm 1 ván nội bộ; 2 ván chéo):
$$a_0{a}_1,a_2{a}_3,b_0{b}_1,b_2{b}_3,c_0{c}_1,c_2{c}_3,d_2{d}_3,e_2{e}_3,d_2{e}_2,d_3{e}_3.$$
- Vòng 2 (A, B, C mỗi nhóm 2 ván nội bộ; D, E mỗi nhóm 1 ván nội bộ; 2 ván chéo):
$$a_0{a}_2,a_1{a}_3,b_0{b}_2,b_1{b}_3,c_0{c}_2,c_1{c}_3,d_0{d}_1,e_0{e}_1,d_0{e}_0,d_1{e}_1.$$
- Vòng 3 (A, B, C mỗi nhóm 1 ván nội bộ; D, E mỗi nhóm 2 ván nội bộ; 3 ván chéo):
$$a_0{a}_3,b_0{b}_3,c_0{c}_3,d_0{d}_2,d_1{d}_3,e_0{e}_2,e_1{e}_3,a_1{b}_1,a_2{c}_1,b_2{c}_2.$$
- Vòng 4 (A, B, C mỗi nhóm 1 ván nội bộ; D, E mỗi nhóm 2 ván nội bộ; 3 ván chéo):
$$a_1{a}_2,b_1{b}_2,c_1{c}_2,d_0{d}_3,d_1{d}_2,e_0{e}_3,e_1{e}_2,a_0{b}_0,a_3{c}_3,b_3{c}_0.$$

Kiểm tra tính hợp lệ:
- Mỗi vòng đúng 10 ván; mỗi người đấu đúng 1 ván mỗi vòng (kiểm tra từng vòng: mỗi tên xuất hiện đúng một lần).
- Nội bộ mỗi nhóm: 6 cặp $x_0{x}_1,x_2{x}_3$ (vòng 1 hoặc 3 tùy nhóm), $x_0{x}_2,x_1{x}_3$, $x_0{x}_3$, $x_1{x}_2$ — đủ 6 cặp của $K_4$, mỗi cặp đúng một lần.
- Các ván chéo: mỗi người đúng 1 ván chéo, mọi ván chéo nối hai người khác nhóm, không ván nào lặp lại.

Vậy đây là một lịch đấu hợp lệ sau 4 vòng. Trong đồ thị tương ứng, mỗi nhóm là một $K_4$ nên một tập độc lập chứa tối đa 1 đỉnh từ mỗi nhóm, suy ra $\alpha (G)\le 5$; hiển nhiên $\alpha (G)=5$. Do đó với cách chia cặp này không thể chắc chắn chọn 6 người đôi một chưa từng thi đấu.

KẾT LUẬN: Giá trị $k$ lớn nhất cần tìm là $k=5$.

Đầu tiên ta có bổ đề sau:
Bổ đề: Trong một bảng $r\times s$ gồm các số $0,1$, giả sử mọi bảng con $2\times 2$ gồm hai hàng liên tiếp và hai cột liên tiếp đều có tổng ít nhất bằng 2. Khi đó số các số 1 trong bảng không nhỏ hơn
$$\min \left\{s\lfloor \frac{r}{2}\rfloor ,r\lfloor \frac{s}{2}\rfloor \right\}.$$
Chứng minh. Trước hết, xét một bảng $2\times s$. Với $1\le j\le s$, gọi $c_j$ là tổng các phần tử của cột thứ $j$. Theo giả thiết, ta có $c_j+c_{j+1}\ge 2$ với mọi $1\le j\le s-1$.
Ghép các cột thành các cặp liên tiếp $(1,2),(3,4),\dots$ ta được $$\sum _{j=1}^s{c}_j\ge 2\lfloor \frac{s}{2}\rfloor .$$
Do đó một bảng $2\times s$ như trên có ít nhất $2\lfloor s/2\rfloor$ số 1.
Trong trường hợp $s$ lẻ, giả sử $s=2k+1$ và bảng có đúng $2k$ số 1. Khi đó
$$(c_1+c_2)+(c_3+c_4)+\cdots +(c_{2k-1}+c_{2k})+c_{2k+1}=2k.$$
Mỗi tổng trong $k$ dấu ngoặc đều không nhỏ hơn 2, nên bắt buộc
$$c_{2k+1}=0,c_{2i-1}+c_{2i}=2$$
với mọi $1\le i\le k$. Từ $c_{2k}+c_{2k+1}\ge 2$ và $c_{2k+1}=0$, suy ra $c_{2k}=2$, do đó $c_{2k-1}=0$. Do đó
$$(c_1,c_2,\dots ,c_{2k+1})=(0,2,0,2,\dots ,0,2,0).$$
Vì mỗi cột chẵn chứa hai số 1, còn mỗi cột lẻ chỉ chứa các số 0, nên mỗi hàng của bảng có đúng $k$ số 1.
Bây giờ trở lại bảng $r\times s$ ban đầu. Nếu $r$ chẵn, ta ghép các hàng thành các cặp liên tiếp. Mỗi cặp hàng tạo thành một bảng $2\times s$, nên chứa ít nhất $2\lfloor s/2\rfloor$ số 1. Vì có $r/2$ cặp hàng, toàn bảng có ít nhất
$$\frac{r}{2}\cdot 2\lfloor \frac{s}{2}\rfloor =r\lfloor \frac{s}{2}\rfloor$$
số 1. Tương tự, nếu $s$ chẵn thì ghép các cột thành từng cặp liên tiếp, ta được ít nhất $s\lfloor \frac{r}{2}\rfloor$ số 1.
Như vậy, bổ đề đúng nếu $r$ hoặc $s$ chẵn.
Ta chỉ còn xét trường hợp $r=2h+1$, $s=2k+1$.
Không mất tính tổng quát, giả sử $h\le k$. Khi đó $\min \{(2k+1)h,(2h+1)k\}=(2k+1)h$.
Ta sẽ chứng minh bằng quy nạp theo $h$ rằng bảng có ít nhất $h(2k+1)$ số 1.
Với $h=0$, khẳng định hiển nhiên. Giả sử $h\ge 1$ và khẳng định đã đúng với $h-1$.
Gọi $t$ là số các số 1 trên hàng đầu tiên.
Nếu $t\ge h$, ta bỏ hàng đầu tiên. Phần còn lại là một bảng $2h\times (2k+1)$. Theo trường hợp số hàng chẵn đã chứng minh, bảng này có ít nhất $2h\lfloor \frac{2k+1}{2}\rfloor =2hk$ số 1.
Vì thế bảng ban đầu có ít nhất $2hk+h=h(2k+1)$ số 1.
Nếu $t\le h-1$, xét bảng $2\times (2k+1)$ tạo bởi hai hàng đầu tiên.
Theo kết quả ở đầu chứng minh, hai hàng này có ít nhất $2k$ số 1.
Nếu chúng có đúng $2k$ số 1, thì theo trường hợp đầu bảng đã xét, mỗi hàng phải có đúng $k$ số 1. Đặc biệt, hàng đầu tiên có đúng $k$ số 1, mâu thuẫn với $t\le h-1<k$ do $h\le k$. Vì vậy, hai hàng đầu tiên phải chứa ít nhất $2k+1$ số 1.
Bỏ hai hàng đầu tiên, ta còn lại một bảng
$$(2h-1)\times (2k+1)=(2(h-1)+1)\times (2k+1).$$
Vì $h-1\le k$, theo giả thiết quy nạp, bảng còn lại có ít nhất $(h-1)(2k+1)$ số 1. Do đó toàn bảng có ít nhất $(2k+1)+(h-1)(2k+1)=h(2k+1)$ số 1.
Cuối cùng, ta chứng minh cận dưới này đạt được. Nếu điền số 1 vào toàn bộ các vị trí thuộc các hàng có chỉ số chẵn và điền số 0 vào các vị trí còn lại, thì mỗi cặp hàng liên tiếp chứa đúng một hàng toàn số 1. Vì vậy, mỗi bảng con $2\times 2$ gồm hai hàng liên tiếp và hai cột liên tiếp có đúng hai số 1. Tổng số các số 1 trong cách điền này là $s\lfloor \frac{r}{2}\rfloor$.
Tương tự, nếu điền số 1 vào toàn bộ các cột có chỉ số chẵn và điền số 0 vào các vị trí còn lại, ta thu được một bảng thỏa mãn giả thiết và có $r\lfloor \frac{s}{2}\rfloor$ số 1. Chọn cách điền tương ứng với số nhỏ hơn trong hai số trên, ta thấy cận dưới đạt được. Vậy số các số 1 ít nhất là
$$\min \left\{s\lfloor \frac{r}{2}\rfloor ,r\lfloor \frac{s}{2}\rfloor \right\}.$$

Trở lại bài toán ban đầu:
Một khu vườn gồm $m\times n$ ô vuông đơn vị có $(m+1)\times (n+1)$ đỉnh. Ta xem các đỉnh này như một bảng gồm các số 0, 1, số 1 biểu thị đỉnh có đặt bóng điện, còn số 0 biểu thị đỉnh không đặt bóng điện. Khi đó bốn đỉnh của mỗi ô vuông đơn vị tạo thành một bảng con $2\times 2$ gồm hai hàng liên tiếp, hai cột liên tiếp.
a) Khu vườn có $2025\times 2026$ ô vuông đơn vị.
Xét các ô vuông nằm trên các hàng $1,3,5,\dots ,2025$ và các cột $1,3,5,\dots ,2025$, có tất cả
$$1013\cdot 1013=1013^2$$
ô vuông như vậy. Hai ô bất kỳ trong số này không có đỉnh chung. Vì mỗi ô phải có ít nhất một đỉnh được đặt bóng điện, nên các bóng điện chiếu sáng các ô trên phải đôi một khác nhau.
Do đó cần ít nhất $1013^2$ bóng điện.
Ta chứng minh cận dưới này đạt được. Đánh số các hàng đỉnh từ 1 đến 2026 và các cột đỉnh từ 1 đến 2027. Đặt bóng tại tất cả các đỉnh là giao điểm của một hàng đỉnh chẵn và một cột đỉnh chẵn.
Trong hai hàng đỉnh liên tiếp có đúng một hàng chẵn, và trong hai cột đỉnh liên tiếp có đúng một cột chẵn nên mỗi ô vuông đơn vị có đúng một đỉnh được đặt bóng điện, nên toàn bộ khu vườn được chiếu sáng. Số hàng đỉnh chẵn và số cột đỉnh chẵn bằng 1013, nên số bóng điện được dùng là $1013^2$.
Vậy số bóng điện ít nhất cần dùng là $1013^2$.
b) Để khu vườn vẫn được chiếu sáng khi một bóng điện bất kỳ bị cháy, mỗi ô vuông đơn vị phải có ít nhất hai đỉnh được đặt bóng điện. Thật vậy, nếu một ô chỉ có đúng một bóng điện thì khi bóng điện đó bị cháy, ô ấy sẽ không còn được chiếu sáng. Ngược lại, nếu mỗi ô có ít nhất hai bóng điện thì sau khi một bóng bất kỳ bị cháy, mỗi ô vẫn còn ít nhất một bóng hoạt động.
Bảng các đỉnh của khu vườn có kích thước $2026\times 2027$.
Điều kiện trên tương đương với việc mọi bảng con $2\times 2$ gồm hai hàng liên tiếp và hai cột liên tiếp đều có tổng ít nhất bằng 2.
Áp dụng bổ đề với $r=2026$ và $s=2027$, số bóng điện không nhỏ hơn
$$\min \left\{2027\lfloor \frac{2026}{2}\rfloor ,2026\lfloor \frac{2027}{2}\rfloor \right\}=2026\cdot 1013=2\cdot 1013^2$$
Theo trường hợp dấu bằng trong bổ đề, cận này đạt được bằng cách đặt bóng điện tại toàn bộ các đỉnh thuộc các cột đỉnh có chỉ số chẵn.
Vậy số bóng điện ít nhất cần dùng là $2\cdot 1013^2$.
c) Khi mở rộng khu vườn thành bảng $2026\times 2026$, bảng các đỉnh có kích thước $2027\times 2027$.
Tương tự câu trên và áp dụng bổ đề với $r=s=2027$, số bóng điện không nhỏ hơn
$$\min \left\{2027\lfloor \frac{2027}{2}\rfloor ,2027\lfloor \frac{2027}{2}\rfloor \right\}=2027\cdot 1013.$$
Theo trường hợp dấu bằng trong bổ đề, cận này đạt được bằng cách đặt bóng điện tại toàn bộ các đỉnh thuộc các hàng đỉnh có chỉ số chẵn hoặc toàn bộ các đỉnh thuộc các cột đỉnh có chỉ số chẵn.
Vậy số bóng điện ít nhất cần dùng là $2027\cdot 1013$.

Ta gọi các giao điểm của các đường kẻ trong bảng là các đỉnh lưới.

Bảng $n\times n$ có tất cả $(n+1{)}^2$ đỉnh lưới.

Mỗi quân đôminô phủ một hình chữ nhật kích thước $1\times 2$, do đó chứa đúng 6 đỉnh lưới.

Vì hai quân đôminô bất kỳ không có điểm chung (kể cả ở đỉnh), nên 6 đỉnh lưới thuộc hai quân khác nhau cũng đôi một phân biệt. Bởi vậy, nếu xếp được 661 quân thì:

$$6\cdot 661\le (n+1{)}^2.$$

Từ đây suy ra được $n+1\ge 63$ hay $n\ge 62$.

Để chỉ ra $n=62$ thoả mãn, ta xếp như sau:



Trên mỗi hàng thuộc tập hợp $\{1,3,5,\dots ,59\}$, ta đặt các quân đôminô nằm ngang phủ các cặp cột:

$$(1,2),(4,5),(7,8),\dots ,(61,62)$$

Có 30 hàng được chọn và trên mỗi hàng có 21 quân, nên ta đặt được 630 quân đôminô.

Trên hai hàng 61 và 62, ta đặt 31 quân đôminô thẳng đứng tại các cột: $1,3,5,\dots ,61$.

Cách sắp xếp trên cho ta 661 quân đôminô, do đó giá trị nhỏ nhất của $n$ bằng 62.

Kết luận: $n_{\min }=62$

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

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):

(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.

Lời giải (nguồn: CLB Toán Lim - LIM Olympic):

(1) Với mỗi tập con $T\subset \{3,4,\dots ,2026\}$, xét bốn tập $T$, $T\cup \{1\}$, $T\cup \{2\}$ và $T\cup \{1,2\}$.
Giả sử tổng các phần tử của $T$ có số dư là $r$ khi chia cho 4. Khi đó tổng các phần tử của bốn tập trên lần lượt có số dư $r,r+1,r+2,r+3$ (mod 4).
Do đó trong bốn tập trên có đúng một tập có tổng các phần tử chia hết cho 4.
Khi $T$ chạy qua tất cả các tập con của $\{3,4,\dots ,2026\}$, các nhóm gồm bốn tập trên tạo thành một phân hoạch của tập hợp tất cả các tập con của $S$. Có $2^{2024}$ cách chọn $T$, nên có đúng $2^{2024}$ tập con của $S$ có tổng các phần tử chia hết cho 4 (kể cả tập rỗng).
Giờ trừ đi tập rỗng (có tổng bằng 0) ta được số tập con cần tìm là $2^{2024}-1$.

(2) Điều kiện $|S_i\setminus S_j|\ne 0$ với mọi $i\ne j$ tương đương với $S_i\not\subset S_j$ với mọi $i\ne j$.
Như vậy các tập $S_1,S_2,\dots ,S_n$ đôi một không chứa nhau.
Trước hết ta chứng minh $n\le 2024$.
Để ý với $n\ge 2$ thì ta không thể có $S_i=S$, do đó $1\le |S_i|\le 2025$ với mọi $i$.
Vì các $|S_i|$ đôi một khác nhau nên trước hết ta có $n\le 2025$.
Giả sử $n=2025$. Khi đó các số $|S_i|$ phải nhận đủ các giá trị $1,2,\dots ,2025$.
Gọi $A,B,C$ là 3 tập $S_i$ bên trên thỏa mãn $|A|=1$, $|B|=2025$, $|C|=2$. Viết $A=\{a\}$.
Do $A\not\subset B$ nên $a\notin B$. Mà $|B|=2025$, suy ra $B=S\setminus \{a\}$.
Mặt khác, từ $A\not\subset C$ ta cũng có $a\notin C$. Vì thế $C\subset S\setminus \{a\}=B$, mâu thuẫn với điều kiện $C\not\subset B$.
Vậy $n\le 2024$. Giờ ta sẽ chứng minh giá trị $n=2024$ đạt được.
Ta chứng minh bằng quy nạp rằng với mọi số chẵn $m\ge 4$, tồn tại một họ ${\mathcal{F}}_m$ gồm $m-2$ tập con của $\{1,2,\dots ,m\}$ sao cho các tập đôi một không chứa nhau và có kích thước lần lượt là $1,2,\dots ,m-2$.
Với $m=4$, lấy ${\mathcal{F}}_4=\{\{1\},\{2,3\}\}$. Rõ ràng họ này thỏa mãn yêu cầu.
Giả sử đã xây dựng được ${\mathcal{F}}_m$. Xét họ
$${\mathcal{F}}_{m+2}=\{A\cup \{m+1\}:A\in {\mathcal{F}}_m\}\cup \{[m],\{m+2\}\},$$
trong đó $[m]=\{1,2,\dots ,m\}$.
Các tập $A\cup \{m+1\}$ có kích thước lần lượt là $2,3,\dots ,m-1$, còn $\{m+2\}$ có kích thước $1$ và $[m]$ có kích thước $m$. Vậy ${\mathcal{F}}_{m+2}$ có đúng một tập ở mỗi kích thước $1,2,\dots ,m$.
Hai tập dạng $A\cup \{m+1\}$ đôi một không chứa nhau vì các tập $A$ ban đầu đôi một không chứa nhau. Mỗi tập $A\cup \{m+1\}$ chứa phần tử $m+1$, trong khi $[m]$ không chứa $m+1$, nên $A\cup \{m+1\}\not\subset [m]$. Ngược lại, $|A\cup \{m+1\}|\le m-1<m=|[m]|$, nên $[m]\not\subset A\cup \{m+1\}$.
Cuối cùng, $\{m+2\}$ không chứa trong bất kì tập nào còn lại vì các tập đó không chứa $m+2$; đồng thời các tập còn lại đều có ít nhất hai phần tử nên không thể chứa trong $\{m+2\}$.
Vậy ${\mathcal{F}}_{m+2}$ cũng thỏa mãn yêu cầu.
Lấy $m=2026$, ta thu được 2024 tập con của $S$ thỏa mãn tất cả các điều kiện của bài toán.
Do đó $n_{\max }=2024$

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.