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

[ThanhLongBin]

Bổ đề "Min of Max" !!!!
Để giải quyết triệt để Bài toán "Thử bi" ta sẽ chứng minh Phương pháp "Dãy số H(b,k) " của bác Tuhiep (Tạm gọi là H-selection !) luôn cho số lần thử là nhỏ nhất và bằng chính k!
Trước hết , mời các bác chứng minh hộ Bổ đề "Min of Max" dc mô tả như sau:
Cho trước m số tự nhiên Q={q1,q2,..qm} xếp trong m ô dc đánh số i=1...m.
Với mỗi hoán vị bất kỳ P={p1,p2..pm} của Q, ta tìm số sau:
Val(P)= max of {i+pi); với i=1...m.
CMR: Khi Val(P) đạt giá trị nhỏ nhất trong các khả năng có thể thì :
p1>=p2>=p3>=...>=pm

Tức là, điều kiện min của Val(P) xảy ra khi hoán vị {pi} là một dãy số giảm dần!

Các bác có thể dùng phép phản chứng, giả thiết rằng tìm dc 1 hoán vị P={p(i),i=1...m} nào có Val(P) là nhỏ nhất nhưng không thỏa mãn điều kiện , tức là tồn tại 1 vị trí thứ j nào đó, ở đó p(j)<p(j+1) thì ta sẽ tìm dc 1 hoán vị khác P' có Val(P')< Val(P)!
Xin mời hai bác xuất chiêu!