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

[tuhiep]

gởi ThanhLongBien
"Cụ thể hơn, với Bài toán đầu tiên (b=2, N=100), chúng ta đã chỉ ra rằng, với dãy số H(2,14), chúng ta chỉ cần 14 lần thử bi là biết dc tầng cần tìm. Tuy vậy, chúng ta chưa chứng minh dc số lần thử =14 là con số nhỏ nhất trong tất cả các phương án thử có thể!!!
Chúng ta sẽ cùng nhau đi tiếp vấn đề này nhé! "
mình dùng qui nạp chứng minh bảng "H" đúng với k nhỏ nhất trong cách thử bi với N tầng đó chứ.

mình trình bày sơ lại nhé.Gốc số 1 hàng b=1 và cột k=1 là tuyệt đối đúng; b=1 và N=1 thì k=1 là hiển nhiên.
cột k=1, cũng quá đúng; vì b nhiều cũng vô ích, vì N=1 chỉ cần k=1 là xong.
dòng b=1, vẫn đúng với N=S(1.k)với k=N,có bao nhiêu tầng cần bấy nhiêu lần thử. vì chọn k<N thì không thử hết được(gọi k=N là đúng cho tiện,nghĩa là k<>N là thừa hoặc thiếu).
H(b+1,k+1)=H(b+1,k)+H(b,k)=>H(b+1,k+1)=S(b,k)+1 ......(1)
và chọn N(max)=S(b,k) là cách phải chọn để k đúng (theo ý trên) mà mình phải chứng minh.

Mình dùng qui nạp chứng minh bảng mình đúng; và chọn N(max)=S(b,k) là cách chọn k đúng như sau.
Ta có N tầng và b bi, chọn tầng x thử lần 1. Chỉ có 2 tình huống xãy ra: bi vở hoặc bi không vở.
bi vở: ta còn (x-1)tầng phải thử với (b-1)bi.nên (x-1)=S(b-1,k-1).
bi không vở N-x=S(b,k-1).
vậy N=S(b,k-1)+S(b-1,k-1)+1
=> N=S(b,k-1)+H(b,k)=S(b,k)=H(b+1,k+1)-1.
vậy chọn k đúng.
Mình chứng minh bảng "H" đúng là ý nầy đấy.