Có 8 bì thư được đánh số 1, 2, 3, 4, 5, 6, 7, 8 và 8 tem thư cũng được đánh số 1, 2, 3,4, 5, 6, 7, 8. Dán 8 tem thư lên 8 bì thư (mỗi bì thư chỉ dán 1 tem thư). Hỏi có thể có bao nhiêu cách dán tem thư lên bì thư sao cho có ít nhất một bì thư được dán tem thư có số trùng với số của bì thư đó?

Đá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à T1, T2,.., Tn và các bì thư B1, B2,…, Bn. 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 un=fn  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à Pn-un

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