Chứng minh bài toán bằng phương pháp loại trừ

Trên một đoàn tàu hỏa, phụ trách một toa tàu thông báo trong toa có một số người bị nhọ mặt và ra hiệu lệnh: Mọi người tập hợp xung quanh tôi, không được soi gương, nói chuyện hay bất kỳ hành động nào có thể giúp cho người khác biết về tình trạng nhọ hay không nhọ. Chỉ được phép nhìn nhau và suy nghĩ, nếu ai biết chắc chắn mình bị nhọ thì khi tàu dừng sẽ xuống rửa. Kết quả là sau khi tàu dừng ở ga thứ 4 thì không còn ai bị nhọ. Hỏi ban đầu trong toa tàu có bao nhiêu người bị nhọ mặt?

Chúng ta sẽ xét từng trường hợp, loại trừ dần như sau:

Trường hợp 1(TH1):  Trên tàu chỉ có 1 người bị nhọ mặt là A

Người đó A sẽ nhìn thấy không ai bị nhọ mặt, mà người phụ trách toa tàu đã thông báo có người bị nhọ, chứng tỏ mình bị nhọ và sẽ xuống ga thứ 1 để rửa. Sau khi tàu dừng ga thứ nhất hết người bị nhọ chứ không phải ga thứ 4 nên trường hợp này loại.

Trường hợp 2(TH2): Trên tàu chỉ có 2 người bị nhọ mặt A và B

Khi đó chẳng hạn A sẽ chỉ thấy 1 người bị nhọ, để biết mình có bị nhọ hay không A sẽ nghĩ: nếu ga thứ nhất B xuống rửa thì mình không bị nhọ(vì họ sẽ suy nghĩ giống như TH1). Nhưng qua ga thứ 1 không thấy ai xuống nên A sẽ nhận ra ngay là mình bị nhọ mặt và xuống rửa ở ga thứ 2(cả B cũng vậy), nghĩa là sau khi tàu dừng ở ga 2 sẽ không còn ai bị mặt nhọ chứ không phải ga thứ 4. Trường hợp này cũng bị loại.

Trường hợp 3(TH3): Trên tàu chỉ có 3 người bị nhọ mặt A, B  và C

Khi đó chẳng hạn A sẽ chỉ thấy 2 người bị nhọ là B và C, để biết mình có bị nhọ hay không A sẽ nghĩ: nếu chỉ B và C bị nhọ thì họ sẽ nghĩ giống như TH2 tức là đến ga 2 cả B và C sẽ xuống rửa mặt. Nhưng qua ga 2 cả 2 đều không xuống chứng tỏ mình(A) đang bị nhọ và sẽ xuống rửa ở ga thứ 3(B, C cũng thế), nghĩa là sau khi tàu dừng ở ga 3 sẽ không còn ai bị mặt nhọ chứ không phải ga thứ 4. Trường hợp này cũng bị loại.

Cuối cùng ta sét trường hợp trên tàu chỉ có 4 người bị nhọ mặt, khi đó 1 người trong họ(ví dụ A) sẽ chỉ quan sát thấy 3 người nhọ mặt. A sẽ nghĩ rằng: nếu chỉ có 3 người bị nhọ mặt thôi thì những người đó sẽ nghĩ giống TH3 nghĩa là đến ga thứ 3 họ sẽ xuống rửa mặt nhưng ga thứ 3 họ cũng không xuống chứng tỏ mình(A) đang bị nhọ mặt và tất nhiên đến ga thứ 4 sẽ xuống rửa, 3 người còn lại cũng suy nghĩ và làm tương tự.

Nói tóm lại với 4 người bị nhọ mặt thì sau khi tàu dừng ở ga thứ 4 sẽ không người nào bị nhọ nữa.

Trong 1 buổi học nữ công ba bạn Cúc, Đào, Hồng làm 3 bông hoa cúc, đào, hồng. Bạn làm hoa hồng nói với Cúc : Hóa ra trong chúng ta chẳng ai làm loại hoa trùng với tên mình nhỉ! Hỏi ai đã làm hoa nào?

Chúng ta sẽ sử dụng sơ đồ như sau bằng cách ký kiệu ba bạn bởi và 3 loại hoa bởi 6 điểm như trên hình vẽ. Nếu ai trồng loại hoa gì thì tên và hoa sẽ nối với nhau bằng nét rõ, ngược lại bởi nét mờ.

Theo bài ra thì Cúc – cúc, Đào – đào, Hồng – hồng được nối bởi nét mờ.

Từ đoạn hội thoại giữa bạn làm hoa hồng với Cúc suy ra bạn làm hoa hồng không thể tên Cúc(vì nếu ngược lại thì Cúc nói chuyện với chính mình!) nên Cúc – hồng sẽ được nối bởi nét mờ. Ta thấy Cúc – hồng và Hồng – hồng đã là nét mờ ⇒ Đào sẽ làm hoa hồng.

Vì Cúc không làm cúc và Cúc không làm hồng nên Cúc sẽ làm hoa đào và còn lại hiển nhiên Hồng là người làm hoa cúc.

Bài toán này học sinh có thể suy luận bình thường hoặc dùng bảng. Tuy nhiên phương pháp dùng đồ thị(hoặc tô màu) như trên cho thấy mối liên hệ trực quan hơn, dễ hiểu hơn.…