Ứng dụng phương pháp Song ánh trong giải toán Tổ hợp

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 Hình 4: minh họa 1 bát phương Sao cho mỗi một mặt là 1 số khác nhau. Tính xác suất để không có 2 số liên tiếp nào (8 và 1 cũng được cho 2 số liên tiếp) được viết trên 2 mặt có chung cạnh. Lời giải: Để giải bài toán, ta xét thêm hình lập phương có các đỉnh là A,B,C,D,E,F,G, H như ở Hình 5, trong đó đỉnh hình lập phương là các trọng tâm các mặt của bát phương. Khi đó ta sẽ kí hiệu như sau: các số 1,2,3,4,5,6,7,8 thứ tự tương ứng lần lượt là các đỉnh A,B,C,D,E,F,G,H. Cạnh của lập phương nối 2 đỉnh lập phương( nối 2 số) thể hiện mối liên hệ (chung cạnh) giữa 2 mặt bát phương. Ta thấy rõ ràng liên hệ này là 1-1. Khi đó thay vì đếm số trường hợp không có 2 số liên tiếp trên cùng một mặt, ta đếm số cách điền các đỉnh của hình lập phương để không có 2 đỉnh liền kề nào là lập thành 1 cạnh lập phương. Hình 5 Ta chia các đỉnh thành 2 nhóm, G1 = { A, C , F , H } và G2 = {G, E , B, D} . Dễ thấy các đỉnh trong cùng 1 nhóm thì không liền kề với nhau. Bài 13: Cho 1 lưới tam giác có chiều dài mỗi cạnh bên là n, được phủ bởi n2 tam giác con đều có cạnh bằng 1. Xác định có bao nhiêu hình bình hành bị giới hạn bởi các đoạn thẳng của lưới. Lời giải: 11 Hình 6 Ta chia tất cả các hình bình hành thành 3 tập. Có các cạnh của 1 hình bình hành bất kỳ phải song song với đúng 2 cạnh của tam giác. Gọi SYZ là tập các hình bình hành có cạnh song song với 2 cạnh XY và ZX của tam giác. Các tập S XY và S ZX xác định tương tự. Do tính đối xứng nên ta có S XY = SYZ = S ZX . Từ đó, đáp án của ta sẽ là 3 SYZ . Mở rộng các cạnh XY và XZ về phí Y và Z thêm 1 đơn vị, ta được các đoạn thẳng mới là XY’ và XZ’. Xét một hình bình hành bất kỳ thuộc SYZ , ta kéo dài các cạnh của hbh đó, cắt đoạn thẳng Y’Z’ tại 4 điểm phân biệt (hiển nhiên). Từ đây ta xác định được rằng, cứ 4 điểm phân biệt trên đoạn thẳng Y’Z’ vẽ song song với XY và ZX, cắt nhau tại 4 điểm sẽ tạo được 1 hbh thuộc SYZ . Vậy ta có ánh xạ từ SYZ ra bộ 4 điểm trên đoạn Y’Z’ là 1 song ánh, mà đoạn Y’Z’ có tất cả n+2 điểm, nên ta có SYZ = Cn4+ 2 . Vậy có tất cả 3Cn4+ 2 hbh bị giới hạn bởi các cạnh của tam giác. Bài 14: Bart hiện là nhân viên của rạp chiếu phim. Rạp này có sức chứa 200 chỗ ngồi. Trong ngày khởi chiếu phần I Star War: The Phantom Menace, có 200 người đứng xếp hàng để mua vé xem phim. Giá mỗi vé là 5$. Trong 200 người mua vé, 100 trong số họ có hóa đơn loại 5$, nửa còn lại là hóa đơn loại 10$(mỗi người có 1 hóa đơn). Bart vốn bất cNn và vẫn không chịu thay đổi. 200 người đó xếp hàng 1 cách ngẫu nhiên và không ai muốn chờ để thay đổi vé của mình khi họ mua vé. Xác suất là bao nhiêu để Bart có thể bán được hết tất cả các vé có lợi nhất (thành công) Lời giải: 12 Để dễ dàng hơn ta thay 100 bằng n . Ta xem xét những người là không phâ biệt được. Ta cân nhắc sự sắp xếp của n người sở hữu hóa đơn 5$ và n người sở hữu hóa đơn 10$ (nói cách khác ta làm phép nhân lên (n!) 2 tới cả hai mẫu số và tử số, việc này không ảnh hưởng tới giá trị của xác suất). Có C2nn cách sắp xếp xác số mà không hạn chế. Bart sẽ thành công khi và chi khi: ta sắp xếp 2n số vào một hàng ngang và đánh số vị trí của chúng từ trái qua phải từ 1, 2,3,..., 2 n . Với 1 ≤ i ≤ 2n , đặt ai (bi ) là số người có hóa đơn 5$ (10$) đứng trước vị trí thứ i . Ta cần đếm số sự sắp xếp thỏa mãn ai ≥ bi với 1 ≤ i ≤ 2n . Gọi S là tập hợp tất cả các sắp xếp như vậy. Gọi T là tập hợp các sự sắp xếp khác nhau như trên. Ta sẽ tìm T . Ta có S = C2nn − T Một phần tử t ∈ T , t = (t1 , t2 ,..., t2 n ) có số i,1 ≤ i ≤ 2 n thỏa mãn ai < bi . Gọi f (t ) là ký hiệu của số chỉ đầu tiên. Bởi sự xác đinh cả ta, f (t ) − 1 f (t ) + 1 a f (t ) = , bf (t ) = và t f ( t ) = 10 . Vì vậy có nhiều hơn số hóa đơn 2 2 10$ so với 5$ tính đến (tại) thời điểm thứ f (t ) . Ta thay đổi toàn bộ các đồng 5$ thành 10$ và các đồng 10$ thành 5$ sau thời điểm thứ f (t ) , thì khi đó ta thu được một hoán vị g (t ) của n + 1 đồng 10$ và n − 1 đồng 5$ Ví dụ: với n=6 ta có: t = ( 5,10,10,5,10,10,10,5,10,5,5,5) Ta có (a1 , a2 ,..., a12 ) = (1,1,1,2,2,2,2,3,3,4,5,6) (b1 , b2 ,..., b2 ) = (0,1,2,2,3,4,5,5,6,6,6,6) f (t ) = 3, a2 = 1, b2 = 1, t3 = 10 g (t ) = (5,10,10,10,5,5,5,10,5,10,10,10) Do đó ta xác định một ánh xạ từ T vào U- là tập hợp hoán vị của n + 1 đồng 10$ và n − 1 đồng 5$. Ta sẽ hứng minh g là một song ánh Đầu tiên ta chứng minh g là một toàn ánh. Xét u là một phần tử bất kỳ thuộc U . Ta đếm số lần xuất hiện của đồng 5$ và 10$ tính từ trái qua phải với i là các giá trị nguyên nhỏ nhất sao cho tính đến thời điểm thứ i số đồng 10$ là nhiều hơn số đồng 5$. Ta thay đổi toàn bộ các đồng 5$ thành 10$ và toàn bộ các đồng 10$ thành 5$ sau thời điểm thứ i . Vì số đồng 10$ có số lượng lớn hơn 2 so với số đồng 5$ trong U nên sẽ có số đồng 10$ nhiều hơn số đồng 5$ tại trước thời điểm i và số đồng 10$ nhiều hơn số đồng 5$ tại 2n − i thời điểm còn lại. Sau bước đổi 5 → 10 và 10 → 5 trên ta thu được số đồng 5$ 13 và 10$ bằng nhau. Không khó để thấy dáy mới này thuộc T , do đó g là một toàn ánh. Bây giờ ta chứng minh g là đơn ánh. Xét t và t ' là 2 phần tử thuộc T . Giả sử rằng tại thời điểm thứ i,1 ≤ i ≤ 2 n là thời điểm đầu tiên t và t ' có sự khác nhau. Không giảm tính tổng quát g/s ti = 5 và , thì f (t ) ≠ i . N ếu f (t ) < i thì f (t ') = f (t ) bởi i − 1 vị trí đầu của t và t ' là hoàn toàn giống nhau. Khi đó tại thời điểm thứ i , g (t ) và g (t ') có giá trị là 10 và 5 tương ứng, do đó g (t ) ≠ g (t ') . Ta lại xét f (t ) > i . Thì tại thời điểm thứ i của g (t ) là ti , có ti = 5 . Bởi vì (i − 1) vị trí đầu của t và t ' như nhau, f (t ') > i . Dô đó tại thời điểm thứ i của g (t ') là t ' , nó bằng 10. Do đó g (t ) ≠ g (t ') . Suy ra g là song ánh. Từ đó theo ta có: T = U = C2nn−1 . Vậy S = C2nn − T = C2nn − C2nn−1 = Trở lại bài toán, ta có n = 200 , vậy xác suất là 1 C2nn n +1 1 201 Bài 15: Cho n là số nguyên dương thỏa mãn các tính chất: nếu n cái domino được đặt trên 1 bàn cờ 6x6 với mỗi domino chiếm 2 đơn vị diện tích vuông, thì luôn luôn có thể đặt thêm 1 domino lên trên bàn mà không phải di chuyển bất kỳ domino nào khác. Xác định giá trị lớn nhất của n. Lời giải: Ta sẽ chứng minh giá trị lớn nhất của n là 11. Hình 7 là cách sắp xếp 12 domino trên bàn cờ thì không thể để thêm 1 domino nào nữa. Suy ra n ≤ 11 . Hình 7 14 Ta sẽ chứng minh rằng với 11 domino trên bàn cờ thì luôn đặt thêm được 1 domino nữa. Ta sẽ chứng minh bằng phản chứng. Giả sử rằng tồn tại cách đặt 11 domino trên bàn cờ mà không thể đặt thêm 1 domino nào nữa. Khi đó số ô vuông trên bàn chưa bị phủ bởi 11 domino là: 36-22=14. Đặt S1 là phần trên của bàn cở ban đầu có kích thước 5x6 (Hình 8). Đặt A là tập các ô vuông trong S1 mà không bị phủ bởi các domino, và S2 là hàng cuối của bàn cờ (bàn cờ chia làm 2 phần S1 và S2). Vì ta không thể điền thêm 1 domino nào vào bàn cờ, nên một trong 2 ô vuông bất kỳ cạnh nhau sẽ được bao phủ bởi 1 domino, suy ra S2 có nhiều nhất là 3 ô không bị phủ bởi domino (trống), suy ra S1 có ít nhất là 14-3=11 ô trống. Hình 8 Đặt S3 là phần dưới của bàn cờ và có kích thước 5x6 (Hình 8), B là tập tất cả các domino nằm trong S3. Ta sẽ định nghĩa một ánh xạ f từ A vào B. Ta có, với mỗi ô vuông trống s trong S1, sẽ tồn tại một ô vuông t nằm dưới s. Suy ra ô vuông t nằm trong S3 và được phủ bởi một domino d. Rõ ràng domino d phải nằm trong S3 (vì nếu ko thuộc S3 thì nó sẽ gồm 2 ô t và s-vô lý). Khi đó ta xác định ánh xạ f là f ( s ) = d . Ta sẽ chứng minh rằng f là đơn ánh. Thật vậy, giả sử ∃s1 , s2 ∈ A sao cho f ( s1 ) = f ( s2 ) = d . Suy ra d phủ 2 ô vuông ở dưới s1 và s2 . Suy ra s1 và s2 nằm cạnh nhau (Hình 9), như vậy khi đó ta có thể đặt thêm 1 domino phủ lên s1 và s2 (vô lý). Vậy f là đơn ánh, suy ra A ≤ B hay B ≥ 11 . N hưng cả bàn cờ chỉ có 11 domino, suy ra B = 11. Khi đó thì hàng trên cùng sẽ không bị phủ bởi 1 domino nào, và sẽ đặt được thêm 1 quân domino nữa (vô lý). 15 Hình 9 Vậy giá trị lớn nhất của n là 11. Bài 16 [China 2000, by Jiangang Yao]: Cho số nguyên dương n và xác định M = {( x, y ) | x, y ∈  ,1 ≤ x, y ≤ n} Hỏi có bao nhiêu ánh xạ f xác định trên M thỏa mãn i. ii. iii. f ( x, y ) là số tự nhiên với mọi ( x, y ) ∈ M n  f ( x, y) = n − 1 với mọi x thỏa mãn 1 ≤ x ≤ n N ếu f ( x1 , y1 ) f ( x2 , y2 ) > 0 thì ( x1 − x2 )( y1 − y2 ) ≥ 0 y =1 Lời giải: Có kết luận Cnn −−11 giá trị của hàm f . Ta coi một hàm f trên M như 2 một ma trận M f = ( si , j ) với n hàng và n cột sao cho f (i, j ) = si , j Điều kiện i,ii,iii trở thành i’. tất cả các thành phần của M f là các số tự nhiên ii’. tổng của tất cả các thành phần của M f theo hàng ngang bằng n − 1 iii’. tất cả các thành phần (nhập vào) của M f có thể đi theo 1 lối đi từ thành phần (nhập vào) trên cùng bên trái s1,1 tới thành phần bên phải dưới sn ,n bằng các bước dịch chuyển xuống hoặc sang phải một đơn vị mỗi lần. Điều đó là đúng vì nếu si , j > 0 và si +1,k > 0 thì j ≤ k vì [i − (i + 1)][ j − k ] ≥ 0 và hơn thế nữa mỗi đường đi thỏa mãn xác định duy nhất một ma trận M f nếu đường đi đó đòi hỏi phải đi qua (xuống) tới si , j nếu si , j > 0 và si .k = 0 với j +1≤ k ≤ n . 16 Ta gọi ma trận thỏa mãn i’, ii’, iii’ là ma trận tốt. Rõ ràng có một song ánh giữa tập hợp tất cả các hàm thỏa mãn điều kiện bài toán với tập các ma trận tốt Ta cần đếm tất cả các ma trận tốt. Do đó ta xét bài toán khác sau: Một công viên bị chia thành một lưới n × n các hình vuông đơn vị. N gười làm vườn của công viên phải trồng n − 1 cây vào mỗi hàng ngang của lưới. Anh ấy có thể trồng bất kỳ chiếc cây nào (các cây không phân biệt) vào một ô vuông. Và anh ta có thể trồng nhiều hơn 1 cây vào ô vuông . Anh ta làm việc trồng cây bắt đầu từ góc tây bắc( trên cùng bên trái) của công viên xuống góc đông nam (dưới cùng bên phải) của công viên. Anh ta trồng một hàng cây tại một thời điểm và khi hoàn thành 1 hàng, anh ta tự chuyển xuống hàng ngang phía dưới ( phía nam). N gười làm vườn có 3 trạng thái 1. trồng 1 cây ở hình vuông anh ta đang đứng 2. chuyển tới một hình vuông ở phía đông (phải) 3. tự động xuống dưới (phía nam) nếu anh ta trồng đủ n − 1 cây ở hàng anh ta đang đứng (trừ hàng cuối) Chúng ta không phải lo lắng ở trường hợp (3) vì người làm vườn luôn cNn thận đếm số cây đã trồng trong 1 hàng và chỉ chuyển xuống hàng tiếp theo nếu đã trồng đủ (n − 1) cây ở hàng đang đứng. Anh ta trồng (n − 1) cây ở mỗi hàng ngang nếu tổng số cây đã trồng là n(n − 1) cây. Do đó anh ta thực hiện n(n − 1) trạng thái loại (1). Với trường hợp chuyển vị trí xuống góc dưới cùng phía bên phải anh ta phải thực hiện (n − 1) trạng thái loại (2). Và do đó anh ta có tất cả n(n − 1) + n − 1 = n 2 − 1 trạng thái. Vì anh ta có thể biểu diễn trạng thái theo ý muốn nên số cách anh ta thực hiện công việc là Cnn −−11 (do phải trồng n − 1 cây). Không khó để thấy rằng có sự tương ứng một-một giữa các ma trận tốt và số cách trồng của người làm vườn. 2 Ví dụ với n = 4 , nếu 1 và e là ký hiệu tương ứng cho trạng thái (1) và (2) thì coi dãy 11ee11111111e11,e1111111111e1e1,11111111e11e11e tương ứng với các hình vẽ sau: ** * * ** * ** * ** 17 * ** * ** * ** * * * Và có 3 ma trận tương ứng là 2 0  0  0 0 1 0 0 0 0 3 0  và  0 0 3 0   0 1 0 0 3 0 0 3 0 0  3 0 0  1 1 1 Do đó số ma trận M f bằng số các hàm số f và cùng bằng Cnn−−11 2 Bài 17: Cho số nguyên dương n, và tập A là tập tất cả các dãy con tăng có tổng bằng n . Đặt a = (a1 , a2 ,..., am ) là phần tử của A . Đặt s(a) là chỉ số bé nhất thỏa mãn as ( a ) , as ( a )+1 ,..., am là các số nguyên liên tiếp. Giả sử n không thể viết k (3k − 1) k (3k + 1) hoặc với mọi số nguyên dương k . Đặt A1 là 2 2 tập con của A thỏa mãn a ∈ A1 khi và chỉ khi a1 ≤ m − s ( a ) + 1 . dưới dạng Chứng minh rằng A = 2 A1 Lời giải: thỏa mãn a ∈ A1 ' khi và chỉ khi Gọi A1 ' là tập con của A a1 > m − s ( a ) + 1 . Khi đó ta có A = A1 ∪ A1 ' . Ta sẽ chứng minh tồn tại 1 song ánh đi từ A1 vào A1 ' . Thật vậy, ta định nghĩa ánh xạ như sau: a = (a1 , a2 ,..., am ) → a ' = (a2 ,..., am−a , am−a +1 + 1,..., am + 1) (*) 1 1 (Thực hiện chia đều a1 cho a1 phần tử cuối của a , và xóa đi a1 , ta được phần tử mới a ' -giúp đảm bảo tổng các phần tử đều bằng n Ví dụ với n = 42 và a = (3,5,7,8,9,10) . Ta có a1 = 3, m = 6 và s(a) = 3 , do đó a ∈ A1 . Khi đó qua phép ánh xạ ở trên, ta được a ' = (5,7,9,10,11) . Ta có 18 thể quan sát dễ dàng trên biều đồ Young (. N hư trên hình 12, ta xóa 3 điểm trong cột thứ nhất (vì a1 = 3 ) và chia đều số điểm đó cho 3 cột sát bên phải nhất. Hình 10 Ta cần chứng minh: i. a ' ∈ A1 ' ii. Phép ánh xạ (*) là đơn ánh iii. Phép ánh xạ (*) là toàn ánh Cm (i): Ta có m − a1 + 1 ≥ s ( a ) (vì a ∈ A1 ). Do s(a) là chỉ số nhỏ nhất để as ( a ) , as ( a )+1 ,..., am là các số tự nhiên liên tiếp, suy ra ta có am−a +1 + 1,..., am + 1 là các số tự nhiên liên tiếp. 1 N ếu m − a1 + 1 ≥ 3 thì ánh xạ (*) cho: a ' = (a2 ,..., am − a , am −a +1 + 1,..., am + 1) = (a1' ,..., am' −1 ) 1 1 a1' = a2 ≤ am' −a −1 = am−a ≤ am−a +1 − 1 = am' −a − 2 . Suy ra s(a ') = m − a1 . 1 1 1 1 Khi đó m '− s ( a ') + 1 = ( m − 1) − ( m − a1 ) + 1 = a1 , lại có a2 > a1 nên suy ra a = a2 > m '− s (a ') + 1 . Vậy a ' ∈ A1' . ' 1 m − a1 + 1 = 2 thì ánh xạ N ếu a ' = (a2 + 1,..., am + 1) = (a1' ,..., am' −1 ) và s (a ') = 1, m ' = m − 1 . a1' = a2 + 1 > m '− s (a ') + 1 = m − 1 = a1 + 1 . Vậy a ' ∈ A1' . 19 (*) cho Khi đó do N ếu m − a1 + 1 = 1 , suy ra s ( a ) = 1 . Khi đó ta có a1 , a2 ,..., am là m số tự nhiên liên tiếp. Khi đó ta có m(m − 1) m(m − 1) m(3m − 1) n = ma1 + = m2 + = (vô lý với giả thiết). 2 2 2 Vậy a ' ∈ A1' và s(a ') = m − a1 (1) Chứng minh ii: ta sử dụng pp phản chứng. Giả sử ∃a ≠ b, a, b ∈ A1 sao cho qua phép ánh xạ (*) có ảnh là a ', b ' ∈ A1' thỏa mãn a ' = b ' . Do phép ánh xạ (*) làm giảm chiều dài của dãy mới đi 1 so với ban đầu, suy ra a và b có cùng chiều dài. Đặt b = (b1 , b2 ,..., bm ) . Ta có m − a1 = s ( a ') = s (b ') = m − b1 (theo 1). Suy ra a1 = b1 , suy ra a = b (mâu thuẫn). Vậy phép ánh xạ (*) là đơn ánh Để chứng minh ý (iii), ta sử dụng ánh xạ ngược của (*). Đặt a ' = (a1' , a2' ,..., am' −1 ) ∈ A1' . Ta thực hiện phép ánh xạ ngược như sau: trừ đi 1 đơn vị ở m − s ( a ') số tự nhiên liên tiếp của a ' , sau đó thêm vào trước a1' số có giá trị bằng m − s ( a ') . Gọi phần tử mới này là a , ta sẽ chứng minh a ∈ A1 . Để ý dạng tổng quát của a như sau: a = (m − s (a '), a1' ,..., as' ( a ') −1 , as' ( a ') − 1,..., am' −1 − 1) (dễ thấy có cái này thì s (a ') − 1 ≥ 1 để thỏa mãn đk về chỉ số). Ta sẽ xét 2 trường hợp: N ếu s(a ') − 1 ≥ 1. Ta có a ' ∈ A1' nên a1' > (m − 1) − s(a ') + 1 = m − s(a ') và as' ( a ')−1 ≤ as' ( a ') − 2 . Khi đó ánh xạ ngược của (*): a = (a1 , a2 ,..., am ) = (m − s (a '), a1' ,..., as' ( a ')−1 , as' ( a ') − 1,..., am' −1 − 1) Lại có as' ( a ') , as' ( a ')+1 ,..., am' −1 là các số tự nhiên liên tiếp nên as ( a ')+1 = as' ( a ') − 1 ,…, am = am' −1 − 1 là các số tự nhiên liên tiếp. Khi đó chỉ số s (a) của a phải nhỏ hơn bằng s (a ') + 1 ( s(a) ≤ s(a ') + 1 ) Kết hợp lại ta có: a1 = m − s ( a ') ≤ m − s ( a ) + 1 , suy ra a ∈ A1 N ếu s ( a ') = 1 . Vì a ' ∈ A1' nên a1' > (m − 1) − s(a ') + 1 = m − 1 . N ếu a1' = m (m − 2)(m − 1) n = a1' + ... + am' −1 = m + ... + (m + m − 2) = m(m − 1) + 2 thì ta có (m − 1) [3(m − 1) + 1] = 2 (vô lý). 20 Vậy a1' ≥ m + 1 suy ra. Khi đó ánh xạ ngược của (*) cho ta có a = (m − 1, a1' − 1,..., a1m−1 − 1) thỏa mãn a1 = m − 1 ≤ m − s (a ) + 1 (do s(a) ≤ 2 ). Vậy ánh xạ ngược của (*) cho ra a ∈ A1 Vậy phép ánh xạ (*) là song ánh, suy ra A1 = A1' , suy ra A = 2 A1 Bài 18 [VMO 1996]: Cho các số nguyên dương k và n với k ≤ n . Hỏi có tất cả bao nhiêu chỉnh hợp ( a1 , a2 ,..., ak ) chập k của n số nguyên dương đầu tiên, mà mỗi chỉnh hợp ( a1 , a2 ,..., ak ) thỏa mãn ít nhất một trong 2 điều kiện sau: 1. Tồn tại s, t thuộc {1, 2,...,k } sao cho s < t và as > at 2. Tồn tại s thuộc {1, 2,...,k } sao cho ( as − s ) không chia hết cho 2 Lời giải: Gọi A = {( a1 , a2 ,..., ak )} với k ≤ n , ai = {1, 2,..., n} với mọi i = 1, 2,..., k . Xét tập B ⊂ A thỏa mãn nếu ( a1 , a2 ,..., ak ) ∈ B thì ai < ai +1 với ∀i = 1,2,..., k − 1 và ai ≡ i (mod 2) với ∀i = 1,2,..., k . Xét tập D ⊂ A mà mỗi chỉnh hợp a ∈ D thỏa mãn yêu cầu bài toán. Rõ ràng ta có D = A \ B nên số chỉnh hợp cần phải tìm là D = A − B (1) Để xét số phần tử của tập B ta thấy ai + i ≡ 2i ≡ 0(mod 2) với ∀i = 1, 2,..., k nên ta lập ánh xạ f : B → E xác định bởi: ( ( a , a ,..., a ) ) = ( a + 1, a + 2,..., a Với E = {( e , e ,..., e )} trong đó f 1 2 k 1 1 2 2 k k + k ) , i = 1,2..., k 2 ≤ ei ≤ n + k , ei ≡ 0(mod 2) với ∀i = 1, 2,..., k và 1 + ei < ei +1 với ∀i = 1,2,..., k − 1 Dễ dàng thấy nếu b, b ' ∈ B mà b ≠ b ' thì f (b) ≠ f (b ') nên f là đơn ánh. Mặt khác từ ei ≡ 0(mod 2) thì ei − i ≡ i(mod 2) và từ ei < ei +1 − 1 suy ra ei − i < ei +1 − i − 1 (hay ai < ai +1 khi đặt ai = ei − i, ai +1 = ei +1 − i − 1 ), mà 2 ≤ ei < ei +1 ≤ n + k nên 1 ≤ ai < ai +1 ≤ n với ∀i = 1,2,..., k − 1 . Từ đó, với mỗi e = ( e1 , e2 ,..., ek ) ∈ E thì tồn tại b = ( a1 , a2 ,..., ak ) ∈ B sao cho f (b) = e , nghĩa là f là toàn ánh. Vậy f là song ánh nên B = E . Với tập E được xác định như n + k  (2) trên ta có B = E = Cmk với m =   2  Từ (1) và (2) và A = n! ta có: (n − k )! 21 D= A−E = n! n + k  − Cmk với m =  (n − k )!  2  N hận xét: 2. Dùng song ánh để chứng minh các hằng đẳng thức tổ hợp Bài 1:Chứng minh hằng đẳng thức (C ) + (C ) + (C ) 2 0 n 1 2 n 2 n 2 + ... + ( Cnn ) = C2nn 2 Hướng dẫn: Ta thấy C2nn bằng số cách chọn ra n đối tượng từ 2n đối tượng đôi một khác nhau. Mặt khác, chia 2n đối tượng này ra thành 2 nhóm: N hóm 1 và nhóm 2 đều gồm n đối tượng. Khi đó để chọn ra n phần tử ta thực hiện như sau. Chọn k phần tử từ nhóm 1: có Cnk cách chọn, sau đó chọn n − k đối tượng từ nhóm 2: có Cnn−k = Cnk cách chọn. Theo quy rắc nhân có ( Cnk ) cách chọn ra n 2 đối tượng mà trong đó có k đối tượng thuộc nhóm 1. Cho k = 0,1,..., n và theo quy tắc cộng ta có đpcm Bài 2:Chứng minh hằng đẳng thức: n  k (C ) k n k =0 2 = nC2nn−−11 HD: Xét bài toán có n học sinh nam và n học sinh nữ. Hỏi có bao nhiêu cách chọn ra n học sinh sao cho có 1 học sinh nam làm lớp trưởng. Bài 3: Chứng minh hằng đẳng thức: n 2 C C k k =0 k n  n−k   2    n−k = C2nn+1 HD: Xét bài toán “chọn n số từ 2n+1 số khác nhau” theo 2 cách: Cách 1: chia 2n+1 số thành n cặp gồm 2 số và 1 số x • Bước 1: chọn ra k cặp, từ mỗi cặp này chọn ra một số. Có Cnk cách chọn ra k cặp và có 2 cách chọn ra 1 số trong mỗi cặp. Vậy theo quy tắc nhân có 2 k Cnk cách chọn theo bước 1 22 n−k • Bước 2: chọn  cặp trong n − k cặp còn lại, ngoài ra số x sẽ  2  được chon nếu n − k lẻ và không chọn được thêm x nếu n − k chẵn. Khi đó có C  n−k   2    n−k cách chọn trong bước 2  n−k     2  n−k Theo quy tắc nhân có C .Cnk .2k cách chọn ra n số trong mỗi lần chọn. Cho k = 0,1, 2,..., n ta có được tổng ở vế trái đẳng thức. Cách 2: chọn theo tổ hợp chập n của 2n + 1 phần tử: có C2nn+1 cách chọn Vậy ta có đpcm Bài 4:CMR: n! = n nCn0 − (n − 1) n Cn1 + (n − 2) n Cn2 − (n − 3) n Cn3 + ... + (−1) n−1 Cnn−1 HD: Xét X là tập toàn ánh từ tập M = {1,2,...,n} vào chính nó. Mỗi toàn ánh từ M vào chính nó là một hoán vị của M . Suy ra số các toàn ánh từ M vào M là X = n! (*) Mặt khác: đặt Hom(M,M)= tập các ánh xạ từ M vào M. Suy ra Hom( M , M ) = n n Đặt Ai = { f ∈ Hom( M , M ) | i ∈ f ( M )} với i = 1, 2,..., n . Khi đó: n X = Hom( M , M ) \   Ai   X = n n −  i =1  Ta có n A i =1 i n A i =1 i (1) = Cn1 (n − 1) n − Cn2 (n − 2) n + Cn3 (n − 3) n + ... + (−1) n−1 Cnn−1 (2) Từ (1) và (2) ta có : X = n nCn0 − (n − 1)n Cn1 + (n − 2)n Cn2 − (n − 3)n Cn3 + ... + (−1)n−1 Cnn−1 Từ (*) và (**) ta có đpcm n   2 C C i =0 i n i n −i 2n−2i = C2nn 3. Dùng song ánh để tính tổng các phần tử của một tập 23 (**) Bài 1:Cho tập A = {1,2,..., n} . Mỗi tập con không rỗng của A ta xác định duy nhất một tổng đan dấu như sau: sắp xếp các phần tử của A theo thứ tự tăng dần sau đó gán luân phiên các dấu + và – sao cho phần tử lớn nhất mang dấu cộng. Tính tổng các tổng đan dấu trên HD: Coi tập rỗng có tổng bằng 0 Với các tập Ai khác rỗng ta chia chúng làm 2 loại: tập A1 chứa các tập chứa phần tử n , tập A2 chứa các tập không chứa phần tử n . Khi đó tương ứng sau là song ánh: f : A2 → A1 Ai = {a1 > a2 > ... > ai } → f ( Ai ) = {n > a1 > a2 > ... > ai } Khi đó tổng của tổng đan dấu của Ai và f ( Ai ) bằng n. Vì A có 2 n tập con nên có 2n−1 cặp tập con Ai và f ( Ai ) . Suy ra tổng các tổng đan dấu bằng n.2n−1 Bài 2: (NMO Việt Nam) Cho tập S = {1,2,..., n} . Gọi T là tập tất cả các tập con không rỗng của S . Với mỗi X ∈ T , gọi m( X ) là trung bình cộng các phần tử của X . Tính m( X ) m=  T HD: Xét song ánh f : T → T , f (X) = {n + 1 − x} với x ∈ X Ta thấy m( X ) + m( f ( X )) = n + 1 . Do đó: 2 m( X ) =  ( m( X ) + m( f ( X )) ) = T .(n + 1)  m = n +1 2 Bài 3: Hãy tính trung bình cộng tất cả các số N = a1a2 ...an chia hết cho 99 và các chữ số của N thuộc tập {1,2,3,4,5,6,7,8} HD: Gọi T là tập tất cả các số dạng N . Khi đó xét tương ứng 24 f : T →T a1...an → b1...bn với bi = 9 − ai , i = 1, 2,..., n Ta thấy: N + f ( N ) = 99...999 nên f ( N ) ∈ T và f là một ánh xạ. Dễ chứng minh f là một song ánh. Khi đó: 2  N =  N + f ( N ) = T .99...9 N ∈T N ∈T n Suy ra TBC các số N là 99...9  = 10 − 1 n chu so 9 25 Tài liệu tham khảo [1] TiTu Andreescu, Zuming Feng; A path to combinatorics for undergraduates [2] Lê Hải Châu, Giới thiệu các bài thi chọn HỌC SINH GIỎI TOÁN phổ thông trung học toàn quốc (từ năm 1962 ñến năm 2000) [3] N guyễn Sinh N guyên, N guyễn Văn N ho, Lê Hoàng Phò; Tuyển tập các bài dự tuyển Olympic toán học quốc tế 1991-2001 [4] Vũ Dương Thụy, N guyễn Văn N ho; 40 năm Olympic toán quốc tế [5] N guyễn Văn Mậu (chủ biên), Chuyên đề TOÁN RỜI RẠC và một số vấn đề liên quan (tài liệu dùng cho lớp bồi dưỡng giáo viên THPT Chuyên – hè 2007) [6] Tủ sách toán học và tuổi trẻ, Các bài thi Olympic toán trung học phổ thông Việt Nam (1990 – 2006), Nxb Giáo dục (2007). [7] Đề thi học sinh giỏi quốc gia các năm 2012,2014 [8] tai lieu\CH2.pdf 26