Tài liệu ỨNG DỤNG LÝ THUYẾT TỔ HỢP TRONG CHƯƠNG TRÌNH TOÁN TRUNG HỌC PHỔ THÔNG

BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC ĐÀ NẴNG TRẦN THỊ NHẬT NGUYÊN ỨNG DỤNG LÝ THUYẾT TỔ HỢP TRONG CHƯƠNG TRÌNH TOÁN TRUNG HỌC PHỔ THÔNG LUẬN VĂN THẠC SĨ KHOA HỌC Đà Nẵng - 2014 BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC ĐÀ NẴNG TRẦN THỊ NHẬT NGUYÊN ỨNG DỤNG LÝ THUYẾT TỔ HỢP TRONG CHƯƠNG TRÌNH TOÁN TRUNG HỌC PHỔ THÔNG Chuyên ngành: Phương pháp Toán sơ cấp Mã số: 60 46 0113 LUẬN VĂN THẠC SĨ KHOA HỌC Người hướng dẫn khoa học: PGS. TS Nguyễn Gia Định Đà Nẵng - 2014 LỜI CAM ĐOAN Tôi cam đoan đây là công trình nghiên cứu của riêng tôi. Các kết quả, số liệu nêu trong luận văn là hoàn toàn trung thực và chưa từng được ai công bố trong bất kỳ công trình nào khác. Học viên Trần Thị Nhật Nguyên MỤC LỤC MỞ ĐẦU........................................................................................................1 1. Lý do chọn đề tài ..............................................................................1 2. Mục tiêu nghiên cứu của đề tài ........................................................3 3. Đối tượng và phạm vi nghiên cứu ....................................................3 4. Phương pháp nghiên cứu ..................................................................3 5. Bố cục luận văn ................................................................................3 CHƯƠNG 1. CÁC NGUYÊN LÝ ĐẾM CƠ BẢN ....................................5 1.1. NGUYÊN LÝ CỘNG VÀ NGUYÊN LÝ NHÂN ..................................5 1.1.1. Nguyên lý cộng ..........................................................................5 1.1.2. Nguyên lý nhân ............................................................................6 1.2. TỔ HỢP ...................................................................................................6 1.3. CÁC TÍNH CHẤT CỦA HỆ SỐ TỔ HỢP .............................................9 1.4. SONG ÁNH ...........................................................................................25 1.5. PHÉP ĐỆ QUY .......................................................................................28 1.6. CÁC BÀI TOÁN ỨNG DỤNG ..............................................................34 CHƯƠNG 2. CÁC PHƯƠNG PHÁP ĐẾM DÙNG NGUYÊN LÝ BAO HÀM – LOẠI TRỪ, NGUYÊN LÝ FUBINI VÀ HÀM SINH .......41 2.1. NGUYÊN LÝ BAO HÀM – LOẠI TRỪ ...............................................41 2.2. PHÉP TÍNH THEO HAI CÁCH: NGUYÊN LÝ FUBINI .....................47 2.3. HÀM SINH .............................................................................................51 2.4. CÁC BÀI TOÁN ỨNG DỤNG ..............................................................58 KẾT LUẬN . ..................................................................................................64 DANH MỤC TÀI LIỆU THAM KHẢO ....................................................65 QUYẾT ĐỊNH GIAO ĐỀ TÀI LUẬN VĂN (bản sao) 1 MỞ ĐẦU 1. Lý do chọn đề tài: Tư duy về tổ hợp ra đời rất sớm. Ở Trung Quốc, vào thời nhà Chu người ta đã biết đến những hình vuông thần bí. Nhà triết học cổ Hy Lạp Kxenokrat, sống ở thế kỷ thứ 4 trước công nguyên đã biết cách tính số các từ khác nhau lập từ một bảng chữ cái cho trước. Nhà toán học Pithagore và các học trò của ông đã phát hiện ra nhiều tính chất kỳ lạ của các số. Một kết quả nổi tiếng của trường phái này là kết quả mà ngày nay chúng ta gọi là định lý Pithagore. Tuy nhiên, một thời gian dài sau đó, tổ hợp chỉ phát triển một cách riêng lẻ, chưa hình thành được hệ thống lý luận cơ sở khoa học, phương pháp nghiên cứu đặc thù. Và tổ hợp chỉ thực sự trở thành một ngành của toán học rời rạc vào đầu thế kỷ 17 bằng một loạt các công trình nghiên cứu nghiêm túc của nhà toán học xuất sắc như Pascal, Fermat, Leibnitz, Euler, ... Mặc dầu vậy, tổ hợp vẫn là lĩnh vực mờ nhạt và ít được chú ý tới trong quãng thời gian hơn hai thế kỷ. Từ khi máy tính phát triển và thịnh hành, tổ hợp đã trở thành một lĩnh vực toán ứng dụng với sự phát triển mạnh mẽ. Nó là chiếc cầu nối giữa các bài toán cần được giải quyết và công cụ tính toán là máy tính. Cụ thể là việc giải quyết các bài toán thực tế hay các bài toán trong các lĩnh vực khoa học thường được quy về việc giải quyết các bài toán tổ hợp nào đó. Vì tổ hợp có liên quan tới nhiều vấn đề trong nhiều lĩnh vực của đời sống và các khoa học khác nhau nên khó có thể định nghĩa nó một cách hình thức chặt chẽ. Nói chung, lý thuyết tổ hợp gắn liền với việc nghiên cứu các cấu hình tổ hợp và các cấu trúc tổ hợp. Các vấn đề của lý thuyết tổ hợp liên 2 quan tới các cấu hình tổ hợp cũng rất đa dạng. Tuy nhiên, có bốn loại bài toán thường gặp hơn cả: bài toán đếm, bài toán liệt kê, bài toán tối ưu tổ hợp, bài toán tồn tại. Trong các bài toán kể trên, bài toán đếm thuộc loại bài toán quan trọng. Đây là bài toán nhằm trả lời câu hỏi: “Có bao nhiêu cấu hình tổ hợp thuộc dạng đã cho?” Phương pháp đếm thường dựa vào một số quy tắc, nguyên lý đếm và một số kết quả đếm cho các cấu hình tổ hợp đơn giản. Khi việc xác định chính xác số cấu hình tổ hợp gặp khó khăn hay chưa giải quyết được trọn vẹn, người ta thường đặt ra bài toán đánh giá số các cấu hình tổ hợp đó bằng cách xác định cận trên và cận dưới của nó. Bài toán đếm được áp dụng có hiệu quả vào những công việc mang tính chất đánh giá như tính xác suất của một sự kiện, tính độ phức tạp của một thuật toán, ... Bài toán đếm sẽ được giải quyết tốt nếu chúng ta nắm vững các phương pháp đếm cơ bản, phương pháp đếm dùng hàm sinh, phương pháp đếm bằng nguyên lý bao hàm và loại trừ, phương pháp đếm dùng nguyên lý Fubini. Ngoài ra, trong chương trình toán THPT có đưa vào một số khái niệm và kết quả về tổ hợp liên quan đến các phương pháp đếm. Trong các kỳ thi chọn học sinh giỏi, kỳ thi olympic trong nước và quốc tế về toán đều có ít nhất một bài toán liên quan đến lý thuyết tổ hợp và thường là dạng bài toán khó. Xuất phát từ nhu cầu phát triển và tính thời sự của việc nghiên cứu lý thuyết tổ hợp, chúng tôi quyết định chọn đề tài với tên gọi: Ứng dụng lý thuyết tổ hợp trong chương trình toán THPT để tiến hành nghiên cứu. Chúng tôi hy vọng tạo được một tài liệu tham khảo tốt cho những người muốn tìm hiểu về các bài toán tổ hợp nằm trong bối cảnh bài toán đếm ứng dụng cho chương trình toán THPT. 3 2. Mục tiêu nghiên cứu của đề tài: Mục tiêu của đề tài là nhằm giúp học sinh THPT hiểu được bản chất các khái niệm và ý tưởng về lý thuyết tổ hợp, một lĩnh vực quan trọng của toán học. Mục tiêu này được thực hiện bằng cách tập làm quen cho học sinh với các ví dụ điển hình minh họa những sự kiện toán học trung tâm và bằng cách trau dồi học sinh với một số bài toán chọn lọc cẩn thận. Điều cốt yếu là giúp học sinh tạo được cầu nối giữa các bài tập về tổ hợp ở trường THPT và các khái niệm - bài toán trừu tượng, phức tạp và tinh vi hơn. 3. Đối tượng và phạm vi nghiên cứu: Đối tượng nghiên cứu của đề tài là lý thuyết tổ hợp. Phạm vi nghiên cứu của đề tài là các phép đếm thông dụng và ứng dụng vào chương trình toán THPT. 4. Phương pháp nghiên cứu: 1. Thu thập các bài báo khoa học và tài liệu của các tác giả nghiên cứu liên quan đến các phương pháp đếm, vấn đề quan trọng trong lý thuyết tổ hợp. 2. Tham gia các buổi seminar của thầy hướng dẫn để trao đổi các kết quả đang nghiên cứu. Trao đổi qua email, blog, forum với các chuyên gia về các ứng dụng của lý thuyết xác suất và thống kê. 5. Bố cục luận văn: I. Phần mục lục II. Phần mở đầu 1. Giới thiệu về lịch sử, tính thời sự của vấn đề và sự liên quan đến các lĩnh vực khác. 4 2. Giới thiệu nội dung nghiên cứu của luận văn. III. Phần nội dung Chương 1: Các phương pháp đếm cơ bản 1.1. Nguyên lý cộng và nguyên lý nhân 1.2. Tổ hợp 1.3. Các tính chất của hệ số tổ hợp 1.4. Song ánh 1.5. Phép đệ quy 1.6. Các bài toán ứng dụng. Chương 2: Các phương pháp đếm dùng nguyên lý bao hàm – loại trừ, nguyên lý Fubini và hàm sinh 2.1. Nguyên lý bao hàm - loại trừ 2.2. Phép tính theo hai cách: nguyên lý Fubini 2.3. Hàm sinh 2.4. Các bài toán ứng dụng. IV. Phần kết luận : Tổng kết các kết quả đã đạt được, nêu một số vấn đề chưa giải quyết được và hướng phát triển tiếp theo của đề tài. 5 CHƯƠNG 1 CÁC PHƯƠNG PHÁP ĐẾM CƠ BẢN 1.1. NGUYÊN LÝ CỘNG VÀ NGUYÊN LÝ NHÂN Tính là một trong những kỹ năng cơ bản nhất. Chúng ta bắt đầu đếm trên các ngón tay của mình khi đang học trong trường mẫu giáo hoặc thậm chí sớm hơn, nhưng làm thế nào để tính một cách nhanh chóng, chính xác, và có hệ thống là một khóa học suốt đời . 1.1.1. Nguyên lý cộng Một công việc được hoàn thành bởi một trong k hành động T 1, T2, ..., Tk. Các hành động này có thể làm tương ứng bằng n1, n2, ..., nk cách và giả sử không có hành động nào có thể làm đồng thời, khi đó công việc đó có n 1 + n2 + ...+ nk cách thực hiện. Nguyên lý cộng còn được phát biểu dưới dạng ngôn ngữ tập hợp như sau: Nếu A1, A2,..., Ak là các tập hữu hạn đôi một rời nhau, tức là Ai ∩ Aj = Ø (i≠ j ) thì A 1 ∪A 2 ∪.. .∪ A k|=|A1|+|A2|+.. .+|Ak| , ở đây |Ai| là số các phần tử của tập Ai. Ví dụ 1.1.1. Giả sử cần chọn hoặc một học sinh nam hoặc một học sinh nữ tham gia cuộc họp. Hỏi có bao nhiêu cách để chọn nếu có 37 học sinh nam và 63 học sinh nữ? Giải: Gọi cách chọn thứ nhất là chọn một học sinh nam từ tập 37 học sinh nam, ta có 37 cách. 6 Gọi cách chọn thứ hai là chọn một học sinh nữ từ tập 63 học sinh nữ, ta có 63 cách. Vì tập học sinh nam và tập học sinh nữ là rời nhau nên theo nguyên lý cộng, ta có số cách chọn nhân sự là 37 + 63 = 100 cách. 1.1.2. Nguyên lý nhân Giả sử một nhiệm vụ nào đó được tách ra thành k việc T 1, T2, ..., Tk. Nếu việc Ti có thể làm bằng ni cách sau khi các việc T1, T2, ..., Ti-1 đã được làm (1 ≤ i ≤ k) thì có n1.n2...nk cách thực hiện nhiệm vụ đã cho. Quy tắc nhân còn được phát biểu dưới dạng ngôn ngữ tập hợp như sau: Nếu A1, A2, ..., Ak là các tập hữu hạn bất kỳ và nếu A 1 ×A 2 ×...× A k là tích Descartees của các tập đó thì |A1 × A2 ×. ..×A K|=|A 1||A 2|.. .|A K| Ví dụ 1.1.2. Có bao nhiêu xâu nhị phân có độ dài 7? Giải: Một xâu nhị phân có độ dài 7 gồm 7 bit, mỗi bit có hai cách chọn (hoặc giá trị 0 hoặc giá trị 1). Theo quy tắc nhân ta có: 2.2.2.2.2.2.2 = 128 xâu bit nhị phân có độ dài 7. 1.2. TỔ HỢP Chúng ta thường gặp một số bài toán yêu cầu phải đếm số tổ hợp, tức là đếm số tập hợp các đối tượng không được sắp xếp thứ tự. Định lý 1.2.1. Cho n và k là những số nguyên, với n ≥ k. Số tổ hợp của việc mỗi một lần lấy k phần tử từ n phần tử là ( n ¿) ¿¿ ¿ ¿ 7 Ký hiệu: nCk hoặc C(n; k) hay (n ¿) ¿¿¿ ¿ Chứng minh: Có Pnk = n! (n−k )! cách chọn k đối tượng có thứ tự. Có k! cách để sắp xếp k phần tử được chọn, có nghĩa là, có k! cách để chọn tổ hợp của k phần tử giống nhau. Vì vậy mỗi tổ hợp được tính k! lần trong nPk. n! Do đó có (n−k)!k ! tổ hợp. □ Trong một số tình huống, thứ tự của các phần tử bằng cách nào đó được xác định trước, thì thứ tự của các đối tượng được chọn không còn quan trọng. Ví dụ 1.2.1. Lớp học toán của thầy An có 5 học sinh nam và 9 học sinh nữ. Vào cuối năm, thầy An muốn chụp ảnh cả lớp. Thầy muốn tất cả học sinh đứng trong một hàng, học sinh nam đứng theo thứ tự giảm dần theo chiều cao của họ (giả định rằng họ có chiều cao khác nhau) từ trái sang phải và học sinh nữ cũng đứng theo thứ tự tăng dần theo chiều cao của họ (giả định rằng họ có chiều cao khác nhau) từ trái sang phải. Có bao nhiêu cách để có thể thực hiện công việc này? (Học sinh nam không cần phải đứng cùng nhau, và các học sinh nữ cũng không cần phải đứng cùng nhau.) Giải: Xét 14 khoảng trống trong một hàng s1, s2, ..., s14 Nếu si1, si2, ..., si5 được chọn cho vị trí của các nam sinh, thì học sinh nam được đứng ở những vị trí này theo chiều cao của họ. Các cô gái sau đó 8 cũng có một cách duy nhất để đứng ở vị trí của mình. Do đó câu trả lời là ( 14 ¿ ) ¿ ¿ ¿ ¿ n,k 1 ,k 2 ,...,k m Hệ quả 1.2.2. Cho □ là những số nguyên, với n≥k 1 + k 2 +. ..+k m . Số tổ hợp của việc một lần lấy k 1 ,k 2 ,...,k m phần tử từ n phần tử, theo thứ tự là n ¿) ¿ ¿ ¿ ( ¿ với km + 1 = n – (k1 + k2 + ... + km) Chứng minh: Từ định lý 1.2.1 có (n ¿) ¿¿¿ ¿ cách để lấy k1 phần tử, có n – k1 cách để lấy các phần tử còn lại. Sử dụng định lý 1.2.1 một lần nữa, có (n−k1 ¿) ¿ ¿¿ ¿ cách để lấy k2 phần tử. Tương tự như vậy, chúng ta kết luận rằng số tổ hợp của việc một lần lấy k 1 ,k 2 ,...,k m phần tử từ n phần tử, theo thứ tự là ( n ¿) ¿¿ ¿ ¿ ¿ ¿ = n! k 1 ! k 2 !...k m !k m+1 ! □ 9 Ví dụ 1.2.2. Khoa toán tổ chức một cuộc họp. Sau khi 23 thành viên đàm thoại, họ quyết định chia ra thành 8 nhóm, trong đó 5 nhóm có 3 thành viên và 2 nhóm 4 thành viên để tiếp tục thảo luận. Hỏi có bao nhiêu cách để chia được? 23 ¿ ) ¿ ¿ ¿ ( ¿ Giải: Ta có cách chia nhóm. Từ đó mỗi nhóm thảo luận trên một đề tài, tuyệt đối không được sắp xếp thứ tự nhóm có cùng số lượng. Khi đó câu trả lời là: 1 ¿( 2!5! 23 ¿ ) ¿ ¿ ¿ □ 1.3. CÁC TÍNH CHẤT CỦA HỆ SỐ TỔ HỢP Chúng ta bắt đầu làm quen với hệ số tổ hợp (hay là hệ số nhị thức). Cho n là số nguyên dương. Nếu chúng ta sử dụng hai biến số đa thức (x+y)n như ( x+ y )n=a0 x n +a1 x n−1 y +a2 x n−2 y 2 +. . .+an−1 xy n−1 a n y n với 0 ≤ k ≤ n, ak là hệ số tổ hợp. 1 1 1 1 1 1 2 3 4 1 3 6 1 4 1 10 1 5 .... 10 ... 10 ... 5 1 ... ... Chúng ta có thể chứng minh định lý sau Định lý 1.3.1: Cho n là số nguyên dương. Khi đó n ( x + y ) =¿ ( n ¿ ) ¿ ¿ ¿ ¿ Quy ước: ( n ¿) ¿¿ ¿ ¿ Định lý này giải thích tại sao số (n ¿) ¿¿¿ ¿ được gọi là hệ số tổ hợp. Hệ số tổ hợp cũng là những số hạng trong tam giác Pascal. Chính xác hơn cho n ≥ 0 ( n ¿) ¿¿ ¿ ¿ là hàng thứ n của tam giác. Ví dụ 1.3.1. Bảng số xe gồm 8 chữ số, nó được gọi là chẵn nếu số các số 0 trong nó là chẵn. Có bao nhiêu bảng số xe như vậy? Giải: Cho 0 ≤ k ≤ 4, nếu có 2k các số 0 trong đó, thì có 8 – 2k chữ số khác 0, có 9 cách chọn. Có ( 8¿) ¿¿¿ ¿ số có 2k số 0. cách để chọn 2k vị trí của những số 0, và ( 8 ¿ ) ¿ ¿¿ ¿ bảng 11 98 +¿ ( 8 ¿ ) ¿ ¿ ¿ ¿ Do đó câu trả lời là: Từ định lý 1.3.1 8 8 ( 9 +1 ) = 9 +¿ ( 8 ¿ ) ¿ ¿ ¿ ¿ Và ( 9−1 )8 =98 −¿ ( 8 ¿ ) ¿ ¿ ¿ ¿ 8 8 (9+1) +( 9−1) =108 +88 2 Vậy có bảng số thỏa điều kiện □ Định lý 1.3.2. Cho n và k là số nguyên dương với n ≥ k, ta có các tính chất của hệ số tổ hợp sau: (1) ( n ¿) ¿¿ ¿ ¿ (2) ( ¿ (3) (4) n ¿) ¿ ¿ ¿ ( n ¿) ¿¿ ¿ ¿ kalignl ( n¿ ) ¿ ¿¿ ¿ 12 k (5 n =(n−k+1)¿ ( n ¿ ) ¿ ¿ k ¿ () (6) ( n ¿) ¿¿ ¿ ¿ (7) ( n ¿) ¿¿ ¿ ¿ (8) ( n ¿) ¿¿ ¿ ¿ (9) ( n ¿) ¿¿ ¿ ¿ (10) ( n ¿) ¿¿ ¿ ¿ (11) (n ¿) ¿¿¿ ¿ chia hết cho n nếu n là số nguyên tố và 1≤k ≤n−1 Chứng minh: Tính chất (1) và (2) có thể dễ dàng có được bằng cách sử dụng hệ thức ( n ¿) ¿¿ ¿ ¿ . Chúng ta dùng lý luận tổ hợp để chứng minh nó. (1) Chú ý rằng một tổ hợp của k phần tử giữ lại tương đương với tổ hợp n – k phần tử lấy đi, có nghĩa là ( n ¿) ¿¿ ¿ ¿ . Tính chất này có được từ tính đối xứng của việc khai triển (x+y)n tương ứng với x và y. 13 (2) Tính chất này có được từ định nghĩa tam giác Pascal. Một chú ý là vế bên trái biểu diển số đường mà trong đó chúng ta có thể lấy tổ hợp của k+1 phần tử từ n phần tử cho trước. Cũng có thể tính chúng theo cách sau. Cho một phần tử riêng biệt một cái tên riêng, gọi là "Fat". Chúng ta phân loại tất cả (k+1) phần tử của tổ hợp thành 2 nhóm. Nhóm (A) chứa những phần tử có "Fat", nhóm (B) chứa những phần tử không có "Fat". Khi đó không khó để thấy rằng có ( n−1¿) ¿ ¿¿ ¿ tổ hợp của (A) và ( n−1¿) ¿ ¿¿ ¿ tổ hợp của (B). Do đó, kết quả phải là như nhau (3) Nếu n chẵn, Nếu n lẻ, Cho n ¿) ¿ ¿ ¿ ( ¿ ⌈ ⌈ n−1 n ⌉= 2 2 n−1 n−1 ⌉= 2 2 0≤k≤⌈ n−1 ⌉−1 , 2 k≤n−2 2 hoặc k + 1 ≤ n – k – 1. Do đó ( n ¿) ¿¿ ¿ ¿ ¿ ¿ Từ (1) ta có: ( n ¿) ¿¿ ¿ ¿ nếu n lẻ và n = 2m +1 và 14 ( n ¿) ¿¿ ¿ ¿ nếu n chẵn và n = 2m. (4) kalignl ( n ¿ ) ¿ ¿ ¿ ¿ (5) kalignl ( n ¿ ) ¿ ¿ ¿ ¿ (6) Chú ý rằng ( n ¿) ¿¿ ¿ ¿ =(n−k+1)¿ ( n ¿) ¿ ¿ ¿ . Kết quả này có được bằng cách sử dụng tính chất (2) nhiều lần. (7) Kết quả này có được từ việc sử dụng (1) trong mỗi thành phần của (6). (8) Đặt x = y = 1 trong khai triển của (x + y)n cho kết quả cần chứng minh. Đây cũng là định lý 1.3.3. Cho 0≤k≤n , có (n ¿) ¿¿¿ ¿ tập con k phần tử của S={1,2,...,n}. Tổng từ k = 0 đến k = n cho ta tổng số tập con của S (bao gồm cả Ø và chính S). (9) Đặt x = 1 và y = –1 trong khai triển của (x + y)n cho kết quả cần chứng minh. n (10) Từ (4) và (8) ta có: ∑ k =1 kalignl ( n ¿ ) ¿ ¿ ¿ ¿ ¿ 15 (11) Lưu ý rằng tử số của (n ¿) ¿¿¿ ¿ k)!. Do đó (n ¿) ¿¿¿ ¿ là một số nguyên. Cũng lưu ý rằng n chia cho n!, . Nếu n là số nguyên tố, n là nguyên tố cùng nhau tới k!(n - chia hết cho n. Hệ số tổ hợp với (n ¿) ¿¿¿ ¿ (n ¿) ¿¿¿ ¿ có một ý nghĩa tổ hợp nếu n và k là các số nguyên 0< k ≤ n . Trong định lý 1.3.1, ta mở rộng định nghĩa tới k = 0. Và quy ước ( 0 ¿ ) ¿ ¿¿ ¿ . Nếu 0 ≤ n < k hay k <0 ≤ n, ta không thể lấy k phần tử từ n phần tử, vì vậy quy ước ( n ¿ ) ¿ ¿¿ ¿ . □ Ví dụ 1.3.2. Tính ( 11 ¿ ) ¿ ¿ ¿ ¿ ¿ ¿ Giải: Từ định lý 1.3.2 (4), cho 0 ≤ k≤ 11, 12 ¿ ( 11 ¿ ) ¿ ¿ k +1 ¿ Do đó tổng cần tính là: hay ( 11¿ ) ¿ ¿¿¿¿ ¿