XS-003Nâng cao★ Nổi bật🎲 Xác suất

Đề bài

Một bài thi trắc nghiệm gồm $20$ câu hỏi được hiển thị thành một hàng dọc trên giao diện web. Một học sinh làm bài bằng cách chọn ngẫu nhiên một số lượng câu hỏi bất kỳ (từ $0$ đến $20$ câu) để trả lời, các câu còn lại bỏ trống. Tính xác suất để học sinh đó chọn trả lời sao cho không có bất kỳ $2$ câu hỏi nào nằm kề nhau trên giao diện được trả lời.

Hợp lệ — Chọn 10 câu lẻ — hợp lệ, đây là số câu tối đa

Lời giải

1. Không gian mẫu Mỗi câu trong

20

câu có đúng

2

khả năng: *được chọn trả lời* hoặc *bỏ trống*. Các câu độc lập nhau nên:

∣Ω∣ = 2^{20} = 1048576 (c \overset{a}{ˊ} ch)

2. Đếm số cách chọn không có hai câu kề nhau Gọi

k

là số câu được chọn trả lời. Nếu

k \geq 11

thì trong

20

vị trí chắc chắn có hai câu kề nhau (theo nguyên lý Dirichlet), nên

0 \leq k \leq 10

. Với mỗi

k

cố định, dùng phương pháp vách ngăn: xếp

20 - k

câu bỏ trống thành một hàng dọc. Chúng tạo ra

(20 - k) + 1 = 21 - k

khe (gồm các khe xen giữa và

2

khe ở hai đầu). Muốn

k

câu được chọn không đứng cạnh nhau, ta đặt mỗi câu vào một khe khác nhau — tức chọn

k

khe trong

21 - k

khe:

S \overset{ˊ}{\overset{o}{ˆ}} c \overset{a}{ˊ} ch = (k 21 - k)

Với k = 5: 15 câu bỏ trống tạo ra 16 khe ▲. Chọn 5 khe khác nhau để đặt 5 câu trả lời → C(16, 5) cách.

Tổng số cách thỏa mãn:

∣ A ∣ = k = 0 \sum 10 (k 21 - k)

Khai triển:

∣ A ∣ = (0 21) + (1 20) + (2 19) + (3 18) + (4 17) + (5 16) + (6 15) + (7 14) + (8 13) + (9 12) + (10 11)

∣ A ∣ = 1 + 20 + 171 + 816 + 2380 + 4368 + 5005 + 3432 + 1287 + 220 + 11 = 17711 (c \overset{a}{ˊ} ch)

3. Xác suất

P = \frac{17 711}{1 048 576} \approx 0, 01689

P \approx 1, 69 %

Nhận xét. Số cách chọn không kề nhau trong dãy

n

phần tử là số Fibonacci thứ

n + 2

. Thật vậy, gọi

a_{n}

là số cách: xét câu cuối cùng, nếu bỏ trống thì còn

a_{n - 1}

cách, nếu được chọn thì câu kế cuối buộc phải bỏ trống, còn

a_{n - 2}

cách — suy ra

a_{n} = a_{n - 1} + a_{n - 2}

. Với

n = 20

ta được

F_{22} = 17711

, đúng bằng kết quả trên.