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

[RDSS]

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!

Bài toán của Bác nhìn qua thấy khó quá. Chắc là toán cao cấp rồi và có lẽ phải tìm sách toán đọc lại. Còn bản thân dãy số S(b,k) là chứng minh rồi chứ Bác.Chỉ cần tìm algorithm cho lần ném đầu là xong.Còn công thức của dãy số có lẽ không rút gọn được thì phải.