ĐẠi học quốc gia hà NỘI
Một số bài toán giải bằng phương pháp song ánh
tải về 0.86 Mb.
|
- Điều hướng trang này:
- 3.2.2 Các bài toán tổ hợp giải bằng phương pháp song ánh
- 3.3 Một số bài toán giải bằng phương pháp hàm sinh
- 3.3.1 Bài toán chọn các phần tử riêng biệt.
- 3.3.2 Bài toán chọn các phần tử có lặp
3.2 Một số bài toán giải bằng phương pháp song ánh3.2.1 Phương pháp song ánhĐịnh nghĩa (Giải tích toán học rời rạc). Cho ánh xạ Ánh xạ được gọi là một đơn ánh nếu với hai phần tử bất ḱ mà th́ , tức là . Ánh xạ được gọi là một toàn ánh nếu với mọi đều tồn tại để cho . Ánh xạ được gọi là một song ánh (tương ứng 1 – 1) nếu với mọi đều tồn tại duy nhất để cho . Nói cách khác là song ánh khi và chỉ khi nó vừa là đơn ánh, vừa là toàn ánh.
Phương pháp song ánh dựa vào một ư tưởng rất đơn giản: Nếu tồn tại một song ánh từ A vào B th́ . Do đó muốn chứng minh hai phần tử có cùng số phần tử, chỉ cần xây dựng một song ánh giữa chúng. Hơn nữa ta có thể đếm được số phần tử của một tập hợp A bằng cách xây dựng một song ánh từ A vào một tập hợp B mà ta đă biết cách đếm số phần tử. Bởi B có cùng số phần tử với A nhưng có cấu trúc được mô tả khác A nên ta có thể đếm được số phần tử của B dễ dàng hơn việc đếm số phần tử của A.
Bài 84: (Vô địch Liên Xô). Có một nhóm người mà trong đó mỗi cặp không quen nhau có đúng hai người quen chung, c̣n mỗi cặp quen nhau th́ không có người quen chung. Chứng minh số người quen của mỗi người là như nhau. Giải:
Nếu a quen b và tập các người quen của a và b (không kể a, b) lần lượt là A và B. Mỗi người a’ thuộc A sẽ quen với một người duy nhất thuộc B (do a’ và b không quen nhau, hơn nữa họ đă có một người quen chung là a). Tương tự mỗi người thuộc B cũng quen với duy nhất một người thuộc A . Vậy tồn tại một song ánh đi từ A tới B, tức a và b có số người quen bằng nhau. Nếu a không quen b th́ tồn tại c quen cả a và b. Do đó số người quen của a và b bằng nhau do cùng bằng số người quen của c (suy ra từ trên) Bài 85: Xét tập . Đối với mỗi tập con không trống của A chúng ta xác định duy nhất một tổng đan dấu theo quy tắc sau: Xếp các số của tập con theo thứ tự tăng dần và gán luân phiên các dấu cộng, trừ cho các số liên tiếp theo thứ tự của tập con sao cho số lớn nhất có dấu cộng. Hăy t́m tổng của tất cả các tổng đan dấu. Giải:
Quy ước tổng đan dấu của tập trống có giá trị 0. Mỗi tập con của A được chia làm hai loại: Loại 1: Có chứa n. Loại 2: Không chứa n. Các tập con loại 1 và loại 2 có số phần tử bằng nhau v́ tồn tại một song ánh giữa chúng như sau: Giả sử . Khi đó tổng đan dấu của một tập con trên bằng
Có 2n tập con của A suy ra có 2n – 1 cặp tập hợp con loại 1 và loại 2 theo định nghĩa trên. Vậy tổng của tất cả các tổng đan dấu bằng
Hàm sinh có thể được áp dụng trong các bài toán đếm. Nói riêng các bài toán chọn các phần tử từ một tập hợp thông thường sẽ dẫn đến các hàm sinh. Khi hàm sinh được áp dụng theo cách này, hệ số của xn chính là số cách chọn n phần tử, tức là với an là hệ số của xn với mọi n lớn hơn hoặc bằng 2 th́ hàm sinh của số cách chọn sẽ là .
Bài 86: Có bao nhiêu cách chọn n phần tử phân biệt từ tập hợp k phần tử. Giải:
Bài toán này có thể giải quyết dễ dàng bằng công thức tổ hợp. Nhưng lần này chúng ta sẽ sử dụng hàm sinh. Cụ thể Đầu tiên ta xét tập hợp có một phần tử . Ta có: 1 cách chọn 0 phần tử. 1 cách chọn 1 phần tử. 0 cách chọn 2 phần tử trở lên. Suy ra hàm sinh cho số cách chọn n phần tử từ tập là . Tương tự như vậy, hàm sinh cho số cách chọn n phần tử từ tập cũng là (không phụ thuộc vào sự khác biệt giữa các ). Tiếp tục xét tập 2 phần tử ta có 1 cách chọn 0 phần tử. 2 cách chọn 1 phần tử. 1 cách chọn 2 phần tử . 0 cách chọn 3 phần tử trở lên. Suy ra hàm sinh cho số cách chọn n phần tử từ tập là
Tiếp tục áp dụng quy tắc này ta sẽ được hàm sinh cho số cách chọn các phần tử từ tập k phần tử. Ta có . Như vậy hệ số của xn trong là và bằng số cách chọn n phần tử phân biệt từ tập k phần tử.
Để hiểu cách giải bài toán này trước tiên ta phải mở rộng, ta có quy tắc xoắn Gọi là hàm sinh cho cách chọn các phần tử từ tập hợp A và là hàm sinh cho cách chọn các phần tử từ tập hợp B. Nếu A và B rời nhau th́ hàm sinh cho cách chọn các phần tử từ tập là Quy tắc này đúng cho cả trường hợp chọn các phần tử phân biệt, cũng đúng cho trường hợp chọn nhiều lần cùng một phần tử.
Giải:
Chia tập n phần tử thành hợp của n tập ; mỗi tập gồm duy nhất một phần tử thuộc tập n phần tử. Với mỗi tập ta có: 1 cách chọn 0 phần tử. 1 cách chọn 1 phần tử. 1 cách chọn 2 phần tử. Suy ra hàm sinh của cách chọn có lặp từ tập là
Áp dụng quy tắc xoắn suy ra hàm sinh của cách chọn có lặp các phần tử từ tập hợp n phần tử sẽ là :
Bây giờ ta cần tính hệ số của trong Áp dụng khai triển Taylor
Suy ra hệ số của là . Như vậy số cách chọn k phần tử có lặp từ tập hợp có n phần tử là .
Giải :
Theo bài tập trên số cách chọn 12 cái kẹo từ 5 loại kẹo này là . Bài 89 : Bài toán chọn quả Có bao nhiêu cách sắp xếp một giỏ n trái cây thỏa măn các điều kiện sau : Số táo phải chẵn. Số chuối phải chia hết cho 5. Chỉ có thể có nhiều nhất 4 quả cam. Chỉ có thể có nhiều nhất một quả đào. Bài toán có những điều kiện ràng buộc rất phức tạp và ta có cảm giác như việc giải bài toán là vô vọng. Nhưng hàm sinh lại cho ta cách giải nhanh gọn. Giải: Trước tiên ta đi t́m hàm sinh cho từng loại quả Chọn táo 1 cách chọn 0 quả táo. 0 cách chọn 1 quả táo. 1 cách chọn 2 quả táo. 0 cách chọn 3 quả táo. ……………………….. Như thế ta có hàm sinh . Tương tự ta t́m được hàm sinh cho cách chọn chuối là : Hàm sinh cho cách chọn cam và đào hơi khác một chút. Chọn cam 1 cách chọn 0 quả cam. 1 cách chọn 1 quả cam. 1 cách chọn 2 quả cam. 1 cách chọn 3 quả cam. 1 cách chọn 4 quả cam. 0 cách chọn 5 quả cam. Như thế ta có hàm sinh . Tương tự ta t́m được hàm sinh cho cách chọn đào là :
Áp dụng Quy tắc xoắn suy ra hàm sinh cho cách chọn từ cả 4 loại quả là: Như vậy cách xếp giỏ trái cây gồm n trái đơn giản là cách. Bài 90: T́m hàm sinh để xác định số cách chia 10 quả bóng giống nhau cho 4 đứa trẻ để mỗi đứa nhận ít nhất hai quả. Giải:
Để giải bài toán ta t́m hàm sinh cho số cách chia bóng cho một đứa trẻ. Giả thiết cho mỗi đứa nhận ít nhất hai quả bóng nên ta suy ra 0 cách đứa trẻ nhận 0 quả. 0 cách đứa trẻ nhận 1 quả. 1 cách đứa trẻ nhận 2 quả. 1 cách đứa trẻ nhận 3 quả. Vậy hàm sinh cho cách chia đó là Áp dụng quy tắc xoắn ta t́m được hàm sinh cho cách chia bóng cho 4 đứa trẻ là Suy ra số cách chia 10 quả bóng chính là hệ số của và bằng cách.
|