Tóm tắt: "Những con heo tội nghiệp" (Poor Pigs) là bài toán số 458 trên LeetCode. Đằng sau vẻ ngoài của một câu đố phỏng vấn cho các vị trí lập trình, nó là một bài toán về lý thuyết thông tin: cần bao nhiêu bit để xác định một vật trong vật. Bài viết sẽ xây dựng lời giải từ những trường hợp nhỏ, thiết kế cụ thể từng thí nghiệm, liên hệ với định lý mã hoá của Shannon, dùng thời gian để giảm số con heo, và cuối cùng đặt bài toán vào khung của lý thuyết độ phức tạp.
Dưới đây là phát biểu của bài toán 458 trên LeetCode:
Có chai chất lỏng, trong đó có đúng một chai chứa độc. Để tìm ra chai độc, ta cho một số con heo uống thử, con nào uống phải chai độc sẽ chết sau một khoảng thời gian cố định, con nào không uống phải thì sống. Bài toán cho ba tham số: số chai, thời gian độc phát tác (
minutesToDie), và tổng thời gian cho phép (minutesToTest). Trong mỗi lượt, ta chọn các con heo còn sống và cho mỗi con uống từ một nhóm chai tuỳ ý — một con có thể uống nhiều chai, một chai có thể được nhiều con uống. Yêu cầu: tìm số con heo ít nhất để chắc chắn xác định được chai độc trong thời gian cho phép.Để có con số cụ thể theo dõi xuyên suốt bài, ta lấy: chai, độc phát tác sau phút, và có phút để thử.
Suy nghĩ đầu tiên thường là: cho mỗi con heo uống một chai, vậy cần tới 1000 con; hoặc cho một con heo uống lần lượt từng chai, nhưng 15 phút một lượt thì 60 phút chỉ thử được 4 chai. Cả hai đều không dùng được. Đáp số thực ra là chỉ cần đến 5 con heo, và phần còn lại của bài viết giải thích vì sao.
Bạn đọc có thể tự trải nghiệm suy nghĩ về giải pháp và thử trên Leetcode trước khi đọc lời giải dưới đây.
Với các bài toán khó, một chiến thuật thường dùng là thu nhỏ nó lại cho tới khi thấy quy tắc. Ta tạm quên con số 1000, và bắt đầu từ những trường hợp nhỏ nhất.
Nếu chỉ có 1 chai và biết chắc có đúng một chai độc, thì chai đó chính là chai độc. Cần 0 con heo.
Đánh số hai chai là và . Cho con heo uống chai số 1.
- Nếu heo chết → chai là chai độc.
- Nếu heo sống → vì chắc chắn có một chai độc, thủ phạm phải là chai .
Ta cần một con heo phân biệt được hai chai.
Trong trường hợp bài toán này, ta sẽ dùng hệ nhị phân để đánh dấu các chai chất lỏng. Vì sao ta lại làm như vậy? Lí do là vì nếu ta xem xét việc dán nhãn một chai chất lỏng là dùng một tập hợp có thứ tự các ký tự hữu hạn, ta có thể tận dụng tính riêng biệt của biểu diễn số trong hệ đếm để phân loại. Ví dụ như khi ta nói trong tập hợp tất cả các số được biểu diễn bằng đúng 4 bit, cần lấy những số có bit ở vị trí thứ nhất đếm từ trái sang là , bit ở vị trí thứ tư đếm từ trái sang là , ta sẽ được tập hợp .
Ta sẽ sử dụng trực giác này với những con heo trong thí nghiệm. Nếu đánh thứ tự các con heo là A, B,… heo A sẽ chịu trách nhiệm xác định bit thứ nhất từ trái sang (bit trái), heo B chịu trách nhiệm xác định bit thứ hai từ trái sang (bit phải).
Ta đánh số bốn chai bằng số nhị phân 2 chữ số, rồi giao mỗi con heo phụ trách một cột bit (dấu ✓ nghĩa là con heo đó uống chai này):
Thiết kế thí nghiệm:
- Heo A uống từ mọi chai có bit trái = 1, tức chai và .
- Heo B uống từ mọi chai có bit phải = 1, tức chai và .
Đọc kết quả với quy ước chết =
1, sống = 0. Ghép lại theo thứ tự (Heo A, Heo B) ta được đúng số nhị phân của chai độc:Minh hoạ: bảng nhị phân: mỗi con heo là một cột, mỗi chai là một hàng biểu diễn trạng thái riêng.
Chẳng hạn nếu A chết, B sống, ta đọc được
10 = chai , đó là chai mà chỉ có A uống. Mỗi chai ứng với một biểu diễn trạng thái sống/chết khác nhau, nên không có sự nhập nhằng.Tăng lên 8 chai, ta viết mỗi chai bằng nhị phân 3 chữ số và lại giao mỗi con heo một cột bit:
Thiết kế thí nghiệm:
- Heo A uống mọi chai có bit trái = 1: chai .
- Heo B uống mọi chai có bit giữa = 1: chai .
- Heo C uống mọi chai có bit phải = 1: chai .
Vì sao ba con heo là đủ: ba con heo, mỗi con hai trạng thái (sống/chết), cho biểu diễn nhị phân khác nhau, vừa đủ cho chai. Ví dụ nếu A và B chết, còn C sống, thì ta đọc
110 = chai .Từ các thí nghiệm trên, ta thấy rằng mỗi con heo cho một bit thông tin — nó sống (
0) hay chết (1). Với con heo, ta có bit, tức làDo đó để phân biệt chai, cần đủ số biểu diễn trạng thái, nghĩa là :
Ký hiệu tức là làm tròn lên.
Với bài toán gốc: con heo, nếu chỉ thử một lượt. Trước khi tìm cách giảm tiếp con số này, ta xét vì sao 10 đã là số nhỏ nhất có thể cho một lượt thử.
Ở phần trên ta xây dựng được một chiến lược dùng con heo. Nhưng liệu có cách dùng ít heo hơn không? Câu trả lời là không, và lý do đến từ lý thuyết thông tin của nhà toán học Claude Shannon (1948).
Trước khi thử, chai độc có thể là bất kỳ chai nào trong chai, khả năng ngang nhau. Shannon đo lượng thông tin còn thiếu — gọi là entropy — bằng công thức: với khả năng đồng đều,
Với , ta đang thiếu khoảng bit thông tin. Đó là lượng thông tin cần thu được để chỉ ra chai độc. Hiểu một cách trực quan là ta cần hỏi câu hỏi nhị phân để phân biệt được 1000 khả năng khác nhau.
Một con heo, sau một lượt thử, chỉ có hai kết cục: sống hoặc chết. Hai khả năng cho tối đa 1 bit thông tin. Ghép hai điều trên lại, ta có kết luận:
Cần thu bit. Mỗi con heo cho tối đa 1 bit. Vậy cần ít nhất con heo.
Đây được gọi là cận dưới lý thuyết thông tin (information-theoretic lower bound). Không chiến lược nào vượt được cận này, vì nó chỉ dựa trên việc đếm lượng thông tin, không phụ thuộc vào cách thiết kế cụ thể.
Chiến lược nhị phân ở Phần 1 dùng đúng con heo. Vậy:
Cận trên (làm được) trùng với cận dưới (giới hạn lý thuyết), nên lời giải là tối ưu. Đây là nội dung của định lý mã hoá nguồn của Shannon (Shannon's source coding theorem): để mã hoá một nguồn có entropy mà không mất mát, cần ít nhất bit, và luôn tồn tại cách đạt được bit. Bài toán Poor Pigs là một trường hợp cụ thể của định lý này.
Một cách diễn đạt tương đương. Coi mỗi con heo như một "đường truyền" chở được 1 bit. Bài toán trở thành: cần bao nhiêu đường truyền để chuyển bit? Câu trả lời là .
Đề bài gốc cho ta thêm một dữ kiện: độc phát tác sau 15 phút, và ta có 60 phút. Nghĩa là trên thực tế ta thực hiện được
Ta sẽ thấy một con heo sống sót qua lượt 1 vẫn có thể dùng được cho lượt 2 và không nhất thiết phải cho tất cả cùng uống một lúc. Điều này làm cho bài toán trông có vẻ trở nên khó suy luận hơn và có cảm giác tuỳ thuộc vào may rủi, nhưng hãy cùng đọc lời giải dưới đây.
Với lượt, các kết cục khả dĩ của một con heo là:
- chết sau lượt 1,
- chết sau lượt 2,
- chết sau lượt 3,
- chết sau lượt 4,
- sống sót qua cả 4 lượt.
Tổng cộng trạng thái phân biệt được. Tổng quát: lượt cho trạng thái. Thay vì 1 bit, mỗi con heo bây giờ truyền được bit.
Để thuận tiện hơn, ta sẽ đổi hệ cơ số từ hệ nhị phân sang một hệ cơ số khác nếu một con heo bây giờ truyền được bit.
Nếu mỗi con heo có trạng thái, thì con heo tạo ra
và ta cần , tức là
Công thức giống hệt trường hợp nhị phân, chỉ khác cơ số: thay vì đếm bằng cơ số 2 (sống/chết), ta đếm bằng cơ số (chết ở lượt nào / sống). Mỗi chai được viết như một số trong hệ cơ số , và mỗi chữ số cho biết con heo tương ứng uống ở lượt nào.
Trong lời giải này, ta sẽ sử dụng hệ tam phân, tức là hệ đếm có 3 ký tự
0 , 1 và 2. Ví dụ với số trong hệ thập phân sẽ bằng trong hệ tam phân: .Quay lại với ví dụ: Lấy chai với vòng thử (mỗi heo có trạng thái). Số heo cần là , so với con nếu chỉ thử một vòng.
Viết mỗi chai bằng 2 chữ số hệ cơ số 3. Quy ước: chữ số cho biết con heo tương ứng uống ở vòng nào — là không uống, là uống vòng 1, là uống vòng 2:
Thiết kế thí nghiệm theo từng vòng:
- Vòng 1: Heo A uống chai (chữ số trái ); Heo B uống chai (chữ số phải ).
- Vòng 2 (chỉ những con còn sống mới uống tiếp): Heo A uống chai (chữ số trái ); Heo B uống chai (chữ số phải ).
Vì sao thiết kế nhất quán: nếu chai độc có chữ số trái (chai hoặc ), thì ở vòng 1 Heo A không đụng tới nó — vòng 1 Heo A chỉ uống các chai có chữ số trái . Do đó Heo A sống qua vòng 1 và còn đó để uống ở vòng 2. Thiết kế không bao giờ đòi một con heo đã chết phải uống tiếp. Nói cách khác, nếu một con heo đã chết ở một vòng nào đó, tức là nó đã truyền được giá trị của chữ số mà nó chịu trách nhiệm, cho nên không cần thiết phải dùng nó cho các vòng tiếp theo.
Giải mã kết quả: đọc "vòng chết" của mỗi con heo như một chữ số cơ số 3 (sống ), chết vòng 1 , chết vòng 2 ), rồi ghép hai chữ số:
Hai con heo, nhờ có thêm một vòng thời gian, làm được việc mà một vòng cần tới ba con.
Với (5 trạng thái mỗi heo):
Số heo giảm từ 10 xuống 5 nhờ tận dụng thời gian. Bảng dưới cho thấy quan hệ giữa số lượt thử và số heo cần dùng:
Minh hoạ: khi số lượt thử tăng, số heo cần thiết giảm.
Chẳng hạn, 2 con heo với 4 lượt thử phân biệt được chai.
Nếu lùi lại một bước, ta thấy Poor Pigs là đại diện của một họ bài toán mà toán học và khoa học máy tính nghiên cứu nhiều: cần hỏi ít nhất bao nhiêu câu để tìm ra thứ mình cần?
Cho một con heo uống từ một nhóm chai rồi quan sát, thực chất là hỏi:
"Chai độc có nằm trong nhóm này không?"
Kết cục sống/chết là câu trả lời không/có. Bài toán trở thành trò "20 câu hỏi": tìm 1 vật trong vật, mỗi câu hỏi có hai đáp án, và số câu tối thiểu là . Trong khoa học máy tính, đại lượng "số câu hỏi ít nhất" này có tên là độ phức tạp truy vấn (query complexity), và sơ đồ các câu hỏi nối tiếp gọi là cây quyết định (decision tree). Số heo (một vòng) hay số lượt thử (nhiều vòng) chính là chiều cao của cây quyết định đó.
Lập luận " khả năng thì cần câu hỏi nhị phân" ở Phần 2 có tên là cận đếm (counting bound). Nó là một kỹ thuật chứng minh cận dưới cơ bản, và xuất hiện ở nhiều nơi.
Ví dụ, sắp xếp bằng so sánh. Có cách hoán vị một danh sách phần tử. Mỗi phép so sánh " có nhỏ hơn không?" cho 1 bit. Để phân biệt khả năng, cần ít nhất
Đây là lý do một số thuật toán sắp xếp có độ phức tạp là : cùng một cách đếm như với những con heo, chỉ thay "chai" bằng "hoán vị".
Bài toán này minh hoạ rõ một sự phân biệt trong độ phức tạp:
- Hỏi cùng lúc (nonadaptive): tất cả các con heo quyết định uống chai nào ngay từ đầu, không con nào xem được kết quả của con khác. Mọi câu hỏi là xác định từ trước. Thậm chí khi kiểm nhiều vòng trên các con heo, thì vì bản chất kế hoạch kiểm thử đã được xác định, đây vẫn là kiểm thử không thích ứng.
- Hỏi dần (adaptive): việc kiểm thử thích ứng tức là ta quyết định cho ra câu hỏi dựa trên câu trả lời của câu hỏi trước đó. Ví dụ nếu may mắn ở vòng trước đó có một hoặc một số con heo đã chết, ta có thể khoanh vùng những chai cần được kiểm và chỉ kiểm những chai đó.
Khi chỉ có một chai độc, hai cách này tốn công như nhau (). Nhưng khi có nhiều chai độc, khoảng cách giữa hai cách trở thành một câu hỏi nghiên cứu chưa được giải quyết trọn vẹn.
Đoạn code minh hoạ dưới đây làm hai việc: thiết kế (mỗi con heo uống chai nào) và giải mã (từ kết quả sống/chết suy ra chai độc), cho phương án nhị phân một vòng.
1import math
2
3def so_heo_can(n, so_trang_thai=2):
4 """so_trang_thai = r + 1. Mặc định 2 (một vòng: sống/chết)."""
5 return math.ceil(math.log(n, so_trang_thai))
6
7def thiet_ke(n):
8 """Trả về: số heo, và danh sách chai mà mỗi con heo sẽ uống."""
9 k = so_heo_can(n)
10 # Heo thứ j uống chai i nếu bit thứ j của i bằng 1
11 ke_hoach = {j: [i for i in range(n) if (i >> j) & 1] for j in range(k)}
12 return k, ke_hoach
13
14def giai_ma(ket_qua):
15 """ket_qua[j] = 1 nếu heo j chết, 0 nếu sống. Trả về số hiệu chai độc."""
16 return sum(bit << j for j, bit in enumerate(ket_qua))
17
18# ── Thử nghiệm ──────────────────────────────────────────────
19n = 1000
20k, ke_hoach = thiet_ke(n)
21print(f"{n} chai cần {k} con heo (một vòng).")
22
23# Giả sử chai độc là chai số 573. Mô phỏng xem heo nào chết.
24chai_doc = 573
25ket_qua = [1 if chai_doc in ke_hoach[j] else 0 for j in range(k)]
26print("Trạng thái sống/chết:", ket_qua)
27print("Giải mã ra chai:", giai_ma(ket_qua)) # -> 573Khung tư duy "gộp nhiều thứ vào một lần kiểm tra" được dùng ở nhiều lĩnh vực, có thể kể đến như:
- Xét nghiệm gộp mẫu (pooled testing). Đây là ứng dụng trực tiếp nhất, được phát triển đầu tiên bởi Robert Dorfman (1943) khi ông thiết kế cách sàng lọc bệnh cho lính thời Thế chiến II. Ý tưởng căn bản của ông là trộn mẫu của nhiều người vào một lần xét nghiệm. Nếu nhóm âm tính thì cả nhóm sạch chỉ với một lần thử; nếu nhóm dương tính mới xét lại từng người. Trong đại dịch COVID-19, nhiều quốc gia đã dùng cách này để tiết kiệm bộ kit: khi tỷ lệ mắc thấp, số lần xét nghiệm giảm đáng kể so với xét nghiệm từng người. Ở đây mỗi người đóng vai một "cái chai", mỗi lần xét nghiệm gộp là một "con heo". Kỹ thuật tương tự cũng dùng để sàng lọc HIV trong ngân hàng máu.
- Kiểm thử phần mềm. Coi mỗi mô-đun có thể có lỗi như một "chai độc", ta thiết kế số lần chạy thử tối thiểu để khoanh vùng lỗi. Ví dụ một phần mềm có 10 mô-đun, tối đa 2 mô-đun bị lỗi. Số khả năng cần phân biệt là , nên cần
- Mã sửa lỗi. Cách thêm thông tin dư thừa có cấu trúc để phục hồi dữ liệu khi bị hỏng một phần — nền tảng của các mã như Reed–Solomon trong đĩa CD/DVD, mã QR, và truyền dữ liệu không dây đều dựa trên cùng nguyên lý.
- Sinh học phân tử và an ninh mạng. Kỹ thuật gộp mẫu DNA giúp giảm chi phí khi giải trình tự gen; trong an ninh mạng, một số thuật toán phát hiện bất thường dùng ý tưởng tương tự để khoanh vùng thành phần đáng ngờ trong mạng lớn.
Trường hợp một chai độc chỉ là điểm khởi đầu. Bài toán còn nhiều nhánh, trong đó có những câu hỏi chưa được giải quyết trọn vẹn.
- Khi có nhiều hơn một chai độc. Nếu có chai độc trong chai, số phép thử cần thiết tăng lên cỡ . Đây là địa hạt của lý thuyết kiểm tra nhóm (group testing). Với đúng chai độc, đã có cách thiết kế tối ưu (xây dựng Frankl–Füredi). Nhưng với , cách làm đó không mở rộng trực tiếp được, và việc tìm thiết kế tối ưu vẫn là một bài toán mở.
- Hỏi trước có thua hỏi dần không? Với , khoảng cách giữa phương án không thích ứng (hỏi trước) và thích ứng (hỏi dần) vẫn chưa được hiểu đầy đủ ở nhiều khía cạnh.
- Khi kết quả có thể sai. Ngoài đời, xét nghiệm đôi khi cho kết quả sai (dương tính giả, âm tính giả). Thiết kế thí nghiệm chịu được nhiễu cần có cách tiếp cận tương tự như lý thuyết mã sửa lỗi, và câu hỏi "cần bao nhiêu phép thử dư ra để chống nhiễu" cũng còn nhiều điều để nghiên cứu.
Bài toán những con heo tội nghiệp là một dẫn nhập tốt đến thế giới lý thuyết thông tin, nơi có nhiều câu hỏi thú vị khác đang chờ đợi chúng ta trả lời. Bạn nghĩ sao về bài toán này và những hướng nghiên cứu mở kể trên? Chúc bạn và những con heo nhiều điều may mắn!
