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

[ThanhLongBin]

gởi RDSS & ThanhLongBien
bạn ThanhLongBien đưa ra 1 bổ đề nhằm chứng minh k được chọn là nhỏ nhất cho tình huống đặt ra. Mình thật chưa có cách xác định hay chứng minh điều nầy.Mong học hỏi được ở bạn.
Nhưng chứng minh k chọn là nhỏ nhất mình chứng minh bằng truy chứng( chắc từ mới gọi là qui nạp).(nhiều năm mình không đọc lại toán).

. đầu tiên bảng "H" mình tạo ra đúng với dòng b=1 (dòng toàn số 1). nghĩa là với mỗi k có 1 N(max) bằng trực quan và kiểm tra dể.
-dòng b=2; k=2 đúng, k=3 đúng ;nếu k=n đúng và cm được k=n+1 đúng thì dòng b=2 đúng.
- tương tự dòng b=3 sẽ chứng minh đúng.
nếu dòng b=n đúng tôi cm dòng b=n+1 đúng.
Vậy bảng "H" đúng với mọi dòng.
H(b,k)=H(b,k-1)+H(b-1,k-1) giúp mình chứng minh bảng "H" đúng.

Có lẽ bác hiểu nhầm ý tôi rồi!
Tôi xin nhắc lại nhé:
1. Bác với bác RDSS và tôi đều đã nhất trí công thức tính dãy số H(b,k)như bác viết trên. Tiện thể, công thức dạng ấy gọi là "đệ quy" (Recursive).
2. Bác đã dùng "phép quy nạp" (Induction)để chứng minh công thức tổng quát của S(b,k) là số tầng "quét" được với số bi =b và số lần thử =k .
Về mặt logic, chúng ta mới chỉ ra một cách "quét" các tầng ngôi nhà và tính dc số tầng cao nhất có thể bằng phương pháp "Dãy số H(b,k)". Nhưng chúng ta chưa chứng minh dc rằng đây là cách "quét" có kết quả tốt nhất!
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é!

PS. Ngày xưa, hồi học phổ thông cấp 3(bây giờ gọi là Trung học phổ thông), tôi có 3 năm học chuyên toán ở một trường khá danh tiếng ở Hà nội. Các thầy dạy ngày ấy cũng rất nổi tiếng như GS. Phan Đức Chính, cố GS. Lê Đình Thịnh,... Các thuật ngữ toán mà tôi dùng đều của các thầy ấy cả. Sau này, khi học đại học, tôi chuyển sang học Vật lý, nhưng vẫn giữ những tình cảm tốt đẹp nhất với môn Toán.

[RDSS]

Có lẽ bác hiểu nhầm ý tôi rồi!
Tôi xin nhắc lại nhé:
1. Bác với bác RDSS và tôi đều đã nhất trí công thức tính dãy số H(b,k)như bác viết trên. Tiện thể, công thức dạng ấy gọi là "đệ quy" (Recursive).
2. Bác đã dùng "phép quy nạp" (Induction)để chứng minh công thức tổng quát của S(b,k) là số tầng "quét" được với số bi =b và số lần thử =k .
Về mặt logic, chúng ta mới chỉ ra một cách "quét" các tầng ngôi nhà và tính dc số tầng cao nhất có thể bằng phương pháp "Dãy số H(b,k)". Nhưng chúng ta chưa chứng minh dc rằng đây là cách "quét" có kết quả tốt nhất!
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é!

PS. Ngày xưa, hồi học phổ thông cấp 3(bây giờ gọi là Trung học phổ thông), tôi có 3 năm học chuyên toán ở một trường khá danh tiếng ở Hà nội. Các thầy dạy ngày ấy cũng rất nổi tiếng như GS. Phan Đức Chính, cố GS. Lê Đình Thịnh,... Các thuật ngữ toán mà tôi dùng đều của các thầy ấy cả. Sau này, khi học đại học, tôi chuyển sang học Vật lý, nhưng vẫn giữ những tình cảm tốt đẹp nhất với môn Toán.

Còn em chẳng biết thuật ngữ toán học nào cả. Đọc những từ như giai thừa, tổ hợp...của các Bác cứ phái vào google dịch.Còn với bài toán N=100, b=2 thì bằng cách loại dần chúng ta chứng minh được là 14 là nhỏ nhất chứ Bác?

[RDSS]

Có lẽ bác hiểu nhầm ý tôi rồi!
Tôi xin nhắc lại nhé:
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é!

Nhỏ hơn 14 là 13,12,....1. Vì chỉ có hai phương án vỡ hoặc không=>algorithm là ném bi một rồi theo kết quả ném bi hai.
Muốn có 13 lần thử ta phải ném từ tầng 13 vì nếu bi vỡ thì sau khi thử từ tầng 1->12 ta sẽ tìm ra đáp số với 13 lần thử. Nếu không vỡ để vẫn có 13 lần thử ta phải ném từ tầng 25...=> Sau 13 lần thử ta không tìm ra đáp số. Tương tự với 12,11....=> Lần thử ít nhất có thể là 14.

[ThanhLongBin]

Nhỏ hơn 14 là 13,12,....1. Vì chỉ có hai phương án vỡ hoặc không=>algorithm là ném bi một rồi theo kết quả ném bi hai.
Muốn có 13 lần thử ta phải ném từ tầng 13 vì nếu bi vỡ thì sau khi thử từ tầng 1->12 ta sẽ tìm ra đáp số với 13 lần thử. Nếu không vỡ để vẫn có 13 lần thử ta phải ném từ tầng 25...=> Sau 13 lần thử ta không tìm ra đáp số. Tương tự với 12,11....=> Lần thử ít nhất có thể là 14.

Chào bác RDSS
Tôi hoàn toàn hiểu ý tưởng của bác. Đúng là bác đã chứng minh dc với bài toán b=2, N=100! Chúc mừng bác và chúc mừng chúng ta vì đây là lần đầu tiên (đúng ko nhỉ?) chúng ta có một cách chứng minh rằng, 14 lần thử là con số nhỏ nhất!
Một số người, nhất là các thày dạy toán, hay đòi hỏi lời giải phải chặt chẽ.
Tôi thử trình bày lại cách làm của bác xem nó có chặt chẽ hơn ko nhé?
Ta sẽ chứng minh bài toán trên bằng phương pháp Phản chứng (Disproof! Lại thuật ngữ rùi! Sorry!!)
Giả thiết rằng, tồn tại một cách thử bi với số lần thử s =< 13 mà vẫn cho phép ta phát hiện tầng đầu tiên gây bi vỡ trong mọi tình huống có thể xảy ra. Ta chỉ cần chỉ ra một trường hợp mà cách thử bi này ko có đáp số, tức là giả thiết trên là vô lý!
Gọi x(1),x(2),...x(s), là số thứ tự của tầng ứng với các lần thử tương ứng, với s =< 13.
Lập luận như bác RDSS với các tình hướng vỡ hoặc ko của bi số 1, ta có:
x(1)<=13
x(2)<=13+(13-1)
..
x(s)<=13+(13-1)+..+(13-s +1) =13*s -s*(s-1)/2 =s*(27-s)/2 <= 13*14/2=91
Ta thấy ngay, x(i) <=91 với mọi i=1..s
Như vậy, nếu tầng cần tìm ở trong vùng 92..100 thì với cách thử trên, sau khi dùng hết số lần thử s, ta ko thể xác định dc chính xác nó. Điều này mâu thuẫn với giả thiết phản chứng ở trên! ĐPCM.
Các bác thấy có dài dòng quá không?

[RDSS]

Chào bác RDSS
Tôi hoàn toàn hiểu ý tưởng của bác. Đúng là bác đã chứng minh dc với bài toán b=2, N=100! Chúc mừng bác và chúc mừng chúng ta vì đây là lần đầu tiên (đúng ko nhỉ?) chúng ta có một cách chứng minh rằng, 14 lần thử là con số nhỏ nhất!
Một số người, nhất là các thày dạy toán, hay đòi hỏi lời giải phải chặt chẽ.
Tôi thử trình bày lại cách làm của bác xem nó có chặt chẽ hơn ko nhé?
Ta sẽ chứng minh bài toán trên bằng phương pháp Phản chứng (Disproof! Lại thuật ngữ rùi! Sorry!!)
Giả thiết rằng, tồn tại một cách thử bi với số lần thử s =< 13 mà vẫn cho phép ta phát hiện tầng đầu tiên gây bi vỡ trong mọi tình huống có thể xảy ra. Ta chỉ cần chỉ ra một trường hợp mà cách thử bi này ko có đáp số, tức là giả thiết trên là vô lý!
Gọi x(1),x(2),...x(s), là số thứ tự của tầng ứng với các lần thử tương ứng, với s =< 13.
Lập luận như bác RDSS với các tình hướng vỡ hoặc ko của bi số 1, ta có:
x(1)<=13
x(2)<=13+(13-1)
..
x(s)<=13+(13-2)+..+(13-s +1) =13*s -s*(s-1)/2 =s*(27-s)/2 <= 13*14/2=91
Ta thấy ngay, x(i) <=91 với mọi i=1..s
Như vậy, nếu tầng cần tìm ở trong vùng 92..100 thì với cách thử trên, sau khi dùng hết số lần thử s, ta ko thể xác định dc chính xác nó. Điều này mâu thuẫn với giả thiết phản chứng ở trên! ĐPCM.
Các bác thấy có dài dòng quá không?

Bác TuHiep chứng minh trường hợp tổng quát cho b=2, N tầng rồi, nhưng Bác nói đúng, trường hợp tổng quát cho b bi, k lần thử chưa được chứng minh. Em sẽ đọc lại về combinatorics rồi thử đưa lời giải vậy. Hoặc Bác hay Bác TuHiep có thời gian thì giải giúp anh em đi. Em hôm nay bận xem bóng đá.