baem9999
Senior Member
Vừa đọc được 1 bài toán ảo quá, mạn phép chia sẻ với anh em.
Giả sử có 100 tù nhân, được đánh số từ 1 tới 100. Cai ngục cho xây dựng 1 căn phòng có 100 hộp, được đánh số từ 1 tới 100, trong mỗi hộp là 1 số ngẫu nhiên từ 1 tới 100 (ví dụ hộp số 1 có thể chứa số 50, hộp 50 có thể chứa số 3). Mỗi tù nhân được yêu cầu bước vào phòng 1 mình, được phép mở 50 hộp, nếu họ tìm được số của họ thì được qua. Nếu tất cả 100 tù nhân đều tìm được số của mình, thì cả 100 người đều được thả, nhưng nếu chỉ 1 người ko tìm được thì 100 tù nhân sẽ phải chết.
1 tù nhân tính sơ tỉ lệ thành công sẽ là: (1/2)^100 = 0,00...0008 (31 số 0). Kết luận đây là thử thách ko thể hoàn thành.
1 tù nhân khác đưa ra cách giải như sau:
Người nào mang số áo bao nhiêu sẽ vào tìm hộp có số áo đó, trong hộp có số nào sẽ tìm tiếp hộp của số đó. Ví dụ: người số 1 sẽ tìm hộp 1, trong hộp 1 có số 10 sẽ qua tìm hộp 10, trong hộp 10 có số 25 sẽ tìm hộp 25. Cứ như vậy tới khi tìm được số áo của mình hoặc đến khi hết 50 lượt. Nếu trong lúc tìm bị trùng thì sẽ chọn 1 số khác để tiếp túc (Ví dụ tìm hộp 1 ra số 10, tìm số 10 ra số 25, tìm số 25 ra lại số 1), thì sẽ chọn lại 1 số khác để tiếp tục quá trình.
Người tù nhân khẳng định cách này sẽ nâng lên tỉ lệ thành công lên tới 31%, cao hơn rất rất rất nhiều lần so với cách thông thường.
Theo bạn, cách làm này có thực sự nâng cao tỉ lệ thành công hay không? Tại sao?
PS: Số trong hộp ngẫu nhiên 100%, ko có sự sắp đặt nào cả. Các tù nhân phải vào phòng lần lượt từng người 1, sau đó sẽ được đưa ra 1 căn phòng khác, ko được trao đổi với tù nhân khác trong suốt quá trình tìm kiếm.
Edit lần 1: Bài toán là "tìm" được số của mình chứ ko có lấy số của mình ra nhé, ví dụ tù nhân 1 tìm được số của mình xong đi ra thì số hộp trong đó vẫn giữ nguyên 100 hộp và vẫn đủ 100 số nhé.
Giả sử có 100 tù nhân, được đánh số từ 1 tới 100. Cai ngục cho xây dựng 1 căn phòng có 100 hộp, được đánh số từ 1 tới 100, trong mỗi hộp là 1 số ngẫu nhiên từ 1 tới 100 (ví dụ hộp số 1 có thể chứa số 50, hộp 50 có thể chứa số 3). Mỗi tù nhân được yêu cầu bước vào phòng 1 mình, được phép mở 50 hộp, nếu họ tìm được số của họ thì được qua. Nếu tất cả 100 tù nhân đều tìm được số của mình, thì cả 100 người đều được thả, nhưng nếu chỉ 1 người ko tìm được thì 100 tù nhân sẽ phải chết.
1 tù nhân tính sơ tỉ lệ thành công sẽ là: (1/2)^100 = 0,00...0008 (31 số 0). Kết luận đây là thử thách ko thể hoàn thành.
1 tù nhân khác đưa ra cách giải như sau:
Người nào mang số áo bao nhiêu sẽ vào tìm hộp có số áo đó, trong hộp có số nào sẽ tìm tiếp hộp của số đó. Ví dụ: người số 1 sẽ tìm hộp 1, trong hộp 1 có số 10 sẽ qua tìm hộp 10, trong hộp 10 có số 25 sẽ tìm hộp 25. Cứ như vậy tới khi tìm được số áo của mình hoặc đến khi hết 50 lượt. Nếu trong lúc tìm bị trùng thì sẽ chọn 1 số khác để tiếp túc (Ví dụ tìm hộp 1 ra số 10, tìm số 10 ra số 25, tìm số 25 ra lại số 1), thì sẽ chọn lại 1 số khác để tiếp tục quá trình.
Người tù nhân khẳng định cách này sẽ nâng lên tỉ lệ thành công lên tới 31%, cao hơn rất rất rất nhiều lần so với cách thông thường.
Theo bạn, cách làm này có thực sự nâng cao tỉ lệ thành công hay không? Tại sao?
PS: Số trong hộp ngẫu nhiên 100%, ko có sự sắp đặt nào cả. Các tù nhân phải vào phòng lần lượt từng người 1, sau đó sẽ được đưa ra 1 căn phòng khác, ko được trao đổi với tù nhân khác trong suốt quá trình tìm kiếm.
Edit lần 1: Bài toán là "tìm" được số của mình chứ ko có lấy số của mình ra nhé, ví dụ tù nhân 1 tìm được số của mình xong đi ra thì số hộp trong đó vẫn giữ nguyên 100 hộp và vẫn đủ 100 số nhé.
Last edited:
