ĐẠi học quốc gia hà NỘI
Một số bài toán giải bằng phương pháp hệ thức truy hồi
tải về 0.86 Mb.
|
- Điều hướng trang này:
- 3.4.2 Các bài toán tổ hợp giải bằng hệ thức truy hồi
- 3.4.3 Các bài toán tương tự
- 3.5 Bài toán giải bằng nguyên lí cực hạn - khả năng xảy ra nhiều nhất, ít nhất.
- 3.6 Bài toán giải bằng phương pháp sắp xếp thứ tự.
- 3.7 Bài toán giải bằng phương pháp liệt kê các trường hợp.
- KẾT LUẬN
- TÀI LIỆU THAM KHẢO
3.4 Một số bài toán giải bằng phương pháp hệ thức truy hồi.3.4.1 Khái niệm mở đầu và mô h́nh hóa bằng hệ thức truy hồiĐôi khi ta rất khó định nghĩa một đối tượng một cách tường minh. Nhưng có thể dễ dàng định nghĩa đối tượng này qua chính nó. Kỹ thuật này được gọi là đệ quy. Định nghĩa đệ quy của một dăy số định rơ giá trị của một hay nhiều hơn các số hạng đầu tiên và quy tắc xác định các số hạng tiếp theo từ các số hạng đi trước. Định nghĩa đệ quy có thể dùng để giải các bài toán đếm. Khi đó quy tắc t́m các số hạng từ các số hạng đi trước được gọi là các hệ thức truy hồi. Định nghĩa : Hệ thức truy hồi (hay công thức truy hồi) đối với dăy số {an} là công thức biểu diễn an qua một hay nhiều số hạng đi trước của dăy. Dăy số được gọi là lời giải hay nghiệm của hệ thức truy hồi nếu các số hạng của nó thỏa măn hệ thức truy hồi này.
Bài 91 (Lăi kép): Giả sử một người gửi 10.000 đô la vào tài khoản của ḿnh tại một ngân hàng với lăi suất kép 11% mỗi năm. Sau 30 năm anh ta có bao nhiêu tiền trong tài khoản của ḿnh? Giải:
Gọi Pn là tổng số tiền có trong tài khoản sau n năm. V́ số tiền có trong tài khoản sau n năm bằng số có sau n 1 năm cộng lăi suất của năm thứ n, nên ta thấy dăy {Pn} thoả măn hệ thức truy hồi sau: Pn = Pn-1 + 0,11Pn-1 = (1,11)Pn-1 với điều kiện đầu P0 = 10.000 đô la. Từ đó suy ra Pn = (1,11)n.10.000. Thay n = 30 cho ta P30 = 228922,97 đô la.
Giải:
Gọi an là số các xâu nhị phân độ dài n và không có hai số 0 liên tiếp. Để nhận được hệ thức truy hồi cho {an}, ta thấy rằng theo quy tắc cộng, số các xâu nhị phân độ dài n và không có hai số 0 liên tiếp bằng số các xâu nhị phân như thế kết thúc bằng số 1 cộng với số các xâu như thế kết thúc bằng số 0. Giả sử n 3. Các xâu nhị phân độ dài n, không có hai số 0 liên tiếp kết thúc bằng số 1 chính là xâu nhị phân như thế, độ dài n 1 và thêm số 1 vào cuối của chúng. Vậy chúng có tất cả là an-1. Các xâu nhị phân độ dài n, không có hai số 0 liên tiếp và kết thúc bằng số 0, cần phải có bit thứ n 1 bằng 1, nếu không th́ chúng có hai số 0 ở hai bit cuối cùng. Trong trường hợp này chúng có tất cả là an-2. Cuối cùng ta có được: an = an-1 + an-2 với n 3. Điều kiện đầu là a1 = 2 và a2 = 3. Khi đó a5 = a4 + a3 = a3 + a2 + a3 = 2(a2 + a1) + a2 = 13. Bài 93. (Bài toán tháp Hà Nội) Có 3 cọc 1,2,3. Ở cọc 1 có n đĩa xếp chồng lên nhau sao cho đĩa nằm dưới lớn hơn đĩa nằm trên. Hăy chuyển tất cả các đĩa từ cọc 1 sang cọc 3 có thể dùng cọc 2 làm cọc trung gian với điều kiện mỗi lần chỉ được chuyển 1 đĩa từ cọc này sang cọc khác và luôn đảm bảo đĩa nằm dưới lớn hơn đĩa nằm trên. Bài toán đặt ra là: T́m số lần di chuyển đĩa ít nhất cần thực hiện để giải xong bài toán trên. Giải:
Phương pháp di chuyển như sau: Gọi Sn là số lần di chuyển đĩa ít nhất cần thực hiện. Chuyển n – 1 đĩa từ cọc 1 sang cọc 2 (lấy cọc 3 làm trung gian) ta có Sn-1 phép chuyển. Chuyển đĩa lớn nhất từ cọc 1 sang cọc 3. Ta có 1 phép chuyển. Chuyển n – 1 đĩa từ cọc 2 sang cọc 3 (lấy cọc 1 làm trung gian) ta có Sn-1 phép chuyển. Do vậy để chuyển n chiếc đĩa từ cọc 1 sang cọc 3, ta cần ít nhất phép chuyển. Vậy ta có công thức truy hồi của dăy số là Ta có
Bài 94. (Olympic Bungari, 1995) Cho số nguyên . Hăy t́m số các hoán vị của 1, 2,…,n sao cho tồn tại duy nhất một chỉ số thỏa măn . Giải:
Gọi Sn là số các hoán vị thỏa măn điều kiện bài toán. Để ư rằng số các hoán vị mà là Sn-1. (Bởi v́ số các hoán vị Sn-1 là số các hoán vị của sao cho tồn tại duy nhất một chỉ số thỏa măn ). C̣n số các hoán vị thỏa măn điều kiện bài toán với là . Do đó . (Do ). Hiện nhiên S2 = 1 . Tương tự bài trên ta có
Bài 95: Bạn A viết 6 lá thư cho 6 người khác nhau và đă chuẩn bị sẵn 6 phong b́ ghi sẵn địa chỉ của họ. Hỏi có bao nhiêu cách bỏ thư vào phong b́ sao cho không có một bức thư nào gửi đúng đến người có địa chỉ được ghi trên phong b́. Bài 96: Xét đa giác đều 12 đỉnh với tâm O. Chúng ta tô màu các miền đa giác bằng 4 màu đỏ, xanh da trời, xanh thẫm, vàng sao cho hai miền đa giác kề nhau được tô bởi hai màu khác nhau. Hỏi có bao nhiêu cách tô màu như vậy?
Bài 97. Cho 1985 tập hợp, mỗi tập hợp trong số đó gồm 45 phần tử, hợp của hai tập hợp bất ḱ gồm 89 phần tử. Có bao nhiêu phần tử chứa trong tất cả 1985 tập hợp đó. Giải:
Ta sẽ chứng minh rằng có tồn tại số mà a thuộc ít nhất 45 tập hợp khác . Giả sử ngược lại: Mọi phần tử của A đều thuộc nhiều nhất 44 tập hợp nên các phần tử của A thuộc nhiều nhất tập hợp V́ hợp của hai tập hợp bất ḱ có số phần tử là 89 nên giao của hai tập hợp bất ḱ là một phần tử. Suy ra A giao với 1984 tập hợp khác. Suy ra các phần tử thuộc A thuộc 1984 tập hợp khác (mâu thuẫn). Vậy các tập hợp giao nhau bởi một phần tử a duy nhất. (a là duy nhất v́ nếu tồn tại b thuộc vào các tập hợp th́ khi đó giao của hai tập hợp bất ḱ có hai phần tử) Giả sử A* không chứa a. Suy ra A* giao với tại 46 phần tử khác nhau. Do đó A* có ít nhất 46 phần tử (mâu thuẫn với giả thiết).
Bài 98. Cho số thực có tính chất tổng của n số bất ḱ nhỏ thua tổng của số c̣n lại. Chứng minh rằng tất cả các số đều dương. Giải:
Sắp xếp các số đă cho theo thứ tự tăng dần, ta có Theo giả thiết ta suy ra Suy ra
V́ giả thiết ai là nhỏ nhất nên ta có điều phải chứng minh. Bài 99. Cho 2n số nguyên dương phân biệt không vượt quá n2 . Chứng minh rằng tồn tại 3 hiệu bằng nhau. Giải:
V́ 2n số đă cho phân biệt nên ta có thể sắp xếp . Đặt Giả sử không tồn tại ba hiệu ai – aj nào bằng nhau, khi đó Suy ra Hơn nữa Từ hai bất đẳng thức trên suy ra mâu thuẫn.
Bài 100. Người đưa thư phân phát thư tới 19 nhà ở một dăy phố. Người đưa thư phát hiện ra rằng không có hai nhà liền kề nhau cùng nhận thư trong cùng một ngày và không có nhiều hơn hai nhà cùng không nhận thư trong cùng một ngày. Hỏi có bao nhiêu cách phân phối thư? Giải:
Từ giả thiết thứ nhất ta thấy cứ hai nhà liên tiếp có một nhà không nhận thư. Suy ra số nhà không nhận thư ít nhất là 9 và số nhà nhận thư nhiều nhất là 10. Suy ra có nhiều nhất 10 người nhận thư trong cùng một ngày Từ giả thiết thứ hai cứ ba nhà liên tiếp có một nhà nhận thư. Vậy ít nhất có 6 nhà nhận thư trong cùng một ngày. Ta liệt kê các trường hợp của bài toán:
Gán số 1 vào 6 vị trí nhận thư và gán số 0 vào những nhà không nhận thư. Mà giữa hai vị trí 1 phải có một nhà số 0 nên suy ra có 5 nhà không nhận thư. C̣n 8 nhà không nhận thư được sắp xếp như sau: Hai nhà không nhận thư ở hai vị trí đầu, và ở hai vị trí cuối, bốn nhà c̣n lại được sắp xếp vào 5 vị trí xen kẽ với các nhà nhận thư. Vậy trường hợp này có cách xếp.
7 nhà này xen kẽ với 6 nhà không nhận thư nên c̣n 6 nhà không nhận thư được sắp xếp như sau: 2 nhà đầu, 2 nhà cuối, 2 nhà c̣n lại xếp vào 6 vị trí xen kẽ. Có . 2 nhà đầu, 1nhà cuối, 3 nhà c̣n lại xếp vào 6 vị trí xen kẽ. Có . 1 nhà đầu, 2 nhà cuối, 3 nhà c̣n lại xếp vào 6 vị trí xen kẽ. Có . 1 nhà đầu, 1 nhà cuối, 4 nhà c̣n lại xếp vào 6 vị trí xen kẽ. Có . 2 nhà đầu, 0 nhà cuối, 4 nhà c̣n lại xếp vào 6 vị trí xen kẽ. Có . 0 nhà đầu, 2 nhà cuối, 4nhà c̣n lại xếp vào 6 vị trí xen kẽ. Có . 1 nhà đầu, 0 nhà cuối, 5 nhà c̣n lại xếp vào 6 vị trí xen kẽ. Có . 0 nhà đầu, 1 nhà cuối, 5 nhà c̣n lại xếp vào 6 vị trí xen kẽ. Có . 0 nhà đầu, 0 nhà cuối, 6 nhà c̣n lại xếp vào 6 vị trí xen kẽ. Có 1 cách. Vậy trong trường hợp này có 113 cách.
8 nhà này xen kẽ với 7 nhà không nhận thư nên c̣ 4 nhà không nhận thư được sắp xếp như sau: 2 nhà đầu, 2 nhà cuối. Có 1 cách. 2 nhà đầu, 1 nhà cuối, 1 nhà c̣n lại xếp vào 7 vị trí . Có cách. 1 nhà đầu, 2 nhà cuối, 1 nhà c̣n lại xếp vào 7 vị trí . Có cách. 1 nhà đầu, 1 nhà cuối, 2 nhà c̣n lại xếp vào 7 vị trí . Có cách. 2 nhà đầu, 0 nhà cuối, 2 nhà c̣n lại xếp vào 7 vị trí . Có cách. 0 nhà đầu, 2 nhà cuối, 2 nhà c̣n lại xếp vào 7 vị trí . Có cách. 0 nhà đầu, 1 nhà cuối, 3 nhà c̣n lại xếp vào 7 vị trí . Có cách. 1 nhà đầu, 0 nhà cuối, 3 nhà c̣n lại xếp vào 7 vị trí . Có cách. 0 nhà đầu, 0 nhà cuối, 4 nhà c̣n lại xếp vào 7 vị trí . Có cách. Vậy trong trường hợp này có 183 cách. Bằng cách chứng minh tương tự ta có kết quả cho 2 trường hợp c̣n lại:
Vậy người đưa thư có cách phân phối thư.
Luận văn MỘT SỐ BÀI TOÁN TỔ HỢP ĐẾM đă phân loại được một số dạng bài tập tổ hợp sử dụng các phép đếm từ cơ bản đến nâng cao. Ngoài ra cũng đă chọn lọc được một số bài toán tổ hợp hay phù hợp với học sinh trung học phổ thông khi ôn tập chuẩn bị tham gia vào các ḱ thi tốt nghiệp, cao đẳng, đại học hay tham gia các ḱ thi học sinh giỏi quốc gia, quốc tế. Rơ ràng các bài toán tổ hợp là rất khó, không có khuôn mẫu nhất định cho việc giải, do vậy luôn đ̣i hỏi sự sáng tạo, tư duy không ngừng từ phía người đọc. Mặt khác các bài toán này thường kích thích cho việc h́nh thành tư duy toán học và kĩ năng tŕnh bày, giải quyết vấn đề của học sinh. Ngoài việc phát triển những kĩ năng này, các bài toán tổ hợp c̣n mang tính thực tế và tính thẩm mỹ cao, v́ thế đem lại cho học sinh sự đam mê, hứng thú. Tôi tin rằng một bài toán tổ hợp sẽ luôn thú vị và đem đến những cuộc tranh luận hấp dẫn hơn bất cứ thể loại toán nào khác.
Каталог: files -> ChuaChuyenDoi ChuaChuyenDoi -> ĐẠi học quốc gia hà NỘi trưỜng đẠi học khoa học tự nhiên nguyễn Thị Hương XÂy dựng quy trình quản lý CÁc công trìNH ChuaChuyenDoi -> TS. NguyÔn Lai Thµnh ChuaChuyenDoi -> Luận văn Cao học Người hướng dẫn: ts. Nguyễn Thị Hồng Vân ChuaChuyenDoi -> 1 Một số vấn đề cơ bản về đất đai và sử dụng đất 05 1 Đất đai 05 ChuaChuyenDoi -> Lê Thị Phương XÂy dựng cơ SỞ DỮ liệu sinh học phân tử trong nhận dạng các loàI ĐỘng vật hoang dã phục vụ thực thi pháp luật và nghiên cứU ChuaChuyenDoi -> TRƯỜng đẠi học khoa học tự nhiên nguyễn Hà Linh ChuaChuyenDoi -> ĐÁnh giá Đa dạng di truyền một số MẪu giống lúa thu thập tại làO ChuaChuyenDoi -> TRƯỜng đẠi học khoa học tự nhiêN ChuaChuyenDoi -> TRƯỜng đẠi học khoa học tự nhiên nguyễn Văn Cường tải về 0.86 Mb. Chia sẻ với bạn bè của bạn:
|