Đặt vấn đề

Giả sử một buổi sáng đẹp trời, vì một lý do nào đó mà tác giả chưa nghĩ ra, trước mặt chúng ta xuất hiện 1000 chai rượu.

999 chai hoàn toàn bình thường.

1 chai có độc.

Chất độc này khá kỳ quặc:

• Uống vào không chết ngay.
• Chính xác khoảng 1 giờ sau mới phát tác.
• Ta chỉ có 10 con chuột để thử.
• Và quan trọng nhất: chỉ được thử đúng một lần.

Sau một giờ, ta phải chỉ chính xác:

Chai nào có độc?

Nghe qua thì có vẻ vô lý.

Nếu có 1000 chai mà chỉ có 10 con chuột, cách suy nghĩ tự nhiên nhất là:

Cho mỗi con chuột uống một chai.

Nhưng như vậy ta chỉ kiểm tra được 10 chai.

Cho mỗi con uống 100 chai?

Nếu một con chết thì biết độc nằm trong 100 chai đó, nhưng hết giờ rồi, không còn lượt thử thứ hai để tìm tiếp.

Bài toán trông giống như đang thiếu chuột.

Nhưng thật ra chúng ta không thiếu chuột.

Chúng ta đang lãng phí thông tin mà mỗi con chuột có thể mang về.

Và đây là chỗ bài toán bắt đầu trở nên rất đẹp.

Mỗi con chuột không chỉ có nhiệm vụ trả lời:

“Chai này có độc hay không?”

Nó có thể trả lời một câu hỏi tổng quát hơn:

“Chất độc có nằm trong tập chai mà tôi vừa uống hay không?”

Một thay đổi rất nhỏ trong cách đặt câu hỏi.

Nhưng nó biến 10 con chuột thành một hệ thống có thể phân biệt hơn 1000 khả năng khác nhau.

Hay nói hơi ngáo một chút:

Trước mặt ta không còn là 10 con chuột nữa.

Đó là 10 bit biết thở.

10 con chuột có thể nói được bao nhiêu điều?

Hãy quên rượu đi một chút.

Nhìn vào một con chuột.

Sau một giờ, nó chỉ có hai trạng thái:

• sống
• chết

Nếu gọi:

1sống = 0
2chết = 1

thì một con chuột có thể lưu được 1 bit thông tin.

Hai con chuột sẽ có bốn khả năng:

100
201
310
411

Ba con chuột có tám khả năng:

1000
2001
3010
4011
5100
6101
7110
8111

Tổng quát, với n con chuột, số trạng thái khác nhau là:

$$ 2^n $$

Với 10 con:

$$ 2^{10} = 1024 $$

Đây chính là con số quan trọng nhất của cả bài toán.

Ta có:

11000 chai

và:

11024 trạng thái sống/chết

Tức là 10 con chuột có đủ khả năng biểu diễn 1024 kết quả khác nhau.

Trong khi chúng ta chỉ cần phân biệt 1000 chai.

Dư 24 trạng thái.

Xong bài toán.

Quá dễ.

Ít nhất là trên lý thuyết.

Vấn đề còn lại chỉ là:

Làm thế nào biến mỗi chai rượu thành một trạng thái của 10 con chuột?

Câu trả lời nằm trong thứ mà máy tính làm hàng nghìn tỷ lần mỗi giây.

Số nhị phân.

Đánh số từng chai bằng nhị phân

Ta đánh số các chai từ:

11
22
33
4...
51000

Sau đó chuyển số thứ tự của mỗi chai sang dạng nhị phân 10 bit.

Ví dụ:

1chai 1    = 0000000001
2chai 2    = 0000000010
3chai 3    = 0000000011
4chai 4    = 0000000100
5chai 5    = 0000000101
6...
7chai 1000 = 1111101000

Ta cũng đánh số 10 con chuột từ phải sang trái:

1Chuột 10  Chuột 9 ... Chuột 3  Chuột 2  Chuột 1

Mỗi con chuột chịu trách nhiệm cho một bit.

Quy tắc rất đơn giản:

Nếu bit tương ứng của chai bằng 1, con chuột đó phải uống một giọt từ chai này.

Nếu bit bằng 0, nó không uống.

Ví dụ chai số 13.

13 trong hệ nhị phân là:

10000001101

Các bit bằng 1 nằm ở vị trí:

11
23
34

Vậy ta lấy một ít rượu từ chai số 13 cho:

1Chuột 1
2Chuột 3
3Chuột 4

uống.

Các con còn lại không uống chai này.

Tiếp tục làm tương tự với toàn bộ 1000 chai.

Mỗi con chuột cuối cùng sẽ uống một hỗn hợp gồm một giọt từ rất nhiều chai khác nhau.

Nghe hơi giống tiệc buffet mà thực đơn được thiết kế bởi một kỹ sư phần mềm mất ngủ.

Nhưng điều quan trọng là:

mỗi chai có một tập chuột uống nó hoàn toàn khác nhau.

Đó chính là chữ ký của chai.

Một ví dụ nhỏ hơn cho dễ nhìn

1000 chai hơi nhiều.

Ta thu nhỏ bài toán xuống còn:

18 chai
23 con chuột

Bởi vì:

$$ 2^3 = 8 $$

Ba con chuột có thể tạo ra tám trạng thái.

Gọi ba con là:

1A
2B
3C

Đánh số chai từ 0 đến 7 để ví dụ nhìn gọn hơn:

Ví dụ chai số 6:

1110

Ta cho:

1A uống
2B uống
3C không uống

Nếu chai 6 có độc, một giờ sau:

1A chết
2B chết
3C sống

Ta đổi lại thành bit:

1110

110 trong hệ nhị phân chính là:

16

Vậy chai số 6 có độc.

Không cần thử lần hai.

Không cần khoanh vùng.

Không cần đoán.

Chính trạng thái của ba con chuột đã mã hóa trực tiếp số thứ tự của chai độc.

Trở lại với 1000 chai

Với bài toán thật, ta có 10 con chuột.

Mỗi chai được gán một số nhị phân dài 10 bit.

Giả sử chai có độc là chai số:

1713

Đổi 713 sang nhị phân:

11011001001

Ta không cần biết trước chai 713 có độc.

Ngay từ đầu, quy tắc thử nghiệm đã đảm bảo rằng chai 713 được cho những con chuột tương ứng với các bit 1 uống.

Sau một giờ, giả sử trạng thái chuột là:

1chết sống chết chết sống sống chết sống sống chết

Nếu quy ước:

1chết = 1
2sống = 0

ta thu được:

11011001001

Đổi về hệ thập phân:

1713

Chai 713 có độc.

Thứ trông giống một thí nghiệm hóa học thực ra lại là một bài toán mã hóa thông tin.

Điều thú vị không nằm ở số nhị phân

Nếu chỉ dừng ở đây, bài toán đơn giản là một mẹo binary khá vui.

Nhưng thứ mình thấy thú vị hơn nằm sâu hơn một tầng.

Ban đầu chúng ta thường nghĩ:

Một con chuột dùng để kiểm tra một chai.

Đó là cách suy nghĩ kiểu một-một:

11 chuột → 1 chai

Nhưng bài toán không hề yêu cầu như vậy.

Một con chuột có thể uống mẫu từ hàng trăm chai.

Và một chai có thể được nhiều con chuột uống.

Chúng ta chuyển từ:

1đối tượng → người kiểm tra

sang:

1đối tượng → tổ hợp người kiểm tra

Đó là một thay đổi cực kỳ lớn.

Ta không dùng từng con chuột để tìm chai độc.

Ta dùng toàn bộ 10 con chuột để tạo ra một mã số.

Nói cách khác:

 11000 chai
 2       ↓
 3mã hóa
 4       ↓
 510 bit
 6       ↓
 710 con chuột
 8       ↓
 9sống / chết
10       ↓
1110 bit kết quả
12       ↓
13giải mã
14       ↓
15chai độc

Không có con chuột nào biết chai độc là chai nào.

Mỗi con chỉ biết đúng một mẩu thông tin:

10 hoặc 1

Nhưng khi ghép 10 mẩu thông tin lại với nhau, ta có câu trả lời hoàn chỉnh.

Cái này nghe quen quen.

Bởi vì máy tính cũng đang làm chính xác như vậy.

Một con chuột chính là một bit vật lý

Bit thường được mô tả rất trừu tượng:

10
21

Nhưng bit không phải thứ gì đó sống lơ lửng trong thế giới toán học.

Ở ngoài đời, bit luôn cần một trạng thái vật lý để tồn tại.

Nó có thể là:

• transistor bật hoặc tắt
• vùng vật liệu có hoặc không có điện tích
• hướng từ hóa này hoặc hướng từ hóa kia
• ánh sáng có hoặc không
• điện áp cao hoặc điện áp thấp

Và trong bài toán kỳ quặc này:

1chuột sống = 0
2chuột chết = 1

Một con chuột trở thành một thiết bị lưu trữ 1 bit cực kỳ tệ về mặt đạo đức, tốc độ và khả năng tái sử dụng.

Nhưng về mặt toán học, nó vẫn là một bit.

Mười con chuột tạo thành một thanh ghi 10 bit:

10100111010

Và thanh ghi 10 bit chứa được:

$$ 2^{10}=1024 $$

giá trị.

Thế nên câu hỏi thực sự của bài toán không phải:

10 con chuột thử được bao nhiêu chai?

Mà phải là:

10 đối tượng có hai trạng thái tạo được bao nhiêu kết quả phân biệt?

Khi đổi cách đặt câu hỏi, lời giải gần như tự xuất hiện.

Vì sao 9 con chuột không đủ?

Đây là cách kiểm tra xem lời giải có thực sự tối ưu hay không.

Nếu chỉ có 9 con chuột:

$$ 2^9 = 512 $$

Ta chỉ phân biệt được 512 trạng thái.

Nhưng có 1000 khả năng chai độc.

512 chiếc nhãn không thể gắn duy nhất cho 1000 chai.

Chắc chắn ít nhất hai chai phải dùng chung một mã.

Nếu kết quả đó xuất hiện, ta không thể biết chai nào trong hai chai có độc.

Vậy 9 con không đủ.

Còn 10 con:

$$ 2^{10}=1024 \ge 1000 $$

đủ.

Do đó số chuột tối thiểu chính xác là:

$$ \lceil \log_2 1000 \rceil = 10 $$

Đây cũng là một ví dụ rất đẹp về giới hạn thông tin.

Muốn phân biệt N khả năng bằng các câu trả lời có hai trạng thái, ta cần ít nhất:

$$ \lceil \log_2 N \rceil $$

bit thông tin.

Nếu có một triệu chai thì sao?

Giả sử thay vì 1000 chai, một ông chủ nào đó quyết định tích trữ:

11.000.000 chai

Có đúng một chai độc.

Ta vẫn chỉ có một lượt thử.

Cần bao nhiêu con chuột?

Ta tìm n sao cho:

$$ 2^n \ge 1.000.000 $$

Ta có:

$$ 2^{19}=524.288 $$

chưa đủ.

Nhưng:

$$ 2^{20}=1.048.576 $$

đủ.

Vậy chỉ cần:

120 con chuột

Một triệu chai.

Hai mươi con chuột.

Con số này ban đầu nghe rất vô lý.

Nhưng đây chính là sức mạnh của tăng trưởng theo lũy thừa.

Mỗi khi thêm một con chuột, số trường hợp ta phân biệt được gấp đôi.

11 chuột  → 2 chai
22 chuột  → 4 chai
33 chuột  → 8 chai
410 chuột → 1024 chai
520 chuột → hơn 1 triệu chai
630 chuột → hơn 1 tỷ chai

30 con chuột về lý thuyết có thể phân biệt hơn:

$$ 2^{30}=1.073.741.824 $$

khả năng.

Một tỷ chai.

Chỉ vì mỗi con vật mang về đúng một câu trả lời:

1có
2hoặc
3không

Đây thực ra là bài toán thiết kế câu hỏi

Có một cách khác để nhìn bài toán.

Mỗi con chuột đang hỏi một câu hỏi dạng Yes/No.

Ví dụ con thứ nhất hỏi:

Chai độc có nằm trong nhóm các chai có bit cuối bằng 1 không?

Con thứ hai hỏi:

Chai độc có nằm trong nhóm các chai có bit thứ hai bằng 1 không?

Con thứ ba hỏi:

Chai độc có nằm trong nhóm các chai có bit thứ ba bằng 1 không?

…

Mười câu hỏi được hỏi đồng thời.

Sau một giờ, ta nhận được mười câu trả lời.

Ví dụ:

 1Yes
 2No
 3Yes
 4Yes
 5No
 6No
 7Yes
 8No
 9No
10Yes

Hay:

11011001001

Và thế là đủ để xác định một chai duy nhất.

Đây là điểm rất hay của bài toán:

Giới hạn không nằm ở số lần ta được hỏi.

Giới hạn nằm ở lượng thông tin mà mỗi câu trả lời mang lại.

Nếu biết thiết kế câu hỏi đúng, một câu trả lời có/không có thể loại bỏ một nửa thế giới khả năng.

Mười câu như vậy đủ để đi từ 1000 khả năng xuống đúng một.

Nó khá giống trò đoán số

Giả sử mình nghĩ một số từ 1 đến 1000.

Bạn có thể hỏi những câu như:

Số đó lớn hơn 500 không?

Nếu có, khoảng tìm kiếm còn 501–1000.

Tiếp tục:

Lớn hơn 750 không?

Rồi:

Lớn hơn 875 không?

Mỗi câu hỏi cắt không gian tìm kiếm gần một nửa.

Đây chính là ý tưởng của binary search.

Với 1000 số, khoảng:

$$ \log_2 1000 \approx 9.97 $$

nên chỉ cần khoảng 10 câu hỏi Yes/No.

Bài toán con chuột cũng thu được 10 bit.

Nhưng có một khác biệt rất đẹp.

Binary search hỏi:

1câu 1
2↓
3xem kết quả
4↓
5câu 2
6↓
7xem kết quả
8↓
9câu 3

Các câu hỏi phụ thuộc vào kết quả trước đó.

Trong bài toán chai rượu, ta không có thời gian làm vậy.

Thuốc độc cần một giờ mới phát tác.

Cho nên 10 câu hỏi phải được thiết kế trước, rồi thực hiện đồng thời.

Thay vì tìm kiếm tuần tự, ta mã hóa toàn bộ đáp án ngay từ đầu.

Nếu con chuột có ba trạng thái thì sao?

Đến đây có thể nghịch thêm một chút.

Giả sử tồn tại một loại thuốc kỳ quặc hơn.

Sau một giờ, chuột có thể có ba trạng thái:

1khỏe
2say
3chết

Và ta có thể phân biệt chắc chắn ba trạng thái này.

Khi đó mỗi con chuột không còn mang 1 bit nhị phân nữa.

Nó có 3 trạng thái.

10 con chuột có thể tạo ra:

$$ 3^{10}=59.049 $$

kết quả.

Tức là cùng 10 con chuột, về lý thuyết ta có thể phân biệt gần 60.000 chai.

Điều này cho thấy bản chất bài toán không nằm ở chuột.

Nó nằm ở:

1số trạng thái quan sát được

Nếu mỗi thiết bị có k trạng thái và có n thiết bị độc lập, số cấu hình có thể biểu diễn là:

$$ k^n $$

Binary chỉ là trường hợp:

1k = 2

Máy tính hiện đại thích binary không phải vì số 0 và 1 có phép thuật gì đặc biệt.

Mà bởi trong thế giới vật lý, việc xây một thiết bị phân biệt chắc chắn giữa hai trạng thái thường dễ hơn rất nhiều so với phân biệt hàng chục trạng thái mong manh sát nhau.

Nhưng ngoài đời bài toán có một đống giả định

Đây là một câu đố toán học, nên có vài giả định được giấu dưới tấm thảm.

Ta giả sử:

• Chỉ có đúng một chai độc.
• Chất độc luôn phát tác sau một giờ.
• Một lượng mẫu đủ nhỏ vẫn làm chuột chết.
• Một con chuột có thể uống mẫu từ nhiều chai.
• Việc pha nhiều mẫu không làm mất tác dụng của chất độc.
• Chuột không chết vì nguyên nhân khác.
• Chúng ta quan sát chính xác trạng thái sống/chết.

Nếu thay đổi các giả định này, bài toán sẽ khó hơn rất nhiều.

Ví dụ nếu có thể có hai chai độc, kết quả không còn đơn giản là số nhị phân của một chai nữa.

Hai chai có thể kích hoạt hợp của hai tập chuột, làm nhiều mã khác nhau cho cùng một kết quả.

Khi đó ta bắt đầu bước sang những bài toán sâu hơn về:

• group testing
• coding theory
• error-correcting codes
• combinatorial design

Tức là từ một đám chuột uống rượu, đi vài bước thôi là tới cả một vùng toán học dùng trong xét nghiệm y tế, mạng máy tính và lưu trữ dữ liệu.

Đời đôi khi hơi kỳ.

Group Testing: họ hàng nghiêm túc của bài toán này

Có một bài toán thực tế rất giống.

Giả sử có 10.000 mẫu xét nghiệm và ta nghi chỉ có vài mẫu dương tính.

Cách bình thường:

110.000 người
2→ 10.000 xét nghiệm

Nhưng nếu tỷ lệ dương tính rất thấp, ta có thể trộn nhiều mẫu lại thành một pool.

Nếu pool âm tính:

toàn bộ những người trong pool đều âm tính.

Nếu pool dương tính:

ít nhất một người trong nhóm có vấn đề, cần kiểm tra tiếp.

Đó là ý tưởng của group testing.

Thay vì:

1một phép thử → một đối tượng

ta sử dụng:

1một phép thử → một tập đối tượng

Rồi suy luận ngược từ tập hợp kết quả.

Bài toán 1000 chai rượu là phiên bản cực đoan và sạch đẹp của tư duy này.

Mỗi con chuột là một phép kiểm tra trên một tập chai.

Mười kết quả cùng nhau tạo ra chữ ký của chai độc.

Một bài toán về chuột, nhưng bài học lại là về dữ liệu

Mình thích bài toán này không phải vì lời giải nhị phân.

Thứ đáng nhớ hơn là cách chúng ta đo tài nguyên.

Ban đầu ta nhìn thấy:

110 con chuột

và nghĩ:

110 phép thử

Nhưng đây là cách đếm sai.

Thứ thật sự ta có là:

110 biến

mỗi biến có:

12 trạng thái

Do đó không gian kết quả là:

12 × 2 × 2 × ... × 2

mười lần.

Hay:

$$ 2^{10}=1024 $$

Một hệ thống đôi khi trông rất nghèo tài nguyên nếu ta nhìn từng thành phần riêng lẻ.

Nhưng sức mạnh của nó nằm ở số tổ hợp mà các thành phần có thể tạo ra.

Một transistor chỉ bật hoặc tắt.

Nghe chẳng có gì ghê gớm.

Nhưng hàng tỷ transistor phối hợp với nhau, và chúng ta có CPU, GPU, RAM, điện thoại, mô hình AI.

Một bit gần như chẳng nói được gì.

Nhưng hàng tỷ bit phối hợp với nhau có thể chứa một bộ phim, một hệ điều hành, hay những dòng chữ bạn đang đọc.

Và trong câu đố này cũng vậy.

Một con chuột chỉ trả lời được:

10 hoặc 1

Nhưng mười con chuột ghép lại có thể chỉ thẳng vào một chai giữa một nghìn chai.

Tổng kết

Lời giải của bài toán 1000 chai rượu rất ngắn:

• Đánh số 1000 chai bằng số nhị phân 10 bit.
• Mỗi con chuột đại diện cho một bit.
• Với mỗi chai, con chuột nào có bit tương ứng bằng 1 thì uống mẫu từ chai đó.
• Sau một giờ, ghi lại chuột nào sống và chuột nào chết.
• Quy ước chết là 1, sống là 0.
• Ghép 10 trạng thái thành một số nhị phân.
• Đổi số đó về hệ thập phân.
• Đó chính là số thứ tự của chai độc.

Bởi vì:

$$ 2^{10}=1024 $$

nên 10 con chuột đủ để phân biệt 1000 chai.

Nhưng điều đáng nhớ hơn là thế này:

Đừng hỏi “một tài nguyên xử lý được bao nhiêu đối tượng”.

Hãy hỏi:

“Toàn bộ trạng thái của hệ thống này có thể mã hóa được bao nhiêu thông tin?”

Có những bài toán không cần thêm tài nguyên.

Chúng chỉ cần ta ngừng dùng tài nguyên theo cách một-một.

1000 chai vẫn nằm đó.

10 con chuột vẫn chỉ là 10 con chuột.

Một giờ vẫn chỉ là một giờ.

Không có gì được thêm vào.

Chỉ có cách chúng ta sắp xếp thông tin thay đổi.

Và đôi khi, trong máy tính cũng như ngoài đời, khác biệt giữa một bài toán bất khả thi và một lời giải mười dòng chỉ nằm ở đúng chỗ đó.

Tham khảo

• Binary number
• Information theory
• Group testing
• Binary search