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

[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?

[tuhiep]

mình đưa ra 1 thí dụ cơ bản. chập 2 của 8 phần tử. số khả năng đáp án là 28<2^5 thoả yêu cầu. Vậy bạn giải thử xem.

[tuhiep]

hay dể hơn là 2 chập 6, điều kiện 15< 2^4 thoả. vậy 4 lần thử bạn tìm thử xem. nếu bạn giải được bài trên hay bài nầy, thì test 8 lần chọn 2 trong 20 là quá dể.

[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ú.

[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.