Bài học

Đếm bằng phần bù và song ánh

Mục tiêu bài học

Sau bài này, em có thể nhận ra cấu hình bù dễ đếm và chứng minh một phép mã hóa là song ánh. Năng lực cần đạt không dừng ở việc nhớ một công thức: em phải nhận ra tín hiệu của bài toán, giải thích vì sao chọn phương pháp và trình bày một chuỗi suy luận có thể kiểm tra được.

Kiến thức cần có

Quy tắc cộng–nhân, hoán vị, chỉnh hợp, tổ hợp và xác suất cổ điển.

Chuẩn HSG so với bài chuẩn

Bài chuẩn thường áp dụng trực tiếp một công thức đếm hoặc một tỉ số xác suất. Mở rộng dành cho HSG: bài HSG yêu cầu đổi mô hình bằng song ánh, đếm đôi, Dirichlet, cây xác suất hoặc Bayes và phải kiểm soát điều kiện của từng bước. Nội dung mở rộng được giới thiệu từng bước trong bài; em không cần biết trước ngoài các kiến thức đã nêu ở trên.

Câu hỏi mở đầu

Có bao nhiêu xâu nhị phân dài 8 chứa ít nhất một cặp 11 liên tiếp? Hãy dừng lại một phút và viết ra hai điều: dữ kiện nào đang khống chế bài toán, và trường hợp đặc biệt nào đáng thử trước. Câu trả lời ban đầu chưa cần hoàn chỉnh; mục đích là tập thói quen nhìn cấu trúc trước khi tính.

Công cụ và cách phát hiện

Phần bù hiệu quả khi điều kiện “ít nhất một” có nhiều giao nhau nhưng điều kiện “không có” có thể mô tả gọn. Song ánh hiệu quả khi mỗi cấu hình khó được mã hóa thành đúng một đối tượng quen thuộc và có phép khôi phục duy nhất. Khi đọc đề, ta không hỏi ngay “dùng công thức nào”, mà hỏi “điều kiện nào phải được tận dụng hết”. Một lời giải HSG tốt thường có ba lớp: nhận diện cấu trúc, chọn phép biến đổi bảo toàn điều kiện, rồi kiểm tra trường hợp biên hoặc dấu bằng. Ba lớp này phải xuất hiện rõ trong bài viết, không được giấu sau một chuỗi tính toán.

Cách làm an toàn là dự đoán kết quả bằng một trường hợp cân bằng hoặc đối xứng, sau đó thử biến đổi ngược từ đích. Nếu phép biến đổi tạo ra điều kiện mới, phải ghi điều kiện ấy ngay tại chỗ. Nếu dùng một bất đẳng thức, phải nêu điều kiện áp dụng và trường hợp đẳng thức. Nếu giải phương trình, mọi nghiệm nhận được sau bình phương, đặt ẩn hoặc đổi biểu diễn đều phải thử lại. Đây là phần trình bày thường quyết định điểm số trong bài HSG.

Một song ánh chưa hoàn chỉnh nếu chưa chỉ ra cách khôi phục.

Ví dụ mẫu thứ nhất

Ví dụ

Ví dụ 1 — Xâu có hai số 1 kề nhau

1
Đếm xâu nhị phân dài 8 chứa ít nhất một cặp 11 liên tiếp.
2
Đề không chỉ định sẵn phép biến đổi. Muốn đi tiếp, ta phải đọc điều kiện, dự đoán trường hợp đẳng thức hoặc cấu trúc nghiệm, rồi mới chọn công cụ. Nếu biến đổi trước khi có định hướng, lời giải rất dễ dài hoặc mất điều kiện.
3
Đếm phần bù là các xâu không có hai số 1 kề nhau.
4
Gọi $a_n$ là số xâu dài n không có 11. Xâu hợp lệ kết thúc bằng 0 sau một xâu dài $n-1$ , hoặc kết thúc bằng 10 sau một xâu dài $n-2$ , nên $a_n=a_{n-1}+a_{n-2}$ , với $a_1=2,a_2=3$ . Suy ra $a_8=55$ . Tổng có $2^8=256$ xâu, nên số cần tìm là $256-55=201$ .
Gọi $a_n$ là số xâu dài n không có 11. Xâu hợp lệ kết thúc bằng 0 sau một xâu dài $n-1$, hoặc kết thúc bằng 10 sau một xâu dài $n-2$, nên $a_n=a_{n-1}+a_{n-2}$, với $a_1=2,a_2=3$. Suy ra $a_8=55$. Tổng có $2^8=256$ xâu, nên số cần tìm là $256-55=201$.
5
Sau khi có kết quả, cần đối chiếu lại điều kiện và trường hợp xảy ra dấu bằng hoặc nghiệm đặc biệt. Không cộng số xâu có 11 ở từng vị trí vì một xâu có thể chứa nhiều cặp.
6
Chứng minh tổng quát số xâu bù là $F_{n+2}$ .
Chứng minh tổng quát số xâu bù là $F_{n+2}$.

Ví dụ mẫu thứ hai

Ví dụ

Ví dụ 2 — Chọn không kề nhau

1
Chọn 4 số từ ${1,2,ldots,10}$ sao cho không có hai số liên tiếp.
Chọn 4 số từ ${1,2,ldots,10}$ sao cho không có hai số liên tiếp.
2
Đề không chỉ định sẵn phép biến đổi. Muốn đi tiếp, ta phải đọc điều kiện, dự đoán trường hợp đẳng thức hoặc cấu trúc nghiệm, rồi mới chọn công cụ. Nếu biến đổi trước khi có định hướng, lời giải rất dễ dài hoặc mất điều kiện.
3
Nén ba khoảng trống bắt buộc bằng $b_i=a_i-(i-1)$ .
Nén ba khoảng trống bắt buộc bằng $b_i=a_i-(i-1)$.
4
Viết $a_1<a_2<a_3<a_4$ và $a_{i+1}ge a_i+2$ . Đặt $b_i=a_i-(i-1)$ . Khi đó $1le b_1<b_2<b_3<b_4le7$ . Phép ngược là $a_i=b_i+i-1$ , nên đây là song ánh với các tập con 4 phần tử của ${1,ldots,7}$ . Vậy có $inom74=35$ cách.
Viết $a_1<a_2<a_3<a_4$ và $a_{i+1}ge a_i+2$. Đặt $b_i=a_i-(i-1)$. Khi đó $1le b_1<b_2<b_3<b_4le7$. Phép ngược là $a_i=b_i+i-1$, nên đây là song ánh với các tập con 4 phần tử của ${1,ldots,7}$. Vậy có $inom74=35$ cách.
5
Sau khi có kết quả, cần đối chiếu lại điều kiện và trường hợp xảy ra dấu bằng hoặc nghiệm đặc biệt. Không nén hai đầu vì chỉ các khoảng giữa mới bắt buộc.
6
Tổng quát hóa thành $inom{n-k+1}{k}$ .

Tự kiểm chứng lời giải

Trước khi chuyển sang luyện tập, em hãy kiểm tra lại hai ví dụ theo bốn câu hỏi. Một: mọi phép chia, căn, logarit hoặc ẩn phụ có kèm điều kiện chưa. Hai: kết quả trung gian có đúng chiều và đúng miền không. Ba: trường hợp dấu bằng hoặc nghiệm biên có thật sự thỏa đề gốc không. Bốn: kết luận cuối đã trả lời đủ điều đề hỏi chưa. Với Điều kiện “ít nhất một” tạo nhiều phần giao, một cách kiểm tra tốt là thay một giá trị đơn giản vào cả biểu thức ban đầu lẫn biểu thức sau biến đổi; hai kết quả phải khớp. Cách thử số không thay cho chứng minh, nhưng nó phát hiện nhanh lỗi dấu, lỗi hệ số và nghiệm ngoại lai. Sau đó, hãy thử kể lại ý tưởng bằng ba câu ngắn: tín hiệu nào xuất hiện, công cụ nào được chọn, và vì sao điều kiện của đề làm công cụ ấy trở nên sắc. Nếu ba câu này rõ ràng, em đã nắm phương pháp chứ không chỉ chép lại phép tính.

Một vòng kiểm tra độc lập nữa là đổi cách biểu diễn: với đại số, thử phân tích hoặc khai triển ngược; với hình học, đối chiếu bằng tọa độ, độ dài hay thể tích; với xác suất, cộng các trường hợp để kiểm tra tổng; với dãy và giải tích, thế vài giá trị hoặc so giới hạn biên. Em cần ghi rõ phép kiểm tra đã xác nhận điều gì và điều gì vẫn phải dựa vào chứng minh. Thói quen này giúp phân biệt một đáp số có vẻ hợp lý với một lời giải thật sự kín kẽ.

Luyện tập có hướng dẫn

Ở ba câu vừa rồi, điều quan trọng hơn đáp số là lý do chọn bước đầu. Em nên tự nói thành lời: “Tôi chọn Điều kiện “ít nhất một” tạo nhiều phần giao vì dữ kiện của đề tạo đúng cấu trúc cần thiết”. Nếu không nói được câu đó, hãy quay lại sơ đồ phương pháp trước khi làm phần độc lập.

Luyện tập độc lập

Lỗi thường gặp

Nhìn thấy dữ kiện rồi nhân hoặc cộng xác suất ngay mà chưa dựng mô hình

Kiểm tra nhanh

Tóm tắt và nối bài

Điều cần giữ lại là: chỉ dùng phần bù khi đếm phần tránh dễ hơn và luôn viết phép nghịch đảo của song ánh. Khi tự luyện, em hãy ghi riêng “tín hiệu nhận dạng” ở lề bài giải; sau vài bài, việc chọn công cụ sẽ nhanh hơn hẳn. Bài sau đếm cùng một tập theo hai cách để tạo đẳng thức và bất biến.