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

[RDSS]

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ỉ?

[tuhiep]

gởi ThanhLongBien
"Chào bác RDSS và bác Tuhiep,
Tôi năm nay cùng được Trời cho 54 tuổi, tức là kém bác Tư vài năm, hơn bác RD dăm tuổi."

câu bạn nói rất thông thường, nhưng với mình đó là câu nói lên: bạn có nhiều may mắn trời ban.
những ai cùng tuổi mình, hay lớn hơn mình năm ba tuổi sẽ phải chứng kiến cảnh tang thương của nước Việt. Sẽ phải chứa trong tim nhiều đau buồn, những đau buồn nhìn bằng mắt, nghe bằng tai, cảm nhận bằng tim óc.
ở tuổi 18 mình lần lượt dự đám ma cho gần 30 bạn học, cho vài mươi bạn trong xóm. Ở tuổi 22 mình nhìn cái đói giết hại lối xóm cả người, hay nhân cách.
sau đó vài năm, lại nhìn xác người lần lượt tấp vào bờ vì nạn vượt biên. nếu các bạn sống nơi hẻo lánh như mình sẽ chứng kiến cảnh giết người cướp của, của bọn côn đồ.
khoãng 15 năm trở lại đây, đất nước vươn lên từng ngày, có thể những người trẽ còn thấy nhiều điều chưa tốt, nhiều điều còn gây bức xúc;
nhưng mình phải chấp tay cảm ơn thượng đế. Hi vọng những người trẽ hôm nay và mãi mãi sau nầy được sống tốt đẹp hơn.

[ThanhLongBin]

gởi ThanhLongBien
"Chào bác RDSS và bác Tuhiep,
Tôi năm nay cùng được Trời cho 54 tuổi, tức là kém bác Tư vài năm, hơn bác RD dăm tuổi."

câu bạn nói rất thông thường, nhưng với mình đó là câu nói lên: bạn có nhiều may mắn trời ban.
những ai cùng tuổi mình, hay lớn hơn mình năm ba tuổi sẽ phải chứng kiến cảnh tang thương của nước Việt. Sẽ phải chứa trong tim nhiều đau buồn, những đau buồn nhìn bằng mắt, nghe bằng tai, cảm nhận bằng tim óc.
ở tuổi 18 mình lần lượt dự đám ma cho gần 30 bạn học, cho vài mươi bạn trong xóm. Ở tuổi 22 mình nhìn cái đói giết hại lối xóm cả người, hay nhân cách.
sau đó vài năm, lại nhìn xác người lần lượt tấp vào bờ vì nạn vượt biên. nếu các bạn sống nơi hẻo lánh như mình sẽ chứng kiến cảnh giết người cướp của, của bọn côn đồ.
khoãng 15 năm trở lại đây, đất nước vươn lên từng ngày, có thể những người trẽ còn thấy nhiều điều chưa tốt, nhiều điều còn gây bức xúc;
nhưng mình phải chấp tay cảm ơn thượng đế. Hi vọng những người trẽ hôm nay và mãi mãi sau nầy được sống tốt đẹp hơn.

Bác hoàn toàn hiểu ý em khi nhấn mạnh : "bạn có nhiều may mắn trời ban".
Hồi những năm 65-72, nhà em ở ngôi làng nhỏ, ngoại thành Hà nội. Xui xẻo là cạnh đó có cái Đài phát thanh Đông dương là mục tiêu của các trận không kích... Trung bình, mỗi nhà nhận dc vài quả bom to nhỏ, chẳng nhà nào còn nguyên cả. Sau cơn mưa, hố bom ngập nước, nổi lên vài cái mũ rơm...Em khi ấy có 6 tuổi thôi...
Bọn trẻ con phải chạy đi sơ tán, còn bố mẹ vẫn ở lại nhà, vẫn cấy lúa, trồng khoai...
Trại sơ tán ở gần biên giới TQ. Mọi tuyến đường bộ, đường sắt lên đó đều bị bom đánh hỏng. Lương thực dc ngựa thồ từ TQ sang chủ yếu là ngô (bắp) răng-ngựa và đá muối. Người lớn thì phải đi làm, còn trẻ con thì sáng đi học chiều về giã ngô. Cái giống ngô-răng-ngựa này to như răng con ngựa và rắn như đá! Giã ngô từ trưa đến chiều thì đủ ăn cho bữa tối và sáng ngày mai. Muối mỏ là loại muối người TQ khai thác từ hầm mỏ trên núi ra ở dạng các cục to cỡ 20x30 cm. Khi dùng phải lấy búa mới đập ra dc và sau lấy đá ráp, đổ nước vào để mài lấy nước muối... Ăn cái muối này nó lợ lợ, hơi mặn, hơi chát...vì thành phần của nó chủ yếu là MgCL, CaCL và có một ít NaCL...Bọn em ko bị chết đói, chỉ bị suy dinh dưỡng và còi xương thôi...Ấy chẳng là phước Trời ban thì là gì?

Chẳng ai so đo nỗi bất hạnh cả, nhưng em cảm thấy, em vẫn may mắn hơn bác vì không phải chứng kiến người Việt mình sát hại lẫn nhau.
Em cũng như bác, cầu mong cho các thế hệ trẻ sau này, đừng bao giờ phải trải qua những cảnh đau lòng ngày ấy.
Kính bác.

[RDSS]

gởi ThanhLongBien
"Chào bác RDSS và bác Tuhiep,
Tôi năm nay cùng được Trời cho 54 tuổi, tức là kém bác Tư vài năm, hơn bác RD dăm tuổi."

câu bạn nói rất thông thường, nhưng với mình đó là câu nói lên: bạn có nhiều may mắn trời ban.
những ai cùng tuổi mình, hay lớn hơn mình năm ba tuổi sẽ phải chứng kiến cảnh tang thương của nước Việt. Sẽ phải chứa trong tim nhiều đau buồn, những đau buồn nhìn bằng mắt, nghe bằng tai, cảm nhận bằng tim óc.
ở tuổi 18 mình lần lượt dự đám ma cho gần 30 bạn học, cho vài mươi bạn trong xóm. Ở tuổi 22 mình nhìn cái đói giết hại lối xóm cả người, hay nhân cách.
sau đó vài năm, lại nhìn xác người lần lượt tấp vào bờ vì nạn vượt biên. nếu các bạn sống nơi hẻo lánh như mình sẽ chứng kiến cảnh giết người cướp của, của bọn côn đồ.
khoãng 15 năm trở lại đây, đất nước vươn lên từng ngày, có thể những người trẽ còn thấy nhiều điều chưa tốt, nhiều điều còn gây bức xúc;
nhưng mình phải chấp tay cảm ơn thượng đế. Hi vọng những người trẽ hôm nay và mãi mãi sau nầy được sống tốt đẹp hơn.

Nếu vậy em may mắn hơn các Bác rồi. Muốn phản bác lời của Bác nhưng ngại động chạm đến chính trị, điều mà ở site này có lẽ không nê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é!)