Báo cáo nghiên cứu khoa học: "PHƯƠNG PHÁP TẬP HỢP VÀ ÁNH XẠ GIẢI TOÁN TỔ HỢP"

Chia sẻ: Nguyễn Phương Hà Linh Linh | Ngày: | Loại File: PDF | Số trang:8

Thêm vào BST

Báo xấu

160
lượt xem 36
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Báo cáo nghiên cứu khoa học: "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 A  m, B  n . Khi đó tồn tại các song ánh f: A{1, 2, ..., m}, g: B{1, 2, ..., n}. Giả sử Ta xây dựng ánh xạ h: A  B  {1, 2, ..., m + n} như sau  f x  Nếu x  A h x   g x m Nếu x  B   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 A1, A2, ... An là các tập hữu hạn đôi một rời nhau, tức là Ai  A j   , i,j {1,  Mệnh đề 2. 2, ..., n}, i  j, thì A1  A2  ...  An  = A1+ A2 + ... + An  1.2. Quy tắc nhân A B  A  B  Mệnh đề 3. Nếu A và B là tập hữu hạn, thì . Chứng minh A  m, B  k và A  a1 ; a2 ;... an  , B  b1; b2 ;... bk  tính Đề-các Giả sử A  B gồm các cặp (ai; bj), 1  i  m,1  j  k , có thể viết thành một bảng chữ nhật có m dòng k cột như sau.  a1; b1  ,  a1; b2  ,....,  a1; bk  .K K K K K K K K K  am ; b1  ,  am ; b2  ,....,  am ; bk  Ai   ai ; b1  ,  ai ; b2  ,....,  ai ; bk ; 1  i  m  . Đặt Ai  k 1  i  m  . Rõ ràng Ai  Aj   nếu i  j và A  B  A1  A2  ...  Am A  B  A1  A2  ...  Am  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à A 1  A2 , ...  An là tích Đề các của n tập hợp đó thì A1  A2  ...  An  A1  A2  ...  An . 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ử X   x1 , x2 ,..., xk  , Y   y1 , y2 ,..., ym  . 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. y  , y 2 ,..., y k đều xác định một ánh xạ f từ X tới Y, Đảo lại, mọi dãy k phần tử của Y là 1 nếu ta đặt f  xi   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 i k k  Y  mk . song ánh . Vậy, theo quy tắc tương đương, số ánh xạ từ X tới Y bằng Y  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: y1  0, y k  x1  x 2  ...  x k 1 (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ố n 1, 2, 3, 4 và số chữ số 1 bằng số chữ số 2. Chứng minh rằng M = N = C 2 n . Lời giải n Hiển nhiên M = C 2 n . 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. 1212122 Ví dụ 12121221221112 1221112  1234142. 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 (1)  x1,(1)a1a2 x2,..., 1)a1a2...ak xk ,(1)a2...ak ak1 xk1,..., 1)ank ank1 xn1,(1)ank1 xn a1 ( ( 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 n  k 1 toán chính là số các bộ A, tức là 2 . 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ó 10! A (1) 25 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ó 5 5 5 A  Ai2  S = A \  Ai = A  Ai = A + A i1 i 1 i1 i 2 5 i 1 i 1 i 1 5   Ai1  Ai2  Ai3 + Ai1  Ai2  Ai3  Ai4   Ai  (2) 1i1 i2  i3  5 1i1  i2 i3  i4 5 i 1  i1, i2 ,..., ik  bất kỳ thoả 1 i < i Xét k bất kỳ thuộc tập 1,2,3, 4,5 và xét b ộ
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 A1 , A2 ,... A2 n . Ký hiệu các màu dùng để tô là m1 , m2 ,..., mn 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  , trong đó bộ  m i  có thứ tự; mỗi m , i  1, n , có mặt đúng hai lần  m , . . . , m i2 n A ,..., m i2 n i i1 1 mi2 n 1 : mi1 ). trong bộ; mi  mi , j  1, 2 n (Quy ước j 1 j  , trong đó bộ  m ,..., m  có thứ tự; mỗi mi , i  1, n , có mặt đúng Xét tập B  n    m ,..., m  i1 i2 n i i 1 2n hai lần trong bộ; mi  mi , j  1,2n  1. j 1 j Đặt g  n   B  n  . Ta có f  n   g  n   n.g  n  1 . (4)  m ,..., m  trong B(n) thỏa m = mi2 n , ta có Thật vây, ký hiệu C(n) là tập tất cả các bộ i1 i1 i2 n 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).  m ,..., m  với mỗi m có mặt Tiếp theo ta tính g (n). Ký hiệu T là tập các bộ có thứ tự i i1 i2 n đú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. n B  n   T \ UTi . Theo nguyên lý bù trừ ta có Hiển nhiên ta có i 1 n n T T  Ti2   Ti2  Ti3 Ti = T T B(n) = T   g(n) = + i1 i1 i 1i1  i2  n 1i1  i2  i3  n i 1 i 1 n T  Ti2  ...  Tik  + ... + ( 1)k + ... + (1)n Ti (5) i1 1i1i2 ...ik 5 i 1 Trước tiên ta có 2n! T (6) 2n  i1, i2 ,..., ik  1,2,..., n Xét k bất kỳ thuộc tập và xét b ộ bất kỳ thỏa mãn k 1  i1  i2  ...  ik  n . Đặt tương ứng mỗi b  I Ti j với bộ phận đ ược từ b bằng cách bỏ đồng j 1 mi1 , một phần tử mi2 ,..., một phần tử mik . Dễ dàng chứng minh được rằng thời khỏi b một phần tử k I Ti j tương ứng nói trên xác lập cho ta một song ánh từ tập đến tập V gồm tất cả các bộ có thứ tự j 1
 m ,..., m  thỏa mãn mỗi m , j  1, k , mặt đúng một lần, mỗi có còn i1 i2 n  k ij m  M \ m ,..., m  có mặt đúng hai lần. Vậy i i1 ik  2n  k ! . k I Ti j  V  2 n k j 1 Từ (5) và (6) suy ra  2n !   2n  k !.C k n k g  n    1 . (7) n 2n k n 2 k 1 Áp dụng cho g(n 1) ta có n 1 n (2n  2  h)! h (2n  1  k )! k 1 ( 2n  2)! h C n 1 =   (1) k  (1) C n 1 g(n 1) = (8) n 1 h 2 n k 2 n1 2 h 1 k 1 Thay (7) và (8) vào (4) ta được n n (2n  k )! k (2n  1  k )! k 1 (2 n)!  (1) k C n + n.  (1) k C n 1 f(n) = n k 2 n k 2n 2 k 1 k 1 n  (2n  k )! (2n  1  k )!  (2 n)!  (1) k  2 nk C nk  2 nk Cnk11 .n = 2n   k 1 n ( 2 n  1  k )!   ( 2 n  k ).C n  C n 11 .n k k k ( 2 n)!  ( 1) = nk 2 2n k 1 n (2n  1  k )!   ( 2 n)! k (2n  k ).C nk  C n .k k  (1) = nk 2n 2 k 1 Đơn giản biểu thức cuối ta nhận được  2n  1  k !.C k n k f  n   2n   1 . n 2n  k k 0 k  1,2,..., n Ak Ak  n Tiếp theo ta nhận xét rằng mỗi cách tô màu mà tồn tại sao cho và Ak và Ak  n 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à cùng màu, k  1, 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ó Ak và Ak  n cùng màu k  1, n . Từ đó suy ra, số cách tô màu đôi một không tương đương là n (2 n  1  k )! k (n  1)! f (n)  n! n! k  (1) Cn + 2 nk 2n n 2 k 1 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 [(n  k) / 2]  C n 1 , n  Z  k k 2 C C n k n 2n k 0 Lời giải n C 2 n1 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à [( n  k ) / 2] k k không được chọn nếu (n k) chẵn. Rõ ràng bước 1 có 2 Cn cách chọn và bước 2 có C n  k 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) Ck  k n C m k k m  2n  k k 0 2   m k n Cho trước các số nguyên dương m, n. Tính T  k 0 Lời giải m n 2 m k   Cm  k 2 n  k  2 m  n 1 . Các luỹ k k C Ta chứng minh tổng cần tính bằng 2, tức là: nk k 0 k 0 thừa của 2 gợi ta liên tưởng đến số tập con một tập hợp. mk k Trong các tập con của tập S  1, 2,..., m  n  1 , dễ thấy có C n  k 2 tập dạng {a1, a2, ..., n an+i}, (1 < i  m+1) trong đó a1
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 N  a1a 2 ...a 2002 thì f  N   b1b 2 ...b 2002 , với b i  9  a i Do N+f(N) = 99...9 (2002 số 9) chia hết 9, nên f là song ánh. Từ đó suy ra N  f ( N )  = M .99...9 (2002 số 9)   N= 2 NM NM 10 2002  1 Cuối cùng ta nhận được trung bình cộng các số N là 99...9  . { 2 2002cs9 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 Trần Quốc Chiến, Giáo trình lý thuyết đồ thị, Đại học Đà Nẵng, 2002. [1] Trần Quốc Chiến, Giáo trình Toán rời rạc, Đại học Đà Nẵng, 2004. [2] 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). [3] Tạp chí Toán học và Tuổi trẻ, từ 2000  2006. [4] Một số đề thi vô địch Toán Olympic và các nước. [5] Discrete Mathematics and its Applications Mc Graw - Hill 1994. (B ản dịch: Toán học rời rạc [6] ứng dụng trong tin học, NXB Khoa học và Kỹ thuật, Hà Nội 2000). Discrete Mathematics for Computer Scientits. (Bản dịch: Toán học rời rạc cho các nhà khoa [7] học máy tính, Khoa Công nghệ Thông tin. Trường ĐHKHTN – ĐHQGHN, 1998). Thomas H. Cormen và các tác giả khác, Introduction to Algorithms. Mc Graw - Hill Book [8] Company, 1994. [9] Hoffcropt I. And Ullman J.D., Formal languages and their relation to Automata,Addison - Wesly, Reading Mass London, 1969. Nguyễn Hữu Anh, Toán rời rạc, NXB Giáo dục, Hà Nội, 1999. [10] Nguyễn Hữu Ngự, Giáo trình lý thuyết đồ thị, Đại học Tổng hợp Hà Nội. [11] 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. [12]