11:08:00
Đề bài:
Có n người bị tình nghi một vụ ăn cắp tài khoản ngân hàng. Những người này chỉ là kỹ sư tin học hoặc nhà quản lý.
Tuy nhiên, hồ sơ của họ đều đã bị hủy và không ai biết ai là ai, do vậy cảnh sát cần thẩm vấn từng người.
Điều tra ban đầu cho thấy chắc chắn hung thủ là người quản lý.
Biết rằng các kỹ sư tin học luôn luôn nói thật còn các nhà quản lý thì không chắc như vậy. Và hơn nữa, n người này đều biết nghề nghiệp thật sự của nhau.
Cảnh sát cần đặt câu hỏi để xác định ai làm nghề gì và câu hỏi chỉ có thể ở dạng trả lời có hoặc không, đúng hoặc sai …
1. Nếu như số kỹ sư tin học nhiều hơn số nhà quản lý (trong n người), phải hỏi ít nhất bao nhiêu câu để tìm ra ít nhất một kỹ sư tin học?
2. Nếu số kỹ sư ít hơn số nhà quản lý, liệu có thể tìm ra hung thủ?
Giải:
Đáp án câu 1. Với n lẻ, cần n-2 câu hỏi và với n chẵn, cần n-3 câu hỏi.
Chúng tôi gợi ý một chiến thuật như sau: chia hàng người thành 3 hàng: hàng nghi vấn, hàng khả tin, và hàng bị loại. Bắt đầu chọn ngẫu nhiên 1 người cho vào hàng “khả tin” và tất cả những người còn lại cho vào hàng “nghi vấn”.
Tiến hành hỏi như sau: chọn một người X trong hàng “nghi vấn” và một người Y ở đầu hàng “khả tin” và hỏi Y: “X là nhà quản lý hay kỹ sư tin học?” (hoặc “X có phải là nhà quản lý?” …).
+ Nếu câu trả lời là “quản lý”, cho cả X lẫn Y vào hàng “bị loại”.
+ Nếu câu trả lời là “kỹ sư”, cho X vào đầu hàng “khả tin”.
+ Nếu hàng “khả tin” không còn ai, chọn ngẫu nhiên một người ở hàng “nghi vấn” cho vào hàng “khả tin”.
Tiến hành hỏi như trên cho đến khi không còn ai trong hàng “nghi vấn”. Người đứng đầu hàng “khả tin” lúc này chắc chắn là kỹ sư tin học.
Theo cách làm này, sau mỗi câu hỏi ta thấy rằng có ít nhất một người sẽ bị chuyển vào hàng “bị loại”, do vậy sau tối đa n-1 câu hỏi, chúng ta sẽ tìm ra kỹ sư tin học.
Vì sao điều này đúng: nhận thấy rằng mỗi khi cho một cặp vào hàng “bị loại”, ít nhất một trong 2 phải là nhà quản lý, do đó ở mỗi lần hỏi, số lượng kỹ sư tin học ở hai hàng “khả tin” và “nghi vấn” luôn lớn hơn số nhà quản lý, và do vậy khi hàng “nghi vấn” trống thì người đứng đầu hàng “khả tin” phải là kỹ sư tin học.
Với chiến thuật này, ta có thể dừng trước 1 bước: khi hàng “nghi vấn” còn 1 người, nếu hàng “khả tin” không có ai, người còn lại này chính là kỹ sư tin học, ngược lại, người đứng đầu hàng “khả tin” là kỹ sư tin học. Do vậy, chỉ cần n-2 câu hỏi.
Với n chẵn, ta có thể loại bỏ 1 người bất kỳ và áp dụng cách làm trên với n-1 người còn lại với n-3 câu hỏi. Đáp án này có thể chứng minh là tối ưu.
Đáp án câu 2. Nếu như tất cả các nhà quản lý đều nói dối thì không thể xác định ra ai là ai khi số lượng nhà quản lý lớn hơn số kỹ sư tin học.
TS Trần Nam Dũng
ĐH Khoa học Tự nhiên, ĐH Quốc gia TP HCM