Phương pháp song ánh trong giải bài toán Tổ hợp ứng dụng giải đề thi HSG

Phương pháp song ánh A. Mở đầu Tổ hợp là một trong những nội dung bắt buộc trong các đề thi HSG Quốc gia và Quốc Tế. Nhưng đây là một vấn đề khó và ít có tài liệu viết đầy đủ. Do vậy trong chuyên đề này tôi xin đưa ra thảo luận và trao đổi với các thầy cô một chuyên đề tổ hợp đó là phương pháp song ánh. Nội dung cơ bản các chuyên đề là nhắc lại khái niệm về song ánh, cách vận dụng song ánh trong một số dạng toán thi học sinh giỏi thường gặp, từ đó giúp cho các học sinh có được những kiến thức cơ bản về phương pháp song ánh trong các bài toán tổ hợp B. Nội dung I. Khái niệm về song ánh 1. Định nghĩa Cho 2 tập hợp X và Y (khác rỗng). Một ánh xạ f từ X lên Y là một quy tắc cho tương ứng mỗi phần tử x ∈ X với 1 và chỉ 1 phần tử y ∈ Y Ký hiệu f : X →Y x  y = f ( x) Tập X gọi là tập nguồn, tập Y là tập đích Ánh xạ f được gọi là đơn ánh nếu mọi x1 , x2 ∈ X , f ( x1 ) = f ( x2 )  x1 = x2 Khi đó ta có X ≤ Y Ánh xạ f được gọi là toàn ánh nếu ∀y ∈ Y , ∃x ∈ X sao cho f ( x) = y Ánh xạ f được gọi là song ánh nếu nó vừa là đơn ánh, vừa là toàn ánh II. Phương pháp song ánh trong các bài toán tổ hợp 1. Phương pháp song ánh để đếm số phần tử của một tập hợp và chứng minh hai tập có cùng số phần tử Nội dung cơ bản: Để đếm số phần tử của một tập nhất định, ta có thể thay nó bởi một tập hợp khác có cùng số phần tử và số phần tử của tập hợp mới có cách đếm dễ Bài 1: (Bài toán chia kẹo của Euler) 1 Cho m, n ∈  * , hỏi phương trình x1 + x2 + ... + xn = m (*) có bao nhiêu nghiệm nguyên không âm. Hướng dẫn: Kí hiệu T là tập các nghiệm của (*) trên tập số tự nhiên. Gọi A là tập tấ cả các dãy nhị phân gồm (m + n − 1) chữ số trong đó có (n − 1) chữ số 0 và m chữ số 1 F: T →A Xét tương ứng: ( x ,..., x )  1...101...10...01...1 1 n    x1 so1 x2 so1 xn so1 Dễ thấy F là một song ánh. Vậy số nghiệm của (*) = số dãy nhị phân của A. Số dãy nhị phân của A bằng số cách xếp n − 1 chữ số 0 vào trong (m + n − 1) chữ số của các dãy nhị phân (trong A) và bằng Cmn −+1n −1 . Vậy số nghiệm của (*) là Cmn −+1n −1 Bài 2 [VMO 2012_ câu 5]: Cho một nhóm có 5 cô gái, kí hiệu là G1 , G2 ,..., G5 và 12 chàng trai. Có 17 chiếc ghế được xếp thành một hàng ngang. Người ta xếp nhóm người đó chỉ ngồi vào các chiếc ghế đó sao cho các điều kiện sao cho đồng thời thỏa mãn: 1. mỗi ghế có duy nhất 1 người ngồi 2. Thứ tự ngồi của các cô gái, xét từ trái qua phải là G1 , G2 , G3 , G4 , G5 3. Giữa G1 và G2 có ít nhất 3 chàng trai 4. Giữa G4 và G5 có ít nhất 1 chàng trai và nhiều nhất 4 chàng trai. Hỏi có tất cả bao nhiêu cách sắp xếp như vậy (Hai cách xếp được coi là khác nhau nếu tồn tại 1 chiếc ghế mà người ngồi ở chiếc ghế đó trong 2 cách xếp là khác nhau) Hướng dẫn: Bổ đề (bài toán chia kẹo của Euler): cho k , n là các số nguyên dương. Số nghiệm nguyên không âm của pt x1 + x2 + ... + xk = n Áp dụng vào bài toán: đánh số thứ tự các ghế từ trái sang phải là 1,2,…,17. Gọi x1 là số chàng trai được xếp bên trái G1 , x2 là số chàng trai ở giữa G1 và G2 ; x3 là số chàng trai ở giữa G2 và G3 ; x4 là số chàng trai ở giữa G3 và G4 ; x5 là số chàng trai ở giữa G4 và G5 ; x6 là số chàng trai ngồi bên phải G5 . Khi đó bộ số ( x1 , x2 ,..., x5 ) hoàn toàn xác định vị trí các cô gái và ta có: 1. x1 + x2 + ... + x6 = 12 2. 3 ≤ x2 2 3. 1 ≤ x5 ≤ 4 Đổi biến y2 = x2 − 3 và y5 = x5 − 1 ta được x1 + y2 + x3 + x4 + y5 + x6 = 8 với các Nn không âm và có thêm điều kiện y5 ≤ 3 . Tiếp theo, áp dụng bài toán chia kẹo ở dạng x1 + y2 + x3 + x4 + x6 = 8 − y5 Ta được số cách phân ghế cho các cô gái là C124 + C114 + C104 + C94 = 1161 Vì còn có 12 chàng trai có thể hoán đổi vị trí ở 12 chiếc ghế dành cho họ nên số cách xếp t/m ycbt là 12!.1161 Bài 3 [VMO 2014_ câu 3]: Cho đa giác đều có 103 cạnh. Tô màu đỏ cho 79 đỉnh của đa giác và tô màu xanh cho các đỉnh còn lại. Gọi A là số cặp đỉnh đỏ kề nhau và B là số cặp đỉnh xanh kề nhau. a. Tìm tất cả các giá trị có thể nhận được của cặp ( A, B) b. xác định số cách tô màu các đỉnh của đa giác để B = 14 . Biết rằng, hai cách tô màu được xem là như nhau nếu chúng có thể nhận được từ nhau thông qua 1 phép quay quanh tâm đường tròn ngoại tiếp đa giác. Hướng dẫn: a. Số đỉnh màu xanh là 24 đỉnh (103-79). N ếu tất cả các đỉnh đỏ chia thành một cụm thì A=78. N ếu bị cắt thành 2 cụm thì A=77. Và cứ thế tiếp tục, tức là nếu có k cụm (mỗi cụm là các đỉnh cùng màu đỏ đứng sát nhau) thì A = 79 − k . N ếu có k cụm đỏ thì cũng có k cụm xanh nên có B = 24 − k . Các giá trị có thể của k là từ 1 đến 24, nên có 24 khả năng tất cả b. Để có B = 14 thì k = 10 (phải chia quân xanh thành 10 cụm, quân đỏ thành 10 cụm). Đếm số cách chia như thế nào ? Gọi X là số cụm các điểm đỏ liền nhau, thì B = 24 − X . Do vậy B = 14 thì X = 10 . Áp dụng công thức chia kẹo của pt chia kẹo, ta suy ra được số cách chia 24 điểm xanh vào 10 cụm là C239 . Tiếp theo, ta sẽ xem xét việc xếp các điểm xanh- đỏ như là vệc có sẵn 79 điểm đỏ ở trên đường tròn, và ta bỏ đi 10 cụm điểm xanh và các khoảng trống giữa 2 điểm đỏ liên tiếp, mỗi khoảng có tối đa 1 cụm. N hư vậy thì số cách chọn ra 10 khoảng trống trong 79 khoảng là C7910 . Sự trùng lặp theo phép quay là ở chỗ ta chọn 10 vị trí trong 79 vị trí theo đường tròn. N hờ có (79,10)=1 mà ta không phải lo về “các cấu hình C7910C239 lộn xộn”, mỗi cách tô bị lặp đúng 79 lần, do vậy đáp số là 79 Định lý 4.1: 3 Cho A và B là 2 tập hợp hữu hạn, và f là 1 ánh xạ đơn ánh từ A vào B. Khi đó số phần tử của B ít nhất là bằng số phần tử của A. Và nếu f là song ánh thì A và B có cùng số phần tử Bài 4: Với mỗi đỉnh của đa giác đều 9 đỉnh (cửu giác) được tô bởi màu đỏ hoặc xanh da trời. Chứng minh rằng tồn tại 2 tam giác đơn sắc đồng dạng , trong đó tam giác đơn sắc là tam giác có tất cả các đỉnh là cùng 1 màu Lg: Ta gọi đơn giác đỏ (xanh) nếu tất các đỉnh của tam giác là đỏ hoặc xanh. Vì đa giác có 9 đỉnh, mỗi đỉnh chỉ tô 2 màu xanh hoặc đỏ nên có ít nhất 5 đỉnh có dùng 1 màu. Không mất tính tổng quát, giả sử đó là màu đỏ. Suy ra có it nhất C52 = 10 đơn giác đỏ. Giờ ta chứng minh có 2 tam giác đỏ đồng dạng. Hình 1 Đặt A1 , A2 , A9 là các đỉnh của đa giác (Hình 1) và ω là đường tròn ngoại tiếp đa giác. 9 đỉnh đa giác chia đường tròn này thành 9 cung bằng nhau. Gọi mỗi cung trong 9 cung này là 1 mảnh. Gọi Ai Aj Ak là tam giác thỏa mãn A A ≤ A A ≤ A A . Định nghĩa a là số mảnh của cung  A A không chứa i j j k k i i, j i j điểm Ak . Ta định nghĩa tương tự với a j ,k và ak ,i . Khi đó ΔAi Aj Ak được xác định bởi bộ ba (a i, j , a j ,k , ak ,i ) . Do 1 tam giác có 3 đỉnh, nên ta dễ thấy 1 ≤ ai , j ≤ a j ,k ≤ ak ,i ≤ 7 (trường hợp góc lớn nhất là 3 đỉnh nằm kề nhau trên đường tròn). Do  Ai Aj +  Aj Ak +  Ak Ai = 1800 , do đó ai , j + a j ,k + ak ,i = 9 . Ví dụ với tam giác ΔA2 A4 A8 ta xác định được bộ ba tương ứng là (2,3,4). Dễ thấy 4 các tam giác đồng dạng cho cùng 1 bộ ba, trong khi 2 tam giác không đồng dạng có các bộ ba khác nhau. Từ đó ta xây dựng song ánh A →B như sau: A: tập các tam giác đồng dạng B: tập các số tự nhiên a, b, c thỏa mãn 1 ≤ a ≤ b ≤ c ≤ 7 và a+b+c=9. Ta có thể liệt kê ra các phần tử của B là (1,1,7), (1,2,6), (1,3,5), (1,4,4), (2,2,5), (2,3,4), (3,3,3) có tất cả 7 phần tử. Suy ra A cũng có 7 phần tử hay có tất cả 7 dạng tam giác khác nhau. Trong khi đó ta có 10 tam giác đơn sắc, nên tồn tại ít nhất 2 tam giác đơn sắc đồng dạng. Bài 5: Cho n nguyên dương. Hỏi có bao nhiêu các biểu diễn n thành tổng của ít nhất 2 số nguyên dương. (Ví dụ có 3 cách biểu diễn số 3 thành tổng của các số nguyên dương: 3=1+1+1=1+2=2+1) Lời giải: Ta viết n dưới dạng sau: (1_1_..._1) gồm n số 1. Xét n-1 khoảng trống trong đó là a1a2 ...an−1 , khi đó các khoảng trống sẽ có 2 trạng thái là 0 hoặc 1. N ếu trạng thái là 0, thì ta sẽ thay khoảng trống bởi dấu “+”, nếu trạng thái là 1 thì thay bởi “)+(“. Ví dụ như 4=(1_1_1_1)= (a1 , a2 , a3 ) . Khi đó nếu (a1 , a2 , a3 ) = (0,0,1) thì 4=(1+1+1)+(1)=3+1 là một cách biểu diễn. Ta có tất cả 2n-1 cách biểu diễn cho dãy nhị phân (n-1) bit a1a2 ...an−1 và mỗi dãy nhị phân cho một cách biểu diễn duy nhất của n. Trong dãy nhị phân này, chỉ có trường hợp duy nhất là dãy 00…0 là không biểu diễn dưới dạng tổng của ít nhất 2 số. Do đó có 2n-1-1 cách biểu diễn n dưới dạng tổng của ít nhất 2 số nguyên dương Bài 6 [AHSME 1992]: Cho 10 điểm đặt trên phần dương trục x(X+), 5 điểm đặt trên phần dương trục y (Y+). Khi đó ta có tất cả 50 đoạn thẳng nối giữa 10 điểm trên X+ với 5 điểm trên trục Y+. Khi đó có tối đa bao nhiêu giao điểm của 50 đoạn thẳng nằm trong góc phần tư thứ nhất? (Hình 2) 5 Hình 2 Lời giải: Ta có, cứ 2 điểm trên X+ và 2 điểm trên Y+ thì tạo thành 1 tứ giác và khi đó chỉ xác định được duy nhất 1 giao điểm. Khi đó số giao điểm lớn nhất có thể tạo được là C102 C52 = 45.10 = 450 . Dấu bằng xảy ra ⇔ không có 3 đường nào cùng cắt nhau tại một điểm trong góc phần tư thứ nhất Bài 7 [China 1991, by Weichao Wu]: Cho n là số tự nhiên với n ≥ 2 , và đặt dãy S = (1,2,..., n ) . Một dãy con của S được gọi là dãy con số học nếu nó có ít nhất 2 phần tử và nó là 1 cấp số cộng. Dãy con số học được gọi là cực đại nếu dãy này không thể kéo dài bằng cách thêm vào một phần tử khác của S. Xác định số dãy con số học cực đại Lời giải: Ta có công sai a2 − a1 phải lớn hơn a1 để không thể điền thêm phần tử nào vào bên trái dãy con( phía trước a1 ), nên a2 ≥ 2a1 . Lại có a2 ≤ 2m nên a1 ≤ m . Khi đó để một dãy con là cực đại thì1 ≤ a1 ≤ m và 2a1 ≤ a2 ≤ n (1). Ta cũng có, với mỗi bộ ( a1 , a2 ) thỏa mãn điều kiện trên thì cũng cho ra duy nhất 1 dãy con cực đại có phần tử ban đầu a1 và công sai a2 − a1 . Suy ra dãy số con cực đại và bộ ( a1 , a2 ) thỏa mãn đk (1) là song ánh. Ta có, với mỗi cách chọn a1 thì có n − 2a1 + 1 cách chọn a2. Do có m cách chọn a1 nên số bộ ( a1 , a2 ) thỏa mãn đk (1) là: m  ( n − 2a a1 =1 1 m(m + 1) +m 2 = 2m 2 − m 2 = m 2 + 1) = mn − 2 Vậy có m2 dãy con cực đại với n=2m 6 Xét với n=2m+1, với m là số nguyên dương. Tương tự ta có: a2 ≥ 2a1 , suy ra a1 ≤ m . Lý luận tương tự, ta có số dãy con cực đại là: m  ( n − 2a a1 =1 1 m(m + 1) +m 2 = m(2m + 1) − m 2 = m 2 + m + 1) = mn − 2  n2  Vậy, với mỗi số tự nhiên n, ta có   dãy con số học cực đại 4 Song ánh có thể được sử dụng giữa các tập hợp mà các tập hợp này không cần hữu hạn. Dưới đây là 1 ví dụ. Bài 8 [PEA Math Materials] Giả sử rằng có 2 quản trị PEA, là những người duy nhất có quyền quay số truy cập vào tệp tài liệu Internet của học viện, biết rằng tại một thời điểm tệp này chỉ xử lý cho một yêu cầu truy cập. Với 15 phút sử dụng tệp cho 1 lần truy cập và tệp chỉ được sử dụng từ 4h chiều đến 6 giờ chiều trong ngày. Biết rằng không có yêu cầu truy cập nào được thực hiện sau 5h45 chiều, và 1 người không được yêu cầu truy cập quá 1 lần. Ít nhất 1 người trong số họ thực hiện thành công cuộc gọi. Hỏi xác suất là bao nhiêu để cả 2 người đều có thể thực hiện thành công cuộc gọi của mình? Lời giải: Gọi An và Giang là 2 quản trị của PEA. Ta biết rằng yêu cầu truy cập vào tệp internet của học viện chỉ được thực hiện trong 105 phút. Giả sử An gọi sau 4h x phút, Giang gọi sau 4h y phút, khi đó ta có thể ánh xạ bộ thời gian gọi của 2 người tới điểm (x,y) trên mp tọa độ (Hình 3). Rõ ràng đây là một song ánh. 7 Hình 3 Tập hợp các điểm (x,y) là hình vuông OA2PZ2. Rõ ràng một người không thể gửi yêu cầu truy cập thành công nếu người còn lại đang làm việc với tệp, do đó để cả 2 người có thể đều truy cập được tệp tài liệu thì ta phải có x − y > 15 . Xét miền của tập hợp các điểm (x,y) được xác định bởi x − y ≤ 15 . Đây là giao của 2 phương trình đường thẳng với hình vuông, cắt tại các điểm Z1, Z2, A1, A3. Ta xác định được Z1=(0,15), Z3=(90,105), A1=(15,0), A3=(105,90) Từ đó, xác suất để cả 2 người cùng truy cập được vào tệp là: p= S ΔZ Z Z + S ΔA A A 1 2 3 1 2 3 SOA PZ 2 2 = 902 36 = 1052 49 Hệ quả 1 Cho 2 số nguyên dương m và n a. Có Cnm−−11 bộ nguyên dương x1 + x2 + ... + xm = n ( x , x ,..., x ) 1 2 m thỏa mãn phương trình b. Có Cnm+−m1−1 bộ nguyên không âm ( x1 , x2 ,..., xm ) thỏa mãn phương trình x1 + x2 + ... + xm = n Bài 9: Có 5 con xúc xắc được đổ ra. Hỏi có bao nhiêu xác suất để tổng của 5 mặt trên xúc xắc là 14? Lời giải: Gọi 5 xúc xắc lần lượt là d1 , d 2 ,..., d 5 và xi là con số mặt trên của xúc xắc d i . Với mỗi xi ta có 6 khả năng, nên có tất cả 65 khả năng có thể xảy ra đối với cả 5 xúc xắc. Gọi A là tập hợp các khả năng tổng các mặt là 14. Ta | A| cần tính 5 . Do đó ta cần tính số bộ 5 số nguyên ( x1 , x2 ,..., x5 ) thỏa mãn 6 1 ≤ xi ≤ 6 và x1 + x2 + .... + x5 = 14 Theo Hệ quả 1 thì có tất cả C145−−11 = 715 bộ 5 số nguyên dương thỏa mãn x1 + x2 + .... + x5 = 14 . Gọi B là tập các bộ 5 số nguyên dương có tổng bằng 14 và có ít nhất 1 số lớn hơn 6. Đặt Bi ⊂ B thỏa mãn xi > 6 . Ta có Bi ∩ B j = ∅ với i ≠ j (do x1 + x2 + ... + x5 > 6 + 6 + 1 + 1 + 1 = 15 , suy ra B = ∪ Bi . Ta cũng có Bi = B j , suy ra B = 5 B1 . Ánh xạ từ ( x1 , x2 ,..., x5 ) ∈ B1 tới ( y1 , y2 ,..., y5 ) với y1 = x1 − 5 và yi = xi với 2 ≤ i ≤ 5 . Đây là 1 song ánh giữa tập B1 tới tập các bộ 5 8 ( y , y ,..., y ) nguyên 1 2 5 dương thỏa mãn y1 + y2 + ... + y5 = 8 . Suy ra B1 = C85−−11 = C74 = 35 . Suy ra B = 175 Vậy A = 715 − 175 = 540 . Vậy xác suất xuất hiện 5 mặt có tổng là 14 là 540 5 = 65 72 Bài 10 [Aime 2000] Cho 8 chiếc nhẫn khác nhau, tìm số cách xếp 5 chiếc nhẫn xếp trên 4 ngón tay (không tính ngón cái) trên một bàn tay. Biết rằng thứ tự từng chiếc nhẫn trên một ngón tay là quan trọng và không bắt buộc ngón nào cũng phải có nhẫn. Lời giải: Ta có C85 cách chọn ra 5 chiếc nhẫn bất kỳ để đeo trong 8 chiếc nhẫn đã cho. Đăt a, b, c, d là số chiếc nhẫn trên từng ngón tay. Ta có a+b+c+d=5. Theo Hệ quả 1 ta có C83 cách sắp xếp các chiếc nhẫn vào 4 ngón tay (giả thiết là các chiếc nhẫn ko phân biệt). Lại có với mỗi cách sắp xếp 5 chiếc nhẫn ko phân biệt thì tương ứng có 5! cách sắp xếp đối với 5 chiếc nhẫn phân biệt. Vậy ta có số cách sắp xếp là: C85 .C83 .5! = 376320 Bài 11: N gân hàng Bảo Hiểm của nước cộng hòa Fatand có 15 nhân viên điều hành cấp cao. Mỗi nhân viên này có 1 thẻ truy cập vào kho của ngân hàng và trên mỗi thẻ bất kỳ đều có 1 bảng gồm m mã hóa khác nhau. Để mở được kho, mỗi người sẽ đặt thẻ của mình vào khóa điện tử của kho. Máy tính sẽ thu thập tất cả các mã khác nhau trên thẻ và hầm sẽ được mở khi và chỉ khi tập các mã hóa có n mã hóa (khác nhau) đặt trước. Vì lý do bảo mật, hầm có thể được mở nếu và chỉ nếu có ít nhất thẻ của 6 nhân viên cao cấp. Tìm n và m thỏa mãn n nhỏ nhất để có thể thực hiện được chính sách bảo mật nêu như trên. Lời giải: Dễ thấy với mỗi một nhóm gồm 5 nhân viên cao cấp thì sẽ thiếu ít nhất 1 mã hóa so với n mã hóa đặt trước để mở được hầm. Đặt A là tập hợp các nhóm có 5 nhân viên và B là tập hợp gồm n mã hóa cần để mở hầm. Xét ánh xạ từ A vào 1 trong các mã hóa có thể thiếu trong nhóm 5 người (số mã hóa thiếu có thể nhiều hơn 1, nhưng chỉ xét ánh xạ 1-1 để dễ thực hiện). Gọi ánh xạ này là f, ta sẽ chứng minh nó là đơn ánh. Thật vậy, gọi a1 , a2 ∈ A là 2 nhóm khác nhau thỏa mãn f (a1 ) = f (a2 ) = c , c là mã còn thiếu. Do a1 khác a2 nên 9 tồn tại nhóm 6 người lấy từ 2 nhóm a1 và a2 mà vẫn thiếu ít nhất 1 mã (mã c), (vô lý so với giả thiết). Vậy f là đơn ánh. Rõ ràng f là ánh xạ từ A vào B nên ta có: n = B ≥ A = C155 = 3003 Ta sẽ chứng minh n=3003 thỏa mãn. Khi đó cho mỗi nhóm 5 người 1 nhận được 1 mã c(a) khác nhau trong 3003 mã cho trước (điều này có thể thực hiện được vì ta có tất cả 3003 nhóm). Tiếp theo ta viết mỗi mã c(a) này vào thẻ của các thành viên không nằm trong nhóm . Khi đó, mỗi mã sẽ được viết cho 10 người không trong nhóm, suy ra ta viết tất cả 10.C155 các mã, đồng 10.C155 thời được chia đều cho 15 người nên thẻ mỗi người sẽ có = 2002 mã 15 khác nhau. Xét một nhóm gồm 6 người bất kỳ. Theo như cách sắp xếp mã như trên, với nhóm a gồm 5 người bất kỳ sẽ chỉ thiếu duy nhất một mã c(a). Ta sẽ chứng minh nhóm 6 người có đủ n mã khác nhau. Thật vậy, xét 2 nhóm 5 người bất kỳ a1 và a2 từ 6 người được chọn. Khi đó ta có c( a1 ) ≠ c( a2 ) . Ta sẽ chứng minh rằng nhóm a2 có mã c(a1). Giả sử trong a2 không có mã c(a1), khi đó theo định nghĩa hàm c như ban đầu, ta có c ( a1 ) = c ( a2 ) (vô lý). Vậy một nhóm 6 người sẽ có đủ mã để mở kho, hay m=2002 Kết luận: n=3003, m=2002 Bài 12 [AIME 2001, by Richard Parris]: Cho các số 1,2,3,4,5,6,7,8 được điền bất kỳ lên mặt của 1 bát phương 10