Nguyễn Thị Ngọc Ánh<br />
<br />
Tạp chí KHOA HỌC & CÔNG NGHỆ<br />
<br />
128(14): 127 - 131<br />
<br />
HƯỚNG DẪN HỌC SINH TRUNG HỌC PHỔ THÔNG KHÁ GIỎI SỬ DỤNG<br />
PHƯƠNG PHÁP SONG ÁNH GIẢI MỘT SỐ BÀI TOÁN ĐẾM<br />
Nguyễn Thị Ngọc Ánh*<br />
Trường THPT Chuyên Thái Nguyên<br />
<br />
TÓM TẮT<br />
Phương pháp song ánh ( PPSA) là một phương pháp hay để giải một số bài toán đếm. Tuy nhiên, ở<br />
nước ta hiện nay có ít bài viết về phương pháp này và chưa tác giả nào đề cập đến việc dạy phương<br />
pháp này như thế nào cho đối tượng học sinh (HS) khá giỏi trung học phổ thông (THPT). Chúng<br />
tôi xin chia sẻ kinh nghiệm dạy các khái niệm ánh xạ (AX), đơn ánh (ĐA), toàn ánh (TA), song<br />
ánh (SA). Đồng thời, phân tích một số ví dụ về vận dụng PPSA vào giải một số bài toán đếm để<br />
giúp HS hiểu rõ hơn về phương pháp này.<br />
Từ khóa: Phương pháp song ánh, bài toán đếm.<br />
<br />
MỞ ĐẦU*<br />
<br />
NỘI DUNG NGHIÊN CỨU<br />
<br />
Năm 1992, các tác giả Chen Chuan-Chong và<br />
Koh Khee-Meng đã viết về Nguyên lí Đơn<br />
ánh và Nguyên lí Song ánh trong cuốn<br />
“Những nguyên lí và kĩ thuật trong Tổ hợp”.<br />
Với kí hiệu X là số phần tử của tập hợp X,<br />
nội dung của hai nguyên lí này được tác giả<br />
nêu ra như sau:<br />
<br />
Dạy khái niệm AX, ĐA, TA, SA cho HS<br />
khá giỏi THPT:<br />
<br />
Nguyên lí Đơn ánh (The Injection Principle):<br />
Cho A và B là hai tập hợp hữu hạn. Nếu có<br />
một đơn ánh từ A đến B, thì A B .<br />
Nguyên lí Song ánh (The Bijection<br />
Principle): Cho A và B là hai tập hợp hữu<br />
hạn. Nếu có một song ánh từ A đến B, thì<br />
A B .<br />
Phương pháp vận dụng hai nguyên lí trên vào<br />
giải toán gọi là PPSA [1, tr - 230]. Phương<br />
pháp này đã được đề cập đến trong các tài<br />
liệu: [1], [3], [4], [5], [7]. Tuy nhiên, chưa tác<br />
giả nào đề cập đến việc phải dạy PPSA như<br />
thế nào cho HS khá giỏi THPT. Qua bài viết<br />
này, chúng tôi xin chia sẻ kinh nghiệm vận<br />
dụng PPSA ở trường THPT với đối tượng là<br />
HS khá giỏi. Để vận dụng phương pháp này<br />
hiệu quả trước tiên chúng ta phải giúp HS<br />
phân biệt được các khái niệm AX, ĐA, TA,<br />
SA, sau đó hướng dẫn các em vận dụng tính<br />
chất của các AX vừa học vào các ví dụ nhằm<br />
từng bước hình thành PPSA.<br />
*<br />
<br />
Email: anhtoan416@gmail.com<br />
<br />
Khái niệm AX, ĐA, TA, SA<br />
a. Ánh xạ f từ tập hợp X vào tập hợp Y (ký<br />
hiệu f: X Y) là một quy tắc cho tương ứng<br />
mỗi phần tử x X với một phần tử xác định<br />
y Y, phần tử y gọi là ảnh của phần tử x, ký<br />
hiệu y = f(x).<br />
Với mỗi tập A X: f(A) =<br />
gọi là ảnh của tập A.<br />
<br />
f ( x)<br />
<br />
x A<br />
<br />
<br />
<br />
b. TA là AX từ X vào Y trong đó f(X) = Y.<br />
c. ĐA là AX từ X vào Y thỏa mãn:<br />
x1 , x2 X : x1 x2 f ( x1 ) f ( x2 ) .<br />
d. SA là AX vừa là ĐA, vừa là TA.<br />
Dạy các khái niệm AX, ĐA, TA, SA cho HS<br />
khá giỏi THPT<br />
Trong thực tế giảng dạy chúng tôi nhận thấy<br />
HS thường khó phân biệt các khái niệm: AX,<br />
ĐA, TA, SA . Do đó, chúng tôi xin đề xuất<br />
một phương án dạy bốn khái niệm trên thông<br />
qua các hoạt động (HĐ) như sau [2] :<br />
HĐ1: Giáo viên (GV) vẽ hai vòng tròn rời<br />
nhau. GV gọi 3 HS đứng vào vòng 1 và qui<br />
ước đây là tập hợp các con. Gọi 4 HS nữ<br />
đứng vào vòng 2 và qui ước đây là tập hợp<br />
các mẹ đẻ của các con ở vòng kia. Tiếp đó,<br />
GV dùng 3 sợi dây để nối tương ứng giữa con<br />
và mẹ để tạo ra mô hình (MH) 1.<br />
127<br />
<br />
Nguyễn Thị Ngọc Ánh<br />
<br />
Tạp chí KHOA HỌC & CÔNG NGHỆ<br />
<br />
128(14): 127 - 131<br />
<br />
M1<br />
<br />
C1<br />
C2<br />
<br />
M2<br />
<br />
M4<br />
<br />
M3<br />
<br />
C3<br />
<br />
Mô hình 1<br />
<br />
HĐ 2: GV đưa ra khái niệm AX, minh họa thông qua MH1 và phân tích:<br />
Tập X : tập các con. Tập Y: tập các mẹ đẻ.<br />
Vậy tương ứng mỗi x X với một phần tử xác định y Y được thể hiện ở đây là tương ứng mỗi<br />
con thuộc tập các con có duy nhất một mẹ đẻ ( biểu thị bằng sợi dây nối), chú ý là không con nào<br />
‘đứng bơ vơ’ vì không có mẹ tương ứng. Đây là điểm cần nhớ của khái niệm AX.<br />
Hđ 3: GV cùng HS lần lượt xây dựng các MH 2, MH 3 và yêu cầu xác định xem MH nào thỏa<br />
mãn khái niệm AX.<br />
<br />
C3<br />
<br />
C1<br />
<br />
M1<br />
<br />
C2<br />
<br />
M2<br />
<br />
Mô hình 2<br />
<br />
C1<br />
<br />
M1<br />
C2<br />
<br />
M2<br />
<br />
C3<br />
<br />
M3<br />
Mô hình 3<br />
<br />
HS trả lời MH2 không phải là AX vì có con<br />
C3 ‘đứng bơ vơ’, MH3 thỏa mãn vì tuy có C2<br />
và C3 chung một mẹ nhưng mỗi con vẫn có<br />
duy nhất một mẹ.<br />
HĐ 4: GV vẽ MH1, MH3 lên bảng và thông<br />
báo cho HS biết MH1 thỏa mãn điều kiện cứ<br />
hai con khác nhau thì có hai mẹ khác nhau<br />
nên là MH của một ĐA. Nhưng MH3 không<br />
thỏa mãn khái niệm ĐA vì con C2 và C3<br />
chung mẹ M2. GV yêu cầu HS thử nêu khái<br />
niệm ĐA và chỉnh sửa lại khi phát biểu của<br />
HS chưa chính xác.<br />
<br />
128<br />
<br />
HĐ 5: GV thông báo TA là AX thỏa mãn<br />
không có mẹ nào trong tập các mẹ đẻ ‘đứng<br />
bơ vơ’ và yêu cầu HS xây dựng một số MH<br />
minh họa. Từ đó, GV hướng dẫn HS nhớ khái<br />
niệm TA.<br />
HĐ6: Cuối cùng GV đưa ra khái niệm SA và<br />
yêu cầu HS xây dựng MH minh họa.<br />
Sau khi HS đã nắm được bốn khái niệm AX,<br />
ĐA, TA, SA. GV và HS cùng tìm thêm các ví<br />
dụ và phản ví dụ trong toán học và trong thực<br />
tế minh họa cho các khái niệm này. Đồng<br />
thời, giúp các em nêu ra được các tính chất<br />
của các khái niệm đó.<br />
Áp dụng PPSA vào giải một số bài toán đếm<br />
<br />
Nguyễn Thị Ngọc Ánh<br />
<br />
Tạp chí KHOA HỌC & CÔNG NGHỆ<br />
<br />
128(14): 127 - 131<br />
<br />
PPSA được coi là một kỹ thuật đếm nâng cao<br />
được vận dụng trong giải toán tổ hợp. Ý nghĩa<br />
của phương pháp là thay thế cho việc đếm số<br />
phần tử của một tập hợp A nhất định, ta đi<br />
đếm số phần tử của một tập hợp B có cùng số<br />
phần tử với tập hợp A. Số phần tử của tập hợp<br />
B là dễ đếm. Để có được kết quả này ta cần<br />
chứng minh có một SA giữa hai tập hợp A và<br />
B. Muốn có một bất đẳng thức liên quan đến<br />
số phần tử của hai tập hợp, ta xây dựng một<br />
đơn ánh giữa hai tập hợp đó. Khi hướng dẫn<br />
HS vận dụng PPSA vào giải một bài toán<br />
đếm, chúng tôi thường hướng dẫn các em<br />
theo bốn bước sau:<br />
<br />
bằng 1. Tập hợp Y là tập các dãy nhị phân<br />
nói trên.<br />
<br />
Bước 1: Dựa vào giả thiết, xác định xem cần<br />
xây dựng một đơn ánh hay một song ánh.<br />
<br />
Một đường đi như thế gồm (m + n) đoạn (mỗi<br />
đoạn là một cạnh ô vuông). Tại mỗi đoạn chỉ<br />
được chọn một trong hai giá trị đi lên (ta mã<br />
hóa là 1) hay sang phải (ta mã hóa là 0). Số<br />
đoạn đi lên đúng bằng n và số đoạn sang phải<br />
đúng bằng m. Như vậy, có một song ánh giữ<br />
tập hợp A các đường đi thỏa mãn yêu cầu bài<br />
toán với tập hợp B các dãy nhị phân có cùng<br />
độ dài (m + n). Trong mỗi dãy nhị phân đó có<br />
đúng n thành phần bằng 1, m thành thành<br />
bằng 0.<br />
<br />
Bước 2: Tìm hai tập hợp X, Y tương ứng<br />
trong ánh xạ cần xây dựng.<br />
Bước 3: Chỉ ra cách xây dựng ánh xạ từ X<br />
tới Y.<br />
Bước 4: Trình bày lời giải.<br />
Ví dụ 1:<br />
Cho một lưới gồm các ô vuông. Các nút được<br />
đánh số từ 0 đến m theo chiều từ trái sang<br />
phải và từ 0 đến n theo chiều từ dưới lên trên.<br />
Hỏi có bao nhiêu đường đi khác nhau từ nút<br />
(0 ; 0) đến nút (m, n) nếu chỉ cho phép đi trên<br />
cạnh các ô vuông theo chiều từ trái sang phải<br />
hoặc từ dưới lên trên.<br />
<br />
Giải:<br />
n<br />
<br />
0<br />
<br />
(m,n)<br />
m,n<br />
<br />
1<br />
0<br />
<br />
1<br />
0<br />
<br />
1<br />
0<br />
<br />
0<br />
<br />
1<br />
<br />
m<br />
<br />
(0,0)<br />
<br />
Phân tích: Đây là một bài toán đếm nên có<br />
thể vận dụng Nguyên lí Song ánh. Ta cần xây<br />
dựng một song ánh giữa tập hợp X các đường<br />
đi thỏa mãn với một tập hợp Y nào đó.<br />
<br />
Dễ thấy B C m n A C m n . Vậy số<br />
n<br />
đường đi cần tìm là Cm n<br />
Ví dụ 2: [ Balkan 1997]<br />
Lấy m và n là số tự nhiên lớn hơn 1. Gọi S tập<br />
hợp có n phần tử. Lấy A1, A2, A3,…,Am là<br />
những tập con của S. Giả sử rằng, cứ 2 phần<br />
tử bất kỳ x, y thuộc S đều có 1 tập hợp A i<br />
( i 1, m ) thỏa mãn điều kiện: nếu x Ai thì<br />
y Ai còn nếu x <br />
A thì y Ai. Chứng<br />
m i<br />
n<br />
<br />
2<br />
minh rằng:<br />
.<br />
<br />
Tìm tập Y: Ta thấy các đường đi thỏa mãn<br />
đều có độ dài (m + n) vì có n đoạn đi lên và<br />
m đoạn đi sang ngang. Sự khác nhau giữa các<br />
đường đi chỉ là sự sắp xếp thứ tự giữa các<br />
đoạn đi lên và các đoạn đi ngang. Đây là một<br />
bài toán có 2 khả năng cơ bản. Ta có thể mã<br />
hóa mỗi đoạn đi lên bởi số 1, mỗi đoạn đi<br />
ngang bởi số 0. Khi đó, mỗi đường đi thỏa<br />
mãn tương ứng với một dãy nhị phân có độ<br />
dài (m + n), trong đó, có đúng n thành phần<br />
<br />
Phân tích: Bài toán yêu cầu chứng minh một<br />
bất đẳng thức nên có thể sử dụng Nguyên lí<br />
Đơn ánh. Tập S có n phần tử nên ta sẽ tìm<br />
một đơn ánh từ S tớt tập T nào đó. Tập T có<br />
2 m phần tử. Bài toán có hai quan hệ “thuộc”<br />
và “không thuộc” nên có thể đưa về bài toán<br />
dãy nhị phân. Ta biết, tập hợp các dãy nhị<br />
m<br />
phân có độ dài m thì có 2 phần tử ( do tại<br />
mỗi vị trí chỉ có thể chọn là 1 hoặc 0). Tập<br />
T phải liên quan đến m tập nêu trong đề<br />
<br />
n<br />
<br />
n<br />
<br />
129<br />
<br />
Nguyễn Thị Ngọc Ánh<br />
<br />
Tạp chí KHOA HỌC & CÔNG NGHỆ<br />
<br />
128(14): 127 - 131<br />
<br />
bài. Ta có cách xây dựng đơn ánh như<br />
trong lời giải sau:<br />
Giải:<br />
<br />
Giải :<br />
<br />
Mỗi phần tử x của S ta cho tương ứng với một<br />
dãy nhị phân f x x1 , x2 ,..., xm , với<br />
xi 1 nếu xi Ai và xi 0 nếu<br />
xi Ai . Ta có ánh xạ: f: S T =<br />
x1 , x2 ,..., xm xi 0;1 .<br />
<br />
<br />
<br />
<br />
<br />
Từ<br />
<br />
<br />
<br />
giả<br />
<br />
thiết<br />
<br />
<br />
<br />
<br />
ta<br />
<br />
có,<br />
<br />
nếu<br />
<br />
x y f ( x) f ( y ) .Vậy f là một đơn<br />
<br />
ánh nên S T . Mỗi phần tử của T là<br />
một dãy nhị phân có độ dài m nên<br />
T 2 m . Vậy n 2 m .<br />
Ví dụ 3: Để xem một buổi biểu diễn xiếc,<br />
mỗi người phải mua một vé vào giá 1 USD.<br />
Mỗi khán giả chỉ được phép mua một vé. Mọi<br />
người đến mua vé đứng xếp thành một hàng<br />
dọc trước cửa bán vé. Mỗi người chỉ mang<br />
đúng một tờ 1 USD hoặc đúng 1 tờ 2 USD.<br />
Người bán vé quên không mang theo tiền. Giả<br />
sử có n người mang tờ 1 USD và m người<br />
mang tờ 2 USD ( m n ). Tìm số cách xếp<br />
hàng sao cho người có tờ 1 USD thì được<br />
nhận ngay vé, người có tờ 2 USD thì khi đến<br />
lượt của mình được nhận ngay vé và một tờ 1<br />
USD trả lại ?<br />
Phân tích: Đây là một bài toán hay nhưng<br />
khó đối với đa số HS phổ thông. PPSA được<br />
vận dụng rất rõ nét trong cách giải bài toán.<br />
Định hướng ban đầu là sử dụng Nguyên lí<br />
Song ánh vì đây là một bài toán đếm. Mỗi<br />
cách xếp hàng bất kì của (m + n) khán giả nói<br />
trên ta gọi là một véc tơ. Tập hợp các véc tơ<br />
này ta kí hiệu là X. Một véc tơ gọi là tốt nếu<br />
tương ứng với cách xếp hàng thỏa mãn yêu<br />
cầu bài toán. Các véc tơ còn lại gọi là các véc<br />
tơ xấu. Ta chứng minh có một song ánh từ<br />
tập A các véc tơ xấu đến tập B các véc tơ rất<br />
xấu (đặc điểm cụ thể của B xem trong lời giải)<br />
theo hai chiều: ứng với mỗi véc tơ thuộc A có<br />
duy nhất một véc tơ thuộc B và ngược lại.<br />
<br />
130<br />
<br />
Mã hóa người có tờ 1 USD bởi số 1, người có<br />
tờ 2 USD bởi số 2. Mỗi cách xếp hàng bất kỳ<br />
tương ứng với một véc tơ có (m+n) thành<br />
phần trong đó n thành phần bằng 1, m thành<br />
phần bằng 2. Thành phần thứ i tương ứng với<br />
người xếp hàng ở vị trí thứ i. Số véc tơ như<br />
m<br />
thế là Cn m .<br />
Một véc tơ gọi là tốt nếu tương ứng với cách<br />
xếp hàng thỏa mãn yêu cầu bài toán. Các véc<br />
tơ còn lại gọi là các véc tơ xấu. Chúng ta đếm<br />
xem có bao nhiêu véc tơ xấu bằng cách xây<br />
dựng một song ánh từ tập A các véc tơ xấu<br />
đến tập B các véc tơ có (m n 1) thành<br />
phần . Mỗi véc tơ của B có hai tính chất :<br />
i, Có m thành phần 2, (n+1) thành phần 1<br />
ii, Thành phần 2 đứng vị trí đầu tiên.<br />
Ta có:<br />
<br />
B Cmmn1 .<br />
<br />
Cách xây dựng song ánh như sau:<br />
- Giả sử v là một véc tơ xấu, tức là từ thành<br />
phần đầu tiên đến hết thành phần thứ (i-1) thì<br />
tương ứng với việc mua vé diễn ra suôn sẻ.<br />
Đến thành phần thứ i tương ứng với người thứ<br />
i mua vé nhưng người bán vé không có tiền<br />
trả lại. Vị trí i lúc này ta gọi là vị trí xấu. Như<br />
vậy, từ thành phần 1 tới hết (i-1) có số lượng<br />
thành phần 1 bằng số lượng thành phần 2.<br />
Xây dựng một véc tơ v ' bằng cách thực hiện<br />
hai bước:<br />
- Bước 1: Thêm thành phần 1 vào trước<br />
thành phần đầu tiên của v . Khi đó, vị trí<br />
xấu là ( i +1).<br />
- Bước 2: Từ vị trí đầu tiên của véc tơ ở bước<br />
1 tới hết vị trí (i+1), thay các giá trị 1 bởi 2 và<br />
giá trị 2 bởi 1. Các thành phần từ vị trí (i+2)<br />
trở đi giữ nguyên giá trị cũ.<br />
Sau hai bước trên ta thu được véc tơ v ' thuộc<br />
tập B.<br />
- Xét véc tơ bất kỳ u ' bất kỳ thuộc B, gọi j là<br />
số tự nhiên bé nhất thỏa mãn từ vị trí 1 đến<br />
hết vị trí j thỏa mãn số thành phần 1 bằng số<br />
<br />
Nguyễn Thị Ngọc Ánh<br />
<br />
Tạp chí KHOA HỌC & CÔNG NGHỆ<br />
<br />
thành phần 2. Thao tác ngược lại ở trên, từ vị<br />
trí 1 tới hết vị trí j ta thay 2 bởi 1 và 1 bởi 2.<br />
Các vị trí còn lại giữ nguyên như cũ. Bỏ đi số<br />
1 ở thành phần đầu tiên ta được một véc tơ<br />
xấu thuộc A.<br />
Vậy có một song<br />
ánh từ A đến B nên số véc<br />
m<br />
m 1<br />
tơ tốt bằng: Cn m - Cm n .<br />
Đây cũng là kết quả cần tìm của bài toán.<br />
Chúng tôi đã tiến hành thực nghiệm tại lớp<br />
chuyên Toán 10 khóa 25, trường trung học<br />
phổ thông Chuyên, tỉnh Thái Nguyên. Nội<br />
dung thực nghiệm gồm 3 tiết. Tiết 1: Hướng<br />
dẫn học sinh phân biệt được 4 khái niệm: AX,<br />
ĐA, TA, SA, lấy được các ví dụ và phản ví<br />
dụ minh họa. Tiết 2: PPSA. Tiết 3: Vận dụng<br />
PPSA vào giải một số bài toán đếm trong các<br />
đề thi học sinh giỏi. Cảm nhận chung của<br />
chúng tôi là các em rất hào hứng tham gia các<br />
hoạt động theo hướng dẫn của giáo viên. 84<br />
% các em được hỏi ý kiến đều cảm thấy thích<br />
thú khi sử dụng PPSA vào giải bài tập. Các<br />
em bắt đầu tự đọc được một số bài viết về<br />
phương pháp này ở mức độ khó hơn.<br />
KẾT LUẬN<br />
Bài báo đề xuất một phương án dạy cho HS<br />
khá giỏi THPT phân biệt được bốn khái niệm:<br />
AX, ĐA, TA, SA, nêu được nội dung của<br />
PPSA và hướng dẫn các em vận dụng PPSA<br />
vào giải toán. Thông qua phương pháp giảng<br />
<br />
128(14): 127 - 131<br />
<br />
dạy đã nêu, chúng tôi mong muốn tạo hứng<br />
thú cho học sinh khi học chủ đề này. Thực<br />
nghiệm bước đầu cho thấy những đề xuất nêu<br />
trên là có tính khả thi. Chúng tôi sẽ tiếp tục<br />
nghiên cứu để có thể dạy tốt hơn phương<br />
pháp này cho đối tượng học sinh khá giỏi<br />
THPT.<br />
TÀI LIỆU THAM KHẢO<br />
1. Phan Huy Khải (2002), Các phương pháp giải<br />
toán sơ cấp 12, Nxb Hà Nội.<br />
2. Bùi Văn Nghị (2009), Vận dụng lý luận vào<br />
thực tiễn dạy học môn toán ở trường phổ thông,<br />
Nxb Đại học Sư phạm, Hà Nội.<br />
3. Phạm Minh Phương (2010), Một số chuyên đề<br />
toán tổ hợp bồi dưỡng học sinh giỏi trung học phổ<br />
thông, Nxb Giáo dục Việt Nam.<br />
4. Nguyễn Văn Thông (2012), Bồi dưỡng học sinh<br />
giỏi toán Tổ hợp – Rời rạc, Nxb Đại học Quốc gia<br />
Hà Nội, Hà Nội.<br />
5. Chen Chuan-Chong, Koh Khee-Meng (1992),<br />
Principles and techniques in combinatorics,<br />
World Scientific.<br />
6. V.K. Balakrishnan, Ph.D (1995), Theory and<br />
problems of combinatorics, McGraw-Hill, INC,<br />
Singapore.<br />
7. Titu Andreescu, Zuming Feng (2004), A Path to<br />
Combinatoricts for Undergraduates ( Counting<br />
Strategies), Birkhauser Boston, United states of<br />
America.<br />
<br />
SUMMARY<br />
INSTRUCTING GOOD AND EXCELLENT STUDENTS<br />
OF HIGH SCHOOLS IN APPLYING THE BIJECTIVE METHOD<br />
TO SOLVE SOME COUNTING PROBLEMS<br />
Nguyen Thi Ngoc Anh*<br />
Thai Nguyen Specialized High School<br />
<br />
The Bijective method (BM) is an interesting method to solve some counting problems. However,<br />
in Vietnam there are few articles mentioned on this method and there is not any author mentioning<br />
how to teach this method for good and excellent students of high schools (HS). So, we would like<br />
to share teaching experience of concepts on mapping, injective, surjective and bijective functions.<br />
Simultaneously, we analyze some examples on applying the bijective method to solve some<br />
counting problems in order to help students understanding more about this method.<br />
Keywords:<br />
<br />
*<br />
<br />
Email: anhtoan416@gmail.com<br />
<br />
131<br />
<br />