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

[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 đá.