Phương pháp tập hợp và ánh xạ giải toán tổ hợp

PHƯƠNG PHÁP TẬP HỢP VÀ ÁNH XẠ GIẢI TOÁN TỔ HỢP SET AND MAPPING METHOD SOLVING COMBINATORICAL PROBLEMS TRẦN QUỐC CHIẾN Trường Đại học Sư phạm, Đại học Đà Nẵng NGUYỄN VĂN THÔNG HV Cao học khoá 2004-2007 TÓM TẮT Các bài toán tổ hợp ngày càng chiếm một vị trí quan trọng trong các kỳ thi olympic, vô địch toán ... Toán tổ hợp là một dạng toán khó, đòi hỏi tư duy lôgic, tư duy thuật toán cao, tính hình tượng tốt, phù hợp với mục đích tuyển chọn học sinh có khả năng và năng khiếu toán học. Hơn nữa, nội dung các bài toán kiểu này ngày càng gần với thực tế, và điều này hoàn toàn phù hợp với xu hướng của toán học hiện đại. Bài báo đề xuất phương pháp tập hợp và ánh xạ để giải một số lớp bài toán tổ hợp quan trọng. ABSTRACT Combinatorics Problems play an important role in Olympic Contests. Combinatorics is a difficult branch of Mathematics, requiring logical and high algorithmic thinking and smart imagination, suitable for selecting students with mathematical and informatic capacities. In addition, problems of such type are close to practice and this fact approaches the tendency of Modern Mathematics. The article suggests a method using sets and mappings solving some classes of Combinatorics. MỞ ĐẦU Các bài toán tổ hợp được phân thành bốn dạng sau: Bài toán tồn tại, bài toán đếm, bài toán liệt kê và bài toán tối ưu, trong đó bài toán đếm đóng vai trò quan trọng. Công cụ chính để giải bài toán đếm là hai quy tắc đếm cơ bản: Quy tắc cộng và Quy tắc nhân. Trong công trình này các tác giả tiếp cận các bài toán đếm từ góc độ tập hợp và ánh xạ. Công cụ của phương pháp này là Quy tắc tương đương đơn giản sau: Quy tắc tương đương: Hai tập hợp hữu hạn A và B có cùng số phần tử khi và chỉ khi tồn tại song ánh từ A vào B. 1. ỨNG DỤNG CHỨNG MINH CÁC QUY TẮC ĐẾM 1.1. Quy tắc cộng  Mệnh đề 1. Cho A và B là hai tập hữu hạn. Nếu A  B = . thì AB= A+ B. Chứng minh Giả sử ,A m B n  . Khi đó tồn tại các song ánh f: A{1, 2, ..., m}, g: B{1, 2, ..., n}. Ta xây dựng ánh xạ h: A  B  {1, 2, ..., m + n} như sau       f x h x g x m     Dễ dàng chứng minh h là song ánh. Từ đó, theo quy tắc tương đương ta có AB= m + n = A+ B Bằng qui nạp, có thể mở rộng mệnh đề 1 cho n tập hợp đôi một rời nhau. Nếu x  A Nếu x  B  Mệnh đề 2. Nếu A1, A2, ... An là các tập hữu hạn đôi một rời nhau, tức là i jA A  , i,j {1, 2, ..., n}, i  j, thì A1  A2  ...  An  = A1+ A2 + ... + An  1.2. Quy tắc nhân  Mệnh đề 3. Nếu A và B là tập hữu hạn, thì A B A B   . Chứng minh Giả sử ,A m B k  và  1 2; ;... ,nA a a a  1 2; ;... kB b b b tính Đề-các A B gồm các cặp (ai; bj), 1 ,1i m j k    , có thể viết thành một bảng chữ nhật có m dòng k cột như sau.             1 1 1 2 1 1 2 ; , ; ,...., ; . ; , ; ,...., ; k m m m k a b a b a b a b a b a b K K K K K K K K K Đặt         1 2; , ; ,...., ; ; 1i i i i kA a b a b a b i m   . Rõ ràng  1 .iA k i m   i jA A  nếu i  j và 1 2 ... mA B A A A     1 2 ... . .mA B A A A m k A B        W Bằng qui nạp, có thể mở rộng mệnh đề 3 cho n tập hợp.  Mệnh đề 4. Nếu A1, A2, ... , An là các tập hợp hữu hạn bất kỳ và A1  A2 , ...  An là tích Đề các của n tập hợp đó thì 1 2 1 2... ... .n nA A A A A A       2. ỨNG DỤNG GIẢI BÀI TOÁN ĐẾM Các bài toán dưới đây sẽ gặp khó khăn nếu giải bằng phương pháp khác, trong khi đó phương pháp tập hợp và ánh xạ sẽ cho những lời giải đẹp và chính xác. 2.1. Bài toán 1 Có bao nhiêu ánh xạ từ một tập hợp X có k phần tử tới một tập Y có m phần tử. Lời giải Giả sử  1 2, ,..., kX x x x ,  1 2, ,..., mY y y y . Mỗi ánh xạ từ X tới Y được hoàn toàn xác định bởi bảng các giá trị của nó. x x1 x2 ...........xi ............xk f(x) f(x1) f(x2)........f(xi).........f(xk) Dòng thứ hai (f(x1) f(x2)............f(xk)) là một dãy k phần tử của Y. Nó là một phần tử của tích Đề các Y YY .... Y = Yk. Đảo lại, mọi dãy k phần tử của Y là  1 2, ,..., ky y y   đều xác định một ánh xạ f từ X tới Y, nếu ta đặt   ii f x y . Sự tương ứng đó giữa tập hợp các ánh xạ từ X tới Y và tích Đề-các Yk là một song ánh . Vậy, theo quy tắc tương đương, số ánh xạ từ X tới Y bằng kk kY Y m  .  Hệ quả. Số cách phân phối k đồ vật vào m ngăn kéo là mk. Chứng minh. Mỗi cách phân phối là một ánh xạ từ tập hợp k đồ vật vào tập hợp m ngăn kéo. Vậy, theo kết quả bài toán 1, có mk cách phân phối k đồ vật vào m ngăn kéo. 2.2. Bài toán 2 (Vô địch Trung Quốc - 1997) Trong các xâu nhị phân có độ dài n, gọi an là số các xâu không chứa 3 số liên tiếp 0, 1, 0 và bn là số các xâu không chứa 4 số liên tiếp 0,0,1,1 hoặc 1,1,0,0. Chứng minh rằng bn+1 = 2an. Lời giải Ta gọi một xâu thuộc loại A nếu nó không chứa 3 số liên tiếp 0, 1, 0 và gọi một xâu thuộc loại B nếu nó không chứa 4 số hạng liên tiếp 0, 0, 1, 1 hoặc 1, 1, 0,0. Với mỗi xâu X = (x1, x2, ..., xn), ta xây dựng f(X) = (y1, y2, ..., yn+1) như sau: 1 k 1 2 k 1y 0, y x x ... x (mod 2)     k {2, ..., n+1}. Rõ ràng X chứa 3 số liên tiếp 0, 1, 0 khi và chỉ khi f(X) chứa 4 số hạng liên tiếp 0, 0, 1, 1 hoặc 1, 1, 0, 0 tức là X thuộc loại A khi và chỉ khi f(X) thuộc B. Vậy f là một song ánh đi từ tập các xâu loại A độ dài n đến tập các xâu loại B độ dài n+1 mà bắt đầu bằng 0. Nhưng từ mỗi xâu X thuộc B ta nhận được một xâu X cũng thuộc B bằng cách đổi các phần tử của X theo quy tắc 1  0, 0  1 nên số các xâu loại B độ dài n+1 gấp đôi số các xâu loại B độ dài n+1 mà bắt đầu bằng số 0. Từ đó ta có điều phải chứng minh. 2.3. Bài toán 3 (Vô địch Ucraina - 1996) Gọi M là số các số nguyên dương viết trong hệ thập phân có 2n chữ số, trong đó có n chữ số 1 và n chữ số 2. Gọi N là số tất cả các số viết trong hệ thập phân có n chữ số, trong đó chỉ có các chữ số 1, 2, 3, 4 và số chữ số 1 bằng số chữ số 2. Chứng minh rằng M = N = nnC2 . Lời giải Hiển nhiên M = nnC2 . Ta chỉ cần chứng minh M = N. Với mỗi số có n chữ số gồm các chữ số 1, 2, 3, 4 và số chữ số 1 bằng số chữ số 2, ta “nhân đôi” thành số có 2n chữ số theo quy tắc sau: đầu tiên, hai phiên bản của số này được viết kề nhau thành số có hai chữ số, sau đó các chữ số 3 ở n chữ số đầu và các chữ số 4 ở n chữ số sau được đổi thành chữ số 1, các chữ số 3 ở n chữ số sau và các chữ số 4 ở n chữ số đầu được đổi thành chữ số 2. Ví dụ: 12341421234142123414212121221221112. Như thế, ta thu được một số có đúng n chữ số 1 và n chữ số 2. Rõ ràng đây là một đơn ánh từ tập các số n chữ số sang tập các số 2n chữ số. Để chứng minh đây là một song ánh, ta xây dựng ánh xạ ngược như sau: với mỗi số có n chữ số 1 và n chữ số 2, ta cắt n chữ số đầu và n chữ số cuối rồi cộng chúng theo cột với quy tắc: 1+1=1, 2+2=2, 1+2=3, 2+1=4, và ta thu được một số có n chữ số gồm các chữ số 1, 2, 3, 4 với số chữ số 1 bằng số các số 2. Ví dụ 12121221221112  1234142 1221112 1212122  1234142. Như thế song ánh giữa hai tập hợp đã được thiết lập và ta có M=N. 2.4. Bài toán 4 (IMO - 2005) Cho các số nguyên dương n, k với n  k. Xét phép toán f đối với bộ sắp thứ tự X = [x1, ..., xn] như sau: mỗi lần chọn k số liên tiếp tuỳ ý trong X và đổi dấu của chúng. Tìm số các bộ thứ tự X =[x1, ..., xn] thoả mãn các điều kiện: (i) Mọi phần tử của X đều thuộc tập {-1,1}. (ii) Có thể thực hiện hữu hạn lần phép toán f để từ X nhận được bộ [1,1,...,1]. Lời giải Xét bộ thứ tự X = [x1, ..., xn] tuỳ ý. Ta có hai nhận xét sau: 1) Có đúng n  k + 1 nhóm k số liên tiếp. 2) Sau một số chẵn lần thực hiện phép toán f cho một nhóm k số liên tiếp trong X thì giá trị k số đó không đổi. Như vậy, mỗi phương án thực hiện hữu hạn lần phép toán f đối với X tương ứng với một bộ nhị phân A = [a1, a2, ..., an-k+1], trong đó ai tính theo modun 2 của số lần thực hiện f cho nhóm k số liên tiếp [xi, xi+1, ..., xi+k-1], và X trở thành  nanaakaaakaaaaaa xxxxxx knknknkkk 111221211 )1(,)1(,...,)1(,)1(,...,)1(,)1( 11......21    Từ đó, dễ thấy mỗi bộ A xác định duy nhất một bộ X thoả điều kiện bài toán nên đáp số bài toán chính là số các bộ A, tức là n k 12   . 2.5. Bài toán 5 (VMO - 1995 - Bảng B) Từ các số 1, 2, 3, 4, 5 có thể lập được bao nhiêu số có 10 chữ số thoả 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. Lời giải Gọi S là số cần tìm và A là tập gồm tất cả các số có 10 chữ số, lập được từ các chữ số 1, 2, 3, 4, 5 thoả mãn điều kiện 1) của đề bài. Hiển nhiên ta có A 52 !10 (1) Với mỗi i = 1, 2, ..., 5, 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. Khi đó theo Nguyên lý bù trừ ta có S =  5 1 \ i iAA = A   5 1i iA = A   5 1i iA +    51 21 21 ii ii AA     51 321 321 iii iii AAA +    51 4321 4321 iiii iiii AAAA   5 1i iA (2) Xét k bất kỳ thuộc tập  1,2,3,4,5 và xét bộ  1 2, ,..., ki i i bất kỳ thoả 1 i1< i2 <...< ik  5. Gọi T là tập gồm tất cả các số có (10k) chữ số, lập được từ các chữ số 1, 2, 3, 4, 5 thỏa mãn: mỗi chữ số ij, j=1,2,...,k, có mặt đúng một lần, còn các chữ số khác, mỗi chữ số có mặt đúng hai lần. Đặt tương ứng mỗi số a  kiii AAA  ... 21 , với số nhận được từ a bằng cách bỏ đồng thời ở a một chữ số i1, một chữ số i2, ... , một chữ số ik. Rõ ràng là phép tương ứng trên xác lập một song ánh từ 1 2 ... ki i i A A A   đến T. Điều này cho ta kiii AAA  ... 21 = T = k k   52 )!10( (3) Từ (1), (2) và (3) ta có S = 52 !10 4 1 5 2 !9C 3 2 5 2 !8C 2 3 5 2 !7C 1 4 5 2 !6C 02 !5 2.6. Bài toán 6 (VMO - 1995) Cho số nguyên 2n  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 thoả 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, thoả 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 đều đã cho. Hỏi có tất cả bao nhiêu cách tô màu đôi một không tương đương? Lời giải Xuất phát từ một đỉnh nào đó, lần lượt theo chiều kim đồng hồ, ký hiệu các đỉnh của đa giác bởi 1 2 2, ,... nA A A . Ký hiệu các màu dùng để tô là 1 2, ,..., nm m m và gọi M là tập tất cả n màu ấy. Gọi f(n) là số cách tô màu thoả mãn các điều kiện 1), 2) của bài toán. Ta có  f n A , với   1 2,..., ni iA m m , trong đó bộ  1 2, . . . , ni im m có thứ tự; mỗi mi, 1,i n , có mặt đúng hai lần trong bộ; 1 , 1,2 j ji i m m j n     (Quy ước 2 1 1 : ni i m m   ). Xét tập     1 2,..., ni iB n m m , trong đó bộ  1 2,..., ni im m có thứ tự; mỗi , 1,im i n , có mặt đúng hai lần trong bộ; 1 , 1,2 1 j ji i m m j n      . Đặt    g n B n . Ta có      . 1f n g n n g n   . (4) Thật vây, ký hiệu C(n) là tập tất cả các bộ  1 2,..., ni im m trong B(n) thỏa 1im = nim 2 , ta có A = B(n) \ C(n). Mỗi bộ của C(n) có thể xác định bằng 2 bước như sau: bước 1 chọn màu i đặt vào vị trí 1 và 2n, bước này có n cách chọn; bước 2 ta lấy (n1) màu còn lại đặt vào các vị trí 2, 3, ..., 2n1, bước này có g(n1) cách chọn (vì mỗi bộ 2n2 thành phần này chính là một bộ trong B(n1)). Vậy, theo quy tắc nhân, C(n) = n.g(n1). Từ đó suy ra (4). Tiếp theo ta tính g(n). Ký hiệu T là tập các bộ có thứ tự  1 2,..., ni im m với mỗi mi có mặt đúng hai lần trong bộ và Ti , i=1,...,n, là tập các bộ trong T có mi chiếm hai vị trí liên tiếp. Hiển nhiên ta có   1 \ n i i B n T T   U . Theo nguyên lý bù trừ ta có g(n) = B(n) = T   n i iT 1 = T    n i iT 1 +    nii ii TT 21 21 1     niii iii TTT 321 321 1 + ... + (1)k    5...1 21 21 ... k k iii iii TTT + ... + (1)n  n i iT 1 (5) Trước tiên ta có T n n 2 !2 (6) Xét k bất kỳ thuộc tập  1,2,...,n và xét bộ  1 2, ,..., ki i i bất kỳ thỏa mãn 1 21 ... ki i i n     . Đặt tương ứng mỗi 1 j k i j b T  I với bộ phận được từ b bằng cách bỏ đồng thời khỏi b một phần tử 1i m , một phần tử 2 ,...,im một phần tử kim . Dễ dàng chứng minh được rằng tương ứng nói trên xác lập cho ta một song ánh từ tập 1 j k i j T  I đến tập V gồm tất cả các bộ có thứ tự  1 2,..., n ki im m  thỏa mãn mỗi , 1,jim j k , có mặt đúng một lần, còn mỗi  1\ ,..., ki i im M m m có mặt đúng hai lần. Vậy   1 2 ! 2j k i n k j n k T V     I . Từ (5) và (6) suy ra         1 2 ! 2 ! 1 . . 2 2 n k k nn n k k n n k g n C      (7) Áp dụng cho g(n1) ta có g(n1) = 12 )!22(   n n       1 1 112 )!22()1( n h h nhn h Chn =       n k k nkn k Ckn 1 1 12 )!12()1( (8) Thay (7) và (8) vào (4) ta được f(n) = n n 2 )!2(      n k k nkn k Ckn 1 2 )!2()1( + n.       n k k nkn k Ckn 1 1 12 )!12()1( = n n 2 )!2(            n k k nkn k nkn k nCknCkn 1 1 1 .2 )!12( 2 )!2()1( = n n 2 )!2(         n k k n k nkn k nCCknkn 1 1 1 .).2(2 )!12()1( = n n 2 )!2(        n k k n k nkn k kCCknkn 1 .).2( 2 )!12()1( Đơn giản biểu thức cuối ta nhận được       0 2 1 ! 2 1 . . 2 n k k nn k k n k f n n C      Tiếp theo ta nhận xét rằng mỗi cách tô màu mà tồn tại  1,2,...,k n sao cho kA và k nA  khác màu, đều có đúng 2n cách tô màu tương đương với nó; còn mỗi cách tô màu mà kA và k nA  cùng màu, 1,k n  , đều có đúng n cách tô màu tương đương với nó. Hơn nữa, dễ thấy, có tất cả !n cách tô màu mà trong mỗi cách đều có kA và k nA  cùng màu 1,k n  . Từ đó suy ra, số cách tô màu đôi một không tương đương là n nnf 2 !)(  n n!      n k k nkn k Ckn 1 2 )!12()1( + 2 )!1( n 3. ỨNG DỤNG TÍNH BIỂU THỨC TỔ HỢP Ý tưởng áp dụng bài toán đếm để tính biểu thức tổ hợp là biểu diễn biểu thức tổ hợp bằng số cách xây dựng một cấu hình tổ hợp thích hợp mà số cấu hình tổ hợp này dễ dàng tính được thông qua các công thức tổ hợp cơ bản. 3.1. Bài toán 7 (Vô địch Trung Quốc - 1994) Chứng minh n k k [(n k) / 2] n n n k 2n 1 k 0 2 C C C , n Z       Lời giải n nC 12  là số cách chọn k số từ 2n+1 số khác nhau. Ta chọn n số từ 2n+1 số theo cách sau. Trước hết, từ 2n+1 số , ta chia ra n cặp và số x. Bước 1: Chọn ra k cặp rỗi từ mỗi cặp chọn ra một số. Bước 2: Chọn [(nk)/2] cặp trong (nk) cặp còn lại, ngoài ra, số x sẽ được chọn nếu (nk) lẻ và không được chọn nếu (nk) chẵn. Rõ ràng bước 1 có k kn2 C cách chọn và bước 2 có [(n k) / 2] n kC   cách chọn và ta chọn được tổng cộng n số, trong đó k chạy từ 0 tới n. Lập luận đó cho ta điều phải chứng minh. 3.2. Bài toán 8 (VMO - 2004) Cho trước các số nguyên dương m, n. Tính k km n n k m k n k m k k 0 k 0 C CT 2 2          Lời giải Ta chứng minh tổng cần tính bằng 2, tức là: m n k m k k n k m n 1 n k m k k 0 k 0 C 2 C 2 2          . Các luỹ thừa của 2 gợi ta liên tưởng đến số tập con một tập hợp. Trong các tập con của tập  S 1,2,...,m n 1   , dễ thấy có k m kn kC 2  tập dạng {a1, a2, ..., an+i}, (1 < i  m+1) trong đó a1<a2< ... < an+i và an+1 = n+k+1 với 0km (do có nn kC  cách chọn n phần tử (a1, a2, ..., an) từ tập {1, 2, ..., n+k}, 1 cách chọn an+1 = n+k+1, và 2m-k cách chọn tập con của tập {n+k+1, ..., n+m+1}). Như vậy m k m k n k k 0 C 2    là số tập con của S có nhiều hơn n phần tử. Tương tự n k n k m k k 0 C 2    là số tập con của S có nhiều hơn m phần tử, cũng tức là số tập con của S có không quá n phần tử. Vậy m k m k n k k 0 C 2    + n k n k m k k 0 C 2    là số tất cả các tập con của S, tức là 2m+n+1 . Đó chính là điều phải chứng minh. 3.3. Bài toán 9 (VMO - 2002) Cho tập S gồm tất cả các số nguyên trong đoạn [1; 2002]. Gọi T là tập hợp tất cả các tập con không rỗng của S. Với mỗi X thuộc T, kí hiệu m(X) là trung bình cộng các phần tử của X. Tính m = T Xm TX   )( Lời giải Ta xây dựng song ánh f: TT như sau:    f X 2003 x x X , X T     . Rõ ràng XT, m(X) + m(f(X)) = 2003. Do đó          m X 20032 m X m X m f X T .2003 m T 2        . 3.4. Bài toán 10 (Olimpic 30.4.2000) Hãy tính trung bình cộng tất cả các số N gồm 2002 chữ số thỏa mãn N chia hết cho 99 và các chữ số của N thuộc  1,2,3,4,5,6,7,8 . Lời giải Gọi M là tập các số N thoả điều kiện đề bài. Ta xây dựng ánh xạ f: M M như sau Nếu 1 2 2002N a a ...a thì   1 2 2002f N b b ...b , với i ib 9 a  Do N+f(N) = 99...9 (2002 số 9) chia hết 9, nên f là song ánh. Từ đó suy ra 2  MN N =     MN NfN )( = M .99...9 (2002 số 9) Cuối cùng ta nhận được trung bình cộng các số N là { 2002 2002cs9 10 199...9 2   . KẾT LUẬN Bài toán tổ hợp là bài toán có nội dung thực tế, lý luận hấp dẫn và lý thú, những điều nghe như là đơn giản nhưng giải được nó là một quá trình tư duy sâu sắc, ứng dụng tập hợp và ánh xạ sẽ làm rõ hơn cách giải toán rời rạc cho học sinh giải toán ở trường Trung học phổ thông, chuyên Toán, Tin. TÀI LIỆU THAM KHẢO [1] Trần Quốc Chiến, Giáo trình lý thuyết đồ thị, Đại học Đà Nẵng, 2002. [2] Trần Quốc Chiến, Giáo trình Toán rời rạc, Đại học Đà Nẵng, 2004. [3] Trần Quốc Chiến, Giáo trình lý thuyết tổ hợp (Dùng cho lớp cao học Toán). [4] Tạp chí Toán học và Tuổi trẻ, từ 2000  2006. [5] Một số đề thi vô địch Toán Olympic và các nước. [6] Discrete Mathematics and its Applications Mc Graw - Hill 1994. (Bản dịch: Toán học rời rạc ứng dụng trong tin học, NXB Khoa học và Kỹ thuật, Hà Nội 2000). [7] Discrete Mathematics for Computer Scientits. (Bản dịch: Toán học rời rạc cho các nhà khoa học máy tính, Khoa Công nghệ Thông tin. Trường ĐHKHTN – ĐHQGHN, 1998). [8] Thomas H. Cormen và các tác giả khác, Introduction to Algorithms. Mc Graw - Hill Book Company, 1994. [9] Hoffcropt I. And Ullman J.D., Formal languages and their relation to Automata,Addison - Wesly, Reading Mass London, 1969. [10] Nguyễn Hữu Anh, Toán rời rạc, NXB Giáo dục, Hà Nội, 1999. [11] Nguyễn Hữu Ngự, Giáo trình lý thuyết đồ thị, Đại học Tổng hợp Hà Nội. [12] Nguyễn Tô Thành và Nguyễn Đức Nghĩa, Toán rời rạc, NXB Giáo dục, Hà Nội, 1997.