Bài toán 100 tù nhân

Cụ Dumbledore · 8/8/22

Áp dụng lý thuyết đồ thị thì ta mô hình hoá đc cái hộp chứa số thứ tự theo dạng. Đỉnh = số thứ tự. Hộp x chứa số y thì có 1 cạnh có hướng nối từ đỉnh x tới y. Với cách này ta thấy đồ thị mô tả các hộp là tập hợp các đồ thị con dạng vòng.
=> Tù nhân nào có stt nằm trong 1 đồ thị dạng vòng có số đỉnh < 50 thì tỉ lệ tìm ra stt của mình là 100%.
Ta thấy đồ thị vòng con có số đỉnh lớn nhất sẽ giảm dần từ 100 về 1. Khi giảm dưới 50 thì tỉ lệ thành công của 100 tù nhân sẽ luôn là 100%. Và vì thứ tự sắp xếp là random nên tỉ lệ xuất hiện của bất kỳ đồ thị nào trong tập hợp tất cả các đồ thị có thể xảy ra là như nhau. Nếu anh nào tìm ra đc tập hợp đồ thị khả thi thì có thể tính đc xác suất thành công trung bình dễ dàng. Tôi ko tìm đc nhưng tôi đoán là làm cách này tỉ lệ thắng trung bình tăng lên 31% là đúng.

Sent from Xiaomi M2102J20SI using vozFApp

kiemrong08 · 8/8/22

Vấn đề là sau khi lấy được áo, ông tù nhân lấy được đúng sẽ bảo các ông còn lại vị trí các hộp nếu các hộp ko bị xáo trộn thế thì cũng dễ lấy

hero123 · 8/8/22

deathmetal27 đã nói:
đừng lôi toán vào cái 4rum này , đố đọc bảng cứu chương còn khối thằng ko thuộc đấy

thým có thuộc không :shame:

Chocuaanhne · 8/8/22

jupyter đã nói:
ông kia nói đúng mà
50 người đầu tiên chọn các hộp từ 1-50
cả 50 người còn sống tức hộp 1 đến 50 chứa các số từ 1-50 thôi
người thứ 51 trở đi chọn các hộp từ 51 trở đi là tỉ lệ 100%

nếu được lật 50 lần ho 1 người thì tỉ lệ thành công làm gì 0.5^100 được. chỉ 0.5^50(nếu kết quả ^100 là đúng) thôi vì từ thằng 51 trở đi thì còn max 50 hộp mà được lật 50 lần thì 100% ra đúng hộp...

Ông kia đã hiểu sai đề mà ông còn vào cãi được @@

khaccanh · 8/8/22

Giả sử có 2 tù nhân mang áo số 1 và số 2 , trong phòng có 2 hộp, 1 hộp chứa số 1 và 1 hộp chứa số 2
-Trường hợp 1 : 2 tù nhân chọn ngẫu nhiên
xác suất để 2 người đều chọn đúng số của mình là 0.5 * 0.5 = 0.25
-Trường hợp 2 : người mang áo số 1 sẽ chọn hộp 1 và người mang áo số 2 sẽ chọn hộp 2
xác suất để người số 1 chọn đúng vẫn là 1/2.
Tuy nhiên nếu người số 1 chọn đúng thì người số 2 100% chọn đúng.
nếu người số 1 chọn sai thì người số 2 100% chọn sai.
như vậy xác suất để cả 2 chọn đúng là 50%
=> khả năng chọn cả 2 chọn trúng nếu chơi theo chiến lược sẽ tăng lên thật. Nếu cả 2 chọn ngẫu nhiên sẽ có 4 trường hợp : 1Đ 2S, 1Đ 2Đ, 1S 2S, 1S 2Đ. Trong 4 trường hợp có 1 trường hợp cả 2 số đúng là 25%
Còn chọn theo chiến lược đã loại đi 2 trường hợp là 1Đ 2S và 1S 2Đ nên giờ chỉ còn 2 TH là 1Đ 2Đ và 1S 2S. xác suất tăng lên 50% thật
Quy nạp lên thì ra bài toán 100 người thôi

Cụ Dumbledore · 8/8/22

Áp dụng lý thuyết đồ thị thì ta mô hình hoá đc cái hộp chứa số thứ tự theo dạng. Đỉnh = số thứ tự. Hộp x chứa số y thì có 1 cạnh có hướng nối từ đỉnh x tới y. Với cách này ta thấy đồ thị mô tả các hộp là tập hợp các đồ thị con dạng vòng.
=> Tù nhân nào có stt nằm trong 1 đồ thị dạng vòng có số đỉnh < 50 thì tỉ lệ tìm ra stt của mình là 100%.
Ta thấy đồ thị vòng con có số đỉnh lớn nhất sẽ giảm dần từ 100 về 1. Khi giảm dưới 50 thì tỉ lệ thành công của 100 tù nhân sẽ luôn là 100%. Và vì thứ tự sắp xếp là random nên tỉ lệ xuất hiện của bất kỳ đồ thị nào trong tập hợp tất cả các đồ thị có thể xảy ra là như nhau. Nếu anh nào tìm ra đc tập hợp đồ thị khả thi thì có thể tính đc xác suất thành công trung bình dễ dàng. Tôi ko tìm đc nhưng tôi đoán là làm cách này tỉ lệ thắng trung bình tăng lên 31% là đúng.

Sent from Xiaomi M2102J20SI using vozFApp

Chocuaanhne · 8/8/22

jupyter đã nói:
tôi hỏi thật là anh đã đặt bút làm chưa,hay ngồi đoán giống mấy người trên
cách giải trên k hề tăng xác suất thắng của riêng 1 người
làm cho dc câu này đã rồi bàn luận tiếp

Xamlol, tôi đọc giải rồi, và tôi nghĩ là tôi hiểu nó, cách giải trên không hề tăng rate thành công từng người, xác nhận, và tôi chưa hề đề cập đến nó?

Tôi khẳng định là ông kia hiểu sai đề, theo ý là pick được số đúng xong sẽ lấy luôn hộp, và tôi khẳng định tiếp ngay cả khi hiểu sai đề thì cách tính rate ông kia cũng sai.

baem9999 đã nói:
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.

Chỗ này thớt hiểu sai rồi, nếu kết thúc loop tức là đã tìm được số rồi, còn phải chọn tiếp làm gì

khaccanh · 8/8/22

jupyter đã nói:
ông kia nói đúng mà
50 người đầu tiên chọn các hộp từ 1-50
cả 50 người còn sống tức hộp 1 đến 50 chứa các số từ 1-50 thôi
người thứ 51 trở đi chọn các hộp từ 51 trở đi là tỉ lệ 100%

cái này sai rồi, lúc tìm xong thì những người còn lại ko biết người đó tìm được hay không. Bác đọc kỹ lại đề đi
"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."
Chứ người sau mà biết thông tin người trước tìm được hay không được thì game lại dễ hơn nhiều rồi
mà kể cả như vậy thì lập luận 50 người đầu còn sống thì hộp 1-50 chỉ chứa số 1-50 cũng sai nốt.

baem9999 · 8/8/22

Chocuaanhne đã nói:
Xamlol, tôi đọc giải rồi, và tôi nghĩ là tôi hiểu nó, cách giải trên không hề tăng rate thành công từng người, xác nhận, và tôi chưa hề đề cập đến nó?

Tôi khẳng định là ông kia hiểu sai đề, theo ý là pick được số đúng xong sẽ lấy luôn hộp, và tôi khẳng định tiếp ngay cả khi hiểu sai đề thì cách tính rate ông kia cũng sai.

Chỗ này thớt hiểu sai rồi, nếu kết thúc loop tức là đã tìm được số rồi, còn phải chọn tiếp làm gì

Đúng rồi, nhưng t đặt ra luôn kẻo mấy ông bảo số lượt còn lại thì mình dùng làm gì

nvtn2006 · 8/8/22

Hiểu đơn giản là có 100 box, mỗi ông được chọn 50 lần tương được là 1/2 tổng số box, thế thì tỉ lệ chọn đúng số mình muốn phải là 50% chứ nhỉ !!!

Chocuaanhne · 8/8/22

jupyter đã nói:
k
pick dc số đúng xong bỏ lại hộp,ông kia hiểu đúng đề
50 ông sau xem rằng cả 50 ông đầu đều thành công cả,vì k xem như thế thì cũng k làm dc gì hơn
nên 50 ông sau cứ thế mà chọn từ hộp 51 -100 thôi,bởi từ 51-100 mà chứa số bé hơn 51 như 40 chẳng hạn thì coi như ông thứ 40 thất bại rồi

Haha vậy thì ông mới không hiểu, cả theo cách bốc ngẫu nhiên hay loop thì cách tính trên đều sai, ngay câu tô đậm trên nó cũng là một câu vô nghĩa không hiểu ông muốn chứng minh cái gì.

baem9999 · 8/8/22

nvtn2006 đã nói:
Hiểu đơn giản là có 100 box, mỗi ông được chọn 50 lần tương được là 1/2 tổng số box, thế thì tỉ lệ chọn đúng số mình muốn phải là 50% chứ nhỉ !!!

Bởi thế tỉ lệ 100 người đều chọn đúng là 50%^100 đúng ko? Tương đương (1/2)^100=0,00...008 (31 số 0) là gần như bằng 0. Nhưng nếu áp dụng cách giải trên lại nâng tỉ lệ lên tận ~31%, nghe qua thì thực là vô lý nhưng lại dựa hoàn toàn trên quy luật toán học đấy.

khaccanh · 8/8/22

jupyter đã nói:
giải ra cụ thể đây
để toàn bộ tù nhân sống sót theo chiến thuật này thì
50 hộp đầu phải chứa từ 1 đến 50:50! cách sắp xếp
50 hộp sau phải chứa từ 51 đến 100:50! cách sắp xếp
xác suất thành công cách này là 50!*50!/100!=a
xác suất thành công nếu bốc bừa là 0.5 mũ 100=b
mà a>b=> cách này tăng xác suất thành công
ok chưa anh
Xem tệp đính kèm 1310195

"
để toàn bộ tù nhân sống sót theo chiến thuật này thì
50 hộp đầu phải chứa từ 1 đến 50:50! cách sắp xếp
50 hộp sau phải chứa từ 51 đến 100:50! cách sắp xếp"
-> cái này sai hoàn toàn nhé
Phản ví dụ là :
hộp 1 chứ số 51, hộp 51 chứa số 1. các hộp còn lại chứ số đúng thứ tự vd : hộp 2 chứa số 2, hộp 52 chua số 52
Trường hợp này thì toàn bộ tù nhân vẫn sống sót. Nhưng 50 hộp đầu vẫn lọt số 51 vô mà

Sonah · 8/8/22

jupyter đã nói:
giải ra cụ thể đây
để toàn bộ tù nhân sống sót theo chiến thuật này thì
50 hộp đầu phải chứa từ 1 đến 50:50! cách sắp xếp
50 hộp sau phải chứa từ 51 đến 100:50! cách sắp xếp
xác suất thành công cách này là 50!*50!/100!=a
xác suất thành công nếu bốc bừa là 0.5 mũ 100=b
mà a>b=> cách này tăng xác suất thành công
ok chưa anh

nói chung cứ xài chiến thuật thì sẽ tăng tỉ lệ so với random dù ít hay nhiều
mà chiến thuật của anh thì tăng tỉ lệ thành công lên ko đáng kể =))

idtent2008 · 8/8/22

Khổ các vozers ghê :doubt:

Xác suất mỗi tù nhân bốc trúng hộp vẫn là 50%.
Nhưng cái loop strategy này biến bài toán từ việc bốc hộp sang việc cách sắp xếp các số trong hộp như thế nào. Và tính ra dc có khoảng gần 31% các số trong hộp tạo vòng lặp nhỏ hơn 51. Và điều đó đồng nghĩa tỷ lệ thoát của tù nhân là 31%.
Các ông đang bị kéo sai hướng vào việc tính xác suất của việc bốc hộp của tù nhân rồi. Hiểu chưa các vozers :boss:

Thechangeisgood · 8/8/22

tính toán nhiều làm lol gì cho mệt đầu, càng tính càng sai. 1 được 2 không. 50-50 nhé

Sonah · 8/8/22

jupyter đã nói:
chiến thuật này là ông @provkl321 nghĩ ra,đáp án ông này đưa ra sai nhưng chiến thuật này rất hay
hiện tại thì chiến thuật của ông này chỉ thua các nhà toán học thôi,còn lại cân hết
chiến thuật này tỉ lệ thành công vẫn rất bé,nhưng vẫn gấp 13 lần so với bốc bừa

chiến thuật càng đơn giản thì càng dễ dụ bọn tù nhân làm theo, cơ mà vẫn khó sống =))

dụ đc 99 thằng theo thì ra tù làm big boss

Orcs · 8/8/22

baem9999 đã nói:
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é.

Như này là tìm đúng số rồi, còn tìm số khác cái qq gì nữa :amazed:

Mỗi số là duy nhất thì làm sao mà trùng

Chocuaanhne · 8/8/22

jupyter đã nói:
giải ra cụ thể đây
để toàn bộ tù nhân sống sót theo chiến thuật này thì
50 hộp đầu phải chứa từ 1 đến 50:50! cách sắp xếp
50 hộp sau phải chứa từ 51 đến 100:50! cách sắp xếp
xác suất thành công cách này là 50!*50!/100!=a
xác suất thành công nếu bốc bừa là 0.5 mũ 100=b
mà a>b=> cách này tăng xác suất thành công
ok chưa anh

nếu được lật 50 lần ho 1 người thì tỉ lệ thành công làm gì 0.5^100 được. chỉ 0.5^50(nếu kết quả ^100 là đúng) thôi vì từ thằng 51 trở đi thì còn max 50 hộp mà được lật 50 lần thì 100% ra đúng hộp...

Uh rồi có ra kết quả trên không.
Không hiểu đọc như nào mà ra được cách trên, và có như ông nói thì 0.5^50 vẫn sai, hay là sai rồi nên log acc clone đá lại??

Chocuaanhne · 8/8/22

jupyter đã nói:
tôi bảo cách của ông này hay,tăng xác suất thành công gấp 13 lần, nhưng kết quả sai ngay từ trên này rồi anh ơi
dc cái chửi đổng là giỏi

Tôi chưa hề đưa ra một câu thái quá lại bị chụp mũ chửi đổng?
Câu anh quote lại tôi đầu tiên vẫn còn "ông kia nói đúng mà" đấy, hay giờ lại chụp mũ tôi bắt bẻ, ok?

Bài toán 100 tù nhân

Cách giải này có thực sự tăng tỉ lệ thành công không?

Có

Không

Senior Member

Đã tốn tiền

Senior Member

Member

Member

Senior Member

Member

Member

Member

Member

Member

Member

Member

Senior Member

Junior Member

Senior Member

Senior Member

Member

Member

Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này