Nội dung tài liệu
Giới thiệu và những kiến thức cần ôn tập.
Tài liệu gồm 32 trang, được biên soạn bởi tác giả Nguyễn Sỹ Thái (Trung Tâm Luyện Thi 29Edu), hướng dẫn sử dụng kỹ thuật “vết dầu loang” trong bài toán đếm và xác suất nâng cao.
TÓM TẮT NỘI DUNG:
Bạn Lan đi học mỗi ngày. Giả sử các con phố từ nhà Lan đến trường tạo thành một lưới ô vuông hoàn hảo, hỏi có bao nhiêu con đường ngắn nhất để Lan đi từ nhà đến trường? Rất dễ phải không? Vì các con phố tạo thành một lưới ô vuông m × n hoàn hảo, ta có ngay công thức tổ hợp mCm+n.
Nhưng nếu lưới đó có vài ngã tư đang sửa đường, một đoạn phố cấm đi, hay một cây cầu bắt buộc phải qua … thì công thức ấy còn dùng được không?
Lúc đó, thay vì cố tìm một công thức cho toàn bộ hành trình, ta chỉ trả lời một câu hỏi rất cục bộ: “Muốn đến được điểm này, ngay trước đó ta phải đứng ở đâu?”
Trả lời được câu hỏi đó, ta ghi số cách đến mỗi điểm bằng tổng số cách đến các điểm đứng ngay trước nó, bắt đầu từ điểm xuất phát rồi để các con số “loang” dần ra tới đích. Toàn bộ quá trình chỉ áp dụng quy tắc cộng, kể cả khi sơ đồ có vật cản.
Chuyên đề này trình bày cơ sở toán học của kĩ thuật (vì sao được cộng, khi nào được cộng), sau đó áp dụng cho sáu mô hình thường gặp: lưới có vật cản, lưới có điểm bắt buộc đi qua, lưới không vuông, đường đi không vượt đường chéo, sơ đồ một chiều ngoài lưới, và bài toán xác suất trên các đường đi.
MỤC LỤC:
1 Bài toán mở đầu 3.
2 Cơ sở lí thuyết 4.
2.1 Sơ đồ bước đi 4.
2.2 Nguyên lí vết dầu loang 4.
2.3 Các hệ quả 6.
2.4 Phương pháp giải 8.
2.5 Mở rộng: trải sơ đồ theo số bước 8.
2.6 Xác suất: khi nào các đường đi đồng khả năng? 9.
3 Các mô hình bài toán điển hình 11.
3.1 Mô hình 1: Lưới có vật cản 11.
3.2 Mô hình 2: Bắt buộc đi qua hoặc phải tránh một điểm, một đoạn đường 13.
3.3 Mô hình 3: Lưới không vuông và lưới có bước chéo 15.
3.4 Mô hình 4: Đường đi không vượt đường chéo 17.
3.5 Mô hình 5: Sơ đồ một chiều (đồ thị có hướng) 18.
3.6 Mô hình 6: Xác suất trên các đường đi đồng khả năng 20.
4 Bài tập tự luyện 23.
5 Đáp án 32.