Ở 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?
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ì anh B chia đôi đoạn [1, n/2], nếu không thì anh B chia đôi đoạn [n/2+1, n], cứ thế.
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 lọc DNA (DNA screening), thử máu, giao 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…
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:
- A nghĩ trong đầu m số thay vì 1 số.
- 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.
- A có thể trả lời dối vài lần.
- Có một xác suất nhất định là A sẽ nghĩ một số.
Ví dụ, trong Thế chiến thứ hai, khi thử máu cả trăm nghìn binh lính để xem những ai trong đó bị một bệnh nhất định (lúc đó bệnh 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ể số 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ể số 3). Hiển nhiên là vì mẫu 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ề một nhánh nghiên cứu gọi là “thử nghiệm nhóm” (group testing), một đề tài rất thú vị.
Và đó cũng là cơ sở khoa học và ý nghĩa thực tiễn của “phương pháp gộp mẫu” trong xét nghiệm sàng lọc SARS-CoV-2 ở các quốc gia hiện nay.
Một nghiên cứu khoa học về ứng dụng group testing như một chiến lược để giám sát dịch tễ học COVID-19 có thể tham khảo ở đây.
[/membersonly]
