Bài giảng Nhập môn Lý thuyết Tổ hợp - Chương 1: Mở đầu - Nguyễn Anh Thi

Bài giảng Nhập môn Lý Thuyết Tổ Hợp Nguyễn Anh Thi ĐH KHTN, Tp HCM 2017 Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 1 / 13 Chương 1 MỞ ĐẦU Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 2 / 13 Nội dung Nội dung 1 Nguyên lý chuồng bồ câu 2 Phương pháp quy nạp toán học Quy nạp yếu Quy nạp mạnh Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 3 / 13 Nguyên lý chuồng bồ câu Nguyên lý chuồng bồ câu (Derichlet) Gọi dxe là số nguyên nhỏ nhất lớn hơn hay bằng x. Giả sử có n chim bồ câu trong k chuồng. Khi đó tồn tại ít nhất một chuồng chứa từ dn/ke bồ câu trở lên. Ví dụ Trong nhóm có 367 người thì ít nhất có 2 người sinh cùng ngày. Ví dụ Chứng minh rằng trong 10 số tự nhiên bất kỳ có thể chọn 2 số có hiệu chia hết cho 9. HD: Khi chia 10 số bất kỳ cho 9 ta sẽ có mỗi số có một số dư trong 9 số dư: 0, 1, 2, . . . , 8. Do đó theo nguyên lý chuồng bồ câu phải tồn tại ít nhất hai số có cùng số dư. Hiệu của hai số đó sẽ chia hết cho 9. Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 4 / 13 Nguyên lý chuồng bồ câu Ví dụ Trong một lớp học phải có ít nhất bao nhiêu học sinh để cho có ít nhất 6 học sinh chơi cùng một nhạc cụ, biết rằng có 5 loại nhạc cụ các học sinh được chọn học là A,B,C,D và E. HD: Gọi số học sinh của lớp là N. Theo nguyên lý chuồng bồ câu ta có dN5 e = 6. Khi đó 25 < N ≤ 30 Do đó ta có thể chọn N = 26. Vậy lớp phải có ít nhất 26 học sinh. Ví dụ Cho tập X = {1, 2, 3, 4, 5, 6, 7, 8, 9}. Lấy A là tập hợp con của X gồm 6 phần tử. Khi đó trong A sẽ có hai phần tử có tổng là 10. HD: Ta lập các chuồng như sau: {1, 9}, {2, 8}, {3, 7}, {4, 6}, {5}. Do A có 6 phần tử nên trong 6 phần tử đó sẽ có 2 phần tử trong 1 chuồng. Ta được điều cần chứng minh. Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 5 / 13 Nguyên lý chuồng bồ câu Ví dụ Chứng minh rằng tồn tại một số trong dãy các số 7, 77, 777, 7777, · · · chia hết cho 2003. HD: Giả sử không tồn tại số nào trong dãy trên chia hết cho 2003. Ta chọn ra 2003 số hạn đầu tiên của dãy trên và lần lượt chia chúng cho 2003. Do không có số nào chia hết cho 2003, nên các số dư của chúng ít nhất là 1 và nhiều nhất là 2002. Ta có 2003 số dư, và chỉ có 2002 giá trị mà các số dư có thể nhận được. Theo nguyên lý chuồng bồ câu thì sẽ có ít nhất hai số có cùng số dư khi chia cho 2003. Giả sử ta gọi hai số đó nằm ở vị trí thứ i và thứ j trong dãy trên, với i < j ta gọi chúng là ai và aj. Khi đó ai = 2003ki + r, và aj = 2003kj + r. Suy ra aj − ai = 2003(kj − ki) chia hết cho 2003. Dễ dàng thấy rằng aj − ai = 77 . . . 7× 10i. Mà 10i và 2003 là hai số nguyên tố cùng nhau, nên suy ra 77 . . . 7 chia hết cho 2003. Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 6 / 13 Nguyên lý chuồng bồ câu Ví dụ Chứng minh rằng nếu có 10 điểm nằm trong một hình vuông đơn vị thì có ít nhất hai điểm trong chúng có khoảng cách gần hơn √ 2 3 , và có ít nhất ba điểm trong chúng nằm trong một vòng tròn bán kính 12 . HD: -Ta chia hình vuông ra thành 9 ô vuông bởi các đường thẳng như hình vẽ Bởi vì có 10 điểm được đặt trong 9 hình vuông nên có ít nhất một hình vuông chứa 2 điểm. Khoảng cách 2 điểm trong hình vuông nhỏ thì nhỏ hơn hoặc bằng độ dài đường chéo, tức là bằng √ 2 3 . Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 7 / 13 Nguyên lý chuồng bồ câu HD:-Ta chia hình vuông ra thành 4 phần như hình vẽ Theo nguyên lý chuồng bồ câu có ít nhất 3 điểm nằm trong một tam giác nhỏ. Ta thấy mỗi tam giác nhỏ thì nội tiếp trong một đường tròn có bán kính là 12 . Do đó ta được điều cần chứng minh. Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 8 / 13 Phương pháp quy nạp toán học Quy nạp yếu Phương pháp: Khi chứng minh một khẳng định nào đó đúng với mọi số nguyên dương m bằng phương pháp quy nạp yếu, ta sẽ chứng minh theo các bước sau: Chứng minh khẳng định đúng cho trường hợp m nhận các giá trị nhỏ nhất, (thường là 0, 1, 2 . . . ). Giả sử khẳng định đúng với m = n. Ta chứng minh khẳng định đúng với m = n+ 1. Ví dụ Với mọi số nguyên dương m, chứng minh rằng 12 + 22 + · · ·+m2 = m(m+ 1)(2m+ 1)6 . Ví dụ Cho A =  1 1 00 1 1 0 0 1 . Tính An, với n là một số nguyên dương nào đó. Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 9 / 13 Phương pháp quy nạp toán học Quy nạp yếu Ví dụ Cho a0 = 0, và an+1 = 3an + 1 với mọi số nguyên dương n. Tìm một công thức cho am. HD: Ta thử tính những giá trị đầu tiên của dãy số trên: 1, 4, 13, 40, 121, . . . . Có thể đoán được dạng của dãy số trên là am = (3m − 1)/2. Ta sẽ chứng minh khẳng định này bằng quy nạp. Dễ dàng thấy rằng kết luận đúng với trường hợp m = 0, 1. Giả sử khẳng định đúng với m = n. Ta chứng minh khẳng định đúng với m = n+ 1. Theo giả thiết quy nạp ta có an+1 = 3an + 1 = 3.(3n − 1) 2 + 1 = 3n+1 − 1 2 . Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 10 / 13 Phương pháp quy nạp toán học Quy nạp yếu Ví dụ Với mọi số nguyên dương n, chứng minh rằng số các tập con của tập [n] là 2n. HD: Với n = 1, ta thấy tập [1] có hai (21) tập con là {1}, ∅. Giả sử khẳng định đúng với n = k, ta chứng minh khẳng định đúng với n = k+ 1. Ta chia các tập con của [n+ 1] ra thành hai nhóm. Nhóm một chứa phần tử n+ 1 và nhóm hai không chứa phần tử n+ 1. Ta dễ dàng thấy số phần tử của nhóm hai là 2n, chính là số tập con của [n]. Nhóm chứa n+ 1 gồm tập con của n và n+ 1. Do đó số phần tử của nhóm này cũng là 2n. Suy ra số tập con của [n+ 1] là 2n + 2n = 2n+1. Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 11 / 13 Phương pháp quy nạp toán học Quy nạp mạnh Phương pháp Khi chứng minh một khẳng định nào đó đúng với mọi số nguyên dương m bằng phương pháp quy nạp mạnh, ta sẽ chứng minh theo các bước sau: Chứng minh khẳng định đúng cho trường hợp m nhận các giá trị nhỏ nhất, (thường là 0, 1, 2 . . . ). Giả sử khẳng định đúng với mọi số nguyên m nhỏ hơn hay bằng n. Ta chứng minh khẳng định đúng với m = n+ 1. Ví dụ Cho dãy số {an} được định nghĩa như sau a0 = 0, và an+1 = a0 + a1 + a2 + · · ·+ an + n+ 1 với n ≥ 1. Chứng minh rằng với mọi số nguyên n, ta có an = 2n − 1. HD: Với n = 0, ta thấy khẳng định đúng. Giả sử khẳng định đúng với mọi số nguyên m nhỏ hơn hay bằng n, ta chứng minh khẳng định đúng với m = n+ 1. Bởi quan hệ đệ quy ta có an+1 = a0 + a1 + · · ·+ an + n+ 1 = (20−1)+(21−1)+ · · ·+(2n−1)+n+1 = 1+2+4+ · · ·+2n = 2n+1−1. Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 12 / 13 Phương pháp quy nạp toán học Quy nạp mạnh Ví dụ Cho hàm f : N→ N thỏa mãn điều kiện f(m+ n) = f(m) + f(n) với mọi m và n. Chứng minh rằng tồn tại một hằng số c sao cho f(n) = cn. HD: Với m = 0, ta có f(n+ 0) = f(n) + f(0), suy ra f(0) = 0. Giả sử khẳng định đúng với mọi số nguyên dương nhỏ hơn hay bằng n. Nghĩa là tồn tại một hằng số c sao cho f(k) = ck với k ≤ n. Ta có f(n+ 1) = f(n) + f(1) = cn+ c = c(n+ 1). Nguyễn Anh Thi ( ĐH KHTN, Tp HCM) Bài giảng Nhập môn Lý Thuyết Tổ Hợp 2017 13 / 13