Sử dụng một số nguyên lí của toán rời rạc vào bài toán đếm bồi dưỡng sinh viên Olympic

Toán rời rạc là một dạng toán khó và có vai trò quan trọng trong việc rèn luyện kĩ năng giải toán và giải quyết các vấn đề trong thực tiễn cho sinh viên. Các bài toán rời rạc được coi trọng trong chương trình môn toán phổ thông và đại học, cao đẳng của nhiều nước trên thế giới. Ở nước ta, do nhiều nguyên nhân khác nhau, dạng toán này còn chưa đề cập nhiều trong chương trình, chủ yếu được bổ sung cho học sinh giỏi thi các đội tuyển toán.
Nội dung trích xuất từ tài liệu:
Sử dụng một số nguyên lí của toán rời rạc vào bài toán đếm bồi dưỡng sinh viên OlympicNo.10_Dec2018|Số 10 – Tháng 12 năm 2018|p.12-21 TẠP CHÍ KHOA HỌC ĐẠI HỌC TÂN TRÀO ISSN: 2354 - 1431 http://tckh.daihoctantrao.edu.vn/Sử dụng một số nguyên lí của toán rời rạc vào bài toán đếm bồi dưỡngsinh viên OlympicLê Thiếu Tránga*aTrường Đại học Tân Trào*Email: lttrang0466@tuyenquang.edu.vnThông tin bài viết Tóm tắtNgày nhận bài: Toán rời rạc là một dạng toán khó và có vai trò quan trọng trong việc rèn luyện07/11/2018 kĩ năng giải toán và giải quyết các vấn đề trong thực tiễn cho sinh viên. Các bàiNgày duyệt đăng: toán rời rạc được coi trọng trong chương trình môn toán phổ thông và đại học,10/12/2018 cao đẳng của nhiều nước trên thế giới. Ở nước ta, do nhiều nguyên nhân khác nhau, dạng toán này còn chưa đề cập nhiều trong chương trình, chủ yếu đượcTừ khoá: bổ sung cho học sinh giỏi thi các đội tuyển toán. Tuy nhiên, nếu không nắmSinh viên; tổ hợp; bài toánđếm; nguyên lí; qui tắc; được mạch kiến thức và phân loại đầy đủ, sinh viên trong đội tuyển Olympicrời rạc toán cũng làm chưa tốt dạng toán này. Do vậy, việc trang bị kiến thức từ cơ bản đến nâng cao giúp cho sinh viên có thể giải quyết tốt dạng toán này. I. Một số kiến thức cơ bản về tổ hợp  X 1  a, b, c  X1  3 . 1. Qui tắc đếm X 2 là tập hợp loại có 2 chữ số a. Qui tắc cộng: Một công việc được thực hiện theomột trong k phương án A1 , A2 ,..., Ak .    X 2  ab, ac, ba , bc, ca , cb  X 2  6 . Có n1 cách thực hiện phương án A1 , n 2 cách X 3 là tập hợp loại có 3 chữ sốthực hiện phương án A2 ,..., n k cách thực hiện phương  X 3  abc , acb, bca , bac , cab, cba  X 3  6.  án Ak . Khi đó có n1  n2  ...  nk cách thực hiệnmột trong các phương án trên. Vậy có tất cả: X1  X 2  X 3 =3+6+6=15 số Quan điểm tập hợp: Nếu tập hợp hữu hạn X là thỏa mãn bài toán.hợp của n tập hợp đôi một rời nhau X 1 , X 2 ,..., X n b. Qui tắc nhân: Một công việc được thực hiện baothì X  X 1  X 2  ...  X n , gồm k công đoạn A1 , A2 ,..., Ak . Công đoạn A1 có n1 cách thực hiện; Mỗi cách ( X là số phần tử của tập hợp X ). thực hiện công đoạn A1 có có n 2 cách thực hiện công Ví dụ 1: Từ tập X  a, b, c , lập được bao nhiêu đoạn A2 ; …..; Mỗi cách thực hiện công đoạn A1 ,số tự nhiên, mỗi số có các chữ số khác nhau? A2 ,…, Ak 1 có n k cách thực hiện công đoạn Ak . Giải: Lập phương án đếm: Đếm loại có 1 chữ số,loại có 2 chữ số và loại có 3 chữ số. Khi đó công việc được thực hiện bởi n1 .n2 ...nk cách. X 1 là tập hợp loại có 1 chữ số Quan điểm tập hợp: Nếu X 1 , X 2 ,..., X n là các tập hợp hữu hạn thì:12 L.T.Trang / No.10_Dec 2018|p.12-21 X1  X 2  ...  X n  X1 . X 2 ... X n , Số các hoán vị lặp của tập hợp X là:( X1  n! X 2  ...  X n là tích Đề các của n tập hợp). Pn  k1 !k 2 !...k p ! Ví dụ 2: Một chiếc cặp số, mã khóa là một bộ 3 sốkết hợp của 3 vòng số, mỗi vòng gồm 10 số: 0, 1,…, 9. Ví dụ 4: Từ chữ BENZEN , có thể lập được baoMột người quên mã khóa, hỏi người đó phải thử nhiều nhiêu từ khác nhau? ...