Cả hai câu hỏi đều rất hay.
- (Câu này do anh Minh gửi.) Có n tù nhân và một phòng biệt giam trong đó có 2 công tắc. Mỗi ngày, một tù nhân được chọn ngẫu nhiên và nhốt vào phòng. Hôm sau, tù nhân đó được thả ra khỏi biệt giam. Một trong số n tù nhân lại được chọn ngẫu nhiên và nhốt vào biệt giam. Tất cả sẽ được thả nếu một ngày nào đó có một tù nhân đoán đúng rằng tất cả các tù nhân đều đã từng vào biệt giam. Nếu đoán sai sẽ bị giết sạch. Các tù nhân không liên lạc được với nhau ngoại trừ hai cái công tắc.
Họ phải làm sao để được thả?
- (Câu này do anh Nghị gửi.) Có 100 tù nhân. Trong một căn phòng lớn có 100 cái hộp, mỗi hộp đựng tên một tù nhân. Các tù nhân được quyền bàn thảo kế hoạch với nhau trước. Sau đó, hoàn toàn không liên lạc với nhau nữa, từng tù nhân được dẫn vào phòng. Mỗi anh vào được mở xem 50 cái hộp tùy ý, sau đó phải rời phòng và để lại trạng thái mọi thứ trong phòng y hệt như cũ. Tất cả các tù nhân sẽ được thả nếu tất cả các tù nhân đều tìm thấy tên mình trong 50 cái hộp mà mình mở.
Kế hoạch của các tù nhân như thế nào để xác suất được thả là lớn hơn 30 phần trăm?
32 Comments
Anh Hưng: câu 1 có nghĩa là các tù nhân cũng không được phép bàn luận kế hoạch phải làm thế nào trước khi cái luật nó được đưa ra luôn hả?
em nghĩ chắc tù nhân phải được thỏa thuận trước rồi. nếu vậy thì theo tính toán của em, chỉ cần 1 cái công tắc thôi cũng đã đủ để bọn tù nhân tìm được chiến thuật để thắng. chắc là 2 công tắc thì yêu cầu cao hơn, chẳng hạn như làm sao để mà thắng càng nhanh càng tốt, pk anh Hưng?
Hi Thái, Câu 1: tù nhân biết luật “dẫn ngẫu nhiên”
Em trả lời câu 1:
Giải thích dựa trên hình: http://www.flickr.com/photos/instcode/3299485642/
)
Trong đó:
- Quá trình để nhận biết tât cả tù nhân đã vào phòng biệt giam hay chưa là quá trình duyệt cây nhị phân ở trên cho đến khi số lần đi theo nhánh “new” bằng n. Trong đó:
+ New: Khi một tù nhân vào phòng biệt giam lần đầu tiên.
+ Return: Khi tù nhân đó đã từng vào phòng biệt giam rồi.
- Một tù nhân khi bị đưa vào phòng biệt giam sẽ xem mình đang ở trạng thái nào để từ đó thông báo cho người kế tiếp bằng cách dùng 2 bits để tính parity cho số lần đi qua nhánh “new” và “return”:
+ 1 Bit để đánh dấu số lần đi qua nhánh “new” là lẻ.
+ 1 Bit để đánh dấu số lần đi qua nhánh “return” là lẻ.
- Để ý các node cùng màu thì sẽ có số lượt người “new” là giống nhau… Dựa vào thông tin đó, chắc chắn tù nhân sẽ biết mình đang ở trạng thái nào ở ngày nào (nếu ổng có kiến thức về computer science
Ah quên, qua đây không biết có ai biết webapp online nào hỗ trợ vẽ cây cối dạng như trên không ta? Cám ơn trước…
Hix, cách giải mình bị sai rồi.. Để suy nghĩ thêm đã
Bác Hưng có thể “bật mí” 1 chút về luật “dẫn ngẫu nhiên” hoặc cho biết luật đó trong tiếng Anh là gì để dễ tra cứu không ạ?
Cháu cũng mò ra cách để tù nhân có thể thoát ra chỉ với 1 công tắc rồi nhưng mà với cách đó chắc lúc ra được thì thành cụ hết cả rồi (với n lớn)
Cháu đang nghĩ cách tận dụng 2 công tắc 
@Ngọc Minh:
Câu 85: “Dẫn ngẫu nhiên” nghĩa là chọn mỗi người với xác suất 1/n. (uniform distribution)
Câu 86: Dẫn từng người vào phòng, từ số 1 đến số 100, không “ngẫu nhiên” gì hết. Mỗi tù nhân biết mình là người thứ bao nhiêu được dẫn vào phòng.
Cho em hỏi câu 86 sau khi vào fòg rồi thì có thể tráo đổi các tên trog hộp hay ko? Còn nếu ko cho tráo tên luôn thì hình như bài này ko giải được?
) –> XS tìm được tên mình của 98 ng sau là 100%. Ta chỉ cần xét 2 ng đầu.
? Bất kể ng thứ 1 và ng thứ 2 có 2 kế hoạch gì với nhau thì với việc chỉ mở 50 cai hộp làm sao đạt đc XS 60% nếu sau đó 2 ng ko đc thôg báo cho nhau 
?
- Bây h chỉ xét 2 ng. Tức là g/s sau khi 2 ng đầu mở mỗi ng 50 cái hộp thì 98 ng sau biết chắc chắn tên mình nằm ở đâu (bằg 1 kế hoạch nào đó
- Ng thứ 1 XS tìm đc tên của ng ta là 1/2.
Để XS tổg hợp lớn hơn hoặc bằg 30% thì ng thứ 2 fải có XS tìm được tên mình ít nhất là 60% trog khi ng ta chỉ đc mở có 50 cái hộp trên 100
@tigonhongtrang,
Không được thay đổi trạng thái phòng. Bài giải được đấy.
Vậy các tù nhân có được đánh số không hả bác? Từ 1 đến n chẳng hạn thế :-/ Các tù nhân có được thông báo là từ ngày nào bắt đầu trò chơi không ạ :-/
Ở câu 85 mỗi tù nhân có biết con số n không ạ? Và họ có thống nhất một quy tắc chơi không?
Nếu có thì một người A cố định, mỗi lần vào sẽ thiết lập 2 công tắc là 00
Mỗi người vào sẽ làm như sau:
– Nếu người đó biết mình đã được đếm thì không làm gì cả.
– Nếu người đó chưa được đếm nhưng 2 công tắc là 11 thì không làm gì cả và chưa được đếm.
– Nếu người đó chưa được đếm và 2 công tắc không phải là 11 thì cộng thêm 1 vào (00 cho thành 01, 01 thành 10, 10 thành 11)
Mỗi lần người A vào nhìn vào công tắc sẽ biết có thêm bao nhiêu người được chuyển từ trạng thái chưa được đếm sang được đếm. Khi nào số người này bằng n thì A sẽ đoán.
Cách giải này có nhược điểm là có thể các tù nhân phải đợi rất lâu.
Câu trả lời trên của bạn dungnt mình nghĩ là đúng. Nhược điểm thì như bạn nói.
Mở rộng một chút: Giả sử mỗi tù nhân chỉ bị giam 1 ngày. Có tất cả 100 tù nhân. Theo luật “dẫn ngẫu nhiên” thì mất thời gian bao lâu để tất cả các tù nhân được thả, giả sử là sử dụng phương pháp của dungnt.
Nếu mỗi tù nhân chỉ giam 1 ngày thì chỉ cần đếm ngày là đủ biết rồi. 100 ngày sau thì ai vô cuối cùng sẽ là người đoán.
Bạn Bo chưa hiểu bài toán. Quan trọng là mỗi tù nhân đều có thể bị giam lại.
Hi Đức!
Mình hiểu là mỗi tù nhân đều có thể bị giam lại.
Do đọc nhanh câu mở rộng của bạn nên mình trả lời sai ý.
Sorry!
à mình nhầm là do
Đề bài: Mỗi ngày, một tù nhân được chọn ngẫu nhiên và nhốt vào phòng. Hôm sau, tù nhân đó được thả ra khỏi biệt giam.
Phần mở rộng bạn ghi: Mở rộng một chút: Giả sử mỗi tù nhân chỉ bị giam 1 ngày.
Bạn ghi “chỉ bị giam” nên mình cứ nghỉ là chỉ giam 1 ngày thôi. hihi
À, wow, câu hỏi kì này hay quá, mà cũng khó quá
. Lời giải của dungnt hình như chỉ đúng cho n <= 5 thôi.
)
Anh Hưng cho em hỏi là mình có thể giả sử các tù nhân đều rất thông minh không ạ? Ví dụ như một ngày nào đó mà vẫn chưa thấy ai dám đoán, thì kết luận là những người khác vào nhìn công tắc mà vẫn chưa đủ kết luận, suy ra là cái gì đấy …em chưa nghĩ ra
Còn câu hỏi số 86, có lẽ là các tù nhân sẽ phải thỏa thuận với nhau xem mỗi người sẽ mở những hộp theo thứ tự nào. Anh Hưng thấy sai hướng thì á lên 1 tiếng để bọn em suy nghỉ cách khác ha. Giả sử người thứ j được phân công sẽ mở hộp các hộp thứ tự Aj (50 integers). Vấn đề là có hay không 1 cách phân hoạch các tập Aj sao cho cho dù người ta trộn các nametag thế nào chăng nữa, thì 30% là cả hội sẽ thoát.
Weekend này ráng ngồi suy nghĩ mới được, mà em nghi la giải không ra quá. Bài quá hay.
A, giải được câu 85 rồi, xong rồi đọc lại mới hiểu lời giải của dungnt, mới thấy bạn này giải chính xác rồi. Vậy tương tự như thế, lời giải 1 công tắc mà mấy bạn ở trên có nói đến (nhưng không chịu bật mí ra) có lẽ là thế này:
Lão leader mỗi lần bị tống cổ vào phòng, nếu thấy đèn còn sáng, lão tắt đi và lẩm bẩm CỘNG MỘT.
Những tù nhân khác, mỗi lần vào phòng mà thấy đèn còn sáng thì tự nhủ “thôi để lần tới vậy”; còn nếu thấy
đèn tắt thì bật đèn lên và hi vọng: vậy là tui đã được VÀO ĐỘI, tất nhiên là nếu người này đã “vào đội” rồi thì thôi, mặc kệ cái đèn ra sao thì ra, chờ đến khi chú khác bị nhốt vào thui.
Trở lại lão leader, sau (n-1) lần tắt đèn, lão biết rằng vậy là thời cơ đã đến. Thế là cả hội thoát.
Mấy bài “design protocol” như thế này fun nhưng cũng là time-killer
Lời giải của bạn dungnt đúng rồi. Mình xin bổ xung một chút:
- Trạng thái công tắc ban đầu là ngẫu nhiên vì thế mỗi tù nhân cần thông báo cho người đếm 2 lần. Người đếm dừng lại và đoán khi tổng số đếm được là 2*n.
- Hai công tắc là cần thiết khi: 1) Mỗi tù nhân bị bắt buộc thay đổi trạng thái ít nhất một công tắc 2) Không phân biệt được thứ tự công tắc (không có trái, phải, trước, sau do đó không thể phân biệt giữa 01 và 10)
Hello Phú,
A_j phải “dynamic” hơn nữa, tùy them tìm thấy gì trong hộp, không fix A_j trước
(Cannot type Vietnamese for some weird reason, my bad)
Oh ban Thang, neu cac de cac cong tac ngau nhien nhu the, thi lam sao biet khi nao bat dau dem. Neu vay cung khong can dem 2n, chi can nguoi dau tien vao phong (ngay thu 1) tat het cac cong tac.
Bai 86 em hieu roi, nhu vay la nhung nguoi nay duoc dan vao phong theo mot thu tu nhat dinh. Em co nen gia su la neu co 1 anh nao do, vao phong ma mo het 50 cai hop van chua thay ten minh, thi ca lu bi xu luon ma khong can den ngay 100 khong? Em giai duoc voi n = 4, 8, dang co gang tong quat len.
) Kho’ ghe^
Con neu het 100 ngay nguoi ta moi phan quyet, thi em lai bi’
Ah, Phú nói đúng là các tù nhân biết mình là người thứ mấy được dẫn vào phòng. (Có lẽ đề bài cho không rõ điểm này.) Đúng là chỉ cần một tù nhân không tìm thấy tên thì cả lũ bị xù. (Trong bài toán nguyên thủy là bị … tử hình hết, tôi thấy bạo lực quá nên không dịch ra
)
85. Hello Phú, nếu tù nhân không biết mình là người thứ mấy được dẫn vào phòng giam thì bài toán vẫn có thể giải được (có lẽ đây mới là đề bài gốc).
Xét thuật toán đơn giản trong đó có một người (leader) đứng ra tăng biến đếm lên 1 nếu công tắc ở trạng thái 11 rồi sau đó đặt công tắc về 00, những người còn lại (followers) đưa công tắc từ 11 đúng hai lần (nếu công tắc không ở trạng thái này). Người leader thông báo mọi tù nhân vào phòng khi biến đếm tăng đến 2 * n
Khi đó, người leader có thể đếm nhầm nhiều nhất là lần đầu tiên nếu công tắc ban đầu đặt tại 11. Khi đếm đến 2 * n, có ít nhất 2 *n – 1 lần bấm công tắc, mỗi người bấm không quá 2 lần nên ta vẫn có thể suy ra cả n người đã từng vào phòng.
Clarification:
“Biết thứ tự” là tôi nói về câu 86.
Câu 85 thì không cần biết thứ tự dẫn vào phòng. Câu 85 mà còn biết thứ tự thì … đố làm chi nữa
thanks anh Hưng đã clarified, đúng là em đang nói về bài 86. bạn Thắng, ý tui là nếu công tắc ban đầu không ở default state thì cũng không sao, chỉ cần người đầu tiên chui vào phòng là tắt biến hết mấy cái công tắc là xong, sau đó thì bắt đầu đếm, cho nên vẫn chỉ mất từng đó lần đếm thôi.
btw, trong khi chờ đợi mọi người đưa ra lời giải chính thức, tui có 1 mánh nhỏ để giải bài 86, nhưng mà tà đạo 1 chút, ai biểu mấy ông giữ ngục không ra luật rõ ràng là có phải mở hộp thật nhanh hay là cứ tà tà mà mở. Với lại đề nói rõ là cứ mở 50 hộp đã, rồi mới đóng và để lại như cũ.
anh thứ 1 vào phòng, mở 50 hộp đầu tiên. The chance tìm thấy tên mình là 50%. Trong lúc đó, nếu mà thấy tên người thứ 2 (và tên mình) thì thôi, không mở nữa, chui ra luôn. Còn nếu mở hết 50 cái hộp mà không thấy tên người thứ 2, thì cứ từ từ đóng hộp lại, chậm thôi.
trong lúc đó, anh thứ 2 ở ngoài timing, thấy lâu lâu anh 1 chưa ra thì biết là không thấy tên mình trong 50 hộp đầu, còn nếu thấy ra sớm hoặc xui lắm là ra đúng giờ thì biết là tên mình trong 50 hộp đầu. Cho nên khi đến lượt, anh thứ 2 cứ thế mà mở, đồng thời để ý tìm tên anh thứ 3.
Hồi nào đến giờ, anh thứ 3 vẫn đang ở ngoài, cho nên biết rõ là anh thứ 2 mở 50 hộp đầu hay 50 hộp sau (same logic), cho nên khi đến lượt mình, cộng với timing anh thứ 2, thi sẽ biết là tên mình ở 50 hộp đầu hay sau, lại cứ thế mà tiến hành.
Rõ ràng là không ai nháy ai hết, nhưng chance để survive la 50%. Nhưng nếu mấy anh này bị nhốt riêng và thời gian bị đến lượt try his luck la fixed, thì lại bí
Nếu Leader nó chỉ tống vào phòng 1 lần thì lấy ai là người đếm hả các bác?
Bài 85. Các bạn mặc định là thằng leader có đủ thời gian đếm như vậy. Nhưng nhỡ thằng leader số lần được nhốt vào không đủ để đếm thì sao.
Phản ví dụ cho vui. Lúc đầu nhốt Leader (1) sau đó nhốt từ thằng 2-N (N=100 hay 99 thì tùy) vào luôn. Sau đó cứ ngày tới luân phiên nhốt leader (1) + thằng (2). Nói chung chả ai biết là có bao nhiêu người đã nhốt cả. Biến đến ở đây vẫn thế thôi. là dừng ở con số “cộng một”=2
Theo tớ thì ta có 2 bít đếm + số n. Quy về cái ngôn ngữ hình thức giữa các trạng thái biến đổi vẫn khó có thể có hàm tính toán số người đã vào phòng giam.
Cơ mà cái phản ví dụ của em lại là dẫn có tính toán ko phải ngẫu nhiên roài
. Em không biết mấy mô hình xác xuất lắm. Chả lẽ sau N ngày với N đủ lớn thì chỉ cần bảo đã có 100 thằng vào có khi xong. N đủ lớn khéo tất cả die hết rồi 
.
Nếu mặc định là xác suất mỗi người được chọn với 1/n thì kiểu gì người (2) cũng có lúc vào ở trạng thái đèn ko ở 11. bật lên 11, rồi thể nào cũng có lúc sau đó leader (1) vào. Thêm 1.
Rồi sẽ có lúc người (3) vào ở trạng ko phải 11. Nghĩa là sẽ có lúc nó được quyền tự đếm “Hà hà cuối cùng ta đã được đếm”. Leader thể nào cũng có lúc vào lại và lại thêm 1.
Nếu như phản ví dụ giả sử có thằng vào mãi chả được đếm thì xác xuất dẫn vào ngẫu nhiên sẽ không còn đúng xét ra vô hạn nữa.
Hơi ngụy biện tí nhỉ
.