Đoán bí mật

 Copy from Pro. Ngo Hung

 

Ở cuối quyển " Các cuộc phiêu lưu của một nhà toán học", nhà toán học Stan Ulam (1909-1984) có nhắc đến bài toán 20-câu hỏi nổi tiếng: giả sử anh A nghĩ trong đầu một số nguyên từ 1 đến 1 triệu, anh B phải hỏi bao nhiêu câu hỏi nhị phân (nghĩa là chỉ trả lời có hoặc không) để đoán được bí mật này?

Giả sử anh A nghĩ một số từ 1 đến n, dễ thấy rằng phương pháp tìm kiếm nhị phân có thể áp dụng được ở đây. Anh B hỏi: "số anh nghĩ có phải từ 1 đến n/2 không?", nếu có thì ta chia đôi đọan [1,n/2], nếu không thì ta chia đôi đọan [n/2+1, n], vân vân.

Bài toán căn bản này có nhiều biến thể khó, thú vị, và có rất nhiều ứng dụng: từ sàng DNA (DNA screening), thử máu, nghi thức giải quyết tranh chấp trong mạng máy tính (conflict resolution protocol), đến tăng hiệu suất hệ thống mạng (xem tin), vân vân.

Các điều kiện sau đây, hoặc một tập con của chúng, dẫn đến các câu hỏi toán học thú vị có tính ứng dụng cao:

1. A nghĩ trong đầu d số thay vì 1 số.
2. B phải hỏi tất cả các câu hỏi cùng một lúc, và dựa trên tất cả các câu trả lời đoán (các) bí mật của A.
3. A có thể trả lời dối vài lần.
4. Có một xác suất nhất định là A sẽ nghĩ một số.

Ví dụ: trong thời thế chiến thứ hai, khi thử máu cả trăm nghìn lính xem những ai trong đó bị một bệnh nhất định (lúc đó giang mai - syphilis - là đối tượng chính), người ta thường phải bỏ một tập con các mẫu máu vào một hợp chất hóa học. Nếu hợp chất có phản ứng (đổi màu chẳng hạn), thì trong tập con các mẫu máu đó có ít nhất một mẫu bị bệnh.

Các tập con mẫu máu này là các câu hỏi nhị phân. Các tập con phải được thiết kế trước, vì ta không thể lấy mẫu một nửa số lính, rồi tùy theo kết quả thử lấy nửa số khác hoặc chia đôi số đã lấy. Việc thiết kế trước các tập con này chính là biến thể số 2 nêu trên. Rõ ràng là tổng số "bí mật" (trong trường hợp này là số lính bị bệnh) nhiều hơn một (biến thể số 1). Ngoài ra, ta cũng không biết có nhiều nhất bao nhiêu lính bị bệnh, cho nên có thể phải tìm một xác suất bệnh (biến thể thứ 4). Các hợp chất có thể có phản ứng sai do mẫu máu không tinh khiết (biến thể thứ 3). Hiển nhiên là vì máu có hạn, nên ta phải tối ưu tổng số phép thử (đồng nghĩa với tối ưu tổng số câu hỏi).

Các bài toán này thuộc về nhánh nghiên cứu gọi là "thử nhóm" (group testing), một đề tài rất thú vị. Bạn xem thêm bài survey tôi viết đã lâu, và một bài báo khác tôi thiết kế một giải thuật như vậy.