ĐỀ THI
Ngày thi thứ nhất
Bài 1. Cho dãy số $\left(u_n\right)$ giảm ngặt thoả mãn $u_n>0$. Biết rằng $\left(s_n\right)$ hội tụ với:
$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad s_n=u_1+u_2+\ldots+u_n, \forall n \in \mathbb{N}^*$
(a) Chứng minh rằng $\lim n u_n=0$.
(b) Đặt $b_n=\frac{1}{u_{n+1}}-\frac{1}{u_n}, \forall n \in \mathbb{N}^*$. Chứng minh rằng $\left(b_n\right)$ không bị chặn.
Bài 2. Gọi $S$ là tập con của ${1,2, \ldots, 2017}$ sao cho $S$ không chứa hai phần tử mà phần tử này chia hết cho phần tử kia và cũng không chứa hai phần tử nguyên tố cùng nhau. Hỏi $S$ chứa nhiều nhất bao nhiêu phần tử ?
Bài 3. Cho $n>2$ là số tự nhiên và $X={1,2, \ldots, n}$. Với mỗi song ánh $f: X \rightarrow X$, gọi $A_f$ là tập hợp tất cả các bộ $(i, j)$ sao cho $i<j$ và $f(i)>f(j)$.
(a) Có bao nhiêu song ánh $f$ thoả mãn $\left|A_f\right|=1$ ?
(b) Giả sử $f$ là một song ánh mà $\left|A_f\right|=k>0$. Chứng minh rằng tồn tại một song ánh $g: X \rightarrow X$ sao cho $\left|A_g\right|=k-1$ và:
$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \sum_{k=1}^n|f(k)-k| \geq \sum_{k=1}^n|g(k)-k|$
Bài 4. Cho tam giác $A B C$ nhọn nội tiếp đường tròn $(O)$ và điểm $D$ di động trên cung $B C$ chứa $A(D$ khác $A)$. Lấy trên $A B, A C$ lần lượt các điểm $M, N$ để $M D=M B$ và $N C=N D$.
(a) Chứng minh rằng đường cao $D H$ trong tam giác $D M N$ luôn đi qua một điểm cố định.
(b) $D M, D N$ theo thứ tự cắt lại $(O)$ tại $E, F$. Chứng minh rằng đường tròn ngoại tiếp các tam giác $E M B, F N C$ cắt nhau tại điểm $K$ thuộc đường thẳng $B C$ và đường cao $K I$ của tam giác $K M N$ luôn đi qua một điểm cố định.
Ngày thi thứ hai
Bài 5. Với mỗi số nguyên $n \notin{0,1,-1}$, ký hiệu $p(n)$ là ước nguyên tố lớn nhất của n. Gọi $\mathcal{F}$ là tập hợp tất cả các đa thức $f(x)$ có hệ số nguyên thoả mãn:
$\quad\quad\quad\quad f(n+p(n))=n+p(f(n)) \forall n \in \mathbb{Z}, n>2017, f(n) \notin{0,1,-1}$
(a) Tìm tất cả các đa thức bậc nhất là phần tử của $\mathcal{F}$.
(b) Xác định số phần tử của $\mathcal{F}$.
Bài 6. Với mỗi số tự nhiên $n$, ký hiệu $T(1+n, 3+n, 4+n)$ là tập hợp tất cả các bộ $(a, b, c)$ với $a, b, c$ là các số tự nhiên thoả mãn:
$\quad\quad\quad\quad\quad 1 \leq a \leq 1+n, a+1 \leq b \leq 3+n, b+1 \leq c \leq 4+n$
Gọi $a_n$ là số phần tử của $T(1+n, 3+n, 4+n)$.
(a) Tính $a_4$.
(b) Tìm tất cả số tự nhiên $n$ để $a_n$ chia hết cho 3 .
Bài 7. An và Bình luân phiên nhau đánh dấu các ô vuông của hình vuông $101 \times 101$ ô. An là người bắt đầu. Một ô sẽ không thể được tô màu nếu trên cùng hàng với nó hoặc cùng cột với nó đã có ít nhất 2 ô được tô. Ai không đi được nữa sẽ thua. Hãy xác định ai là người có chiến thuật thắng.
Bài 8. Đường tròn $(O)$ nội tiếp tứ giác $A B C D$ và tiếp xúc với các cạnh $A B, B C$, $C D, D A$ lần lượt tại các điểm $E, F, G, H$. Gọi $I, J$ là trung điểm của các đoạn thẳng $A C, B D$. Giả sử $I B, I D, J A, J C$ theo thứ tự cắt $E F, G H, H E, F G$ tại $M, N, P, Q$
(a) Chứng minh rằng $I J, M N, P Q$ đồng quy tại điểm $S$.
(b) Các tia đối của các tia $J A, I B, J C, I D$ lần lượt cắt $(O)$ tại các điểm $A^{\prime}, B^{\prime}, C^{\prime}, D^{\prime} . A^{\prime} C^{\prime}, B^{\prime} D^{\prime}$ lần lượt cắt $P Q, M N$ tại $U, V$. Gọi $K$ là hình chiếu của $S$ trên $U V$. Chứng minh rằng $\angle A K B=\angle C K D$.
LỜI GIẢI
Bài 1. Cho dãy số $\left(u_n\right)$ giảm ngặt thoả mãn $u_n>0$. Biết rằng $\left(s_n\right)$ hội tụ với:
$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad s_n=u_1+u_2+\ldots+u_n, \forall n \in \mathbb{N}^* .$
(a) Chứng minh rằng $\lim n u_n=0$.
(b) Đặt $b_n=\frac{1}{u_{n+1}}-\frac{1}{u_n}, \forall n \in \mathbb{N}^*$. Chứng minh rằng $\left(b_n\right)$ không bị chặn.
Lời giải. (a) Do $\left(s_n\right)$ là dãy số dương tăng ngặt và hội tụ nên với $\epsilon>0$ bất kỳ, tồn tại $T \in \mathbb{N}^$ dể với $m, n \in \mathbb{N}^, T<m<n$ thì
$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \sum_{k=m+1}^n u_k=s_n-s_m<\epsilon .$
Một hệ quả của sự kiện trên là $\lim u_n=0$. Do $\left(u_n\right)$ giảm ngặt nên cũng từ điều kiện trên, ta có $(n-m) u_n<s_n-s_m<\epsilon$ hay:
$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad n u_n<\epsilon+m u_n .$
Do $\lim u_n=0$ tồn tại $T^{\prime}>T$ dể với $n>T^{\prime}>T$, ta có $u_n<\frac{\epsilon}{m}$. Lúc đó thì:
$\quad\quad\quad\quad\quad\quad\quad\quad n u_n<\epsilon+m \cdot \frac{\epsilon}{m}=2 \epsilon, \forall n>T^{\prime} .$
Lại có $n u_n>0 \forall n \in \mathbb{N}^*$ nên theo định nghĩa về giới hạn, ta có $\lim n u_n=0$.
(b) Dĩ nhiên $\left(u_n\right)$ là dãy giảm nên $b_n>0 \forall n \in \mathbb{N}^*$
Do đó ta chỉ cần chứng minh rằng $\left(b_n\right)$ không bị chặn trên.
Giả sử rằng $\left(b_n\right)$ bị chặn trên. Khi đó tồn tại số thực $c>0$ để $b_n<c, \forall n \in \mathbb{N}^*$. Với điều kiện ấy, ta có
$\quad\quad\quad\quad \frac{1}{u_{n+1}}-\frac{1}{u_1}=\sum_{k=1}^n\left(\frac{1}{u_{k+1}}-\frac{1}{u_k}\right)<n c<(n+1) c, \forall n \in \mathbb{N}^*$
Từ đó thì
$\quad\quad\quad\quad\quad\quad\quad \frac{1}{(n+1) u_{n+1}}-\frac{1}{(n+1) u_1}<c, \forall n \in \mathbb{N}^* .$
Do $\lim n u_n=0$ nên khi $n \rightarrow+\infty$ thì
$\quad\quad\quad\quad\quad\quad\quad\quad\quad \frac{1}{(n+1) u_{n+1}}-\frac{1}{(n+1) u_1} \rightarrow+\infty$
Điều vô lý này cho thấy điều giả sử là sai. Do đó $\left(b_n\right)$ không bị chặn trên.
Bài 2. Gọi $S$ là tập con của ${1,2, \ldots, 2017}$ sao cho $S$ không chứa hai phần tử mà phần tử này chia hết cho phần tử kia và cũng không chứa hai phần tử nguyên tố cùng nhau. Hỏi $S$ chứa nhiều nhất bao nhiêu phần tử ?
Lời giải . Xét tập hợp $S={1010,1012,1014, \ldots, 2016}$. Tất cả các phần tử đều chẵn nên không có hai phần tử nào nguyên tố cùng nhau. Hơn thế nữa, phần tử lớn nhất nhỏ hơn 2 lần phần tử nhỏ nhất nên cũng không có hai phần tử mà phần tử này chia hết cho phần tử kia. Do đó $S$ thoả mãn đề bài và $|S|=504$.
Ta sẽ chứng minh rằng đây chính là giá trị lớn nhất cần tìm. Giả sử ngược lại rằng tồn tại một tập hợp $S$ thoả mãn tính chất đề bài và có ít nhất 505 phần tử.
Với mỗi số chẵn $i$ để $1010 \leq i \leq 2016, i$ có thể viết được dưới dạng $i=2^\alpha \cdot m$ với $\alpha \in \mathbb{N}^*$ và $(m, 2)=1$. Xét các tập hợp $A_i$ có dạng như sau:
$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad A_i=[2^k \cdot m \mid 0 \leq k \leq \alpha] .$
Rõ ràng 2017 là số nguyên tố nên $2017 \notin S$, vì nếu không thì tất cả các số còn lại đều nguyên tố cùng nhau với nó, mâu thuẫn với tính chất của $S$. Rõ ràng mọi số nguyên dương $a \leq 1008$ đều thuộc về ít nhất một tập hợp $A_i$ nào đó nêu trên.
Tiếp theo, ta xét 504 tập hợp:
$\quad\quad\quad\quad\quad\quad A_{1010} \cup{1009}, A_{1012} \cup{1011}, \ldots, A_{2016} \cup{2015} .$
Các tập hợp này chứa tất cả các số nguyên dương từ 1 dến 2016.
Vì $S$ có ít nhất 505 phần tử nên phải có ít nhất hai phần tử $a<b$ thuộc cùng một tập hợp nào đó trong 504 tập hợp ở trên. Ta có hai trường hợp:
- Nếu $b=i+1$ và $a \in A_i$ thì rõ ràng $(i, i+1)=1$ nên $b$ nguyên tố cùng nhau với tất cả các số thuộc $A_i$, dẫn đến $(a, b)=1$, mâu thuẫn.
-
Nếu $a, b \in A_i$ thì theo cách xây dựng $A_i$, ta sẽ có $a \mid b$, cũng mâu thuẫn. Do đó không thể có $S$ để $|S| \geq 505$. Vậy $\max S=504$.
Nhận xét. Ngoài lời giải trên, dưới đây là một cách tiếp cận khác mang ý tưởng thuật toán
- Xét tập hợp $S$ thoả mãn yêu cầu bài toán mà có $|S|$ lớn nhất. Ta thực hiện phép biến đổi trên các phần tử của $S$ như sau: Xét số $a=\min S$. Nếu như $a \leq 1008$ thì lập tập hợp $S^{\prime}=(S \backslash{a}) \cup{2 a}$.
-
Ta chứng minh rằng $S^{\prime}$ vẫn thoả mãn yêu cầu bài toán. Dĩ nhiên $2 a \notin S$ nên $|S|=\left|S^{\prime}\right|$. Rõ ràng không có $k \in S, k \neq a$ để $2 a \mid k$, vì nếu thế thì $a \mid k$, vô lý.
-
Nếu có $k \in S$ để $k \mid 2 a$, ta có $a<k \leq 2 a$ nên $k=2 a$, cũng vô lý.
-
Do đó tập hợp $S^{\prime}$ cũng thoả mãn điều kiện. Thực hiện phép biến đổi cho đến khi thu được tập hợp $S_f \subset{1009, \ldots, 2017}$ và thoả mãn yêu cầu.
-
Đến đây dễ dàng có $\left|S_f\right|=|S|=504$. Bài toán kết thúc.
Lời giải trên có thể thay 2017 bởi số nguyên dương $n$ bất kỳ.
Bài 3. Cho $n>2$ là số tự nhiên và $X={1,2, \ldots, n}$. Với mỗi song ánh $f: X \rightarrow X$, gọi $A_f$ là tập hợp tất cả các bộ $(i, j)$ sao cho $i<j$ và $f(i)>f(j)$.
(a) Có bao nhiêu song ánh $f$ thoả mãn $\left|A_f\right|=1$ ?
(b) Giả sử $f$ là một song ánh mà $\left|A_f\right|=k>0$. Chứng minh rằng tồn tại một song ánh $g: X \rightarrow X$ sao cho $\left|A_g\right|=k-1$ và:
$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \sum_{k=1}^n|f(k)-k| \geq \sum_{k=1}^n|g(k)-k|$
Lời giải . (a) Gọi $S_n$ là số song ánh $f$ có $\left|A_f\right|=1$ tương ứng với mỗi giá trị $n$. Với $n=3$, ta có hai hoán vị thoả mãn là $(1,3,2)$ và $(2,1,3)$ nên $S_3=2$. Xét quan hệ giữa $S_{n+1}, S_n$ thông qua hoán vị của dãy $(1,2, \ldots, n, n+1)$.
- Nếu $f(n+1)=n+1$ thì loại $n+1 \mathrm{ra}$, ta có một hoán vị thoả mãn đề bài của $n$ số nguyên dương đầu tiên, có tất cả $S_n$ hoán vị như thế.
-
Nếu $f(n+1) \neq n+1$ thì rõ ràng $f(n)=n+1$ vì nếu $f(i)=n+1$ với $i<n$ thì $\left|A_f\right| \geq 2$, không thoả mãn bài toán. Khi đó, ta phải có được $f(n+1)=n$, từ đó $f(n)=n+1$ và $f(i)=i$ với $1 \leq i \leq n-1$. Ta có thêm 1 hoán vị nữa.
Từ đó $S_{n+1}=S_n+1$. Từ công thức truy hồi này, ta có số song ánh cần tìm là $n-1$.
(b) Gọi $j$ là chỉ số lớn nhất sao cho $f(j)=t<j$. Rõ ràng chỉ số $j$ luôn tồn tại vì $\left|A_f\right|=k>0$. Khi đó, ta cũng có $f(i)=i$ với $j+1 \leq i \leq n$.
Xét chỉ số $m$ sao cho $f(m)=t+1 \leq j$ thì $1 \leq m \leq j$. Dễ thấy rằng khi đổi chỗ hai số $(f(j), f(m))$ này sẽ làm giảm giá trị $\left|A_f\right|$ đi 1 đơn vị. Xét song ánh $g: X \rightarrow X$ tương ứng với việc đổi chỗ này mà $\left|A_g\right|=k-1$. Ta sẽ chứng minh rằng
$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad T=\sum_{i=1}^n\left|b_i-i\right|-\sum_{i=1}^n\left|a_i-i\right| \leq 0 .$
Thật vậy, ta có:
$\quad\quad\quad\quad\quad\quad\quad\quad T=\left|b_j-m\right|+\left|b_m-j\right|-\left|a_j-j\right|-\left|a_m-m\right| $
$\quad\quad\quad\quad\quad\quad\quad\quad\quad =|t+1-j|+|t-m|-|t-j|-|t+1-m|$
Vì $t+1 \leq j$ nên ta có:
$T=j-(t+1)-(j-t)+|t-m|-|t+1-m|=|t-m|-|t+1-m|-1$
Vì $t-m$ và $t+1-m$ là hai số nguyên liên tiếp nên $T \leq 1-1=0$.
Song ánh $g$ như trên thoả mãn điều kiện bài toán.
Bài 4. Cho tam giác $A B C$ nhọn nội tiếp đường tròn $(O)$ và điểm $D$ di động trên cung $B C$ chứa $A(D$ khác $A)$. Lấy trên $A B, A C$ lần lượt các điểm $M, N$ để $M D=M B$ và $N C=N D$.
(a) Chứng minh rằng đường cao $D H$ trong tam giác $D M N$ luôn đi qua một điểm cố định.
(b) $D M, D N$ theo thứ tự cắt lại $(O)$ tại $E, F$. Chứng minh rằng đường tròn ngoại tiếp các tam giác $E M B, F N C$ cắt nhau tại điểm $K$ thuộc đường thẳng $B C$ và đường cao $K I$ của tam giác $K M N$ luôn đi qua một điểm cố định.
Lời giải. (a) Gọi $D H$ cắt $(O)$ tại $X$. Do
$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \angle A M D=2 \angle A B D=2 \angle A C D=\angle A N D$
nên tứ giác $A M N D$ nội tiếp. Từ đó $\angle D M N=\angle D A C=\angle D B C$. Lại có:
$\quad\quad\quad\quad\quad\quad\quad \angle B D X =\angle H D M-\angle M D B=90^{\circ}-\angle H M D-\angle M D B $
$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad =90^{\circ}-\angle M B D-\angle D B C=90^{\circ}-\angle A B C .$
Từ đó $A X \perp B C$. Vậy $D H$ đi qua điểm $X$ cố định.
(b) Ta có $\angle M E B=180^{\circ}-\angle B C D=180^{\circ}-\angle B O M$ nên tứ giác $O M E B$ nội tiếp. Tương tự thì tứ giác $C N O F$ nội tiếp. Khi đó, ta có $(O M B)$ và $(O C N)$ cắt nhau tại $K$ nằm trên $B C$. Ta có $\angle O M K=\angle O B C$ và:
$\quad\quad\quad\quad \angle M K N=\angle M K O+\angle N K O=\angle O B A+\angle O C A=\angle B A C$
Từ đó $\angle O M K+\angle M K N=\angle B A C+\angle O B C=90^{\circ}$ nên $M O \perp K N$. Chứng minh tương tự thì $O N \perp K M$. Do đó $O$ là trực tâm tam giác $K M N$.
Vậy $K O \perp M N$. Hơn nữa $K I \perp M N$ nên $K I$ đi qua điểm $O$ cố định.
Nhận xét. Một số bài toán ở Đội tuyển PTNK 2017 liên quan đến mô hình trên:
1) Cho tam giác $A B C$ nội tiếp đường tròn $(O)$. Đường tròn qua $O, A$ lần lượt cắt $(O), A B, A C$ tại $D, E, F$. Gọi $D E, D F$ cắt lại $(O)$ tại $M, N . M N$ cắt $B C$ tại $K$. Chứng minh rằng tâm đường tròn ngoại tiếp tam giác $K E F$ luôn thuộc một đường thẳng cố định.
2) Cho tam giác $A B C$ nhọn nội tiếp đường tròn $(O)$. Lấy $D, E, F$ trên $B C, C A, A B$ sao cho $(A E F),(B F D),(C D E)$ cùng đi qua $(O)$. Các đường tròn này lần lượt cắt lại $(O)$ tại $K, M, N$. Các đường cao $d_K, d_M, d_N$ của các tam giác $K E F, M F D, N D E$ cắt nhau tạo thành tam giác $\delta$. Gọi $H, P, Q$ lần lượt là trực tâm các tam giác $D E F, K M N$ và $\delta$. Chứng minh rằng $H P=H Q$ và $Q$ là trực tâm tam giác $A B C$.
Ngảy thi thứ hai
Bài 5. Với mỗi số nguyên $n \notin{0,1,-1}$, ký hiệu $p(n)$ là ước nguyên tố lớn nhất của $n$. Gọi $\mathcal{F}$ là tập hợp tất cả các đa thức $f(x)$ có hệ số nguyên thoả mãn điều kiện
$\quad\quad\quad\quad f(n+p(n))=n+p(f(n)) \forall n \in \mathbb{Z}, n>2017, f(n) \notin{0,1,-1}$
(a) Tìm tất cả các đa thức bậc nhất là phần tử của $\mathcal{F}$.
(b) Xác định số phần tử của $\mathcal{F}$.
Lời giải . (a) Trước hết, ta thấy rằng $f(n) \equiv 0, f(n) \equiv 1, f(n) \equiv-1$ thoả mãn bài toán vì không có ràng buộc ở đề bài cho các giá trị này. Ta thấy rằng có hữu hạn giá trị $n>2017$ để $f(n) \in{0,1,-1}$ nên có vô hạn $n>2017$ để $f(n) \notin{0,1,-1}$. Trong lập luận bên dưới, ta chỉ xét $n$ để $f(n) \notin{0,1,-1}$.
Nhận xét rằng với mọi $n \in \mathbb{Z}$ và $|n| \geq 2$ thì $2 \leq p(n) \leq|n|$. Đẳng thức ở bất đẳng thức thứ hai xảy ra khi và chỉ khi $|n|$ là số nguyên tố.
Trong đẳng thức đã cho, thay $n=q>2017$ là số nguyên tố, ta có:
$\quad\quad\quad\quad\quad f(q+p(q))=q+p(f(q)) \text { hay } f(2 q)=q+p(f(q))$
Từ đó $f(2 q)>q$ với mọi $q>2017$ là số nguyên tố. Do đó, $f(n)$ không thể là đa thức hằng (khác $0,1,-1$ ) và trong trường hợp deg $f>0$, hệ số bậc cao nhất của $f$ cũng không thể âm, vì nếu không thì có $q$ đủ lớn để $f(2 q)<0$, mâu thuẫn.
Cũng từ đẳng thức trên, ta có $f(2 q) \leq q+f(q)$ với mọi $q$ nguyên tố và $q>2017$.
Nếu deg $f=1$, đặt $f(n)=a n+b$ với $a \neq 0$. Bất đẳng thức ở trên đưa về:
$\quad\quad\quad\quad\quad\quad\quad\quad a(2 q)+b \leq q+a q+b \Leftrightarrow a q \leq q \Leftrightarrow a \leq 1$
Theo nhận xét ở trên thì $a>0$ nên $a=1$. Thay vào phía trên thì:
$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad 2 q+b=q+p(q+b) \Leftrightarrow q+b=p(q+b) .$
Từ đây $q+b$ là số nguyên tố. Ta chọn được $q$ đủ lớn để $q+b>2017$ nên áp dụng lập luận trên khi thay $q$ bởi $q+b$, ta có $q+2 b$ cũng phải là số nguyên tố. Tương tự thì $q+k b$ là số nguyên tố với $k \in \mathbb{N}^*$. Chọn $k=q$ thì $q+q b=q(b+1)$ phải là số nguyên tố. Điều này chỉ xảy ra khi $b=0$. Do đó $f(n)=n$. Thử lại ta thấy đa thức này thoả mãn.
(b) Nếu $\operatorname{deg} f=k \geq 2$, ta có $f(2 q) \leq q+f(q)$ và hệ số bậc cao nhất là $a>0$.Viết lại bất đẳng thức trên thành:
$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \frac{f(2 q)}{(2 q)^k} \leq \frac{q}{(2 q)^k}+\frac{f(q)}{(2 q)^k}$
Cho $q \rightarrow+\infty$ thì vế trái tiến tới $a$ trong khi vế phải tiến tới 0 . Từ đó ta phải có $a=0$, vô lý. Vậy có tất cả 4 đa thức thoả mãn đề bài nên $|\mathcal{F}|=4$.
Bài 6. Với mỗi số tự nhiên $n$, ký hiệu $T(1+n, 3+n, 4+n)$ là tập hợp tất cả các bộ $(a, b, c)$ với $a, b, c$ là các số tự nhiên thoả mãn:
$\quad\quad\quad\quad\quad 1 \leq a \leq 1+n, a+1 \leq b \leq 3+n, b+1 \leq c \leq 4+n$
Gọi $a_n$ là số phần tử của $T(1+n, 3+n, 4+n)$.
a) Tính $a_4$.
b) Tìm tất cả số tự nhiên $n$ để $a_n$ chia hết cho 3 .
Lời giải . (a) Xét một bộ $(a, b, c)$ gồm các số nguyên dương thoả mãn điều kiện $1 \leq a<b<c \leq n+4$. Có tất cả $C_{n+4}^3$ bộ như thế. Xét các khả năng sau:
Số các bộ thoả mãn đề bài là $a_n=C_{n+4}^3-1$, dẫn đến $a_4=C_8^3-1=55$.
(b) Ta có biến đổi sau:
$\quad\quad\quad\quad a_n=\frac{(n+4)(n+3)(n+2)}{6}-1=\frac{n(n+1)(n+8)}{6}+3(n+1) .$
Vì $3 \mid 3(n+1)$ nên để $3 \mid a_n$ thì $9 \mid n(n+1)(n+8)$.
Không có hai số nào trong ba số $n, n+1, n+8$ có thể cùng chia hết cho 3 nên điều kiện trên chỉ xảy ra khi $9 \mid n$ hoặc $9 \mid n+1$ hoặc $9 \mid n+8$.
Vậy tất cả các số $n$ cần tìm để $3 \mid a_n$ là $n$ chia 9 dư $0,1,8$.
Nhận xét. Dưới đây là một số bài toán có liên quan về cấu trúc của tập hợp $T$ để bạn đọc thử sức.
1) Chứng minh rằng với các số nguyên dương $a_1<a_2, \ldots<a_n$ thì:
$\quad\quad\quad\quad \left|T\left(a_1, a_2, \ldots, a_n\right)\right|=\sum_{k=1}^{a_1}\left|T\left(a_2-k, \ldots, a_n-k\right)\right|$
2) Với hai bộ số $A=\left(a_1, a_2, \ldots, a_n\right)$ và $B=\left(b_1, b_2, \ldots, b_n\right)$, ta định nghĩa $A<B$ nếu tồn tại chỉ số $t$ để $a_t<b_t$ và $a_k=b_k$ với $t<k \leq n$. Giả sử rằng:
$\quad\quad\quad\quad\quad\quad \left|T\left(a_1, a_2, \ldots, a_n\right)\right|=\left|T\left(b_1, b_2, \ldots, b_n\right)\right|$
Liệu ta luôn có $\left|T\left(a_2, \ldots, a_n\right)\right|<\left|T\left(b_2, \ldots, b_n\right)\right|$ ?
Bài 7. An và Bình luân phiên nhau đánh dấu các ô vuông của hình vuông $101 \times 101$ ô. An là người bắt đầu. Một ô sẽ không thể được tô màu nếu trên cùng hàng với nó hoặc cùng cột với nó đã có ít nhất 2 ô được tô. Ai không đi được nữa sẽ thua. Hãy xác định ai là người có chiến thuật thắng.
Lời giải. Xin giới thiệu hai lời giải của bài toán
CÁCH 1. Để đơn giản, ta gọi hai người chơi là $A$ và $B$ thay vì An và Bình. Ta sẽ chứng minh rằng $B$ có chiến thuật để thắng. Điều này cũng đúng khi thay 101 bằng một số nguyên dương $n \geq 2$ bất kỳ.
Rõ ràng theo luật chơi thì có không quá $2 n$ ô được đánh dấu. Vì thế nên chiến thuật ở đây là $B$ sẽ tìm cách đánh được ô cuối cùng.
Chiến thuật là: người đi trước đánh ô nào thì người sau sẽ đánh một ô bất kỳ cùng dòng với nó sao cho số cột được đánh là nhiều nhất có thể.
Đặc điểm của chiến thuật này là:
Bằng cách đó, trong $n-1$ lượt đầu tiên, một khi $A$ còn đi được thì $B$ vẫn đi được vì vẫn luôn còn hàng trống và các cột vẫn chưa đầy 2 ô. Do đó, sau $n-1$ lượt của $A, B$, bảng còn lại sẽ có đặc điểm là:
Tổng số ô đã đánh là $2 n-2$ nên gọi $a, b$ lần lượt là số cột có 1 ô, 2 ô được đánh thì
$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad a+b=n$ và $a+2 b=2 n-2$.
Suy ra $a=2, b=n-2$, nghĩa là có đúng hai cột mà trên đó có 1 ô được đánh. Hai ô nằm ở vị trí giao giữa hai cột đó và dòng chưa được đánh là hai vị trí cuối cùng có thể đánh. $A, B$ thay phiên đánh vào hai ô đó và $B$ là người đánh cuối cùng nên chiến thắng.
CÁCH 2. Ta có nhận xét rằng
(1) Nếu ở lượt đầu tiên, An đánh vào ô $(1,51)$ giữa hàng 1 thì Bình sẽ đánh vào ô $(101,51)$ giữa hàng cuối. Khi đó, hai bạn sẽ không thể điền vào ô trung tâm nữa. Tiếp theo, mỗi khi An đánh dấu ô nào thì Bình sẽ đánh dấu vào ô đối xứng với ô đó qua tâm. Mỗi khi An điền được thì Bình cũng điền được, vậy Bình sẽ thắng.
(2) Nếu ở lượt đầu tiên, An đánh vào ô $(a, b)$ thì ta có thể đưa về nhận xét (1) bằng cách xây dựng một bảng tương ứng cùng kích thước nhưng hàng 1 và hàng $a$, cột 51 và cột $b$ đổi chỗ cho nhau. Khi đó, An đánh vào ô nào thì Bình sẽ đánh vào ô ở chỉ số hàng/cột tương ứng ở bảng đối chiếu; Bình sẽ đánh vào ô đối xứng như ở chiến lược (1) rồi đánh vào ô có cùng chỉ số hàng/cột ở bảng gốc. Dễ thấy rằng đánh dấu được của mỗi hàng và cột ở hai bảng là giống nhau.
Hình minh họa cho trường hợp $5 \times 5$ khi An đánh vào ô $(5,5)$ trong nước đi đầu tiên. Từ hai nhận xét trên, ta thấy Bình là người có chiến lược thắng trò chơi.
Bài 8. Đường tròn $(O)$ nội tiếp tứ giác $A B C D$ và tiếp xúc với các cạnh $A B, B C, C D, D A$ lần lượt tại $E, F, G, H$. Gọi $I, J$ là trung điểm của $A C, B D$. $I B, I D, J A, J C$ theo thứ tự cắt $E F, G H, H E, F G$ tại $M, N, P, Q$.
(a) Chứng minh rằng $I J, M N, P Q$ đồng quy tại điểm $S$.
(b) Các tia đối của các tia $J A, I B, J C, I D$ lần lượt cắt $(O)$ tại các điểm $A^{\prime}, B^{\prime}, C^{\prime}, D^{\prime} . A^{\prime} C^{\prime}, B^{\prime} D^{\prime}$ lần lượt cắt $P Q, M N$ tại $U, V$. Gọi $K$ là hình chiếu của $S$ trên $U V$. Chứng minh rằng $\angle A K B=\angle C K D$.
Lời giải. (a) Theo định lý đường thẳng Newton thì $I, J, O$ thẳng hàng. Ta sẽ chứng minh rằng $M N, P Q, I J$ đồng quy tại $O$.
Thật vậy, lấy điểm $K$ trên $H E$ sao cho $A K | B D$. Do $J$ là trung diểm $B D$ nên $A(K J, D B)=-1$. Chiếu tâm $A$ lên $H E$ thì $A(K Q, H E)=-1$ hay $(K Q, H E)=$ $-1$. Do đó $K$ nằm trên đường đối cực của $Q$ với $(O)$.
Lại có $H E$ là đường đối cực của $A$ với $(O)$ và $Q \in H E$ nên theo định lý La Hire, $A$ nằm trên đường đối cực của $Q$ với $(O)$. Do đó $A K$ là đường đối cực của $Q$ với $(O)$ nên $A K \perp O Q$. Từ đó mà $B D \perp O Q$.
Chứng minh tương tự thì $B D \perp O P$ nên $O, P, Q$ thẳng hàng. Cũng tương tự, ta có $O, M, N$ thẳng hàng. Vậy $M N, P Q, I J$ đồng quy tại $O$. Hệ quả là $S \equiv O$.
(b) Trước hết, ta chứng minh rằng $E F, G H, A C, P Q$ đồng quy tại $U$ và $H E, G F$, $B D, M N$ đồng quy tại $V$. Gọi $E F$ cắt $A C$ tại $U^{\prime}$. Áp dụng định lý Menelaus cho tam giác $A B C$, ta có:
$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \frac{F C}{F B} \cdot \frac{E B}{E A} \cdot \frac{U^{\prime} A}{U^{\prime} C}=1 .$
Do $A H=A E, B E=B F, C F=C G, D G=D H$ nên ta viết lại thành:
$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \frac{G C}{G D} \cdot \frac{H D}{H A} \cdot \frac{U^{\prime} A}{U^{\prime} C}=1$
Theo định lý Menelaus cho tam giác $A D C$ thì $U^{\prime}, G, H$ thẳng hàng. Do đó $E F, G H, A C$ đồng quy tại $U^{\prime}$. Chứng minh tương tự, ta có $H E, G F, B D$ đồng quy tại $V^{\prime}$.
Mặt khác, ta có tỉ số kép sau:
$\left(U^{\prime} M, E F\right)=B\left(U^{\prime} M, E F\right)=\left(U^{\prime} I, A C\right)=D\left(U^{\prime} N, H G\right)=\left(U^{\prime} N, H G\right) .$
Từ đây thì $H E, M N, F G$ đồng quy tại $V^{\prime} \in B D$. Do $V^{\prime}$ nằm trên $E H, F G$ là các đối của $A, C$ với $(O)$ nên theo định lý La Hire, $A C$ là đường đối cực của $V^{\prime}$ với $(O)$. Tương tự, $E F, A C, P Q, G H$ đồng quy tại $U^{\prime}$ và $B D$ là đối cực của $U^{\prime}$ với $(O)$.
Gọi $S^{\prime}$ là giao diểm của $A C, B D$ thì $S^{\prime}$ là giao diểm hai đường đối cực của $U^{\prime}, V^{\prime}$ với $(O)$, do đó $U^{\prime} V^{\prime}$ là đường đối cực của $S^{\prime}$ với $(O)$. Hơn nữa $E F$ cắt $G H$ tại $U^{\prime}$ và $E H$ cắt $F G$ tại $V^{\prime}$ nên $E G, F H$ đi qua $S^{\prime}$.
Do tính chất đường đối cực, $O S^{\prime} \perp U V$ hay $O, S^{\prime}, K$ thẳng hàng. Gọi $U^{\prime} C^{\prime}$ cắt $(O)$ tại $A_1$ và cắt $B D$ tại $A_2$. Do $B D$ là đường đối cực của $U^{\prime}$ với $(O)$ nên
$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \left(U^{\prime} A_2, A_1 C^{\prime}\right)=-1=\left(U^{\prime} S, A C\right) .$
Khi đó $S A_2, A A_1, C C^{\prime}$ đồng quy. Lại có $C C^{\prime}$ cắt $S A_2$ tại $J$ và $A, J, A^{\prime}$ thẳng hàng nên $A_1 \equiv A^{\prime}$. Từ đó $A^{\prime} C^{\prime}$ qua $U^{\prime} \in P Q$, dẫn đến $U^{\prime} \equiv U$. Tương tự thì $V^{\prime} \equiv V$. Điều này nghĩa là $E F, G H, A C, P Q$ đồng quy tại $U$ và $H E, G F, B D, M N$ đồng quy tại $V$. Để ý rằng $\angle U K O=90^{\circ}$ và $\left(U S^{\prime}, A C\right)=-1$ nên $K S$ là phân giác $\angle A K C$. Tương tự, $K O$ là phân giác $\angle B K D$. Vậy nên ta được
$\quad\quad\quad\quad \angle A K B=\angle A K O+\angle B K O=\angle C K O+\angle D K O=\angle C K D .$
Bài toán kết thúc.
