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

[ThanhLongBin]

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.

Tôi thấy cách bác làm như vậy là thiếu chặt chẽ.
Ta có đầu vào là số bi=b, số tầng =N.
Bác có thể cố định số N và quy nạp theo b, tức là cho b chạy. Khi đó, số k là một con số hoàn toàn xác định theo cặp số (b,N) thỏa mãn điều kiện:
S(b,k-1) < N <=S(b,k); với S(b,k) theo công thức đã biết.
Như vậy, k =k(b,N) là một hàm của 2 biến b,N
Theo phương pháp Quy nạp, bác phải làm 3 bước:
1. Kiểm tra với b=1,2... Số giá trị cụ thể của b cần kiểm tra phụ thuộc vào phương pháp chứng minh ở Bước#3 sau này.
2. Giả thiết rằng "Điều phải chứng minh" đã đúng với mọi giá trị b <= B bất kỳ!
3. Cần phải CM rằng, "Điều phải chứng minh" cũng đúng với b=B+1 dựa trên giả thiết trên.
Trong cách làm của bác, số N tự nhiên lại bị "trói" bằng những giá trị dạng N=S(b,k), trong khi đó, ta phải CM với N bất kỳ cơ mà!
Tiếp nữa, khi N cố định, b tăng 1 đơn vị ,tức là b=B+1, thì k(b,N) cũng thay đổi và khá phức tạp đấy!