Tóm tắt nội dung: Chuyên đề phân tích kỹ thuật vận dụng tư duy Quy hoạch động (Dynamic Programming) để giải quyết các bài toán đếm và xác ...
III. KHỞI ĐỘNG: QUY HOẠCH ĐỘNG TRONG BÀI TOÁN ĐẾM
Trước khi bước vào xác suất, ta luyện “cơ tay” với bài toán đếm. Đây là cách tiếp cận của nhiều tài liệu chuyên đề (chẳng hạn tài liệu “Ứng dụng quy hoạch động trong bài toán đếm và tính xác suất” và bộ bài giảng “Làm chủ tư duy quy hoạch động”): mọi bảng đếm đều trở thành bảng xác suất khi ta chia cho tổng số khả năng.
1. Bài toán leo cầu thang
Ví dụ 1 (bài toán kinh điển): Một cầu thang có 10 bậc. Mỗi bước có thể bước lên 1 bậc hoặc 2 bậc.
a) Có bao nhiêu cách leo hết cầu thang?
b) Nếu mỗi bước người đó chọn ngẫu nhiên bước 1 bậc hoặc 2 bậc (xác suất \(\frac{1}{2}\) mỗi loại), tính xác suất người đó đặt chân lên bậc thứ 10.
(Hình minh họa: Muốn đến bậc \(i\), bước cuối xuất phát từ bậc \(i - 1\) hoặc bậc \(i - 2\). Công thức: \(f(i) = f(i-1) + f(i-2)\) với \(f(0) = f(1) = 1\))
a) Gọi \(f_i\) là số cách leo đến bậc \(i\). Bước cuối là 1 bậc (từ \(i - 1\)) hoặc 2 bậc (từ \(i - 2\)), nên:
\[f_i = f_{i-1} + f_{i-2} \quad \text{với } f_0 = f_1 = 1\]
Dãy giá trị: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 cho \(f_{10} = 89\) cách.
b) Gọi \(p_i\) là xác suất đặt chân lên bậc \(i\). Muốn chạm bậc \(i\) thì phải chạm bậc \(i - 1\) rồi bước 1, hoặc chạm bậc \(i - 2\) rồi bước 2 – hai trường hợp xung khắc:
\[p_i = \frac{1}{2}p_{i-1} + \frac{1}{2}p_{i-2}, \quad p_0 = 1, p_1 = \frac{1}{2} \implies p_n = \frac{2}{3} + \frac{1}{3}\left(-\frac{1}{2}\right)^n\]
Do đó:
\[p_{10} = \frac{2}{3} + \frac{1}{3 \cdot 1024} = \frac{683}{1024}\]
Lưu ý: Hai câu a, b cùng một bảng nhưng khác bản chất: câu a đếm đường đi đến đúng bậc 10, câu b tính xác suất chạm bậc 10 khi bước ngẫu nhiên – con số \(\frac{89}{2^{10}}\) không phải đáp án câu b, vì các con đường có số bước khác nhau nên không đồng khả năng.
2. Đường đi trên lưới ô vuông
Ví dụ 2 (theo Vũ Mạnh Quân): Một con kiến đi theo các cạnh của lưới ô vuông kích thước \(7 \times 5\) từ góc \(A(0; 0)\) đến góc \(B(7; 5)\), mỗi bước sang phải hoặc lên trên một đơn vị (đường đi ngắn nhất).
a) Có bao nhiêu đường đi?
b) Chọn ngẫu nhiên một đường đi. Tính xác suất đường đi qua điểm \(C(3; 2)\).
(Hình minh họa: Bảng “vết dầu loang” – số ở mỗi nút bằng tổng nút bên trái và nút bên dưới)
a) Mỗi nút \((x; y)\) chỉ đến được từ nút bên trái hoặc nút bên dưới, nên số đường:
\[N(x; y) = N(x - 1; y) + N(x; y - 1)\]
Lan dần từ \(A\), ta được tam giác Pascal xoay nghiêng và:
\[N(7; 5) = 792 = C_{12}^5\]
b) Số đường qua \(C\) bằng:
\[(\text{số đường } A \to C) \times (\text{số đường } C \to B) = C_5^2 \cdot C_7^3 = 10 \cdot 35 = 350\]
Xác suất cần tìm:
\[P = \frac{350}{792} = \frac{175}{396} \approx 0{,}44\]
Cẩn thận: “chọn ngẫu nhiên một đường” khác “đi ngẫu nhiên từng bước”. Nếu thay vì chọn đều một trong 792 đường, con kiến ở mỗi nút tung đồng xu để chọn phải/lên (đến biên thì chỉ còn một hướng) thì các đường đi không còn đồng khả năng: đường men theo biên có xác suất lớn hơn. Khi đó phải lập bảng xác suất riêng.
