Có n lá thư và n phong bì ghi sẵn địa chỉ. Bỏ ngẫu nhiên các lá thư vào các phong bì. Hỏi xác suất để xảy ra không một Là thư nào bỏ đúng địa chỉ là bao nhiêu?

(1/n) *(e/n)

e^-1

e/n

1/n

Trả lời:

Đáp án đúng: B

Gọi D_n là số cách xếp n lá thư vào n phong bì sao cho không có lá thư nào đúng địa chỉ. Bài toán này là một bài toán kinh điển về số беспорядки (derangements). Ta có công thức truy hồi và công thức tổng quát cho D_n như sau: * **Công thức truy hồi:** D_n = (n-1) * (D_n-1 + D_n-2), với D₁ = 0, D₂ = 1 * **Công thức tổng quát:** D_n = n! * Σ ((-1)^k / k!) với k chạy từ 0 đến n. Số cách xếp n lá thư vào n phong bì một cách ngẫu nhiên là n! (n giai thừa). Xác suất để không có lá thư nào đúng địa chỉ là P_n = D_n / n! = Σ ((-1)^k / k!) với k chạy từ 0 đến n. Khi n tiến tới vô cùng, P_n tiến tới e^-1 (≈ 0.367879...). Với n đủ lớn, P_n có thể coi là xấp xỉ e^-1. Do đó, đáp án đúng là e^-1.

525 câu trắc nghiệm môn Toán rời rạc kèm lời giải chi tiết - Phần 1

Bộ 525 câu hỏi trắc nghiệm ôn thi môn Toán rời rạc có đáp án dưới đây sẽ là tài liệu ôn tập hữi ích dành cho các bạn sinh viên. Mời các bạn cùng tham khảo!

30 câu hỏi 60 phút

Bắt đầu thi

Câu hỏi liên quan

Câu 18:

Có bao nhiêu xâu nhị phân độ dài 8 chứa ít nhất 3 số 0 và ít nhất 3 số 1?

Lời giải:

Đáp án đúng: C

Câu 19:

Cho các số {1, 2, 3, 4, 5, 6, 7}. Tìm các số tự nhiêm gồm 5 chữ số lấy từ tập trên sao cho không tận cùng bằng chữ số 5.

Lời giải:

Đáp án đúng: A

Số các số tự nhiên có 5 chữ số được lấy từ tập {1, 2, 3, 4, 5, 6, 7} là 7^5 = 16807. Số các số tự nhiên có 5 chữ số được lấy từ tập {1, 2, 3, 4, 5, 6, 7} và tận cùng bằng chữ số 5 là 7^4 = 2401. Số các số tự nhiên có 5 chữ số được lấy từ tập {1, 2, 3, 4, 5, 6, 7} và không tận cùng bằng chữ số 5 là 16807 - 2401 = 14406.

Câu 20:

Đường đi Euler vô hướng trên một đồ thị có đỉnh đầu và đỉnh cuối:

Lời giải:

Đáp án đúng: B

Đường đi Euler (hay còn gọi là đường đi Euler) trên đồ thị vô hướng là đường đi đi qua tất cả các cạnh của đồ thị đúng một lần.

Đồ thị vô hướng có đường đi Euler khi và chỉ khi có đúng 0 hoặc 2 đỉnh bậc lẻ.

- Nếu có 0 đỉnh bậc lẻ, đường đi Euler là chu trình Euler, và đỉnh đầu và đỉnh cuối trùng nhau.

- Nếu có 2 đỉnh bậc lẻ, đường đi Euler bắt đầu từ một đỉnh bậc lẻ và kết thúc ở đỉnh bậc lẻ còn lại, do đó đỉnh đầu và đỉnh cuối khác nhau.

Vậy, đường đi Euler vô hướng trên một đồ thị có đỉnh đầu và đỉnh cuối khác nhau.

Câu 21:

Đồ thị G vô hướng được gọi là liên thông nếu giữa mọi cặp đỉnh u,v bất kỳ đều có:

Lời giải:

Đáp án đúng: C

Một đồ thị vô hướng được gọi là liên thông nếu giữa mọi cặp đỉnh u, v bất kỳ đều có một đường đi vô hướng nối u đến v. Điều này có nghĩa là có thể di chuyển từ đỉnh u đến đỉnh v (và ngược lại) thông qua một chuỗi các cạnh.

Câu 22:

Độ dài của một chu trình trên đồ thị G là:

Lời giải:

Đáp án đúng: B

Độ dài của một chu trình trong đồ thị là số cạnh tạo thành chu trình đó. Ví dụ, một chu trình đơn giản là một tam giác, có 3 đỉnh và 3 cạnh. Vậy độ dài chu trình là 3, tương ứng với số cạnh.

Câu 23:

Đường đi đơn trong đồ thị G là đường đi:

Lời giải: