Có 8 bì thư được đánh số 1, 2, 3, 4, 5, 6, 7, 8 và 8 tem thư cũng được đánh

* Hướng dẫn giải

Đáp án B

Ta xét bài toán tổng quát n tem thư được dán vào n bì thư sao cho có ít nhất 1 bì thư được dán vào tem thư có số trùng với số của bì thư đó

Đánh số các tem thư là ${\mathrm{T}}_1$, ${\mathrm{T}}_2$,.., ${\mathrm{T}}_{\mathrm{n}}$ và các bì thư ${\mathrm{B}}_1$, ${\mathrm{B}}_2$,…, ${\mathrm{B}}_{\mathrm{n}}$. Bài toán được giải quyết bằng nguyên lý phần bù. Lấy hoán vị n phần tử trừ đi trường hợp xếp mà không có tem thư nào được dán cùng số với bì thư.

+ Để giải quyết bài toán không có tem thư nào được dán cùng số với bì thư. Ta xây dựng dãy số f(n) như sau:

Công việc dán n tem thư vào n bì thư sao cho không có bì thư nào được dán vào tem thư có số trùng với số của bì thư đó. Công việc này gồm có 2 bước sau

- Bước 1: dán tem T₁ lên 1 bì thư B_j khác B₁, có n – 1 cách

- Bước 2: Dán tem thư T_j vào bì thư nào đó, có 2 trường hợp xảy ra như sau:

+ TH1: Tem thư T_j được dán vào bì thư B₁. Khi đó còn lại n – 2 tem (khác T₁ và T_j) là T₂,…,T_j-1, T_j+1,…,T_n phải dán vào n – 2 bì thư (khác B₁ và B_j). Quy trình được lặp lại giống như trên. Nên TH này có số cách dán bằng f(n-2)

+ TH2: tem thư T_j không được dán vào bì thư B₁

Khi đó các tem là T₂,…,T_j-1, T_j, T_j+1,…,T_n sẽ được đem dán vào các bì B₁, B₂,…,B_j-1, B_j+1,…,B_n (mà tem thư T_j không được dán vào bì thư B₁). Thì T_j lúc này bản chất giống như T₁, ta đánh số lại T_j º T₁. Nghĩa là n – 1 tem T₂, …, T_j-1, T₁, T_j+1,…,T_n sẽ được đem dán vào n – 1 bì B₁, B₂,…,B_j-1,B_j+1,…,B_n với việc đánh số giống nhau. Công việc này lại được lập lại như từ ban đầu.

Nên TH này có số cách dán bằng f (n-1)

+ Ta xét dãy ${\mathrm{u}}_{\mathrm{n}}=\mathrm{f}\left(\mathrm{n}\right)$  như sau

Như vậy kết quả của bài toán: n tem thư được dán vào n bì thư sao cho có ít nhất 1 bì thư được dán vào tem thư có số trùng với số của bì thư đó sẽ là ${\mathrm{P}}_{\mathrm{n}}-{\mathrm{u}}_{\mathrm{n}}$

Áp dụng với n = 8, ta được kết quả là 8!-14833=25487.