Tài liệu Cac_phuong_phap_dem_nang_cao

SỞ GIÁO DỤC VÀ ĐÀO TẠO NAM ĐỊNH MÉu TRƯỜNG THPT CHUYÊN LÊ HÔNG PHONG SÁNG KIẾN KINH NGHIỆM DỰ THI CẤP TỈNH BÁO CÁO SÁNG KIẾN CÁC PHƯƠNG PHÁP ĐẾM NÂNG CAO Tác giả: Trần Mạnh Sang Trình độ chuyên môn: Cử nhân Toán học Chức vụ: Giáo viên Toán Nơi công tác:Trường THPT chuyên Lê Hồng Phong Nam Định, tháng 5 name 2014 ------ Trang 1 ------ THÔNG TIN CHUNG VỀ SÁNG KIẾN 1. Tên sáng kiến: CÁC PHƯƠNG PHÁP ĐẾM NÂNG CAO 2. Lĩnh vực áp dụng sáng kiến: Dạy Toán cho học sinh các lớp chuyên Toán, học sinh đội tuyển thi Duyên hải và Đồng bằng Bắc Bộ, học sinh đội tuyển thi HSG quốc gia. 3. Thời gian áp dụng sáng kiến: Các năm học từ 2010 - 2011 đến 2013 – 2014. 4. Tác giả: Họ và tên: Trần Mạnh Sang Năm sinh: 1987 Nơi thường trú: Phường Ngô Quyền, thành phố Nam Định Trình độ chuyên môn: Cử nhân Toán học Chức vụ công tác: Giáo viên Toán Nơi làm việc: Trường THPT chuyên Lê Hồng Phong Địa chỉ liên hệ: Số 19 Máy Tơ, thành phố Nam Định Điện thoại: 097.227.6698 5. Đơn vị áp dụng sáng kiến: Tên đơn vị: Trường THPT chuyên Lê Hồng Phong Địa chỉ: 76 Vị Xuyên, tp. Nam Định – tỉnh Nam Định Điện thoại: (0350) 364 0297 ------ Trang 2 ------ ------ Trang 3 ------ I. Điều kiện hoàn cảnh tạo ra sáng kiến: Mục tiêu giáo dục của chúng ta hiện nay là đào tạo những con người lao động tự chủ, năng động, sáng tạo có năng lực giải quyết những vấn đề thường gặp, góp phần xây dựng đất nước giàu mạnh, xã hội công bằng và văn minh, đưa đất nước Việt Nam tiến nhanh trên con đường phát triển hòa nhập với thế giới ở đầu thế kỉ XXI. Đứng trước tình hình đó, Bộ Giáo dục và Đào tạo, Sở Giáo dục và Đào tạo cũng như nhà trường đã đề ra nhiều biện pháp tích cực. Một trong những biện pháp đó là cải tiến chương trình dạy học, cải tiến phương pháp dạy của thầy và phương pháp học của trò, phải có cuộc cách mạng thực sự về phương pháp giáo dục, cũng như cách thức tổ chức kiểm tra chất lượng học sinh để hưởng ứng cuộc vận động của Bộ trưởng Bộ GD - ĐT về chống tiêu cực trong thi cử và bệnh thành tích trong giáo dục. Đối với bộ môn Toán - Bộ môn then chốt của khoa học tự nhiên, thì một trong những khâu quan trọng của quá trình cải tiến chương trình dạy học là tiếp nhận và giải quyết một vấn đề theo nhiều hướng khác nhau, cố gắng tìm đến bản chất của nó, từ đó có mối liên hệ giữa các bài toán riêng lẻ với nhau. Trong chương trình môn Toán cấp THPT chuyên, vấn đề tổ hợp luôn là lĩnh vực khó khăn với cả thầy và trò. Vấn đề này xuất hiện nhiều trong các kì thi HSG quốc gia và quốc tế (có 2 trên 7 bài), là một phần quan trọng trong việc phát hiện và bồi dưỡng các học sinh có tư chất thực sự. Một trong những phần thường hay xuất hiện trong các đề thi chính là bài toán đếm. Bài toán đếm có thể nói là một bài toán cổ xưa nhất: Đếm số súc vật trong chuồng, đếm số học sinh trong lớp, đếm số quân của đoàn quân,... Để đếm, có lẽ ai cũng sẽ có thể cho 1 kết quả, tuy nhiên kết quả đó có đúng hay không? Khi kết quả đúng rồi thì cũng có thể có những cách đếm khác nhau. Ví dụ cùng là kết quả 36 nhưng có người đếm là 36x1, có người lại ra là 6.6, đó đã là hai cách hoàn toàn khác nhau. Có thể thấy được bài toán đếm rất hay dẫn đến nhầm lẫn trong tính toán. Để ------ Trang 4 ------ hiểu rõ hơn các bài toán thuộc dạng này, chúng tôi tìm hiểu và đưa ra các phương pháp đếm nâng cao. Trước hết giúp học sinh hiểu rõ vấn đề bản chất cùng với sự tư suy logic thông qua việc kết hợp các bài toán với nhau. Sau nữa, chúng tôi muốn đưa ra những cách phát biểu khác nhau cho một bài toán, có thể từ những bài đơn giản, khi phát biểu theo ngôn ngữ thực tế lại thấy không dễ dàng, từ đó cho ta cảm giác khó khăn trong giải bài toán. II. Thực trạng (trước khi tạo ra sáng kiến) Đã có rất nhiều bài toán, các đề thi HSG có xuất hiện bài toán đếm: HSG quốc gia (VMO, VNTST), đề thi quốc tế (IMO, IMC) hay các kì thi của các quốc gia (China TST, USA TST,...). Việc giải quyết các bài toán này không hề đơn giản (Thường là bài khó nhất trong đề thi). Một phần khó đối với học sinh của Việt Nam chính là việc các em ít tiếp xúc với dạng toán, dẫn đến cảm giác sợ khi gặp. Vì vậy tôi viết sáng kiến này, tổng kết những kinh nghiệm, phần nào giúp các em học sinh tháo gỡ các khó khăn, nhìn nhận vấn đề đơn giản hơn, bên cạnh đó cũng mong muốn là một tài liệu tham khảo giúp đỡ các thầy cô một phần nhỏ trong quá trình giảng dạy. III. Phương pháp nghiên cứu: Để hoàn thành báo cáo này tôi đã lựa chon các phương pháp nghiên cứu sau: +) Nghiên cứu các loại tài liệu có liên quan đến vấn đề này. +) Trao đổi với các đồng nghiệp để có những nhìn nhận vấn đề dưới nhiều góc độ khác nhau, từ đó tìm ra giải pháp cho vấn đề nghiên cứu. +) Quan sát quá trình tiếp thu kiến thức của học sinh, lắng nghe ý kiến, giải đáp các thắc mắc của các em, để tìm ra khâu mà các em học sinh còn vướng mắc, từ đó rút ra những bài học kinh nghiệm cho bản thân. IV. Đối tượng nghiên cứu: ------ Trang 5 ------ Sáng kiến này tôi đã áp dụng cho các em học sinh lớp chuyên Toán, các em trong đội dự tuyển, đội tuyển thi HSG quốc gia và khu vực từ năm học 2011-2012 đến năm học 2013 – 2014. V. Nội dung chính A. KIẾN THỨC MỞ ĐẦU 1. HAI NGUYÊN LÝ CƠ BẢN 1.1. Nguyên lý cộng: Nếu A, B là các tập hợp không giao nhau (chúng không có phần tử chung) thì | A �B  A  B | . Nguyên lý cộng còn có thể phát biểu một cách khác như sau: Nếu một công việc có thể thực hiện bằng một trong hai phương án loại trừ lẫn nhau: phương án thứ nhất có m cách thực hiện và phương án thứ hai có n cách thực hiện. Khi đó công việc đó có m + n cách thực hiện. Nguyên lý cộng mở rộng: Nếu tập hợp hữu hạn C là hợp của n tập đôi một rời nhau C1, C2, ..., Cn thì: |C| = |C1| + ...| |Cn| 1.2. Định nghĩa: Tích Descartes của hai tập hợp A, B ký hiệu bởi AxB là tập hợp tất cả các cặp thứ tự (a, b) với a  A, b  B. 1.3. Nguyên lý nhân: Nếu A và B là hai tập hợp hữu hạn thì AxB cũng hữu hạn và ta có |A x B| = |A|.|B| Định nghĩa về tích Descartes và nguyên lý nhân trên đây có thể mở rộng cho nhiều tập hợp. Nguyên lý nhân có thể phát biểu một cách khác như sau: Nếu một quá trình có thể được thực hiện qua hai công đọan: công đọan I có n 1 cách thực hiện, công đọan II (sau khi thực hiện I) có n2 cách thực hiện. Khi đó có n1.n2 cách thực hiện quá trình đó. 2. Các đối tượng tổ hợp và các số tổ hợp 2.1. Họ các tập con của một tập hợp E được kí hiệu P(E) = A| A  E Mệnh đề: |P(E)| = 2|E| 2.2. Chỉnh hợp của n phần tử chọn k (hay chỉnh hợp chập k của n phần tử) ------ Trang 6 ------ Giả sử E = a1, a2, ..., an. Chỉnh hợp của n phần tử chọn k là một bộ sắp thứ tự gồm k phần tử (ai1, ..., aik). Số các chỉnh hợp chập k của n phần tử được ký hiệu là Akn. Ta có Akn = n(n-1)..(n-k+1) = n!/(n-k)! 2.3. Tổ hợp của n phần tử chọn k (hay tổ hợp chập k của n phần tử) Giả sử E = a1, a2, ..., an. Tổ hợp của n phần tử chọn k là một bộ không sắp thứ tự gồm k phần tử ai1, ..., aik. Nói cách khác, đó là một tập con gồm k phần tử. Số các tổ hợp chập k của n phần tử được ký hiệu là Ckn. Ta có Ckn = n(n-1)..(n-k+1)/k! = n!/k!(n-k)! 2.4. Hoán vị Giả sử E = a1, a2, ..., an. Một hóan vị của E là một cách xếp các phần tử của E theo một thứ tự nào đó. Nói cách khác, đó chỉnh là chỉnh hợp của n phần tử chọn n. Số các hóan vị của n phần tử ký hiệu là Pn. Ta có Pn = n!. 2.5. Chỉnh hợp lặp Giả sử E = a1, a2, ..., an. Chỉnh hợp lặp của n phần tử chọn k là một bộ sắp thứ tự gồm k phần tử (ai1, ..., aik), trong đó cho phép lấy lặp lại. Số các chỉnh hợp chập k của n, theo quy tắc nhân, bằng nk. 2.6. Tổ hợp lặp Giả sử E = a1, a2, ..., an. Tổ hợp lặp của n phần tử chọn k là một bộ không sắp thứ tự gồm k phần tử ai1, ..., aik, trong đó cho phép lấy lặp lại. Nói cách khác, đó là một đa tập hợp gồm k phần tử lấy từ E. Số các tổ hợp lặp chập k của n phần tử được ký hiệu là Hkn. Ta có Hkn = Ckn+k-1 2.7. Hoán vị lặp Xét đa tập hợp E(r1, r2, ..., rs) có n phần tử, trong đó phần tử a1 có r1 phiên bản, phần tử a2 có r2 phiên bản, ..., phần tử as có rs phiên bản. r1+r2+...+rs = n. Một cách xếp các phần tử của E theo thứ tự nào đó được gọi là một hóan vị lặp của n phần tử của E. ------ Trang 7 ------ Số hoán vị lặp của đa tập hợp E(r1, r2, ..., rs) bằng n!/r1!...rs!. Ck-1n+Ckn = Ckn+1 Bổ đề: (Tính chất hệ số nhị thức): (x+y)n = C0nxn + C1nxn-1y + ...+ Cnnyn Định lý: (Nhị thức Newton): B. CÁC PHƯƠNG PHÁP ĐẾM NÂNG CAO 1. SỬ DỤNG NGUYÊN LÝ BÙ TRỪ Nguyên lý: Cho A1 , A2 , ..., An (n �1) là các tập hợp hữu hạn khác rỗng thì: n n i 1 i 1 U Ai  �Ai  n hay: UA i 1 i � 1�i1 i2 �n n  �(1) Ai �Ai  ...   1 k 1 k 1 1 n2 2 � 1�i1 ...ik �n � 1�i1 i2 ...in1 �n Ai �Ai �... �Ai 1 2 Ai �Ai �... �Ai   1 1 n 1 n1 2 n I i 1 (1) k Chứng minh: Ta chứng minh công thức (1) bằng phương pháp quy nạp theo số n các tập hợp.  n = 1, 2 công thức (1) đúng.  Giả sử công thức (1) đúng đến n tập hợp hữu hạn, khác rỗng cho trước  Xét n + 1 tập hợp hữu hạn bất kỳ: A1, A2, ..., An+1 thì ta có: n 1 n � Ai  � Ai � U U U An1 � i 1 �i 1 � n 1 U Ai  - Theo trường hợp n =2: i 1 (2) n n i 1 i 1 U Ai  An1  (U Ai ) �An1 - Theo giả thiết quy nạp: n UA i 1 i n  �Ai  i 1 � 1�i1  i2 �n Ai �Ai  ...   1 1 2 n - Bây giờ ta đi tính (U Ai ) �An 1 i 1 ------ Trang 8 ------ k 1 n I i 1 Ai (4) (3) Ai �n A ��A  n ( A �A ) - Ta viết: � U i � n1 U i n 1 i 1 �i 1 � n 1 n 1 �n A ��A  n A �A  A � A � A  ...   1   U i � n1 � � j Ii1 Ai � i n 1 j n 1 i 1 1�j  j �n �i 1 � 1 1 2 (5) 2 Từ (3), (4), (5) với chú ý rằng: � 1�i1 ... ik �n Ai �... �Ai  1 k � 1�j1 ... jk 1 �n Aj �... �Aj �An 1 = 1 k 1 � 1�i1 ... ik �n 1 Ai �... �Ai 1 k ta có điều phải chứng minh Một số bài toán áp dụng Bài toán 1: Một lớp có 40 học sinh, trong đó có 20 em giỏi toán, 21 em giỏi lí, 22 em giỏi hoá; 8 em giỏi toán và hoá, 11 em giỏi lí và hoá, 5 em giỏi cả ba môn. Biết rằng mỗi học sinh trong lớp giỏi ít nhất một môn. Tìm số học sinh giỏi cả hai môn toán và lý. Lời giải: Gọi T, L, H lần lượt là số học sinh giỏi toán, lý, hoá. Từ giả thiết T  20 ; L  21 ; H  22 T �H  8 ; L �H  11 ; T �L �H  5 T �L �H  40 . Ta phải tìm T �L . Ta có: T �L �H  T  L  H  T �L  T �H  L �H  T �L �H  40 =20+21+22- T �L -8-11+5  T �L = 20+21+22-8-11+5- 40=9 Vậy có 9 học sinh giỏi cả hai môn toán và lý. Bài toán 2: Có 15 quả cầu đôi một khác nhau, trong đó có 4 quả màu vàng. 5 quả màu xanh, 6 quả màu đỏ. Có bao nhiêu cách chọn ra 10 quả sao cho trong các quả cầu còn lại có đủ ba màu. ------ Trang 9 ------ Lời giải: Gọi A là tập hợp các cách chọn ra 10 quả cầu; V, X, Đ theo thứ tự là tập hợp các cách chọn ra 10 quả cầu mà trong các quả cầu còn lại không có quả nào màu vàng, xanh, đỏ; n là số cách chọn 10 quả cầu thoả mãn yêu cầu. Ta có: n  A  V �X �D  A  ( V  X  D  V �X  X �D  D �V  V �X �D ) V  C116 ; X  C105 ; V �X  C61 ; D  C94 . ; X �D  0; D �V  C50 ; V �X �D  0; A  C1510 . 10 6 5 4 1 Vậy n= C15  (C11  C10  C9  C6  0  1  0)  3003 - (462 + 252 + 126 - 7) = 2170 Bài toán 3: Cho 3 chữ số: 1, 2, 3. Từ các chữ số trên có thể lập được bao nhiêu số gồm n chữ số (n 3) sao cho trong mỗi số đó, có mặt cả ba chữ số 1, 2, 3. Lời giải: Gọi A là tập hợp các số thoả mãn điều kiện bài toán. S là tập hợp các số gồm n chữ số được lập từ ba chữ số đã cho. Ti là tập hợp các số thuộc S mà trong số đó không có mặt chữ số i (i=1,2,3). Ta có: T  X  T1 �T2 �T3 n * T 3 * T1 �T2 �T3  T1  T2  T3  T1 �T2  T2 �T3  T3 �T1  T1 �T2 �T3 dễ tính được: T1 �T2  T2 �T3  T3 �T1  1 , T1 �T2 �T3 = 0 n Vậy: T1 �T2 �T3 = 3. 2n - 3  T  3 -3.2n +3 Bài toán 4: Cho n là số nguyên dương và cho k số nguyên dương a 1, a2, ..., ak đôi một nguyên tố cùng nhau. Tìm số các số nguyên dương a  n sao cho a không chia hết cho ai với mọi i=1, 2, ..., k. ------ Trang 10 ------ * Lời giải: Mỗi i=1, 2, ..., k. Ta đặt Ai   a Σ N / a n, aMai  và A là tập hợp k U Ai các số thoả mãn điều kiện của bài toán thì A  n  (1) i 1 Dễ thấy Ai   ai , 2ai ,..., mi ai  với miN* và thoả mãn: miai  n < (mi+1)ai �n � Σ Nên: Ai  mi  � �. Ai �A j ai � �  �n � Ai �Aj  � � ai a j � � a N * , a n vµ aM  ai a j  (Do (ai, aj) = 1)). � n Hoàn toàn tương tự Ai �Ai �... �Ai  � ai ai ...ai � 1 2 k 1 k Vậy U Ai i 1 k  �Ai  i 1  � 1�i1  i2 �k 2 k � �. � k Ai �Ai  ...  (1) k 1 I Ai 1 2 i 1 k � � �n � � n � n  �� � � � � ...  (1) k 1 � � i 1 a ai ai � a1a2 ...an � �i � 1�i i �k � � 1  2 1 2 � � �n � �n � �n � Ai  n  �� � � � � ...  (1) k �k � i 1 a ai ai � �i � 1�i i �k � � �ai � �i 1 � k 1 2 1 2 Bài toán 5: Cho n là số nguyên dương. Gọi A là tập gồm tất cả các số nguyên dương a �n và  a, n   1 . Xác định A . k k k * Lời giải: Phân tích chuẩn tắc n ta được n  p1 p2 ... pm với ki �� , pi là các ước 1 nguyên tố của n với mọi i. ------ Trang 11 ------ 2 m   *  pi , i  1, m Khi đó A  a Σ � | a n, a M * Gọi Ai   a Σ � | a n, a Mpi  m Suy ra UA i i 1 là tập các số a �n và  a, n   1 Theo nguyên lí bù trừ và bài toán trên ta có: m m i 1 i 1 U Ai  �Ai  � 1�i  j �n Ai �Aj  ...   1 m 1 m I i 1 Ai k � � �n � � n � n  �� � � � � ...  (1) k 1 � � pi � 1�i i �k �pi pi � i 1 � �p1 p2 ... pn � m n n n � 1� � 1 �� 1 � �  �  ...  ( 1) m 1  n� 1 � 1 � ...� 1 � � i 1 p 1�i  j �m p p p1 p2 ... pm p p i i j � 1� � 2 � � pm � Bài toán 6: Cho các số nguyên dương k và n thỏa mãn điều kiện n  k 2  k  1 . Xét n tập hợp A1 , A2 ,..., An thỏa mãn đồng thời các điều kiện: i. Ai  k , i  1,2,..., n ii. Ai �Aj  2k  1, i �j � 1,2,..., n n Tính UA i 1 i . Lời giải: Từ giả thiết suy ra Ai �Aj  1, i �j � 1, 2,..., n Xét một tập bất kì, chẳng hạn Ai . Khi đó A1 �Ai  1, i  2,3,...,n ------ Trang 12 ------ Mà Ai có k phần tử nên theo nguyên lí Dirichlet, phải tồn tại 1 phần tử a �Ai là n 1  k  1. phần tử chung của ít nhất m tập trong các tập A2 , A3 ,..., An với m � k  Aj . Khi đó suy ra Aj �m  1  k , vô lí. Nếu m  n  1 thì sẽ tồn tại Aj mà a � Suy ra m  n  1 hay n I i 1 Ai  1 , suy ra n UA i 1 i  n  k  1  1 Bài toán 7: Cho m quả cầu đôi một khác nhau và n cái hộp đôi một khác nhau (m  n). Có bao nhiêu cách bỏ tất cả các quả cầu vào trong các hộp sao cho hộp nào cũng có ít nhất 1 quả cầu (không kể thứ tự các quả cầu trong mỗi hộp). Khi giải bài toán này, rất nhiều học sinh mắc sai lầm như sau: Trước hết bỏ n vào mỗi hộp một quả cầu: Có Am cách, sau đó phân phối ngẫu nhiên m-n cầu còn n lại vào n cái hộp và có nm-n và kết luận: Am . nm-n cách. Cách giải trên đã mắc sai lầm vì ta không kể thứ tự của các quả cầu trong mỗi hộp. Để giải bài toán này, ta phải dùng nguyên lí bù trừ. Gọi A là số cách bỏ cầu vào hộp thoả mãn điều kiện bài toán; Với mỗi i=1, 2, ..., n ta ký hiệu A i là số cách bỏ cầu vào hộp mà A i không chứa cầu. S là tập hợp tất cả các cách bỏ cầu vào hộp. Thế thì A  S  n UA i 1 i Ta dễ thấy số cách bỏ ngẫu nhiên x quả cầu vào y cái hộp (số lượng cầu trong mỗi hộp không hạn chế và không kể thứ tự các quả cầu trong mỗi hộp) là yx. Thật vậy: Quả cầu thứ nhất có y cách bỏ vào hộp (bỏ vào hộp nào cũng được); quả cầu thứ hai cũng có y cách bỏ vào hộp (bỏ vào hộp nào cũng được, kể cả hộp đã có cầu) ... quả cầu thứ x cũng có y cách bỏ vào hộp. ------ Trang 13 ------ y. y... y  y x Vậy theo quy tắc nhân thì ta có: 1 2 3 cách bỏ hết cầu vào hộp. x Từ nhận xét trên ta thấy: S =nm. Ai   n  1 (bỏ m quả cầu vào n-1 cái hộp m khác hộp Ai) với i=1, 2,..., n Ai �A j   n  2  (bỏ m quả cầu vào n-2 cái hộp khác hộp Ai và Aj), ij m i, j=1, 2,..., n.Tương tự: Ai1 �Ai 2 �... �Aik   n  k  với 1  i1 < i2 < ... < ik  n. m n Từ đó UA i 1 i n  � n  1  m i 1 �  n  2 m 1�i1 i2 �n = Cn1  n  1  Cn2  n  2   ...   1 m A  m  ...   1 n 2 � 1�i1 i2 ...in1 n   n  1 � � � � �n m Cnn1 nm  Cn1  n  1  Cn2  n  2   ...   1 m n 2 m n 1 Cnn 1  n 1 � 1 i 0 i Cni  n  i  m Nhận xét: Bản chất bài toán trên là " Có bao nhiêu toàn ánh f: X Y, trong đó X có m phần tử còn Y có n phần tử, m  n". Bài toán 8: Cho n quả cầu C1,...,Cn và n cái hộp H1,...,Hn. Có bao nhiêu cách bỏ các quả cầu vào hộp, mỗi hộp 1 quả cầu sao cho hộp Hi không chứa quả cầu Ci, i  1,..., n. Ta có thể phát biểu bài toán ở dạng khác: Cho hai tập hợp hữu hạn khác rỗng có cùng số phần tử : X   a1 , a2 ,...an  và Y=  b1 , b2 ,...bn  . Hãy tìm số các song ánh f : X � Y : sao cho (ai)bi, i=1, 2,..., n. Lời giải: Ta ký hiệu A là tập các song ánh f : X � Y thoả mãn điều kiện bài toán; Với mỗi i = 1,..., n. Ta đặt Ai là tập hợp các song ánh f : X � Y mà (ai)=bi; S là tập hợp các song ánh từ X lên Y ------ Trang 14 ------ Ta có nhận xét: Nếu các tập hợp khác rỗng, hữu hạn P, Q có cùng số phần tử là k thì có k! song ánh từ P lên Q (mỗi song ánh tương ứng với 1 hoán vị của k phần tử). Từ nhận xét đó dễ thấy: S =n! Ai   n  1 !, i  1,2,..., n Ai �Ai 2   n  2  !, i �j; 1 i, j  1, 2,..., n . Ai �Ai 2 �... �Ai k   n  k  !, i1 , i2 ,..., ik thoả mãn: 1i1 (2n)! 2 �AI i 1�i  j �n Aj Trong mỗi hoán vị của 2n phần tử có 2n-1 các chọn cặp 2 phần tử kề nhau để đặt hai số k và n + k. Vì vậy Ak = 2(2n - 1)(2n - 2)! = 2(2n - 1)!; n �A k 1 k  (2n)! Tương tự, Trong mỗi hoán vị của 2n phần tử có (2n - 3)(n - 1) các chọn 2cặp, mỗi cặp có 2 phần tử kề nhau để đặt hai số k và n + k và i, n + i. Vì vậy Ai I Aj  8(n  1)(2n  3)!  4(2n  2)! �AI 1�i  j �n i Aj  4Cn2 (2n  2)!  n Cuối cùng ta được: �A k 1 k  �AI 1�i  j �n i n 1 1 (2n)!  (2n)! 2n  1 2 1 Aj  (2n)! 2 Bài toán 12: (VMO-1995, Bảng B). Hỏi từ các số 1, 2, 3, 4, 5 có thể lập được bao nhiêu số có 10 chữ số thỏa mãn đồng thời các điều kiện sau: 1. Trong mỗi số, mỗi chữ số có mặt đúng hai lần 2. Trong mỗi số, hai chữ số giống nhau không đứng cạnh nhau Gợi ý Gọi A là tập gồm tất cả các số có 10 chữ số, lập từ các số 1, 2, 3, 4, 5 thỏa mãn điều kiện (1) của để bài. Với mỗi i kí hiệu Ai là tập gồm tất cả các số thuộc A mà trong mỗi số đều có hai chữ số i đúng cạnh nhau. Suy ra số các số cần tìm là: ------ Trang 17 ------ 5 5 5 A\� A  A� A  A  �Ai  i 1 i i 1 i i 1  5 � i1;i 2;i 31 Ta có: A  Ai1 �Ai 2 �Ai 3  5 �A i 1;i 2 1 5 � i1;i 2;i 3;i 4 1 i1 �Ai 2 5 Ai1 �Ai 2 �Ai 3 �Ai 4  � A i 1 i 10!  10  k  ! ; Ai1 �Ai 2 �... �Aik  5 2 25  k Suy ra kết quả là: 39480 Một số bài tập áp dụng Bài 1: Có n người xếp thành một hàng dọc. Hỏi với mỗi số nguyên dương n �� k ���cho trước có bao nhiêu cách chọn ra k người n người trên sao cho không 2 �� có hai người đứng kề nhau được chọn Bài 2: (Bài đề nghị cho IMO của Trung Quốc năm 1991): Cho s = 1, 2, 3, …, 280. Tìm số tự nhiên n nhỏ nhất sao cho mọi tập hợp con gồm n phần tử của S đều chứa năm số đôi một nguyên tố cùng nhau Bài 3 (VMO - 1995). Cho số nguyên n �2 và cho một đa giác đều 2n đỉnh. Người ta tô tất cả các đỉnh của đa giác đều đó bởi n màu sao cho các điều kiện sau được đồng thời thỏa mãn: 1. Mỗi đỉnh được tô bởi một màu 2. Mỗi màu được dùng để tô cho đúng hai đỉnh không kề nhau Hai cách tô màu, thỏa mãn các điều kiện trên, được gọi là tương đương nếu cách tô màu này có thể nhận được từ cách tô màu kia nhờ một phép quay quanh tâm của đa giác đã cho Hỏi có tất cả bao nhiêu cách tô màu đôi một không tương đương ------ Trang 18 ------ 2. PHƯƠNG PHÁP SỬ DỤNG ÁNH XẠ Để đếm số phần tử của một tập hữu hạn A, ta tìm một tập hữu hạn B có cùng số phần tử như A nhưng dễ đếm hơn. Hoặc khi gặp bài toán yêu cầu chứng minh bất đẳng thức lên quan đến số phần tử của hai tập, ta tìm một ánh xạ ( là đơn hay toàn ánh tùy thuộc vào bất đẳng thức) từ tập này vào tập kia. Điều này được suy ra do nguyên lí ánh xạ. Trước hết có một số kiến thức lý thuyết mở đầu 1. Định nghĩa ánh xạ: Một ánh xạ f từ tập X đến tập Y là một quy tắc đặt tương ứng mỗi phần tử x của X với một và chỉ một phần tử y của Y. Phần tử y được gọi là tạo ảnh của x qua ánh xạ f và được kí hiệu là f  x  . i. Tập X được gọi là tập xác định của f. Tập Y được gọi là tập giá trị của f. ii. Ánh xạ f từ X đến Y được ký hiệu là f : X � Y . 2. Đơn ánh, toàn ánh, song ánh 2.1. Ánh xạ f : X � Y được gọi là đơn ánh nếu với mọi a �ιX , b X , a b thì f  a  �f  b  . Hay với mọi a �X , b �X mà f  a  �f  b  thì a  b . 2.2. Ánh xạ f : X � Y được gọi là toàn ánh nếu với mỗi y �Y đều tồn tại một phần tử x �X sao cho y  f  x  . 2.3. Ánh xạ f : X � Y được gọi là song ánh nếu nó vừa là toàn ánh, vừa là đơn ánh. Nguyên lý ánh xạ. Cho A và B là các tập hữu hạn khác rỗng và f : A � B là một ánh xạ. Khi đó: a) Nếu f là đơn ánh thì A �B ; b) Nếu f là toàn ánh thì A �B ; c) Nếu f là song ánh thì A  B . Chúng ta cùng đến với một số ví dụ mở đầu sau B đây. Bài toán 1: Xét hình chữ nhật 1x4 như hình vẽ. Có bao nhiêu cách để đi từ A đến B trong mỗi A trường hợp sau: a. Chỉ đi lên và qua phải. b. Không có đoạn nào lặp lại. Giải Ta cần đưa việc tính số đường đi thông qua một bộ kí tự mới. a. Ta có thể mã hóa mỗi lần đi lên là số 1, đi qua phải là số 0. Khi đó mỗi đường đi sẽ ứng với một dãy các số 1 và 0, trong đó có đúng 1 số 1 và 4 số 0 ( Ở đây ------ Trang 19 ------ đã xuất hiện song ánh từ tập đường đi với tập bộ số 1, 0 thỏa mãn yêu cầu). Số các dãy đó là số cách chọn 1 vị trí trong 5 vị trí để đặt số 1, có 5 cách. b. Mỗi bước đi có thể coi là một dãy các cách đi lên, qua phải, đi xuống (không được đi qua trái vì nếu thế sẽ có đoạn lặp lại). Có thể thấy sau mỗi bước đi lên hoặc đi xuống thì phải qua phải, vì vậy ta chỉ quan tâm đến đường đi bên trên và đường đi bên dưới. B Ví dụ dãy: LPPXPLP, ta coi nó như dãy TTDT. Như vậy số cách thỏa mãn bằng số cách sắp xếp 2 kí tự T, D vào 4 vị trí mà không cần điều kiện gì ràng buộc, số cách là 24 . A Bài toán 2: Cho hình chữ nhật m �n  m  n  với đỉnh dưới cùng bên trái là A, trên cùng bên phải là B. Có bao nhiêu cách đi từ A đến B trong mỗi trường hợp sau: a. Chỉ được đi lên và qua phải. b. Chỉ được đi lên và qua phải nhưng không được chạm vào đường AC (không kể điểm A). c. Chỉ được đi lên và qua phải nhưng không đi qua điểm I (là giao của dòng i và cột j). Giải a. Tương tự như ý a của bài toán 1, ta có thể mã hóa mỗi lần đi lên là số 1, đi qua phải là số 0. Khi đó mỗi đường đi sẽ ứng với một dãy các số 1 và 0, trong đó có đúng m số 1 và n số 0. Số các dãy đó là số cách chọn m vị trí trong m  n vị trí để đặt số 1, ta m được kết quả là Cm n . b. Đi từ A đến B mà không chạm AC, nghĩa là bước đầu phải qua D. Số bước đi từ A đến B không chạm AC bằng số cách đi từ D đến B mà không chạm AC bằng số cách đi từ D đến B trừ đi số cách đi từ D đến B mà chạm vào AC. ------ Trang 20 ------