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

[ThanhLongBin]

Bác nói Bác TuHiep đưa ra algorithm rồi mà sao em tìm mãi vẫn không thấy nhỉ?

Để tôi giúp bác Tư trình bày lại nhé.

Bài toán: Cho b viên bi hoàn toàn giống nhau và tòa nhà cao N tầng. Có thể thả bi từ tầng bấy kỳ 1,2,...N để xem bi có vỡ hay ko. Sau khi thả, nếu bi ko bị vỡ thì có thể dùng lại như mới! Hãy tìm cách thả bi, với số lần thả ít nhất đối với mọi trường hợp, để xác định chính xác bắt đầu từ tầng nào, bi chắc chắn sẽ bị vỡ!

Lời giải của bác Tư gồm 2 phần:
- Phần 1: Mô hình lý thuyết "Dãy số Tuhiep H(b,k)"
- Phần 2: Áp dụng Dãy số H(b,k) để giải Bài toán.
******************************
PHẦN 1:TUHIEP THEORY
Dãy số tự nhiên H(b,k) được gọi là "Dãy số Tuhiep" nếu thỏa mãn 3 điều kiện sau:
H(1,k)=1 với mọi k (1)
H(b,1)= 1 với mọi b (2)
Với b,k >=1 bất kỳ
H(b+1,k+1)= H(b+1,k) +H(b,k) (3).

Tính chất của Dãy H(b,k):

Lemma 1: (Bác Tư đã giải quyết rồi)
Gọi S(b,k)= Tổng (H(b,n); n=1..k).
Hãy chứng minh quan hệ:
H(b+1,k+1)-1= S(b,k) (4)

Lemma 2: (Hầu như ko phải CM gì }
Gọi H_set = { Tập hợp các dãy số (phức) thỏa mãn điều kiện (3) }
CMR: H_set có tính chất sau:
Với mọi P,Q là 2 phần tử của H_set, và alfa, beta là 2 số (phức) bất kỳ, phẩn tử sau:
R= alfa*P +beta*Q cũng thuộc H_set.

Lemma 3: {Dành cho các bạn làm tiếp)
Hãy mô tả công thức tổng quát của H_set từ đó suy ra trường hợp đặc biệt của H(b,k) khi thỏa mãn điều kiện (1) và (2)



PHẦN 2: ÁP DỤNG LÝ THUYẾT
A. Thuật toán thả bi
Gọi x_x là tầng, từ đó trở lên, bi sẽ vỡ.
1<=x_x <=N.
Với cặp (b,N) cho trước, luôn tồn tại và duy nhất 1 số tự nhiên k thỏa mãn điều kiện:
S(b,k-1) < N <= S(b,k). (5)
Ta sẽ CMR, chỉ cần k lần thử là tìm ra dc x_x trong mọi trường hợp.
Bước 1:
Sau khi có số k trên, ta xây dựng dãy số x(i) có k phần tử như sau:
x(1)= H(b,k);
x(2)= x(1)+ H(b,k-1);
....
x(n)= x(n-1) + H(b,k-n+1); (6)
......
x(k)= x(k-1)+ H(b,1);
Thả bi #1 lần lượt tại các tầng ứng với x(i), i=1..k cho đến khi bi vỡ ở lần thả thứ m <=k nào đó.
Tầng cần tìm, x_x phải nằm trong khu vực này:
x(m-1) < x_x <= x(m).
Bước 2:
Ta đã thả bi mất m lần, còn lại (b-1) bi và số tầng cần tìm là N_new = x(m)- x(m-1)-1;
Từ (6) => N_new = H(b, k-m+1)-1
(4) => N_new = S(b-1,k-m).
Lặp lại Bước 1 ko quá b_new lần, với số b_new= b-1,N_new = S(b-1,k-m)=> k_new= k-m, ta sẽ tìm thấy x_x sau k-m lần thử trong trường hợp xấu nhất.
Tóm lại, với cách thả bi như trên, ta sẽ mất m+ k-m =k lần thử.

B. Chứng minh k là nhỏ nhất. (Bác Tư đã làm quá tốt rồi, ko cần viết lại nhé!)