Nhờ mọi người giải hộ bài toán.

[RDSS]

1/ Bổ sung thêm 1 cách giải bài toán 19 viên bi nhiễm phóng xạ :
- 2 lần thử đầu vẫn như cũ, tức là chia 19 viên thành 3 nhóm 8 viên, 8 viên, 3 viên. Test lần lượt với mỗi nhóm 8 viên, quy về trường hợp : 8 viên (đánh dấu 1->8) có viên NPX và 3 viên (9,10,11) chưa biết có NPX không, nhưng nếu có thì chỉ có 1 (không đồng thời).
- Sử dụng cách ký hiệu của bạn tuhiep ở trên, xét T3(1,9,10,11).
+ Nếu kq0 -> còn 7 viên (2,3,4,5,6,7,8) với 5 lần thử -> dễ (chia 3 nhóm, mỗi nhóm 2 viên, thử lần lượt).
+ Nếu kqx -> Xét tiếp T4(9,10).
++ Nếu T4kq0 thì xét T5(11)-> viên 11 hay viên 1 NPX -> còn 3 lần thử với tối đa 8 viên chưa biết (2,3,4,5,6,7,8,(1)), chứa 1 viên NPX -> vừa đủ xác định.
++ Nếu T4kqx -> T5(9) -> xác định được viên 9 hay viên 10 NPX (cũng suy ra viên 11 không NPX), cũng còn 3 lần thử cho 8 viên (1,2,3,4,5,6,7,8) chứa 1 viên NPX -> xác định được.

2/ Cách này rõ ràng, dễ hiểu hơn cách trước. Mấu chốt là nhanh chóng xác định 1 viên bị lỗi trong 3 lần thử 3,4,5 đồng thời loại trừ chỉ còn 8 viên ở 3 lần thử cuối.
Tuy nhiên, tôi vẫn không thể áp dụng được cách giải này cho trường hợp 20 viên. Ví dụ T4(1,9,10,11) có kqx thì dễ, nhưng kq0 thì lại quy về còn 5 lần thử với 8 viên (2,3,4,5,6,7,8,12) có 2 viên NPX, không giải được. Cũng đã thử nhiều cách khác nhưng không được
Bạn Phan Sôna xem lại giúp xem đề bài có chắc chắn đúng không, hoặc bác nào có cách giải thì post lên anh em tham khảo với.

Chào các bạn! Xét 19 viên bi thì cách thử đơn giản nhất là 7, 8, 4
T1-7 đỏ còn 7 lần thử cho 12 viên dễ.
T1-7 xanh, T2-8 viên xanh. Sáu lần thử cho hai nhóm 7 và 8 dễ.
T2-đỏ, T3-4 viên còn lại-đỏ, còn 5 lần thử cho 7 viên dễ.
T3-xanh, còn năm lần thử cho hai nhóm 7 và 4 cũng dễ.

[RDSS]

Còn trường hợp 20 viên thì mình có cách giải rồi. Nhưng bây giờ không có thời gian ghi ra. Nếu mai chưa ai gửi lời giải thì mình sẽ đưa ra.

[Freedom]

Còn trường hợp 20 viên thì mình có cách giải rồi. Nhưng bây giờ không có thời gian ghi ra. Nếu mai chưa ai gửi lời giải thì mình sẽ đưa ra.

Bạn gợi ý vậy mình đã có thể giải được rồi, tiện thể trình bày luôn, bạn kiểm tra giúp nhé.
Chia 20 viên thành 3 nhóm : 7 viên, 8 viên, 5 viên.
-Lần 1: Test nhóm 7 viên. Nếu kết quả đỏ thì còn 7 lần thử cho 13 viên có 2NPX => xác định được. Nếu kết quả xanh thì :
-Lần 2: Test nhóm 8 viên. Nếu kết quả xanh thì có 2 nhóm, nhóm 7 viên và nhóm 8 viên, mỗi nhóm chứa 1 viên NPX, với 6 lần thử => xác định được. Nếu kết quả đỏ, thì suy ra còn 12 viên chia 2 nhóm : Nhóm 7 viên k/h (1,2,3,4,5,6,7) chứa ít nhất 1 viên NPX; Nhóm 5 viên k/h (8,9,10,11,12) chưa biết nhưng nếu có thì chỉ có 1 viên NPX thôi (không đồng thời). Xét tiếp trường hợp này, sử dụng k/h như của bạn tuhiep :
-Lần 3 : Test B3(1,8,9,10).
+ Nếu B3kqx => (1,8,9,10) chứa ít nhất 1 viên NPX. Sử dụng 2 lần thử 4,5 để xác định viên NPX(lần 4 thử nhóm (9,10)). Nếu viên NPX là 1 trong 3 viên 8,9,10 thì viên NPX còn lại thuộc (1,2,3,4,5,6,7), với 3 lần thử -> dễ. Nếu viên NPX là viên 1 thì viên NPX còn lại thuộc (2,3,4,5,6,7,11,12), với 3 lần thử -> vừa đủ để xác định.
+ Nếu B3kq0 => (2,3,4,5,6,7,11,12) chứa 2 viên NPX, với 5 lần thử. Xét tiếp lần thử 4.
-Lần 4, Test B4(2,3).
+ Nếu B4kqx => lần thử 5 xác định viên 2 hay viên 3 NPX, còn 3 lần thử với 7 viên chứa 1 viên NPX => dễ.
+ Nếu B4kq0 => Xét tiếp lần 5.
-Lần 5, Test B5(11,12).
+ Nếu B5kqx => Lần thử 6 xác định viên 11 hay viên 12 NPX, vì 2 viên này không thể NPX đồng thời nên viên kia cũng chắc chắn là không NPX. Còn 2 lần thử cuối với 4 viên (4,5,6,7) chứa 1 viên NPX -> dễ.
+ Nếu B5kq0 => Còn 4 viên (4,5,6,7) với 3 lần thử => dễ.
------------------------------------------------------------
Hóa ra mấu chốt của bài toán lại nằm ở sự phân bố nhóm ở lần thử đầu. Do xu hướng thường nghĩ đến tính đối xứng nên trong đầu mình cứ mặc định chia nó là 8,8,4 dẫn đến bế tắc. Đúng là lối mòn trong tư duy thật nguy hiểm.
Cảm ơn bạn nhiều!

[tuhiep]

bạn freedom giải chuẩn rồi. Mình cũng như bạn sai lầm khi tách nhóm đầu tiên không phải 7. cám ơn các bạn hiền ./.

[kien1706]

Vấn đề để giải quyết bài toán là lúc đầu sẽ có tổ hợp chập 2 của 20 phần tử có khả năng là đáp an của bài toán( nếu đánh số các bi là 1,2,....,20 thì các cặp có thể là đán án là (1,2),(1,3),....,(1,20),(2,3),(2,4),....(2,20),...(14,15))
và số này bằng 190 trong khi ta có 8 lần thử . điều kiện cần để có thể giải dc bài toán là 2^8> 190 thỏa mãn). Với lần thử đầu tiên dù kết quả là NPX hay không thì cả hai trường hợp ta phải giảm số cặp có thể là đáp án xuống không quá 2^7=128 vì ta còn 7 lần thử).tiếp tục sau lần thử thứ 2 dù kết quả thế nào ta cũng phải giảm số khả năng xuống < 2^6). Và cứ như thế đến lần cuối cùng ta có thể hoàn thành bài toán.với cách chia 8 8 4 vẫn giải được nhưng sẽ phức tạp hơn

[tuhiep]

lí luận là thế. nhưng chia 8 8 4 thì lần thử 4 không tìm được phương án để giảm số khả năng < 2^4 thì làm sao?

[RDSS]

lí luận là thế. nhưng chia 8 8 4 thì lần thử 4 không tìm được phương án để giảm số khả năng < 2^4 thì làm sao?

Chào bạn TuHiep! Bạn Kien 1706 nói đó là điều kiện cần rất đúng, nhưng bạn ấy không thêm rằng chưa phải là điều kiện cần và đủ( theo tôi như vậy chính xác hơn ). Nếu số phương án lớn hơn 2^k thì khỏi giải( vứt luôn vào sọt rác ), ít hơn có thể giải được nhưng cũng có thể không. Ví dụ 16 bi chỉ có 120 phương án, nhưng với 7 lần kiểm( 2^7=128>120 )không giải được. Còn chia 8, 8,4 cũng giải được đấy bạn. Lần thử ba không thử 1, 2, 9, 10( 33 phương án>2^5=32 ) như bạn mà thử 1, 2, 3 là ra thôi.

[Freedom]

Chào bạn TuHiep! Bạn Kien 1706 nói đó là điều kiện cần rất đúng, nhưng bạn ấy không thêm rằng chưa phải là điều kiện cần và đủ( theo tôi như vậy chính xác hơn ). Nếu số phương án lớn hơn 2^k thì khỏi giải( vứt luôn vào sọt rác ), ít hơn có thể giải được nhưng cũng có thể không. Ví dụ 16 bi chỉ có 120 phương án, nhưng với 7 lần kiểm( 2^7=128>120 )không giải được. Còn chia 8, 8,4 cũng giải được đấy bạn. Lần thử ba không thử 1, 2, 9, 10( 33 phương án>2^5=32 ) như bạn mà thử 1, 2, 3 là ra thôi.

Mình không hiểu lắm về lần thử thứ 3 với nhóm (1,2,3) của bạn. Giả sử kết quả là xanh => trong nhóm này chứa ít nhất 1 viên NPX, và nhóm còn lại có 9 viên (4,5,6,7,8,9,10,11,12). Cũng giả sử nếu biết luôn nhóm (1,2,3) chỉ chứa 1 viên NPX thôi thì theo mình để xác định được viên NPX này cũng cần 2 lần thử (>1), và nhóm (4,5,6,7,8,9,10,11,12) cũng cần 4 lần thử (vì 2^3 < 9). Trong khi đó chỉ còn có 5 lần thử, không biết bạn dùng mẹo nào để xác định được 2 viên NPX ?.
Rất mong sự phân tích kỹ hơn của bạn,
Tks,

[RDSS]

Bạn gợi ý vậy mình đã có thể giải được rồi, tiện thể trình bày luôn, bạn kiểm tra giúp nhé.
Chia 20 viên thành 3 nhóm : 7 viên, 8 viên, 5 viên.
-Lần 1: Test nhóm 7 viên. Nếu kết quả đỏ thì còn 7 lần thử cho 13 viên có 2NPX => xác định được. Nếu kết quả xanh thì :
-Lần 2: Test nhóm 8 viên. Nếu kết quả xanh thì có 2 nhóm, nhóm 7 viên và nhóm 8 viên, mỗi nhóm chứa 1 viên NPX, với 6 lần thử => xác định được. Nếu kết quả đỏ, thì suy ra còn 12 viên chia 2 nhóm : Nhóm 7 viên k/h (1,2,3,4,5,6,7) chứa ít nhất 1 viên NPX; Nhóm 5 viên k/h (8,9,10,11,12) chưa biết nhưng nếu có thì chỉ có 1 viên NPX thôi (không đồng thời). Xét tiếp trường hợp này, sử dụng k/h như của bạn tuhiep :
-Lần 3 : Test B3(1,8,9,10).
+ Nếu B3kqx => (1,8,9,10) chứa ít nhất 1 viên NPX. Sử dụng 2 lần thử 4,5 để xác định viên NPX(lần 4 thử nhóm (9,10)). Nếu viên NPX là 1 trong 3 viên 8,9,10 thì viên NPX còn lại thuộc (1,2,3,4,5,6,7), với 3 lần thử -> dễ. Nếu viên NPX là viên 1 thì viên NPX còn lại thuộc (2,3,4,5,6,7,11,12), với 3 lần thử -> vừa đủ để xác định.
+ Nếu B3kq0 => (2,3,4,5,6,7,11,12) chứa 2 viên NPX, với 5 lần thử. Xét tiếp lần thử 4.
-Lần 4, Test B4(2,3).
+ Nếu B4kqx => lần thử 5 xác định viên 2 hay viên 3 NPX, còn 3 lần thử với 7 viên chứa 1 viên NPX => dễ.
+ Nếu B4kq0 => Xét tiếp lần 5.
-Lần 5, Test B5(11,12).
+ Nếu B5kqx => Lần thử 6 xác định viên 11 hay viên 12 NPX, vì 2 viên này không thể NPX đồng thời nên viên kia cũng chắc chắn là không NPX. Còn 2 lần thử cuối với 4 viên (4,5,6,7) chứa 1 viên NPX -> dễ.
+ Nếu B5kq0 => Còn 4 viên (4,5,6,7) với 3 lần thử => dễ.
------------------------------------------------------------
Hóa ra mấu chốt của bài toán lại nằm ở sự phân bố nhóm ở lần thử đầu. Do xu hướng thường nghĩ đến tính đối xứng nên trong đầu mình cứ mặc định chia nó là 8,8,4 dẫn đến bế tắc. Đúng là lối mòn trong tư duy thật nguy hiểm.
Cảm ơn bạn nhiều!

Không thêm không bớt được gì. Bravo!!!

[RDSS]

Số lượng nhiều nhất cho 8 lần thử là 22 viên bi. Mời các bạn giải, nếu còn hứng thú.