Vận dụng cao / Xác suất / XS-002
Đề bài
Một chất điểm di chuyển trên trục tọa độ . Tại thời điểm ban đầu, chất điểm ở gốc tọa độ . Ở mỗi bước di chuyển, chất điểm nhảy sang phải đơn vị với xác suất , hoặc nhảy sang trái đơn vị với xác suất . Tính xác suất để sau đúng bước di chuyển, chất điểm quay trở lại gốc tọa độ và trong suốt quá trình di chuyển, tọa độ của nó luôn lớn hơn hoặc bằng .
Lộ trình 1 / 42
Toàn bộ 42 lộ trình hợp lệ — mọi đường đều xuất phát và kết thúc tại 0, không đường nào đi xuống dưới trục.
Lời giải
1. Cấu trúc của một lộ trình hợp lệ
Gọi là số bước nhảy sang phải () và là số bước nhảy sang trái (). Để đi đúng bước rồi quay về gốc tọa độ:
Mỗi lộ trình cụ thể gồm bước phải và bước trái đều có cùng xác suất:
2. Đếm số lộ trình luôn có tọa độ
Điều kiện "tọa độ luôn " nghĩa là tại mọi bước thứ (), số bước phải đã đi luôn không nhỏ hơn số bước trái đã đi. Số lộ trình như vậy chính là số Catalan thứ :
*Chứng minh bằng nguyên lý phản xạ.* Tổng số lộ trình có bước phải, bước trái (chưa xét điều kiện) là . Một lộ trình *vi phạm* là lộ trình có ít nhất một lần chạm tọa độ . Lấy đối xứng phần đường đi tính từ đầu đến thời điểm chạm lần đầu tiên qua đường thẳng , ta thu được song ánh giữa tập lộ trình vi phạm và tập đường đi từ về trong bước — loại này cần bước phải và bước trái, có đường. Vậy số lộ trình hợp lệ là .
3. Xác suất cần tìm
Mọi lộ trình hợp lệ đều có cùng bước phải và bước trái nên cùng xác suất :