Học phần: BÀI TOÁN ĐẾM (TỔ HỢP SƠ CẤP)
1. BẢNG TỔNG HỢP KÝ HIỆU 2. NGÔN NGỮ TẬP HỢP 3. BÀI TOÁN ĐẾM & KỸ THUẬT VÁCH NGĂN EULER 4. BÀI TẬP CHỌN LỌC 5. TOÁN ĐẾM VÀ CẤU TRÚC TẬP HỢP 6. BỐN DẠNG TOÁN ĐẾM ( TỔ HỢP VÀ HOÁN VỊ) 7. BÀI TOÁN XÁO TRỘN HOÀN TOÀN (DERANGEMENT)
Quay lại khóa học

BÀI TOÁN XÁO TRỘN HOÀN TOÀN (DERANGEMENT)

BÀI TOÁN : Có 10 người mang 10 chiếc nón vào phòng họp. Khi ra về họ đều quên mang nón theo. Nhân viên khách sạn không biết nón nào của ai, và anh ta sẽ đưa ngẫu nhiên mỗi nón cho 1 trong 10 vị khách. Hỏi xác xuất mà có 2 người nhận được đúng nón của mình là bao nhiêu?

Bài toán này thuộc dạng bài toán Xáo trộn hoàn toàn (Derangement) nổi tiếng trong lý thuyết tổ hợp. Để có đúng 2 người nhận đúng nón của mình (và 8 người còn lại nhận sai nón), ta thực hiện tính toán qua 3 bước:

1. Không gian mẫu (Tổng số cách trao nón)

Số cách trao ngẫu nhiên $10$ chiếc nón cho $10$ vị khách là một hoán vị của 10 phần tử:

$$\Omega = 10! = 3.628.800 \text{ cách}$$

2. Số cách trao nón thỏa mãn đề bài

Bước 1: Chọn 2 người nhận đúng nón của mình

Số cách chọn $2$ người từ $10$ người là:

$$C_{10}^2 = \frac{10 \times 9}{2} = 45 \text{ cách}$$

Bước 2: Xếp $8$ người còn lại sao cho KHÔNG ai nhận đúng nón của mình

Số cách xếp $8$ người nhận sai nón chính là số xáo trộn hoàn toàn của $8$ phần tử, ký hiệu là $D_8$.

Công thức tính số xáo trộn hoàn toàn $D_n$:

$$D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}$$

Tính giá trị cho $n = 8$:

$$D_8 = 8! \left( \frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} - \frac{1}{5!} + \frac{1}{6!} - \frac{1}{7!} + \frac{1}{8!} \right) = 14.833 \text{ cách}$$

3. Tính xác suất

  • Tổng số trường hợp thuận lợi:

    $$N = C_{10}^2 \times D_8 = 45 \times 14.833 = 667.485 \text{ cách}$$

  • Xác suất cần tìm ($P$):

    $$P = \frac{N}{\Omega} = \frac{667.485}{3.628.800} = \frac{14.833}{80.640} \approx 0,18394$$

Kết luận: Xác suất để có đúng 2 người nhận được đúng nón của mình là khoảng $18,39\%$ (hoặc phân số tối giản là $\frac{14.833}{80.640}$).

1. KHÁI NIỆM XÁO TRỘN HOÀN TOÀN (DERANGEMENT)

Giả sử có $n$ người mang $n$ chiếc nón khác nhau. Khi trả nón, một cách trao được gọi là Xáo trộn hoàn toàn nếu tất cả $n$ người đều nhận sai nón (không ai lấy đúng nón của mình). Ký hiệu số cách xáo trộn này là $D_n$ (hoặc $!n$).

  • Ví dụ trực quan với 3 người ($A, B, C$) giữ 3 nón ($a, b, c$):

    • Tổng số cách phát nón ngẫu nhiên: $3! = 6$ cách.

    • Các cách phát sao cho không ai đúng nón:

      • Người $A$ lấy $b$, người $B$ lấy $c$, người $C$ lấy $a$ $(b, c, a)$

      • Người $A$ lấy $c$, người $B$ lấy $a$, người $C$ lấy $b$ $(c, a, b)$

    • Vậy $D_3 = 2$ cách.

  • Công thức tổng quát (sử dụng Nguyên lý Bù trừ):

    $$D_n = n! \left( 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \dots + \frac{(-1)^n}{n!} \right)$$

2. GIẢI THÍCH CHI TIẾT BƯỚC 2 TRONG BÀI TOÁN 10 NGƯỜI

Đề bài yêu cầu: Có đúng 2 người nhận đúng nón của mình.

  • Tại sao lại cần $D_8$?

    • Bước 1: Ta đã chọn ra 2 người may mắn nhận đúng nón ($C_{10}^2 = 45$ cách).

    • Bước 2: Ta còn lại 8 người và 8 chiếc nón. Lúc này, để đảm bảo tổng số người nhận đúng nón chỉ dừng lại ở con số 2, bắt buộc cả 8 người còn lại đều phải nhận SAI nón.

    • Nếu trong 8 người này có dù chỉ 1 người nữa nhận đúng nón, bài toán sẽ trở thành "có 3 người nhận đúng nón" $\rightarrow$ vi phạm yêu cầu đề bài.

    • Vì vậy, số cách trao nón cho 8 người còn lại chính là số xáo trộn hoàn toàn của 8 phần tử ($D_8$).

  • Tính toán chi tiết $D_8$ theo công thức:

    $$D_8 = 8! \times \left( \frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} - \frac{1}{5!} + \frac{1}{6!} - \frac{1}{7!} + \frac{1}{8!} \right)$$

    Vì $8! = 40.320$, ta nhân $8!$ vào từng phân số bên trong:

    $$D_8 = \frac{8!}{2!} - \frac{8!}{3!} + \frac{8!}{4!} - \frac{8!}{5!} + \frac{8!}{6!} - \frac{8!}{7!} + \frac{8!}{8!}$$
    $$D_8 = 20.160 - 6.720 + 1.680 - 336 + 56 - 8 + 1 = 14.833 \text{ cách}$$

3. MẸO TÍNH D_n BẰNG CÔNG THỨC TRUY HỒI (DỄ GIẢI THÍCH CHO CON)

Ngoài công thức phân số dài ở trên, $D_n$ còn có một công thức truy hồi rất đẹp:

$$D_n = (n - 1) \cdot (D_{n-1} + D_{n-2})$$

Ta chỉ cần nhớ 2 giá trị đầu: $D_1 = 0$ (1 người thì không thể phát sai cho chính họ được) và $D_2 = 1$ (2 người đổi nón cho nhau). Từ đó tính dần lên:

  • $D_1 = 0$

  • $D_2 = 1$

  • $D_3 = 2 \cdot (1 + 0) = 2$

  • $D_4 = 3 \cdot (2 + 1) = 9$

  • $D_5 = 4 \cdot (9 + 2) = 44$

  • $D_6 = 5 \cdot (44 + 9) = 265$

  • $D_7 = 6 \cdot (265 + 44) = 1.854$

  • $D_8 = 7 \cdot (1.854 + 265) = \mathbf{14.833}$

Nguyên lý Bù trừ (Inclusion-Exclusion Principle) giải quyết bài toán này bằng cách lấy tổng số cách xếp trừ đi các trường hợp "vi phạm" (có người nhận đúng nón), rồi cộng/trừ bù lại các phần bị đếm trùng.

1. ĐẶT BÀI TOÁN VÀ KÝ HIỆU

Giả sử có $n$ người và $n$ chiếc nón.

  • Gọi $S$ là tập hợp tất cả các cách phát nón ngẫu nhiên. Số phần tử của $S$ là:

    $$\vert{}S\vert{} = n!$$

  • Gọi $A_i$ là tập hợp các cách phát nón sao cho người thứ $i$ nhận đúng nón của mình ($i = 1, 2, \dots, n$).

  • Số xáo trộn hoàn toàn $D_n$ chính là số cách phát nón sao cho không có ai nhận đúng nón, tức là số phần tử nằm ngoài tất cả các tập $A_i$:

    $$D_n = \left\vert{} \overline{A_1 \cup A_2 \cup \dots \cup A_n} \right\vert{}$$

2. ÁP DỤNG NGUYÊN LÝ BÙ TRỪ

Theo Nguyên lý Bù trừ, số phần tử nằm ngoài hợp của $n$ tập hợp được tính bằng công thức đan dấu:

$$D_n = \vert{}S\vert{} - S_1 + S_2 - S_3 + \dots + (-1)^k S_k + \dots + (-1)^n S_n$$

Trong đó:

  • $\vert{}S\vert{}$: Tổng số cách xếp tùy ý.

  • $S_1$: Tổng số cách sao cho có ít nhất 1 người nhận đúng nón.

  • $S_2$: Tổng số cách sao cho có ít nhất 2 người nhận đúng nón.

  • $S_k$: Tổng số cách sao cho có ít nhất $k$ người nhận đúng nón.

3. TÍNH TOÁN CHI TIẾT TỪNG GIÁ TRỊ $S_k$

Để tính $S_k$ (số cách xếp có ít nhất $k$ người cố định nhận đúng nón):

  1. Bước 1: Chọn $k$ người nhận đúng nón từ $n$ người $\implies$ Có $C_n^k$ cách chọn.

  2. Bước 2: $(n - k)$ người còn lại phát nón tùy ý $\implies$ Có $(n - k)!$ cách xếp.

Do đó, giá trị của $S_k$ là:

$$S_k = C_n^k \times (n - k)! = \frac{n!}{k!(n - k)!} \times (n - k)! = \frac{n!}{k!}$$

Áp dụng công thức này cho từng bậc:

  • với $k = 1 \implies S_1 = \frac{n!}{1!}$

  • với $k = 2 \implies S_2 = \frac{n!}{2!}$

  • với $k = 3 \implies S_3 = \frac{n!}{3!}$

  • ...

  • với $k = n \implies S_n = \frac{n!}{n!}$

4. THẾ VÀO CÔNG THỨC & KẾT LUẬN

Ráp các giá trị $S_k$ vừa tính vào công thức Nguyên lý Bù trừ:

$$D_n = n! - \frac{n!}{1!} + \frac{n!}{2!} - \frac{n!}{3!} + \dots + (-1)^n \frac{n!}{n!}$$

Rút nhân tử chung $n!$ ra ngoài:

$$D_n = n! \left( 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \dots + \frac{(-1)^n}{n!} \right)$$

💡 MẸO GIẢI THÍCH MÔ HÌNH "CỘNG LỐ - TRỪ LỐ" CHO CÁC CON

Có thể vẽ sơ đồ Venn 2 hoặc 3 hình tròn để minh họa cho con lý do tại sao dấu lại chạy đan xen $(+ \dots - \dots + \dots -)$:

  • Bước 1 (Lấy tất cả): Ta lấy $n!$. Nhưng trong này bị lỡ tính cả những trường hợp có người đúng nón.

  • Bước 2 (Trừ đi $S_1$): Ta trừ đi các trường hợp có 1 người đúng nón. Nhưng việc này lại trừ quá tay (lố) những trường hợp có 2 người cùng đúng nón (vì nhóm 2 người này bị trừ 2 lần).

  • Bước 3 (Cộng bù $S_2$): Vì đã trừ lố, ta phải cộng bù lại $S_2$. Nhưng khi cộng bù $S_2$, ta lại cộng quá tay các trường hợp có 3 người đúng nón.

  • Bước 4 (Trừ lại $S_3$): Lại phải trừ bớt $S_3$...

Cứ nhịp nhàng "trừ lố rồi cộng bù" như vậy đến người thứ $n$, ta sẽ triệt tiêu hoàn toàn mọi trường hợp trùng lặp và thu được kết quả chính xác tuyệt đối.

Hỏi : Trường hợp k =1 ta có S1 = n! = đúng tổng số cách hoán vị của n cái nón. Tức là ta xáo trộn như thế nào thì cũng có ít nhất 1 người nhận đúng nón của mình phải không ?

Khẳng định "xáo trộn thế nào cũng có ít nhất 1 người nhận đúng nón" là không chính xác. Thực tế vẫn tồn tại những cách xáo trộn mà không một ai nhận đúng nón của mình (đó chính là các cách xáo trộn hoàn toàn $D_n$).

Lý do vì sao giá trị tính toán $S_1 = n!$ lại bằng đúng tổng số cách hoán vị là do hiện tượng đếm lặp (cộng trùng) chứ không phải vì mọi cách xếp đều có người đúng nón.

🔍 PHÂN TÍCH NGUYÊN NHÂN $S_1 = n!$

$S_1$ không phải là số cách xếp có ít nhất 1 người đúng nón, mà $S_1$ là tổng đại số đơn thuần:

$$S_1 = \vert{}A_1\vert{} + \vert{}A_2\vert{} + \dots + \vert{}A_n\vert{}$$

  • Tại sao $S_1$ lại bị phồng to lên bằng đúng $n!$?

    • Trong tổng $S_1$, những cách xếp có 2 người đúng nón bị tính lặp 2 lần.

    • Những cách xếp có 3 người đúng nón bị tính lặp 3 lần.

    • Cách xếp duy nhất mà tất cả $n$ người đều đúng nón bị tính lặp tới $n$ lần (xuất hiện trong cả $A_1, A_2, \dots, A_n$).

Chính vì bị cộng lặp nhiều lần các trường hợp trùng nhau đó, tổng $S_1$ mới vô tình tăng lên tới con số $n!$.

💡 VÍ DỤ TRỰC QUAN VỚI $n = 3$ NGƯỜI ($A, B, C$)

Tổng số cách phát nón tùy ý là $3! = 6$ cách. Hãy liệt kê tất cả 6 cách này:

  1. $(a, b, c)$ $\rightarrow$ 3 người đúng nón.

  2. $(a, c, b)$ $\rightarrow$ 1 người đúng ($A$).

  3. $(b, b, c)$ — sửa lại: $(c, b, a)$ $\rightarrow$ 1 người đúng ($B$).

  4. $(b, a, c)$ $\rightarrow$ 1 người đúng ($C$).

  5. $(b, c, a)$ $\rightarrow$ 0 người đúng nón (Xáo trộn hoàn toàn).

  6. $(c, a, b)$ $\rightarrow$ 0 người đúng nón (Xáo trộn hoàn toàn).

Nhận xét:

  • Rõ ràng có 2 cách xếp $(b, c, a)$ và $(c, a, b)$ làm cho KHÔNG AI nhận đúng nón.

  • Số cách thực tế có ít nhất 1 người đúng nón chỉ là 4 cách (các cách 1, 2, 3, 4), chứ không phải 6 cách!

Vậy $S_1$ tính ra bằng 6 như thế nào?

  • Tập $A_1$ (A đúng nón) gồm 2 cách: $(a, b, c), (a, c, b)$ $\rightarrow \vert{}A_1\vert{} = 2$.

  • Tập $A_2$ (B đúng nón) gồm 2 cách: $(a, b, c), (c, b, a)$ $\rightarrow \vert{}A_2\vert{} = 2$.

  • Tập $A_3$ (C đúng nón) gồm 2 cách: $(a, b, c), (b, a, c)$ $\rightarrow \vert{}A_3\vert{} = 2$.

$$\implies S_1 = \vert{}A_1\vert{} + \vert{}A_2\vert{} + \vert{}A_3\vert{} = 2 + 2 + 2 = 6$$

Cách $(a, b, c)$ xuất hiện ở cả 3 tập nên đã bị $S_1$ đếm trùng 3 lần. Đó là lý do $S_1 = 6 = 3!$, chứ không phải mọi cách xếp đều có người đúng nón.

← Bài trước