1. Phương pháp song ánh trong bài toán tổ hợp
Trở ngại lớn nhất khi giải một bài toán tổ hợp là xác định hướng đi. Rõ ràng để có khả năng định hướng tốt thì việc rèn luyện các phương pháp tiếp cận là rất cần thiết. Phương pháp này dựa trên kết quả hiển nhiên sau: "Nếu có một song ánh đi từ một tập hữu hạn \(X\) tới một tập hữu hạn \(Y\) thì lực lượng (tức số phần tử) của \(X\) và \(Y\) bằng nhau".
2. Các bài toán ứng dụng
Bài toán 1 (Vô địch Liên Xô). Có một nhóm người mà trong đó, mỗi cặp không quen nhau có đúng hai người quen chung, còn mỗi cặp không quen nhau thì không có người quen chung. Chứng minh rằng số người quen của mỗi người là như nhau.
Lời giải. Giả sử \(a\) quen \(b\) và tập các người quen của \(a\) và \(b\) (không kể \(a, b\)) là \(A\) và \(B\). Mỗi người \(a'\) thuộc \(A\) sẽ quen với duy nhất một người thuộc \(B\) (do \(a'\) và \(b\) không quen nhau, hơn nữa họ đã có một người quen chung là \(a\)). Tương tự, mỗi người thuộc \(B\) cũng quen với duy nhất một người thuộc \(A\). Vậy tồn tại một song ánh đi từ \(A\) tới \(B\), tức a và \(b\) có số người quen bằng nhau.
Nếu \(a\) không quen \(b\) thì tồn tại \(c\) quen cả \(a\) và \(b\), do đó số người quen của \(a\) và \(b\) bằng nhau do cùng bằng số người quen của \(c\).
Bài toán 2 (Trung Quốc - 1997). Trong các xâu nhị phân có độ dài \(n\), gọi \(a_n\) là số các xâu không chứa quá 3 số liên tiếp \(0, 1, 0\) và \(b_n\) là số các xâu không chứa 4 số liên tiếp \(0, 0, 1, 1\) hoặc \(1, 1, 0, 0\). Chứng minh rằng: \[b_{n+1} = 2a_n.\]
Lời giải. Ta gọi một xâu thuộc loại \(A\) nếu nó không chứa 3 số liên tiếp \(0, 1, 0\) và gọi một xâu thuộc loại \(B\) nếu nó không chứa 4 số hạng liên tiếp \(0, 0, 1, 1\) hoặc \(1, 1, 0, 0\).
Với mỗi xâu \(X = (x_1, x_2, \dots, x_n)\), ta xây dựng \(f(X) = (y_1, y_2, \dots, y_{n+1})\) như sau: \(y_1 = 0\), \(y_k \equiv x_1 + x_2 + \dots + x_{k-1} \pmod 2\). Rõ ràng \(X\) chứa 3 số liên tiếp \(0, 1, 0\) khi và chỉ khi \(f(X)\) chứa 4 số hạng liên tiếp \(0, 0, 1, 1\) hoặc \(1, 1, 0, 0\), tức là \(X\) thuộc loại \(A\) khi và chỉ khi \(f(X)\) thuộc \(B\).
Vậy \(f\) là một song ánh đi từ tập các xâu loại \(A\) độ dài \(n\) đến tập các xâu loại \(B\) độ dài \(n+1\) mà bắt đầu bằng \(0\). Nhưng từ mỗi xâu \(X \in B\) ta nhận được một xâu \(\overline{X} \in B\) bằng cách đổi các phần tử của \(X\) theo quy tắc \(1 \to 0, 0 \to 1\) nên số các xâu loại \(B\) có độ dài \(n+1\) gấp đôi số các xâu loại \(B\) độ dài \(n+1\) mà bắt đầu bằng số \(0\). Từ đó ta có đpcm.
Bài toán 3 (Vô địch Ucraina - 1996). Gọi \(M\) là các số nguyên dương viết trong hệ thập phân có \(2n\) chữ số, trong đó có \(n\) chữ số 1 và \(n\) chữ số 2. Gọi \(N\) là số tất cả các số viết trong hệ thập phân có \(n\) chữ số, trong đó chỉ có chữ số 1, 2, 3, 4 và số chữ số 1 bằng số chữ số 2. Chứng minh rằng \(M = N\).
Lời giải 1. Với mỗi số có \(n\) chữ số gồm các chữ số 1, 2, 3, 4 và số chữ số 1 bằng số chữ số 2, ta "nhân đôi" thành số có \(2n\) chữ số theo quy tắc sau: đầu tiên, hai phiên bản của số này được viết kế nhau thành số có hai chữ số, sau đó các chữ số 3 ở \(n\) chữ số đầu và các chữ số 4 ở \(n\) chữ số sau được đổi thành chữ số 1, các chữ số 3 ở \(n\) chữ số sau và các chữ số 4 ở \(n\) chữ số đầu được đổi thành chữ số 2. Ví dụ: \(1234142 \to 12341421234142 \to 12121221221112\).
Như thế, ta thu được một số có đúng \(n\) chữ số 1 và \(n\) chữ số 2. Rõ ràng đây là một đơn ánh. Để chứng minh đây là một song ánh, ta xây dựng ánh xạ ngược như sau: với mỗi số có \(n\) chữ số 1 và \(n\) chữ số 2, ta cắt \(n\) chữ số đầu và \(n\) chữ số cuối rồi cộng chúng theo cột với quy tắc: \(1 + 1 = 1\), \(2 + 2 = 2\), \(1 + 2 = 4\), \(2 + 1 = 3\), và ta thu được một số có \(n\) chữ số gồm các chữ số 1, 2, 3, 4 với số chữ số 1 bằng số chữ số 2. Ví dụ \(12121221221112 \to 1234142\) như sau:
\[ \begin{array}{c} 1212122 \\ 1221112 \\ \hline 1234142 \end{array} \]Như thế song ánh giữa hai tập hợp đã được thiết lập và ta có \(M = N\).
Lời giải 2. \(\forall k \in S = \{0, 1, \dots, n\}\), ta thực hiện 2 lần (độc lập với nhau) việc đánh dấu \(k\) trong \(n\) vị trí trên một hàng. Sau đó, ở mỗi vị trí ta ghi: chữ số 3 nếu được đánh dấu 3 lần, chữ số 4 nếu không được đánh dấu lần nào, chữ số 1 nếu chỉ được đánh dấu lần đầu và chữ số 2 nếu chỉ được đánh dấu lần sau.
Rõ ràng khi cho \(k\) chạy trên \(S\) thì số tất cả các số thu được chính là \(N\). Hơn nữa, \(\forall k \in S\) thì có thể xem số cách đánh dấu lần đầu là số cách chọn \(k\) trong số \(n\) vị trí, còn số cách đánh dấu lần sau là số cách chọn \(n - k\) vị trí trong \(n\) vị trí. Do đó tổng số cách đánh dấu khi \(k\) chạy trên \(S\) đúng bằng số cách chọn \(n\) phần tử từ \(2n\) phần tử (tức là \(C_{2n}^n\)), và số này chính là \(M\). Vậy ta có điều phải chứng minh.