Câu 5 (7,0 điểm). Một tập hợp con $S\subset \{1,2,\dots ,n\}$ được gọi là tập tốt nếu với mọi $x$ thuộc $S$ thì ít nhất một trong hai số $x-1$ hoặc $x+1$ cũng thuộc $S$.
a) Chứng minh rằng một tập con $S\subset \{1,2,\dots ,n\},n\ge 5$, gồm 5 phần tử là tập tốt khi và chỉ khi nó có dạng $S=A\cup B$, với $A\cap B=\varnothing$, trong đó $A$ gồm 3 số nguyên liên tiếp và $B$ gồm hai số nguyên liên tiếp.
b) Chứng minh rằng số tập con $S$ ($S$ là tập tốt) gồm 5 phần tử của $\{1,2,\dots ,n\},n\ge 5$ là một số chính phương.

(AI giải đề cho tôi)
Nhận xét then chốt: $S$ là tập tốt khi và chỉ khi mỗi khối (run) các số liên tiếp cực đại của $S$ có độ dài ít nhất 2. Thật vậy, phần tử đầu/cuối của mỗi khối có láng giềng trong cùng khối; ngược lại nếu tồn tại khối độ dài 1, phần tử $x$ đó không có $x\pm 1$ trong $S$. Với $|S|=5$, cách phân tích 5 thành tổng độ dài các khối (mỗi khối $\ge 2$) chỉ có thể: $5=5$ hoặc $5=3+2$.

a) Chiều thuận: nếu $S$ là tập tốt gồm 5 phần tử thì $S$ hoặc là một khối 5 số liên tiếp $\{a,\dots ,a+4\}$, hoặc là hợp rời của khối 3 số và khối 2 số liên tiếp. Cả hai trường hợp đều viết được $S=A\cup B$, $A\cap B=\varnothing$ với $A$ gồm 3 số liên tiếp, $B$ gồm 2 số liên tiếp (với khối 5 số, lấy $A=\{a,a+1,a+2\}$, $B=\{a+3,a+4\}$). Chiều ngược: nếu $S=A\cup B$ như trên, mỗi phần tử của $A$ có láng giềng trong $A$, mỗi phần tử của $B$ có láng giềng trong $B$, nên $S$ là tập tốt (khi $B$ kề $A$ thì $S$ là khối 5 liên tiếp, vẫn tốt). $\square$

b) Đếm số tập tốt gồm 5 phần tử:
• Một khối 5 số liên tiếp: khối bắt đầu tại $a$, $1\le a\le n-4$: có $n-4$ tập.
• Hai khối (dài 3 và dài 2), cách nhau ít nhất một số không thuộc $S$:
– Khối 3 đứng trước, bắt đầu tại $i$; khối 2 bắt đầu tại $j\ge i+4$, $j\le n-1$: số cặp ${\sum }_{i=1}^{n-5}(n-i-4)=\frac{(n-5)(n-4)}{2}$.
– Khối 2 đứng trước, bắt đầu tại $j$; khối 3 bắt đầu tại $i\ge j+3$, $i\le n-2$: số cặp ${\sum }_{j=1}^{n-5}(n-j-4)=\frac{(n-5)(n-4)}{2}$.
Tổng trường hợp hai khối: $(n-5)(n-4)$.

Tổng số tập tốt: $(n-4)+(n-5)(n-4)=(n-4)(n-4)=(n-4{)}^2$, là số chính phương. Kiểm tra: $n=5$ cho đúng 1 tập $\{1,2,3,4,5\}=1^2$; $n=6$ cho $(6-4{)}^2=4$ tập: $\{1,\dots ,5\},\{2,\dots ,6\},\{1,2,3,5,6\},\{1,2,4,5,6\}$. $\square$