Câu đố góp vui

Câu này có thể nhiều bạn biết rồi nhưng mình vẫn đăng vì nó là gợi ý để giải câu chính.
Có một nhà vua có 500 thùng rượu, trong đó có một thùng rượu có độc. Ai uống rượu độc bất kể liều lượng bao nhiêu thì sau 24h sẽ lăn ra chết mà trước đó hoàn toàn không có biểu hiện gì. Nhà vua muốn tìm ra bình rươu độc đó trong 24h. Ông có một số tù nhân bị xử tử hình và ông muốn dùng họ vào việc thử rượu. Cần ít nhất bao nhiêu tù nhân để thử và làm như thế nào?
Câu hỏi chính: cần bao nhiêu người nếu thời gian để thử là 48h (thời gian cho tù nhân uống thử không đáng kể)
cần bao nhiêu người nếu thời gian để thử là 48h và thời gian phát độc là 23-24h

6 con :v Max 729 =))

aiemdao đã viết:6 con :v Max 729 =))

Đấy là khi thời gian phát độc là 24h, còn nếu thời gian là 23-24h thì sao?

Oggy121 đã viết:

aiemdao đã viết:6 con :v Max 729 =))

Đấy là khi thời gian phát độc là 24h, còn nếu thời gian là 23-24h thì sao?

Là nó mà :v 48h => max là 2 lần thử :v Cái này là 1 trong đề của event ZEX ( do t ra ) mà :v Max 3^n :v

aiemdao đã viết:

Oggy121 đã viết:

aiemdao đã viết:6 con :v Max 729 =))

Đấy là khi thời gian phát độc là 24h, còn nếu thời gian là 23-24h thì sao?

Là nó mà :v 48h => max là 2 lần thử :v Cái này là 1 trong đề của event ZEX ( do t ra ) mà :v Max 3^n  :v

3^n chỉ tối ưu khi thời gian phát độc chính xác là 24h thôi, còn nếu thời gian phát độc là 23-24h thì chỉ cần 2 người

Oggy121 đã viết:

aiemdao đã viết:

Oggy121 đã viết:

aiemdao đã viết:6 con :v Max 729 =))

Đấy là khi thời gian phát độc là 24h, còn nếu thời gian là 23-24h thì sao?

Là nó mà :v 48h => max là 2 lần thử :v Cái này là 1 trong đề của event ZEX ( do t ra ) mà :v Max 3^n  :v

3^n chỉ tối ưu khi thời gian phát độc chính xác là 24h thôi, còn nếu thời gian phát độc là 23-24h thì chỉ cần 2 người

Đâu thế được :v
Ví dụ có 1 người đi 24 h chỉ thử được có 1 lần :v tức là 2 bình ;v sao là 3^n được :v

3^n là phát độc tối ưu sau 48H :v sau 24h chỉ có 2^n thôi

Đề bài có 3 câu như thế này nhé:
câu 1: uống rượu độc xong thì chính xác là 24h sau sẽ chết luôn và chỉ có 24h để thử. Câu này nổi tiếng rồi
câu 2: uống rượu độc xong thì chính xác là 24h sau sẽ chết luôn và có 48h để thử. Câu này bạn giải rồi, cần 6 người
câu 3: uống rượu độc xong thì người đó sẽ chết trong thời gian t (23<t<24) và có 48h để thử, trường hợp này chỉ cần 2 người.
Uống xong thì tù nhân đâu có chết ngay đâu, có thể cho nó uống tiếp nên vẫn thử được mà

Oggy121 đã viết:Đề bài có 3 câu như thế này nhé:
câu 1: uống rượu độc xong thì chính xác là 24h sau sẽ chết luôn và chỉ có 24h để thử. Câu này nổi tiếng rồi
câu 2: uống rượu độc xong thì chính xác là 24h sau sẽ chết luôn và có 48h để thử. Câu này bạn giải rồi, cần 6 người
câu 3: uống rượu độc xong thì người đó sẽ chết trong thời gian t (23<t<24) và có 48h để thử, trường hợp này chỉ cần 2 người.
Uống xong thì tù nhân đâu có chết ngay đâu, có thể cho nó uống tiếp nên vẫn thử được mà

à uhm :3 nhưng đó mẹo kiểu vậy thì câu 2 t cũng sai rồi :3

Chỉ cần 1 thằng, thử bao nhiêu bình cũng được vì chỉ cần uống liên tục :v rồi đo thời gian đế khi nó chết là dc :v

aiemdao đã viết:

Oggy121 đã viết:Đề bài có 3 câu như thế này nhé:
câu 1: uống rượu độc xong thì chính xác là 24h sau sẽ chết luôn và chỉ có 24h để thử. Câu này nổi tiếng rồi
câu 2: uống rượu độc xong thì chính xác là 24h sau sẽ chết luôn và có 48h để thử. Câu này bạn giải rồi, cần 6 người
câu 3: uống rượu độc xong thì người đó sẽ chết trong thời gian t (23<t<24) và có 48h để thử, trường hợp này chỉ cần 2 người.
Uống xong thì tù nhân đâu có chết ngay đâu, có thể cho nó uống tiếp nên vẫn thử được mà

à uhm :3 nhưng đó mẹo kiểu vậy thì câu 2 t cũng sai rồi :3

Chỉ cần 1 thằng, thử bao nhiêu bình cũng được vì chỉ cần uống liên tục :v rồi đo thời gian đế khi nó chết là dc :v

Câu 2 phải là uống vào chết luôn thì mới ra kết quả là 6 còn câu 3 thì cần ít nhất 2 người vì thời gian phát độc trong khoảng 23-24h nên mỗi lần thử phải cách nhau 1h

Rốt cục chỉ 2 người hiểu. Một người ra đề, một người đã từng ra đề :3
Đọc bình luận thì mình hiểu cơ chế hình như là dùng một tù nhân xác định được tối đa bao nhiêu bình trong thời gian cho phép (n bình) thì ứng với m tù nhân số bình tối đa thử được là n^m
Nhưng chưa hiểu cơ sở để ra được công thức n^m đó @@ các cao nhân khai sáng giúp với

anbinh0212 đã viết:Rốt cục chỉ 2 người hiểu. Một người ra đề, một người đã từng ra đề :3
Đọc bình luận thì mình hiểu cơ chế hình như là dùng một tù nhân xác định được tối đa bao nhiêu bình trong thời gian cho phép (n bình) thì ứng với m tù nhân số bình tối đa thử được là n^m
Nhưng chưa hiểu cơ sở để ra được công thức n^m đó @@ các cao nhân khai sáng giúp với

Để mình giải thích cho bạn nhé:

Câu 1: câu này thì thời gian phát độc là 0h (chết ngay) hay 24h cũng như nhau vì bạn chỉ có 24h để thử
chọn 9 tù nhân đánh số a0, a1, a2, a3,..., a8. Các bình rượu đánh số từ 1 đến 500. Với mỗi bình bạn cho tù nhân thử bằng cách sau:
Đổi số thứ tự của bình ra tổng các lũy thừa của 2 (cách đổi này là duy nhất, là cách đổi số từ thập phân ra nhị phân), VD: 69=2^6 + 2^2 + 2^0 (tương ứng với 1000101 trong hệ nhị phân). Cho người này uống các bình có số thứ tự tương ứng với số mũ trong cách đổi trên, VD người thứ 69 uống bình a0, a2, a6.
Sau khi phát độc thì bạn có thể biết chính xác là bình nào chứa độc vì cách đổi số từ thập phân sang nhị phân là duy nhất và ngược lại. VD: tù nhân a2, a3, a8 trúng độc thì bình thứ 2^2 + 2^3 + 2^8 = 268 trúng độc.

Câu 2: nếu thời gian phát độc chính xác là 24h thì bạn chỉ cần 1 người thôi, đơn giản là cứ cách mỗi phút (cái này chỉ cần sao cho nó uống hết mà không quá 48h là được) cho nó uống 1 bình, đến khi nào nó chết thì truy ra được thời gian nó uống từ đó suy ra bình nào trúng độc
Nếu thời gian phát độc không biết rõ (0<t<24h, uống vào chết luôn hoặc mai mới chết) thì chúng ta cần giải tương tự câu 1 nhưng bây giờ sẽ là hệ tam phân thay vì nhị phân do bạn có 3 lựa chọn: chết trong ngày đầu, chết trong ngày 2 và không chết
Đánh số tù nhân là a0, a1, a2, a3, a4, a5. Các thùng rượu vẫn đánh số từ 1 đến 500. Với bất kì thùng nào thì số thứ tự của nó đều có thể biểu diễn thành n0 + 3n1 + 9n2 + 27n3 + 81n4 + 243n5 (n(i)=0;1;2)
Vào thời điểm bắt đầu thử, t=0 cho tù nhân a(i) uống tất cả các thùng mà n(i)=0. VD tù nhân a0 sẽ uống tất cả các thùng đánh số bằng 3n1 + 9n2 + 27n3 + 81n4 + 243n5 (n(i)=0;1;2). Mỗi người sẽ uống hỗn hợp của 3^5 - 1 thùng (vì không có thùng số 0)
Sau 24h, cho tất cả những ai còn sống uống các thùng mà n(i)=1
Bây giờ ta cho a(i) = 0 nếu người đó chết trong 24h đầu tiên, a(i) = 1 nếu người đó chết trong 24h tiếp theo và a(i) = 2 nếu người đó còn sống. Ta sẽ được thùng thứ a0 + 3a1 + 9a2 + 27a3 + 81a4 + 243a5 trúng độc. VD: người a0, a3 chết trong 24h đàu tiên, người  a1, a2, a5 chết trong 24h tiếp theo và người a4 còn sống thì thùng thứ 417 trúng độc.

Câu 3: Thời gian phát độc là 23-24h (23<t<24) thì ta chỉ cần 2 người.
Đánh số 2 người này là i, j. Đánh số các thùng là (i;j) như kiểu tọa độ với 0<i, j<24.
Vào t=0 cho người i uống các thùng mà i=0 tức là thùng (0;1), (0;2),.. người j uống các thùng mà j=0
1h sau thì người i uống các thùng mà i=1, j uống các thùng j=1
...
đến đây ta có thể biết được thùng nào trúng độc bằng cách suy ngược thời gian (kết quả là duy nhất vì thời gian phát độc ngắn nhất và lâu nhất cách nhau 1h còn mỗi phép thử cũng cách nhau 1h). Thời gian chết của 2 người sẽ rơi vào khoảng 24-48h. VD: người i chết vào lúc 28h còn người j chết vào lúc 36h thì thùng (4;12) trúng độc.

Giải thích cơ sở của các cách giải: nếu thời gian phát độc lớn luôn lớn hơn 0 như trong câu 3 ta có thể dùng 1 người thử nhiều lần. Còn nếu thời gian trúng độc có thể bằng 0 thì mỗi người chỉ thử được 1 lần mà thôi (câu 2). Dù thế nào đi chăng nữa thì mỗi lần thử phải cách nhau bằng khoảng chênh lệch giữa thời gian trúng độc (ở câu 3 là 1h, câu 2 là 24h) để xác định được xem nạn nhân chết trong bao lâu. Ngoài ra nếu tổng thời gian thử lớn hơn thời gian phát độc tối đa thì ta có thể đưa ra nhiều lần thử (câu 1 là 1 lần, câu 2 là 2 lần và câu 3 là 25 lần)

Công thức tổng quát cho các bạn:

log⁡N/(log⁡(1+(T-t_0)/t)

Với N là số thùng cần thử, T là thời gian để thử (câu 1 là 24h, câu 2,3 là 48h), t0 + t là thời gian phát độc. Trường hợp mà thời gian phát độc là chính xác và lớn hơn 0 thì ta chỉ cần 1 người thôi.

Vậy câu 3 làm kiểu tổng quát như 2 câu đầu thì là hệ "25 phân" nhỉ? dạng n0+25n1

===Ý đầu có thể giải đơn giản kiểu này
tối đa mỗi người chỉ được uống 1 lần => Mỗi người sẽ uống 1 nhóm các thùng rượu để có theer phaan biệt được thùng rượu nào gây độc

Ví dụ: người 1 uống thùng 1 và 2 cùng lúc, người 2 uống cùng 2 và 3 cùng lúc. Nếu cả 2 cùng chết thì thùng 2 có độc, người 1 sống người 2 chết thì thùng 3 có độc, người 1 chết người 2 sống thì thùng 1 có độc

Tối đa hóa phương pháp này: Nếu có N người, để N người này uống các nhóm thùng sao cho thỏa mãn điều kiện:

Để 1 thùng tất cả cùng uống => Nếu tất cả cùng chết thì thùng này có độc

Chia N người thành các nhóm (N-1) người, => Có NC(N-1) nhóm , mỗi nhóm này cùng uống 1 thùng khác => Nếu có trường hợp cả nhóm chết, người còn lại sống thì thùng cả nhóm uống có độc

Chia N người thành các nhóm (N-2) , mỗi nhóm này lại cùng uống 1 thùng khác

.v.v.v.

Cuối cùng để 1 thùng không ai uống cả => Nếu k ai chết thì thùng này có độc

Vậy tổng cộng là
1 + NC(N-1) + NC(N-2) + ... + NC1 + 1 = 2^N

2 ý dùng thời gian thì k dùng tổ hợp vì uống liên tục chủ yếu dựa vào thời gian chết
Ý 3 = ý mỗi người được thử tối đa 2 lần cũng giải bằng tổ hợp cho dễ hiểu

Qui nạp từ cái uống 1 lần bên trên
Với mỗi nhóm X người uống 1 lượng Y thùng thì những người còn lại = (N-X) phải đủ để thử hết Y chai
=> Y = 2^(N-X)
=> Chọn ra X người, có NCX nhóm, mỗi nhóm sẽ tìm trong 2^(N-X) thùng

=> Lấy tổng X chạy từ 0 đến N => N người tìm được trong tối đa 3^N