Tài liệu Skkn một số phương pháp giải đếm nâng cao

SỞ GIÁO DỤC VÀ ĐÀO TẠO ĐỒNG NAI Đơn vị:Trường THPT Chuyên Lương Thế Vinh Mã số: ................................ (Do HĐKH Sở GD&ĐT ghi) SÁNG KIẾN KINH NGHIỆM MỘT SỐ PHƯƠNG PHÁP GIẢI ĐẾM NÂNG CAO Người thực hiện: NGUYỄN TẤT THU Lĩnh vực nghiên cứu: - Quản lý giáo dục  - Phương pháp dạy học bộ môn: Toán học  - Lĩnh vực khác: .......................................................  Có đính kèm: Các sản phẩm không thề hiện trong bản in SKKN  Mô hình  Phần mềm  Phim ảnh  Hiện vật khác Năm học: 2013 – 2014 SƠ LƯỢC LÝ LỊCH KHOA HỌC I. THÔNG TIN CHUNG VỀ CÁ NHÂN 1. Họ và tên: Nguyễn Tất Thu 2. Ngày tháng năm sinh: 13-09-1980 3. Nam, nữ: Nam 4. Địa chỉ: Tổ 10 – KP5 - Trảng Dài – Biên Hoà - Đồng Nai 5. Điện thoại: (CQ)/ (NR); ĐTDĐ:0942444556 6. Fax: E-mail: [email protected] 7. Chức vụ: Giáo viên 8. Đơn vị công tác: Trường THPT Chuyên Lương Thế Vinh II. TRÌNH ĐỘ ĐÀO TẠO - Học vị (hoặc trình độ chuyên môn, nghiệp vụ) cao nhất: Thạc sĩ - Năm nhận bằng: 2013 - Chuyên ngành đào tạo: Lí luận và phương pháp dạy học bộ môn Toán III.KINH NGHIỆM KHOA HỌC - Lĩnh vực chuyên môn có kinh nghiệm: Giảng dạy môn Toán Số năm có kinh nghiệm: 11 nằm - Các sáng kiến kinh nghiệm đã có trong 5 năm gần đây: 1. Một số phương pháp xác định CTTQ của dãy số - năm 2008 2. Sử dụng hàm lồi trong chứng minh bất đẳng thức – năm 2009 3. Sử dụng phép đếm để chứng minh đẳng thức tổ hợp – năm 2010 4. Một số phương pháp giải bài toán cực trị tổ hợp – năm 2012 5. Một số phương pháp giải bài toán tồn tại trong tổ hợp – năm 2013 MỘT SỐ PHƯƠNG PHÁP ĐẾM NÂNG CAO I. LÝ DO CHỌN ĐỀ TÀI Chủ đề tổ hợp thường xuyên xuất hiện trong các kỳ thi chọn học sinh giỏi và đây là chủ đề được đánh giá là khó nhất trong đề thi. Về toán tổ hợp ta thường gặp bài toán ở dạng yêu cầu chúng ta đi đếm số cách thực hiện một công việc nào đó. Đây là một dạng toán khó và có nhiều phương pháp để giải. Để giúp học sinh chuyên toán có được những nên tảng vững chắc về các bài toán đếm, chúng tôi hệ thống và minh họa một số phương pháp đếm nâng cao. Đó là lí do mà tôi chọn đề tài: “Một số phương pháp đếm nâng cao” làm đề tài nghiên cứu của mình. II. TỔ CHỨC THỰC HIỆN ĐỀ TÀI 1. Cơ sở lí luận 2. Tiến trình thực hiện để tài 2.1. Phương pháp song ánh Tính chất: Cho A, B là hai tập hợp hữu hạn và ánh xạ f : A → B . Khi đó: • Nếu f là đơn ánh thì A ≤ B • Nếu f là toàn ánh thì A ≥ B • Nếu f là song ánh thì A = B Do đó thay vì đếm số phần tử của A , ta đi đếm số phần tử của B . Ví dụ 1. Cho X = { a1 ,a 2 ,...,a n } với n là số tự nhiên dương, k là số tự nhiên thỏa k≤n. { } Đặt S = (a i1 ,a i2 ,...,a ik ) a i1 ,a i 2 ,...,a i k ∈ X ;1 ≤ i1 ≤ i 2 ≤ ... ≤ i k ≤ n . Tính số phần tử của tập S. Lời giải. Ta có: (a i1 ,a i2 ,...,a ik ) → ( i1 ,i 2 ,...,i k ) là một song ánh từ tập S vào tập S1 gồm các bộ ( i1 ,i 2 ,...,i k ) với 1 ≤ i1 ≤ i 2 ≤ ... ≤ i k ≤ n nên S = S1 . Khó khăn gặp phải khi đếm các bộ của tập S1 là các số i1 ,...,i k có thể bằng nhau. Do đó, ta tìm các phá bỏ các dấu “=” ở trong bất đẳng thức 1 ≤ i1 ≤ i 2 ≤ ... ≤ i k ≤ n . Tức là, ta đưa về đếm các bộ ( j1 , j2 ,..., jk ) với 1 ≤ j1 < j2 < ... < jk ≤ n . Để thực hiện được điều đó, ta tịnh tiến các chỉ số i1 ,i 2 ,...,i k mỗi chỉ số tăng thêm một đơn vị so với chỉ số trước nó. Dẫn tới, ta đi xét tương ứng sau Xét tương ứng ( i1 ,i 2 ,...,i k ) ∈ S1 → ( i1 ,i 2 + 1,...,i k + k − 1) . Rõ ràng, đây là một song ánh từ S1 và tập S 2 là tập gồm các bộ ( j1 , j2 ,..., jk ) sao cho j1 , j2 ,..., jk ∈ { 1,2,...,n + k − 1} và j1 < j2 < ... < jk Suy ra S1 = S 2 = Cnk + k −1 . Hệ quả: Số nghiệm nguyên không âm của phương trình: x1 + x2 + ... + x k = n là Ckn + k −1 . Hệ quả: Số nghiệm nguyên dương của phương trình: x1 + x2 + ... + x k = n là Ckn−−11 . Ví dụ 2. Trong một giải bóng đá có 10 trận đấu và được diễn ra trong vòng 30 ngày. Hỏi ban tổ chức có bao nhiêu cách sắp xếp các trận đá bóng sao cho hai trân đấu kế nhau phải cách nhau ít nhất một ngày. Lời giải. Cách 1: Giả sử trận đấu thứ i được xếp vào ngày xi . Khi đó, mỗi cách xếp các trận đấu tương ứng với một bộ 10 số ( x1 ,x 2 ,...,x10 ) thỏa các điều kiện sau • 1 ≤ x1 < x 2 < x 3 < ... < x10 ≤ 30 • xi +1 − xi ≥ 2 với mọi i = 1,29 . Nếu các bộ ( x1 ,x 2 ,...,x10 ) chỉ thỏa mãn điều kiện thứ nhất thì việc đếm trở nên đơn giản. Khó khăn ở đây là điều kiện thứ 2. Điều kiện này bắt buộc các số x1 ,x2 ,...,x10 không có hai số nào là hai số tự nhiên liên tiếp, do đó ta tìm cách chuyển về hai số kề nhau có thể là hai số tự nhiên liên tiếp để đếm. Ta có x 2 − x1 ≥ 2 ⇔ x 2 − x1 > 1 ⇔ x 2 − 1 > x1 nên hai số x 2 − 1 và x1 có thể là hai số tự nhiên liên tiếp. Tương tự như vậy, ta có xi +1 − 1 và xi có thể là hai số tự nhiên liên tiếp. Dẫn đến, ta sẽ chuyển bộ ( x1 ,x2 ,...,x10 ) về bộ ( x1 ,x 2 − 1,x3 − 2...,x10 − 9 ) . Gọi A là tập các bộ ( x1 ,x 2 ,...,x10 ) thỏa mãn các điều kiện trên B= { ( y1 ,...,y10 ) 1 ≤ y1 < y2 < ... < y10 ≤ 21} Xét ánh xạ f : A → B được xác định như sau f ( x1 ,...,x10 ) = ( x1 ,x 2 − 1,x 3 − 2,...,x10 − 9 ) Ta chứng minh được f là một song ánh Do đó A = B = C10 21 = 352716 . Cách 2: Giả sử giữa ngày thứ nhất đến ngày trận đấu thứ nhất có x1 ngày, giữa trận đấu thứ nhất và trận đấu thứ 2 có x 2 ngày,..., giữa trận đấu thứ 10 đến ngày thứ 30 có x11 ngày. Khi đó, mỗi cách xếp 10 trận đấu tương ứng với một bộ ( x1 ,x 2 ,...,x11 ) thỏa các điều kiện sau • x1 ,x11 ≥ 0; x 2 ,x 3 ,...,x10 ≥ 1 • x1 + x2 + ... + x11 = 30 − 10 = 20 Đặt y1 = x1 ,y11 = x11 ,y i = xi − 1, ∀i = 2,10 Khi đó, mỗi bộ ( x1 ,x 2 ,...,x11 ) tương ứng với một bộ ( y1 ,y 2 ,...,y11 ) thỏa y1 ,y 2 ,...,y11 ≥ 0 và y1 + y 2 + ... + y11 = 11 (*). Số các bộ ( y1 ,y 2 ,...,y11 ) chính là số nghiệm không âm của phương trình (*) và 11 bằng C11 11+11−1 = C 21 . Vậy có C11 21 = 352716 cách xếp 10 trận đấu thỏa các yêu cầu bài toán. Ví dụ 3. Cho đa giác đều 2013 đỉnh. Người ta tô 100 đỉnh của đa giác bởi màu đỏ. Hỏi có bao nhiêu cách tô sao cho giữa hai đỉnh được tô màu kề nhau có ít nhất 3 đỉnh không được tô màu. Lời giải. Gọi các đỉnh của đa giác là A1 ,A 2 ,...,A 2013 Giả sử ta tô màu các đỉnh Ai ,Ai ,...,A i . Khi đó, mỗi cách tô màu thỏa yêu 1 2 100 cầu bài toán ứng với bộ ( i1 ,i 2 ,...,i100 ) thỏa các điều kiện sau • 1 ≤ i1 < i 2 < ... < i100 ≤ 2013 • i k +1 − i k ≥ 4 với ∀k = 1,2012 và 2013 + i1 − i 2013 ≥ 4 . Ta thấy i k +1 − i k ≥ 4 ⇔ i k +1 − i k > 3 ⇔ i k +1 − 3 > i k , do đó ta sẽ thay thế các i k bởi i k − 3(k − 1) . Gọi S là tập các bộ ( i1 ,i 2 ,...,i100 ) thỏa các điều kiện nói trên, S1 là tập các bộ (a1 ,a 2 ,...,a100 ) thỏa • 1 ≤ a1 < a 2 < ... < a100 ≤ 1716 • a100 − a1 ≤ 1712 . Khi đó, ánh xạ f : S → S1 được xác định f(i1 ,i 2 ,...,i100 ) = ( a1 ,a 2 ,...,a100 ) với a k = i k − 3(k − 1), k = 1,100 Dễ dàng kiểm chứng được f là một song ánh. Ta xét các trường hợp sau • a1 ∈ { 1,2,3} , đặt bi = a i − a1 . Khi đó, ánh xạ g đi từ S1 và tập S 2 là tập các bộ ( b1 ,b2 ,...,b100 ) thỏa 1 ≤ b2 < b3 < ... < b100 ≤ 1712 là một song ánh. Ta có 99 S 2 = 3.C1712 . • a1 ≥ 4 . Đặt ci = a i − 3 . Khi đó, ánh xạ h đi từ S1 vào S 3 gồm các bộ ( c1 ,c2 ,...,c100 ) thỏa 1 ≤ c1 < c2 < ... < c100 ≤ 1713 là một song ánh và 100 . S 3 = C1713 99 100 Vậy S = S 2 + S 3 = 3.C1712 . + C1713 Ví dụ 4. Có bao nhiêu chỉnh hợp chập k (a1 ,a 2 ,...,a k ) của n số tự nhiên đầu tiên thỏa ít nhất một trong hai điều kiện sau i) Tồn tại i, j ∈ { 1,2,...,k} thỏa a i > a j và i < j Tồn tại i ∈ { 1,2,...,k} sao cho a i − i là số lẻ. Lời giải. Gọi S là tập các chỉnh hợp chập k của n số tự nhiên đầu tiên. Ta có n! S = A kn = . (n − k)! Gọi A là tập các chỉnh hợp thỏa yêu cầu bài toán. B = { a = (a1 ,a 2 ,...,a k ) ∈ S} và các a i thỏa mãn đồng thời hai điều kiện sau (a) a i +1 > a i với mọi i = 1,k − 1 ii) (b) a i − i luôn là số chẵn với mọi i = 1,k . Ta có A = S − B . Ta đi tính B = ? Với mỗi bộ (a1 ,a 2 ,...,a k ) ⊂ { 1,2,3,...,n} thì tồn tại duy nhất một chỉnh hợp chập k (a1 ,a 2 ,...,a k ) thỏa điều kiện (a). Do đó, ta chỉ cần đi phân tích điều kiện (b) Vì a i − i là số chẵn khi và chỉ khi a i + i là số chẵn. Hơn nữa giá trị của a i − i ta khó kiểm soát còn các giá trị của a i + i chỉ thuộc vào tập { 1,2,3,...,k + n} nên ta xét ánh xạ f từ tập B và tập C được xác định bởi f(a1 ,a 2 ,...,a k ) = ( b1 ,b 2 ,...,b k ) với bi = a i + i và C là tập gồm các bộ ( b1 ,b2 ,...,bk ) thỏa bi là số chẵn ∀i = 1,k và bi ∈ { 1,2,...,n + k} . Ta chứng minh được f là song ánh. Vì vậy B = C = Ck  n+k  .  2    A = Ckn − Ck  n+k  . Vậy  2    Ví dụ 5. Cho một tam giác đều cạnh bằng n . Chia tam giác này thành n 2 tam giác đều cạnh bằng 1 bởi các đường thẳng song song với các cạnh của tam giác đó. Tính số hình bình hành nằm trong tam giác và được tạo bởi các đường thẳng trên. Lời giải. Kí hiệu các đỉnh của tam giác đều cạnh n là ABC và S là tập các hình bình hành cần tính. Tập hợp các hình bình hành cần tính được phân hoạch thành ba nhóm rời nhau là S BC ,SCA ,S AB . Trong đó S BC là tập gồm các hình bình hành có hai cặp cạnh song song với AB và AC ; SCA ,S AB được định nghĩa tương tự. Ta thấy S BC = SCA = S AB và S = 3 S BC . Ta đi tính S BC = ? . Trên các tia AB,AC kéo dài ta lấy các điểm B',C' sao cho BB' = CC' = 1 . Ta chia đoạn B'C' thành n + 1 đoạn bằng nhau B'A1 ,A1A 2 ,...,A nC' Với mỗi hình bình hành thuộc S BC , ta kéo dài các cạnh của hình bình hành, cắt B'C' tại 4 điểm phân biệt thuộc vào tập các điểm T = { B',A1 ,...,A n ,C'} . Khi đó mỗi hình bình hành sẽ tương ứng với 4 điểm thuộc T và ngược lại với 4 điểm thuộc T cho ta một hình bình hành thuộc S BC . Chẳng hạn, trong hình vẽ: Hình bình hành được tô đậm miền trong sẽ tương ứng với 4 điểm B',D,E,F , còn hình bình hành được tô đậm 4 cạnh tương ứng với 4 điểm C',H,F,D . Do đó mỗi hình bình hành thuộc S BC tương ứng với bộ 4 điểm thuộc T nên S BC = Cn4 + 2 . Vậy S = 3C4n + 2 . Ví dụ 6. Cho A là tập hữu hạn các số thực dương. Ta định nghĩa B và C là các tập sau x  B =  x,y ∈ A  , C = xy x,y ∈ A . y  { } 2 Chứng minh rằng A . B ≤ C .  x1 x 2 x k  B = , ,..., Giả sử   yk   y1 y 2 Lời giải. xi với các phân số phân biệt. yi  x  Xét ánh xạ f : A × B → C 2 được xác định bởi f  z; i ÷ = ( zxi ; zyi )  yi   xj   xi   z'; ÷ mà f(a) = f(b) , ta có: a = z; , b = Xét  ÷  yj ÷ y  i   xi z = x jz' xi = x j xi x j ⇒ = ⇒ ⇒ z = z' ⇒ a = b .   y z = y z' y = y y y j i j j  i  i Vậy f là đơn ánh. 2 Suy ra A × B ≤ C × C ⇒ A . B ≤ C . 2.2. Đếm bằng hệ thức truy hồi Nội dung của phương pháp truy hồi là để đếm số phần tử của một tập hợp hữu hạn X , ta phân hoạch X thành các tập con rời nhau X1 ,X 2 ,...,X k . Khi đó X = X1 + X 2 + ... + X k Do đó, để đi đếm số phần tử của tập X ,ta đi đếm số phần tử của các tập có số lượng phần tử nhỏ hơn là X1 ,X 2 ,...,X k . Ví dụ 1. Cho tập hợp A có n (n ≥ 1) phần tử. Hãy tính số tập con của tập A . Lời giải. Gọi S n là tập hợp gồm tập con của tập A = { 1,2,3,...,n} và a n = S n . Ta phân hoạch tập S n thanh hai tập X gồm các tập con chứa n và Y gồm các tập con không chứa n . Khi đó a n = X + Y . • Tính X Với mỗi tập con T ∈ X , ta có T = T'∪ { n} , trong đó T' là một tập con của tập { 1,2,...,n − 1} . Khi đó, ánh xạ f : X → S n −1 , f ( T ) = T' là một song ánh. Do đó X = S n −1 = a n −1 . • Tính Y Vì mỗi tập con H thuộc Y , ta có H không chứa n nên H là một tập con của tập { 1,2,...,n − 1} và ngược lại. Do đó, Y = Sn −1 = a n −1 . Suy ra a n = a n −1 + a n −1 = 2a n −1 = 2 n −1.a1 = 2 n . Nhận xét: Mẫu chốt của lời giải trên là ta đi phân hoạch tập S n thành 2 tập. Một tập gồm các tập con chứa n và một tập gồm các tập con không chứa n , rồi đi tính số phần tử của mỗi tập đã được phân hoạch đó. Ví dụ 2. Cho n là số nguyên dương. Có bao nhiêu xâu kí tự độ dài n : a1a 2 ...a n với kí tự a i lấy trong các số { 0,1,2,...,9} mà số lần xuất hiện của số 0 trong xâu kí tự là số chẵn. Lời giải. Đặt A n là số xâu kí tự có độ dài n mà số lần xuất hiện của số 0 là số chẵn và a n = A n Ta thấy a1 = 9 Vì có 10n xâu kí tự có độ dài n nên số xâu kí tự độ dài n mà trong đó số xuất hiện của chữ số 0 là số lẻ bằng 10 n − a n . Ta phân hoạch tập A n thành hai tập rời nhau X,Y như sau : { X = x ∈ A n x = 0a 2a 3 ...a n } { } và Y = x ∈ A n x = a1a 2 ...a n , a1 ≠ 0 Ta tính X Với x ∈ X thì xâu kí tự a 2 ...a n có độ dài n − 1 và số xuất hiện của chữ số 0 trong xâu là số lẻ. Do đó ta có X = 10 n −1 − a n −1 . Ta tính Y Với x = a1a 2 ...a n ∈ Y thì xâu a 2a 3 ...a n có độ dài n − 1 và số lần xuất hiện của số 0 là số chẵn. Do đó, có a n −1 xâu a 2a 3 ...a n như vậy. Với mỗi xâu a 2a 3 ...a n ∈ A n −1 ta có 9 cách chọn a1 . Suy ra Y = 9a n −1 . Do đó a n = 10 n −1 − a n −1 + 9a n −1 = 8a n −1 + 10 n −1 . Từ đây, ta tìm được a n = 4.8 n −1 + 5.10n −1 , n ≥ 1 . Ví dụ 3. Có bao nhiêu hoán vị (a1 ,a 2 ,...,a n ) của tập { 1,2,3,...,n} sao cho tồn tại duy nhất một chỉ số i sao cho a i > a i +1 . Lời giải. Gọi S n là tập các hoán vị (a1 ,a 2 ,...,a n ) của tập { 1,2,3,...,n} sao cho tồn tại duy nhất một chỉ số i sao cho a i > a i +1 và đặt x n = S n . Rõ ràng với mỗi x = ( a1 ,a 2 ,...,a n ) ∈ S n thì x chỉ có thể xảy ra ba dạng sau +) a n = n , gọi tập các hoán vị thuộc dạng này là tập X +) a i = n , a i −1 > a i +1 còn a j < a j+1 , ∀j ∉ { i − 1,i} , gọi tập các hoán vị thuộc dạng này là Y +) a i = n và a j < a j+1 , ∀j ≠ i , gọi tập các hoán vị thuộc dạng này là Z . Khi đó tập S n được phân hạch thành ba tập X,Y,Z nên S n = X + Y + Z . Dễ thấy X = x n −1 Với mỗi hoán thuộc tập Y , khi ta bỏ a i thì ta thư được một hoán vị thuộc S n −1 và ngược lại mỗi hoán vị thuộc S n −1 ta chèn thêm n vào giữa a i và a i +1 (với a i > a i +1 ) ta được một hoán vị thuộc tập Y . Suy ra Y = x n −1 Với mỗi hoán vị thuộc tập Z ta rút a i ra thì ta thu được hoán vị ( 1,2,3,...,n − 1) và với mỗi hoán vị này, ta có n − 1 cách chèn n vào. Do đó Z = n − 1 . Do đó x n = x n −1 + x n −1 + n − 1 = 2xn −1 + n − 1 và x 2 = 1 . Từ đây ta tìm được x n = 2 n − n − 1, ∀n ≥ 2 . Ví dụ 4. Cho tập A ⊂ ¡ , ta định nghĩa A + 1 = a + 1 a ∈ A . Hỏi có bao nhiêu tập con A của tập { 1,2,...,n} số 400 bài T10). Lời giải. ( n ∈ ¥ ,n ≥ 1) { { } sao cho A ∪ ( A + 1) = { 1,2,...,n} (THTT } Đặt X n = A A ∪ A + 1 = { 1,2,...,n} và a n = A n Ta có a1 = 0,a 2 = 1 . Vì n ∈ A ∪ ( A + 1) , n + 1 ∉ A ∪ ( A + 1) nên n ∉ A và n − 1 ∈ A . Do đó, ta chia tập { } { } X n thành hai tập rời nhau Yn = A ∈ X n n − 2 ∈ A và Z n = A ∈ X n n − 2 ∉ A . +) Tính Yn Với A ∈ Yn , ta đặt B = A\{ n − 1} , khi đó B ∪ B + 1 = { 1,2,...,n − 1} nên Yn = a n −1 . +) Tính Z n Với A ∈ Z n , ta đặt B = A\{ n − 1} , khi đó B ∪ B + 1 = { 1,2,...,n − 2} . Suy ra Zn = a n −2 . Do đó, ta có a n = a n −1 + a n − 2 . Từ đây ta tìm được n −1 n −1   1− 5  1  1 + 5   an = −  ÷ ÷ ÷  ÷ . 2 5  2      Ví dụ 5. Có n tấm thẻ được đánh số từ 1 đến n . Có bao nhiêu cách chọn ra một số thẻ (ít nhất 1 tấm) sao cho tất cả các số viết trên các tấm thẻ này đều lớn hơn hoặc bằng số tấm thẻ được chọn. Lời giải. Gọi S n là tập các thẻ được chọn thỏa yêu cầu bài toán và a n = S n . Ta phân hoạch tập S n thành hai tập rời nhau A và B như sau A là tập gồm các thẻ được chọn không có thẻ mang số n và B là tập gồm các thẻ được chọn trong đó có thẻ ghi số n . Khi đó a n = A + B . • Tính A Xét ánh xạ f : A → S n −1 , f(x) = x là một song ánh. Do đó A = S n −1 • Tính B Ta phân hoạch B thành hai tập rời nhau B1 và B2 B1 gồm các cách lấy 1 thẻ và B2 gồm các cách lấy ít nhất 2 thẻ. Dễ thấy B1 = { n} ⇒ B1 = 1 Xét một cách lấy thẻ thuộc B2 . Giả sử Vì số thẻ lấy ra không ít hơn 2 nên thẻ ghi số 1 không được chọn. Gọi a n là số cách chọn một số thẻ từ n thẻ sao cho tất cả các số viết trên thẻ đều không nhỏ hơn số thẻ được chọn. Ta có các trường hợp sau • Thẻ ghi số n không được chọn, khi đó các thẻ được chọn từ các thẻ được ghi từ số 1 đến n − 1 và tất cả các số viết trên các tấm thẻ đều không nhỏ hơn số thẻ được chọn. Số cách chọn trong trường hợp này là a n −1 . • Thẻ ghi số n được chọn +) Nếu chỉ chọn 1 thẻ ghi số n thì có 1 cách chọn +) Nếu chọn ít nhất hai thẻ thì thẻ ghi số 1 sẽ không được chọn và các thẻ được chọn còn lại (khác thẻ ghi số n ) gồm các thẻ ghi số từ 2 đến n − 1 , ta trừ đi mỗi số ghi trên các thẻ này 1 đơn vị thì ta được các thẻ ghi từ số 1 đến n − 2 . Do đó, trường hợp này có a n − 2 + 1 cách chọn. Từ đó, ta suy ra a n = a n −1 + a n − 2 + 1 và a1 = 1,a 2 = 3 . Do đó ta tìm được a n (1+ 5) = n +1 ( − 1− 5 2 5 ) n +1 − 1. Ví dụ 6. Cho tập A = {−1;0;1} . Tìm số bộ (a1 ,a1 ,...,a n ) thỏa: 1) a i thuộc A với mọi i = 1,2,...,n 2) a i − a i +1 thuộc A với mọi i = 1,2,...,n − 1 . Lời giải. Gọi S n là tập các bộ (a1 ,a1 ,...,a n ) . Ta phân hoạch tập S n thành ba tập rời nhau { } Bn = { (a1 ,a1 ,...,a n ) ∈ S n a n = 0} Cn = { (a1 ,a1 ,...,a n ) ∈ S n a n = −1} . A n = (a1 ,a1 ,...,a n ) ∈ S n a n = 1 Đặt u n = S n , x n = A n , y n = Bn , z n = C n . Xét một bộ (a1 ,a1 ,...,a n ) ∈ A n , khi đó a n −1 = 0 ∨ a n −1 = 1 . Do đó, khi bỏ phần tử a n ta thu được một bộ thuôc A n −1 hoặc Bn −1 . Ngược lại với mỗi bộ thuộc A n −1 hoặc Bn −1 ta có thể thêm vào cuối số 1 hoặc số 0 để thu được một dãy thuộc A n . Do đó, ta có x n = x n −1 + y n −1 Tương tự, ta có y n = x n −1 + y n −1 + z n −1 = u n −1 và z n = z n −1 + y n −1 Do đó u n = x n + y n + z n = x n −1 + y n −1 + u n −1 + z n −1 + y n −1 = 2u n −1 + u n −2 . Từ đó, ta tìm được u = n ( 1+ 2 ) n +1 ( + 1− 2 ) n +1 . 2 Chú ý: Trong một số bài toán, chúng ta cần xây dựng thêm đối tượng phụ để giúp giải quyết bài toán đếm. Ví dụ 7. Từ các chữ số 3,4,5,6 lập được bao nhiêu số có n chữ số và số đó chia hết cho 3 . Lời giải. Gọi A là tập các số tự nhiên có n chữ số được lập từ các chữ số 3,4,5,6 . Ta có A = 4 n . Vì một số tự nhiên khi chi cho 3 chỉ có 3 số dư là 0,1,2 nên ta chia tập A thành 3 tập rời nhau A n ,Bn ,C n theo thứ tự là gồm các x ∈ A mà số dư của x khi chia cho 3 là 0, 1, 2. Ta cần tìm x n = A n , đặt y n = Bn , z n = Cn , ta có x + y + z = 4 n . n n n Xét một số x ∈ A n và x = a1a 2 ...a n có n chữ số. +) Nếu a n = 3 hoặc a n = 6 , khi ta bỏ a n ta thu được số có n − 1 chữ số và số này chia hết cho 3 , ngược lại với mỗi số có n − 1 chữ số chia hết cho 3 thì khi ta thêm vào cuối chữ số 3 hoặc 6 ta được một số chia hết cho 3 và có n chữ số. Nên trường hợp này có x n −1 số. +) Nếu a n = 5 , khi ta bỏ a n , ta thu được một số có n − 1 chữ số thuộc tập Bn −1 và mỗi số thuộc Bn −1 , ta thêm vào cuối chữ số 5 ta thu được một số thuộc A n . Trường hợp này có y n −1 số. +) Nếu a n = 6 . Tương tự như trên ta có z n −1 số. Do đó, ta có x n = x n −1 + y n −1 + zn −1 = 3n −1 . Trong bài toán trên, việc đưa thêm hai tập Bn và Cn vào để giúp chúng ta tìm được quan hệ truy hồi giữa ba đại lượng a n ,bn ,c n . Trong một số bài toán, việc làm xuất hiện các bài toán phụ không còn là việc đơn giản nữa. Ví dụ 8 (VMO 2009). Cho số nguyên dương n . Kí hiệu T là tập hợp 2n số nguyên dương đầu tiên. Hỏi có tất cả bao nhiêu tập con S của T có tính chất: Trong S không tồn tại các số a,b mà a − b ∈ { 1; n} . ( Tập rỗng được coi là một tập có tính chất trên). Lời giải. ........... n 1 2 n −1 ........... n+1 n+2 2n − 1 2n (hình 1) Xét bảng hình chữ nhật 2 × n và đánh các số từ 1 đến 2n như hình trên (hình 1) và ta gọi hai ô chứa n và n + 1 là hai ô đặc biệt. Số tập con thỏa yêu cầu bài toán chính bằng số cách chọn một số số từ bảng sao cho hai ô kề nhau không được chọn và cả hai ô đặc biệt không cùng được chọn và số cách chọn này ta kí hiệu là c n . Gọi a n là số cách chọn một số ô sao cho hai ô kề nhau không được chọn (*) bn là số cách chọn một số ô sao cho hai ô không được chọn và hai ô đặc biệt được chọn Khi đó c n = a n − bn . • Tính a n Gọi x n là số cách chọn một số ô thỏa (*) từ bảng chữ nhật khuyết đơn 2 × n (ở hình 2) x ........... ........... (Hình 2) Ta có các cách chọn thỏa (*) gồm: +) a n −1 cách chọn mà ô ở cột thứ nhất không được chọn. +) 2x n −1 cách chọn mà trong mỗi cách chọn thì ô thuộc cột thứ nhất được chọn. Do đó, ta có a n = a n −1 + 2x n −1 (1) Mặt khác, tất cả các cách chọn một số ô thỏa (*) từ bảng chữ nhật khuyết đơn 2 × n gồm: +) a n −1 cách chọn mà mỗi cách chọn ô chứa x không được chọn +) x n −1 cách chọn mà mỗi cách chọn ô chứa x được chọn. Do đó, ta có x n = a n −1 + x n −1 (2). Từ (1) và (2) ta suy ra a n = 2a n −1 + a n − 2 ∀n ≥ 3 và ta có a1 = 3,a 2 = 7 nên n +1 n +1  1 an =  1 + 2 + 1− 2 . 2  ( • Tính bn Ta có b1 = 0,b2 = b 3 = 1 ) ( ) ........... ........... A B (hình 3) Gọi y n là số cách chọn một số ô thỏa (*) từ hình chữ nhật khuyết kép (hình 3) Khi đó, ta có bn = y n − 2 . Nên ta có y1 = 1 và ta tính được y 2 = 4 Ta thấy tất cả các cách chọn thỏa (*) từ hình chữ nhật kép gồm +) a n − 2 cách chọn mà mỗi cách chọn thì cả A và B đều không được chọn. +) 2x n − 2 cách chọn mà mỗi cách chọn thì một trong hai ô A, B được chọn. +) y n − 2 cách chọn mà mỗi cách chọn thì ccar hai ô A và B đều được chọn. Do đó y n = a n − 2 + 2x n − 2 + y n − 2 = a n −1 + y n − 2 ⇒ 2y n − a n = 2y n −2 − a n −2 Suy ra 2y n − a n = ( −1) n a n − 2 + ( −1) Do đó b = y = n n−2 2 Vậy c = n 2a n − a n − 2 + ( −1) n−2 n −1 . với a n = ( 2 2.3. Đếm bằng công thức bao hàm và loại trừ Với n tập hữu hạn A1 ,A 2 ,...,A n ta có: A1 ∪ A 2 ∪ ... ∪ A n = n ∑ Ak − ∑ k =1 1≤i < j≤ n ) ( ) n +1 n +1  1 1 + 2 + 1 − 2  . 2  A i ∩ A j + ... + ( −1)n −1 A1 ∩ A 2 ∩ ... ∩ A n Ví dụ 1. Ta gọi A là tập hợp “đầy đặn” nếu A chứa đúng 5 số thực và bất kì phần tử x nào của A thì x − 1 hoặc x + 1 cũng thuộc A. Tìm số tập hợp đầy đặn là tập con của { 1; 2; 3;...; 2011; 2012} . Lời giải. Xét một tập hợp “đầy đặn” A = { a,b,c,d,e} với 1 ≤ a < b < c < d < e ≤ 2012 (*). Theo giả thiết, ta thấy rằng b = a + 1,e = d + 1 và c = b + 1 ∨ c = d − 1 . Gọi S là tập hợp tất cả các tập hợp đầy đặn thỏa mãn đề bài. Gọi S1 là các tập con của S mà các tập hợp đầy đặn của nó thỏa mãn c = b + 1 , S 2 là tập con của S mà các tập hợp đầy đặn của nó thỏa mãn c = d − 1. Do S = S1 ∪ S 2 nên S = S1 + S 2 − S1 ∩ S 2 . *Tính số phần tử của tập hợp S1. Xét một tập hợp đầy đặn A = { a,b,c,d,e} thuộc S1 , dễ thấy a,b,c là các số liên tiếp nên ta sẽ đếm số giá trị a thỏa mãn. Do điều kiện (*) nên 1 ≤ a ≤ 2008 . Hơn nữa, ứng với mỗi cách chọn của a, số d nhận giá trị tùy ý từ a + 3 đến 2011 nên có 2009 − a cách chọn d (rõ ràng mỗi cách như thế tương ứng với một cách chọn cặp (d,e) ). Suy ra, S1 = 2008 ∑ ( 2009 − a ) = 2009 ×2008 − a =1 2008 ×2009 . 2 *Tính số phần tử của tập hợp S 2 . Rõ ràng tồn tại một song ánh từ S1 đến S 2 vì với mỗi A1 = { a,b,c,d,e} ∈ S1 thì tập hợp tương ứng với nó sẽ là A 2 = { 2013 − a,2013 − b,2013 − c,2013 − d,2013 − e} ∈ S 2 . Suy ra S 2 = S1 . *Tính số phần tử của tập hợp S1 ∩ S 2 . Dễ thấy đây là các tập hợp chứa 5 phần tử liên tiếp và như thế, với mỗi cách chọn a sẽ tạo thành một tập hợp đầy đặn thuộc S1 ∩ S 2 . Số cách chọn đó chính là 2008 do 1 ≤ a ≤ 2008.  2008 ×2009  − 2008 = 2008 ( 2 ×2009 − 2009 − 1) = 2008 2. Vậy S = 2  2009 ×2008 − ÷ 2   Ví dụ 2. Có bao nhiêu số nguyên dương không vượt quá 2014 chia hết cho 2 hoặc 3 hoặc 7 . 7 Lời giải. Đặt X = { 1,2,...,2014} ; A = n ∈ X nM2 ; B = n ∈ X nM3 ; C = n ∈ X nM { } { Ta có: A ∪ B ∪ C = ∑ A − A ∩ B − B ∩ C − C ∩ A + A ∩ B ∩ C } { }  2014   2014   2014  = 1007, B =  = 671, C =  Mà A =     = 287  2   3   7   2014  A∩B =   = 335, B ∩ C = 95, C ∩ A = 143, A ∩ B ∩ C = 47  2.3  Do đó A ∪ B ∪ C = 1007 + 671 + 287 − 335 − 95 − 143 + 47 = 1439 . Ví dụ 3. Trong một thư viện người ta quan sát trong một tháng thấy được i) Mỗi ngày có 5 người đến đọc sách ii) Hai ngày bất kì thì số người đến đọc sách là 9 Hãy tính xem trong 1 tháng có bao nhiêu người đến đọc sách. Biết tháng đó có 30 ngày. Lời giải. Bài toán tương đương với bài toán sau: Cho các tập Ai , i = 1,30 thỏa: Ai = 5, Ai ∪ A j = 9, ∀i ≠ j . Tính 30 U Ai i =1 Ta có: Ai ∩ A j = Ai + A j − Ai ∪ A j = 1 . Do A1 ∩ Ai = 1, ∀i = 2,3,...,30 nên tồn tại một phần tử a của tập A1 mà a thuộc ít nhất 5 tập trong các tập A 2 ,A 3 ,...,A 30 . Giả sử a thuộc k tập A1 ,A 2 ,...,A k với k≥6 Nếu k ≤ 29 , suy ra tồn tại A m sao cho a ∈ A m với m ≥ k + 1 . Khi đó, tồn tại b j ∈ A m ∩ Ai , i = 1,2,...,k và b j ≠ bi với mọi i ≠ j 30 Suy ra A m ≥ k > 5 trái với giả thiết. Do đó {a} = I Ai ⇒ i =1 30 I i =1 Ai = 1 . 30 30  Bi = 4 ⇒ U Bi = ∑ Bi = 4.30 = 120 . Đặt Bi = Ai \{ a} , ∀i = 1,2,...,30 , ta có:  B ∩ B = ∅ j  i i =1 i =1 Vậy 30 U Ai i =1 = 121 . Ví dụ 4. Từ các số 1,2,3 lập được bao nhiều số tự nhiên gồm 6 chữ số thỏa mãn đồng thời hai đ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. Lời giải. Gọi X là tập các số có 6 chữ số được lập từ các số chữ 1,2,3 và mỗi chữ số xuất hiện đúng 2 lần A là tập các số thoả yêu cầu bài toán A k là tập các số thuộc X là trong đó hai chữ số k đứng cạnh nhau (1 ≤ k ≤ 3) . (A1 là tập các số mà hai chữ số 1 đứng cạnh nhau). Khi đó: và A = X − A1 ∪ A 2 ∪ A 3 3 Ta có: A1 ∪ A 2 ∪ A 3 = ∑ Ai − i =1 Ta có: A1 = A 2 = A 3 = 3 ∑ i,j=1 i≠ j Ai ∩ A j + A1 ∩ A 2 ∩ A 3 . 5! = 30 ; A ∩ A = A ∩ A = A ∩ A = 4! = 12 1 2 2 3 3 1 2! (2!) 2 A1 ∩ A 2 ∩ A 3 = 3! Suy ra : A1 ∪ A 2 ∪ A 3 = 3.30 − 3.12 + 6 = 60 . Vậy A = 90 − 60 = 30 . Ví dụ 5. Có bao nhiêu hoán vị ( a1 ,a 2 ,...,a n ) của tập { 1,2,3,...,n} sao cho a i ≠ i, ∀i = 1,2,...,n . Lời giải. Gọi S là tập hợp các hoán vị của {1;2;…;n} và Ai là tập hợp các hoán vị { a1 ;a 2 ;.....;a n } của {1;2;…;n} thỏa điều kiện a i = i (i=1;2;….;n). Rõ ràng ta có : S = n!; A i = ( n − 1) !; A i I A j = ( n − 2 ) !,....... Ai I Ai I ...... I A i = ( n − k ) !( 1 ≤ i1 < i 2 < ...... < i k ≤ n ) . 1 2 k Ta có: n Dn = A1 I A 2 I ..... I A n = n!− C1n (n − 1)!+ C n2 ( n − 2 ) !− C n3 ( n − 3 ) !+ ...... + ( −1) C nn 0! n  − 1 ( ) 1 1 1 ÷. = n! 1 − + − + ........ +  1! 2! 3! n! ÷ ÷   Chú ý: Trong một số bài toán, ta dùng công thức bao hàm loại trừ để đánh giá các bất đẳng thức. Ví dụ 6. Khi điều tra một lớp học, người ta thấy: 2 Hơn số học sinh có điểm giỏi hai môn Toán và Lý; 3 2 Hơn số học sinh có điểm giỏi hai môn Lý và Văn; 3 2 Hơn số học sinh có điểm giỏi hai môn Văn và Sử; 3 2 Hơn số học sinh có điểm giỏi hai môn Sử và Toán. 3 Chứng minh rằng có ít nhất 1 học sinh đạt điểm giỏi cả 4 môn Toán, Lý, Văn và Sử. Lời giải. Kí hiệu T,L,V,S lần lượt là tập các học sinh có điểm giỏi ở môn Toán, Lý, Văn, Sử. X = T ∩ L, Y = L ∩ V, Z = V ∩ S 2 2 2 Theo đề bài, ta có: X > T , Y > L , Z > V . 3 3 3 Ta cần chứng minh T ∩ L ∩ V ∩ S > 0 ⇔ X ∩ Y ∩ Z > 0 . Không mất tính tổng quát, ta giả sử T ≥ L ≥ V ≥ S Theo nguyên lí bù trừ, ta có: X ∩ Y ∩ Z = X ∩ Y + Z − (X ∩ Y) ∪ Z = X + Y + Z − X ∪ Y − (X ∩ Y) ∪ Z 2 2 2 T + L + V − L − V > 0. 3 3 3 Bài tập vận dụng. Bài 1. Cho 2012 người xếp theo một hàng dọc. Hỏi có bao nhiêu cách lấy ra 100 người sao cho hai người liên tiếp không được chọn. Lời giải. Đánh số 2012 người này từ 1 đến 2012. Ta chọn 100 người như sau n1n 2 ...n α n α +1 n α + 2 ....n α ... 1 4 2 4 31 1 213 1 414 2 4 432 > x1khoâng choïn choïn x 2 khoâng choïn Mỗi cách chọn thỏa yêu cầu bài toán tương ứng với một bộ ( x1 ,x2 ,...,x101 ) thỏa x1 + x2 + ... + x101 = 1912 với x1 ,x101 ≥ 0, xi ≥ 1, i = 2,...,100 . Đặt x1 = y1 ,y100 = x100 ,xi − 1 = yi , i = 2,3,...,99 Ta có phương trình: y1 + y 2 + ... + y101 = 1813, y i ≥ 0 Vậy số cách chọn thỏa yêu cầu bài toán là: C100 1913 . Bài 2. Có k học sinh tham gia một kì thi, ban tổ chức muốn xếp k học sinh này vào một bàn tròn có n chỗ ngồi (n ≥ 4k) sao cho giữa hai học sinh kề nhau có ít nhất 3 ghế trống. Hỏi ban tổ chức có bao nhiêu cách xếp? Lời giải. Bài toán quy về tìm số tập con S = { a1 < a 2 < ... < a k } của tập X = { 1,2,...,n} thỏa a i +1 − a i ≥ 4  n + a1 − a k ≥ 4  bi +1 − b i ≥ 1  Đặt bi = a i − 3(i − 1) ta có:  bk − b1 ≤ n − 3k − 1  b = a − 3(k − 1) ≤ n − 3k + 3 k  k Dễ thấy có một song ánh giữa tập A và tập con B = { 1 ≤ b1 < b2 < ... < b k } của tập Y = { 1,2,...,n − 3k + 3} thỏa bk − b1 ≤ n − 3k − 1 . • b1 ∈ { 1,2,3} ta đặt ci = bi − b1 ta có: 1 ≤ c 2 < c 3 < ... < c k ≤ n − 3k − 1 và bi ,c i là tương ứng 1-1. Do đó số tập con B chính bằng số tập con gồm k − 1 phần tử của tập Z = { 1,2,3,...,n − 3k − 1} và bằng 3Ck −1 . n − 3k −1 • b1 ≥ 4 , ta đặt ci = bi − 3 , ta có 1 ≤ c1 < c 2 < ... < c k ≤ n − 3k và bi ,ci là tương ứng 1-1 Do đó số tập con B là Ckn − 3k . Vậy đáp số của bài toán là: 3Ckn−−13k −1 + Cnk − 3k . Bài 3. Cho tập A = { 1,2,3,...,2n} . Tập con C của A được gọi là tập cân nếu trong C số các số lẻ bằng số các số chẵn (tập rỗng là một tập cân). Chứng minh rằng số tập cân của tập X bằng Cn2n . Lời giải. Gọi M là họ tất cả các tập cân của A, N là họ các tập con của A có n phần tử. Xét X = { 2,4,…2n} là tập các số chẵn của A Y = { 1,2,..2n − 1} là tập các số lẻ của A Gọi B là một phần tử thuộc M thì B là một tập cân. Gọi B1 và B2 thứ tự là tập các số chẵn và số lẻ của B. Theo định nghĩa tập cân ta có B1 = B2 . Xét một ánh xạ f từ M vào N như sau : f ( B ) = B1 ∪ ( Y\B2 ) Do B1 và Y\B2 là hai tập rời nhau nên ta có f ( B ) = B1 + Y / B2 = B1 + Y − B 2 = Y = n Vậy f ( B ) ∈ N Công việc còn lại của ta chỉ là chứng minh f là song ánh. +) f là đơn ánh : Giả sử tồn tại B,C ∈ M mà f(B) = f(C) . Suy ra B1 ∪ ( Y\B2 ) = C1 ∪ ( Y\C 2 ) Mặt khác do B1 ,C1 là tập các số chẵn còn ( Y\B2 ) , ( Y\C 2 ) là tập các số lẻ nên  B = C1 B1 = C1 và ( Y\B2 ) = ( Y\C 2 ) hay  1  B2 = C2 Suy ra B = C . Vậy f là đơn ánh +) f là toàn ánh : Với D ∈ N là một tập con của A có n phần tử, ta kí hiệu M1 ,M 2 là tập các số chẵn và các số lẻ của M . Khi đó đặt B1 = M1 ,B2 = Y\M 2 ,B = B1 ∪ B2 . Ta có B1 = M1 và B2 = Y − M 2 = n − M 2 = M − M 2 = M1 suy ra B1 = B2 Do đó B là một tập cân và f(B) = D . Vậy f cũng là toàn ánh Từ đây ta có thể kết luận được rằng f là song ánh. Vì có một song ánh giữa M và N nên M = N = Cn2n . Vậy A có Cn2n tập cân. Bài 4. Cho m,n là các số nguyên dương ( m,n > 1) . Gọi X là tập có n phần tử và A1 ,A 2 ,...,A m là m tập con của X thỏa: với mọi x,y ∈ X mà x ≠ y thì tồn tại tập A k (1 ≤ k ≤ m) sao cho Chứng minh rằng: n ≤ 2 m . x ∈ A k x ∉ A k hoặc  .   y ∉ A k  y ∈ A k Lời giải. Đặt A = { 0;1} , Y = A m = A × A × ... × A , ta có Y = 2 m Xét ánh xạ f : X → Y sao cho với mỗi x ∈ X cho ta y = f(x) = ( a1 ,a 2 ,...,a m ) với nếu x ∈ A k thì a k = 1 và x ∉ A k thì a k = 0 . ( ' Xét x,x' ∈ X và f(x) = ( a1 ,a 2 ,...,a m ) ; f(x') = a1 ,a'2 ,...,a'm ) Nếu f(x) = f(x') thì a i = a'i , suy ra x ∈ A k ⇔ x' ∈ A k và x ∉ A k ⇔ x' ∉ A k . Điều này xảy ra khi x = x' nên f là đơn ánh. Do đó: X ≤ Y hay m ≤ 2 n . Bài 5. Cho n là số nguyên dương. Một hoán vị ( x1 ,x 2 ,...,x 2n ) của tập { 1,2,...,2n} được gọi là có tính chất T nếu tồn tại i ∈ { 1,2,...,2n − 1} sao cho x i +1 − x i = n . Chứng minh rằng số các hoán vị có tính chất T lớn hơn số các hoán vị không có tính chất T. Lời giải. Gọi A là số các hoán vị có tính chất T, B là số các hoán vị không có tính chất T. Xét ánh xạ f từ B vào A được xác định như sau Với mỗi b = ( b1 ,b2 ,...,b k ,...,b 2n ) ∈ B mà b 2n − bk = n cho ta phần tử