Hướng dẫn học sinh trung học phổ thông khá giỏi sử dụng phương pháp song ánh giải một số bài toán đếm

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