BÀITOÁN BỎ NHẦM THƯ.
Vào thế kỷ XVIII nhà toán học Pháp Montmore đã đưa ra bài toán: Một người nọ viết thư gửi cho 5 người bạn cũ, mời họ đến nhà để cùng nhau gặp gỡ. Ông viết thư và phong bì xong liền giao cho thư ký bỏ thư vào phong bì và gửi đi. Thế nhưng người thư ký vô tâm, vụng về bỏ nhầm thư người này vào phong bì người kia. Hỏi xem người thư ký có thể mắc phải bào nhiêu kiểu bỏ nhầm thư?
Đây thực tế là một bài toán ứng dụng lý thuyết tập hợp. Nhà toán học Thuỵ sĩ Ơle đã đưa ra một công thức truy chứng (qui nạp) sau đây
Cho A, B, C,...biểu diễn cho các phong bì, còn a, b, c,...là các lá thư đã viết Gọi f(n) là số thư bỏ nhầm phong bì. Giả sử là a bỏ nhầm vào B, v.v...các sai lầm kiểu tương tự có thể chia hai loại:
1, Cho nhầm b vào A, lúc bấy giờ các sai lầm của bộ phận thư còn lại (không liên quan đến A, B, a, b) sẽ là f(n-2) kiểu bỏ nhầm.
2, Trừ phong thư cho b vào A, B công việc cho thư vào phong bì (Ngoài A ra) n-1 lá thư b,c, …(Trừ B ra) được cho vào n- 1 phong bì A, C đương nhiên sẽ có f(n- 1) cách sai lầm.
Như vậy ngoài việc cho nhầm a vào B, còn có f(n-2)+f(n- 1) loại sai lầm. a cho vào C, cho vào D. . . có n-2 loại sai lầm và cũng là f(n-2)+f(n-1) loại bỏ nhầm thư. Do đó:
f(n) = (n- 1) [f(n- 1) + f(n-2)]
Bằng phương pháp quy nạp với n = 1, 2, 3, 4, 5 ta có thể tìm được lời giải của bài toán trên:
f(1) = 0 f(2) = l
f(3) = 2 f(4) = 9 f(5) = 44
Vậy có 44 kiểu bỏ nhầm thư.
Nói chung với n > 2 thì:
