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

[RDSS]

Ta cải tiến 1 tí: Nhảy "quãng k" : k,2k,3k,.... Nếu vỡ thì lùi k-1, và sau đó tiến 1 cho đến khi vỡ.
Số lần thử S= [n/k] +k-1 (trong trường hợp xấu nhất).
S nhỏ nhất khi k^2=n. Chắc các bạn còn nhớ Định lý nổi tiếng của Cô-si (Cauchy)!!!
Với n=100 => k=10. Số lần thử = 19! OK?

Và theo cách tính của bạn thì số lần thử chỉ là 18 thôi.

[tuhiep]

'gởi RDSS & ThanhLongBin
bạn ThanhLongBin thích phức tạp vấn đề nhỉ. mình dùng kiến thức thấp thôi. tổng các số nguyên 1+2+3+4+... là n.(n+1)/2. nếu số tầng là 105 thì chuẩn, nhưng 100 thì chịu hẹp 1 chút.
chọn n=14 và test như sau:
lần đầu lên tầng 14 thử bi. nếu bi bể thì 13 lần nữa thử xem tầng nào;không thì
lên thêm 13 tầng nữa (tầng 27) thử, nếu bi bể thì 12 lần nữa thử tầng nào; không thì
lên thêm 12 tầng nữa (tầng 39), cứ thế mình lập lại...
Không quá 14 lần thử mình tìm ra đáp án.
cái không may là ê ẩm chân. Hi vọng 100 tầng có thang máy, nếu không thì ...

[RDSS]

'gởi RDSS & ThanhLongBin
bạn ThanhLongBin thích phức tạp vấn đề nhỉ. mình dùng kiến thức thấp thôi. tổng các số nguyên 1+2+3+4+... là n.(n+1)/2. nếu số tầng là 105 thì chuẩn, nhưng 100 thì chịu hẹp 1 chút.
chọn n=14 và test như sau:
lần đầu lên tầng 14 thử bi. nếu bi bể thì 13 lần nữa thử xem tầng nào;không thì
lên thêm 13 tầng nữa (tầng 27) thử, nếu bi bể thì 12 lần nữa thử tầng nào; không thì
lên thêm 12 tầng nữa (tầng 39), cứ thế mình lập lại...
Không quá 14 lần thử mình tìm ra đáp án.
cái không may là ê ẩm chân. Hi vọng 100 tầng có thang máy, nếu không thì ...

Mình cũng nghĩ như bạn. ThanhLongBin yêu cầu tăng số quả cầu. Nếu số quả cầu là 3 và 4 thì kết quả thế nào các bạn?

[tuhiep]

' gởi RDSS

bạn RDSS đáp ứng yêu cầu của bạn ThanhLongBien đó nhe.
mình vô tư.

[RDSS]

' gởi RDSS

bạn RDSS đáp ứng yêu cầu của bạn ThanhLongBien đó nhe.
mình vô tư.

Nhìn lại thì thấy bạn LongLongBin muốn làm tổng quát cũng hay. Mình thấy là với 2 quả cầu thì s (số lần thử), k (số thứ tự tầng thử đầu), N (số tầng của tòa nhà) phụ thuộc nhau như sau: s=k; N-k<k(k+1)/2<=N=> với k=14 thì N-k=91<14(14+1)/2<=105.

[ThanhLongBin]

'gởi RDSS & ThanhLongBin
bạn ThanhLongBin thích phức tạp vấn đề nhỉ. mình dùng kiến thức thấp thôi. tổng các số nguyên 1+2+3+4+... là n.(n+1)/2. nếu số tầng là 105 thì chuẩn, nhưng 100 thì chịu hẹp 1 chút.
chọn n=14 và test như sau:
lần đầu lên tầng 14 thử bi. nếu bi bể thì 13 lần nữa thử xem tầng nào;không thì
lên thêm 13 tầng nữa (tầng 27) thử, nếu bi bể thì 12 lần nữa thử tầng nào; không thì
lên thêm 12 tầng nữa (tầng 39), cứ thế mình lập lại...
Không quá 14 lần thử mình tìm ra đáp án.
cái không may là ê ẩm chân. Hi vọng 100 tầng có thang máy, nếu không thì ...

Gửi bạn Tư Hiệp!
Xin tặng bạn 2 chữ: "Bái phục"!
Với một bài toán vui thì bạn đã có lời giải rất hay và bạn RDSS, người đăng bài, cũng như tôi đã công nhận kết quả.
Tuy nhiên, nếu chúng ta coi đây là một bài toán suy luận logic nghiêm túc, thì chúng ta vẫn bỏ qua một yêu cầu của đầu bài là phải chứng minh rằng chính phương pháp này cho số lần thử là nhỏ nhất, hoặc mọi phương pháp khác chỉ có thể cho kết quả lớn hơn hoặc bằng mà thôi!!! Bạn nghĩ sao?

[ThanhLongBin]

Mình cũng nghĩ như bạn. ThanhLongBin yêu cầu tăng số quả cầu. Nếu số quả cầu là 3 và 4 thì kết quả thế nào các bạn?

Gửi RDSS,
Mình thử cải tiến phương pháp của bạn Tư Hiệp như thế này:
Gọi số bi =b. Số tầng =N và số lần thử tối ưu là S.
Với b=2, bạn Tư Hiệp phân chia các bước nhảy theo chuỗi số tự nhiên giảm dần, cụ thể là n, n-1, n-2,.,2,1 thỏa mãn điều kiện tổng của chúng >=N và gần N nhất=> n ~ sqrt(2N), sqrt là ký hiệu căn bậc 2. Giả sử ở bước thứ i thì quả số 1 bị vỡ, ta dùng quả số 2 nhiều nhất là n-i lần để thử. Kết quả S=i+n-1=n.
Với b=3, tui cũng phân chia các bước nhảy theo quy tắc "chuỗi một nửa các số chính phương liên tiêp": n^2/2, (n-1)^2/2,...,2 và cũng thỏa mãn điều kiện tổng của chúng >=N và gần N nhất. Giả sử ở bước thứ i, quả số 1 bị vỡ, ta còn 2 quả nữa và lại dùng Phương pháp của Tư Hiệp với "ngôi nhà thứ i" có số tầng là (n-i)^2/2. Kết quả S=i+n-1=n!.
Tui nhớ láng máng tổng 1+4 +9+..+n^2= n(n+1)(2n+1)/6 (?)=> n~(6N)^(1/3) (căn bậc 3 đấy!! Hu hu...).
Với N=100, S=n=7!
Với b bất kỳ, cách phân chia bước nhảy theo quy tắc "chuỗi liên tiếp giảm dần các lũy thừa bậc (b-1) chia cho một hệ số nguyên".
Số b càng lớn, thì tổng lũy thừa bâc (b-1) càng phức tạp, công thức tính cũng rắc rối, thà rằng cứ dùng 2-3 quả và leo tầng nhiều lần còn hơn! .
PS. Trên đây mới là ý tưởng chung, chưa tính đến sai số +/-1 đơn vị do phải lấy phần nguyên của các phân số.

[RDSS]

Gửi RDSS,
Mình thử cải tiến phương pháp của bạn Tư Hiệp như thế này:
Gọi số bi =b. Số tầng =N và số lần thử tối ưu là S.
Với b=2, bạn Tư Hiệp phân chia các bước nhảy theo chuỗi số tự nhiên giảm dần, cụ thể là n, n-1, n-2,.,2,1 thỏa mãn điều kiện tổng của chúng >=N và gần N nhất=> n ~ sqrt(2N), sqrt là ký hiệu căn bậc 2. Giả sử ở bước thứ i thì quả số 1 bị vỡ, ta dùng quả số 2 nhiều nhất là n-i lần để thử. Kết quả S=i+n-1=n.
Với b=3, tui cũng phân chia các bước nhảy theo quy tắc "chuỗi một nửa các số chính phương liên tiêp": n^2/2, (n-1)^2/2,...,2 và cũng thỏa mãn điều kiện tổng của chúng >=N và gần N nhất. Giả sử ở bước thứ i, quả số 1 bị vỡ, ta còn 2 quả nữa và lại dùng Phương pháp của Tư Hiệp với "ngôi nhà thứ i" có số tầng là (n-i)^2/2. Kết quả S=i+n-1=n!.
Tui nhớ láng máng tổng 1+4 +9+..+n^2= n(n+1)(2n+1)/6 (?)=> n~(6N)^(1/3) (căn bậc 3 đấy!! Hu hu...).
Với N=100, S=n=7!
Với b bất kỳ, cách phân chia bước nhảy theo quy tắc "chuỗi liên tiếp giảm dần các lũy thừa bậc (b-1) chia cho một hệ số nguyên".
Số b càng lớn, thì tổng lũy thừa bâc (b-1) càng phức tạp, công thức tính cũng rắc rối, thà rằng cứ dùng 2-3 quả và leo tầng nhiều lần còn hơn! .
PS. Trên đây mới là ý tưởng chung, chưa tính đến sai số +/-1 đơn vị do phải lấy phần nguyên của các phân số.

Hơi ngây ngất nên chưa hiểu. Bạn mà đưa lời giải cho 3 và 4 quả cầu cho 100 tầng thì chắc mình dễ hiểu hơn.

[ThanhLongBin]

Hơi ngây ngất nên chưa hiểu. Bạn mà đưa lời giải cho 3 và 4 quả cầu cho 100 tầng thì chắc mình dễ hiểu hơn.

Xin phép sửa lại cho chính xác hơn, xin thay khái niệm "chuỗi các lũy thừa giảm dần" nêu trên bằng "Chuỗi bậc b" dưới đây.
Toàn bộ ngôi nhà dc chia thành các khối xếp chồng lên nhau có số tầng là N[b, i] với b=số bi, i=chỉ số của khối, thỏa mãn điều kiện:
N[b,1] +N[b,2] +...+N[b,n] >=N và gần N nhất. Số cần tìm là S=n.
Với b=2 thì N[2,n]=n ta gọi là "Chuỗi bậc 1"
Với b=3 thì N[3,n]= N[2,1]+N[2,2]+..+N[2,n]= 1 +2 +..+n = n(n+1)/2 "Chuỗi bậc 2"
Với b=4 thì N[4,n]= N[3,1]+N[3,2]+..+N[3,n]= 1 +3 +6..+n(n+1)/2= n(n+1)(n+2)/6 "Chuỗi bậc 3"..
Với mọi b>=3 thì N[b,n]= N[b-1,1]+N[b-1,2]+..+N[b-1,n]= "Chuỗi bậc (b-1)". Tức là các phần tử của chuỗi bậc (b) bằng tổng của các phần tử dưới nó của chuỗi bậc (b-1)!!!!
Trường hợp cụ thể: b=3, N=100. Ta viết N[i]=N[3,i] cho nó gọn.
Do 8*9*10/6=120 => n=8. Tòa nhà dc chia thành 8 khối.
Khối 1 có N[1]=8*9/2= 36
Khối 2 có N[2]=7*8/2= 28
Khối 3 có N[3]=6*7/2= 21
...
Khối 7 có N[7]= 2*3/2=3.
Khối 8 có N[8]= 1*2/2=1.
Các bước thử bi như sau:
1. Bi số 1: thử ở các tầng số : N[1]=36, nếu ko dc thì lên tầng N[1]+N[2]=36+28=64,N[1]+N[2]+N[3]=85... Sau k lần thử, bi bị vỡ và ta dừng ở khối thứ k có N[k]=(n-k)(n-k+1)/2 tầng!
2. Còn lại 2 bi, ta chỉ kiểm tra trong khối thứ k như bạn TuHiep đã làm. Số lần thử nhiều nhất = n-k.
Như vậy, S=k +n-k = n =8.

[tuhiep]

gởi ThanhlongBien

mình chưa thông cách tính của bạn. với b=4, n=100, bạn chọn 8 lần thử, với lần 1 ở tầng 36 bi vở, thì 3 bi với 7 test còn lại bạn làm sao tiếp.