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

[gameco]

ặc, ném bay qua cửa kính biến mất cầu luôn, không biết rơi ở đâu hay bay vào phòng ngủ của một em nào đó.

[RDSS]

'gởi RDSS
phải có điều kiện chứ? cứ đứng ở tầng 100 mà ném thôi.

Viết thế này chắc dễ hiểu hơn:
Có hai quả cầu thủy tinh và tòa nhà 100 tầng. Cần ít nhất bao nhiêu lần ném để tìm tầng thấp nhất mà từ tầng đó quả cầu sẽ bị vỡ khi ném. Gặp may thì một lần-ném từ tầng một đã vỡ rồi. Nhưng không gặp may thì sao?

[RDSS]

Các bạn đang đi lạc hướng rồi , đây là diễn đàn cờ tướng không phải đố nhau giải toán .

Nếu các bạn muốn làm toán , mình sẽ đưa đề bài toán lớp 2 nâng cao để các bạn giải .

Mình nghĩ cũng khó đấy !!!

Xin cám ơn bạn trước!!!

[ThanhLongBin]

Viết thế này chắc dễ hiểu hơn:
Có hai quả cầu thủy tinh và tòa nhà 100 tầng. Cần ít nhất bao nhiêu lần ném để tìm tầng thấp nhất mà từ tầng đó quả cầu sẽ bị vỡ khi ném. Gặp may thì một lần-ném từ tầng một đã vỡ rồi. Nhưng không gặp may thì sao?
Gởi RDSS,
Vẫn cần làm cho "dễ hiểu hơn" nữa! :D :D
1. Không dùng từ "ném" mà dùng từ "thả" có nghĩa là để các quả cầu rơi tự do xuống đất với vận tốc ban đầu =0.Khi tiếp đất, quả cầu ko hề nẩy lên vì nó làm bằng thủy tinh! :D
2. Có quyền cho rằng ma sát của không khí là rất nhỏ và có thể bỏ qua!
3. Các tầng của tòa nhà có cùng độ cao như nhau. Nếu tính cả "tầng trệt" thì người ngoài Bắc sẽ bảo là "tòa nhà cao 101 tầng", còn người trong Nam vẫn biểu chỉ có 100 tầng thui! Hu hu..
Đấy chỉ là cảm nhận của mình.
Mời các bạn khác cùng "làm rõ đầu bài trước khi làm" nhé!!!

[RDSS]

Gởi RDSS,
Vẫn cần làm cho "dễ hiểu hơn" nữa! :D :D
1. Không dùng từ "ném" mà dùng từ "thả" có nghĩa là để các quả cầu rơi tự do xuống đất với vận tốc ban đầu =0.Khi tiếp đất, quả cầu ko hề nẩy lên vì nó làm bằng thủy tinh! :D
2. Có quyền cho rằng ma sát của không khí là rất nhỏ và có thể bỏ qua!
3. Các tầng của tòa nhà có cùng độ cao như nhau. Nếu tính cả "tầng trệt" thì người ngoài Bắc sẽ bảo là "tòa nhà cao 101 tầng", còn người trong Nam vẫn biểu chỉ có 100 tầng thui! Hu hu..
Đấy chỉ là cảm nhận của mình.
Mời các bạn khác cùng "làm rõ đầu bài trước khi làm" nhé!!!

Vậy thì thế này:
Quả cầu làm bằng chất liệu đặc biệt, cần phải thực hành mới biết từ độ cao nào rơi xuống thì vỡ. Thả bằng cách thò tay ra cửa sổ cho quả cầu rơi. Giữa hai tầng không có cửa sổ để thả. 100 tầng là theo cách tính của người bắc. Các tầng cao bằng nhau hay không không quan trọng.

[zzz]

Không biết tại sao lại phải có 2 quả cầu ở đây? Nếu số quả cầu là vô hạn (để có thể ném vô số lần) thì đáp án sẽ là ceil (log2 (100)) tức là = 7 lần, còn không biết 2 quả thì có mẹo mực gì không? 2 quả ném 2 phát vỡ cả hai thì chắc nhà khoa học làm thí nghiệm tự lao đầu xuống đất như Galile hồi xưa đi thực nghiệm trên tháp nghiêng Pisa vậy :D

[ThanhLongBin]

Viết thế này chắc dễ hiểu hơn:
Có hai quả cầu thủy tinh và tòa nhà 100 tầng. Cần ít nhất bao nhiêu lần ném để tìm tầng thấp nhất mà từ tầng đó quả cầu sẽ bị vỡ khi ném. Gặp may thì một lần-ném từ tầng một đã vỡ rồi. Nhưng không gặp may thì sao?
Ta sẽ "nhẩy cóc" 2 tầng 1 lần theo thứ tự: 1, 3, 5 ,7.... Dùng quả 1 để "thăm dò", nếu ko vỡ thì nhảy tiếp. Nếu vỡ thì lùi lại 1 tầng và thử bằng quả số 2.
Số lần thử = [n/2] +1. Với [x]=phần nguyên của x, n= vị trí cần tìm.
Cách này không dành cho người có "tiền sử áp huyết-tim mạch", giá mà RDSS cho thêm vài quả cầu thì đỡ vất vả hơn! :D :D :D

[RDSS]

Ta sẽ "nhẩy cóc" 2 tầng 1 lần theo thứ tự: 1, 3, 5 ,7.... Dùng quả 1 để "thăm dò", nếu ko vỡ thì nhảy tiếp. Nếu vỡ thì lùi lại 1 tầng và thử bằng quả số 2.
Số lần thử = [n/2] +1. Với [x]=phần nguyên của x, n= vị trí cần tìm.
Cách này không dành cho người có "tiền sử áp huyết-tim mạch", giá mà RDSS cho thêm vài quả cầu thì đỡ vất vả hơn! :D :D :D

Trường hợp xấu nhất là 51 lần thử. Hơi nhiều bạn ạ.

[ThanhLongBin]

Trường hợp xấu nhất là 51 lần thử. Hơi nhiều bạn ạ.

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?

[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ẫn hơi nhiều bạ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! :D :D :D.
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! :D :D :D.
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.

[ThanhLongBin]

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.
Chào Tuhiep,
Ví dụ trên là mình làm với b=3 chứ! Nếu ngay ở tầng 36, bi 1 bị vỡ, thì bạn dùng 2 bị kia để kiểm tra 35 tầng còn lại theo đúng cách làm của bạn với N=36. Nếu ko nhầm thì mất thêm 7 (hay 8 ?) lần nữa thôi! Có lẽ mình vẫn bị độ sai lệch +/-1 ở đâu đó! Hình như S=n+1 thì hợp lý hơn.
Lưu ý:
-b=2 => chuỗi bậc 1 dạng 1,2,..,n và tổng là n(n+1)/2
-b=3 => chuỗi bậc 2 dạng 1,3,..n(n+1)/2 và tổng là n(n+1)(n+2)/6. Bậc của chuỗi bao giờ cũng =(b-1).
Còn với b=4, chuỗi bậc 3 dạng 1,4,...n(n+1)(n+2)/6 và tổng là ...?
(Mình sẽ tính sau nhé, mình linh cảm là tổng này (bậc 4) có dạng n(n+1)(n+2)(n+3)/x với x là số cần tìm! Cứ suy từ 2 trường hợp b=2 và b=3 ra, rất có thể x=b! (giai thừa), bạn có thể dùng phép quy nạp để chứng minh công thức này! :D :D :D )

Với b=4, N=100, áp dụng công thức tổng bậc 4 trên ta có:
6*7*8*9/4!=126 => n=6 và S=n+1 =7!
Có cái rất hay là dù tăng thêm bi nữa, S vẫn =7 thôi đúng như bạn zzz đã nhận xét trong 1 comment của bài này (S>= log2(N)) !!!!! Hay ko?

[tuhiep]

'gởi ThanhlongBien
mình chờ xem bạn sẽ cho đáp án cụ thể như thế nào.
Cám ơn trước.

[RDSS]

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.
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. 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.
.

Chắc bạn có ý là b=2; b=3 chứ không phải b=3; b=4 như bạn viết bên trên? Tôi có cảm giác rằng trong suy luận của bạn vẫn có gì đó không ổn.

[tuhiep]

kĩ niệm nhớ mãi của tuhiep.
Hôm nay bão, nghỉ sớm. Mình kể các bạn mẩu chuyện sau mình tạm gọi tựa là "kĩ thuật dùng dao y khoa trong toán".
Ngày học lớp 10 có 1 bạn học cùng lớp đem đề toán ở 1 trung tâm chuyên toán nào đó, vào lớp nhờ thầy giảng. Thầy xem xong,trầm ngâm suy nghĩ rồi bảo:" học hết tiết học đến giờ nghỉ thầy nói". Chấm dứt tiết học, đến giờ ra chơi, cả lớp ngồi lại chờ nghe thầy giảng.
Lời thầy: "các em nhìn bài toán rất khó, lòng các em bối rối. Các em nghĩ có 1 kĩ xão, một bí quyết gì mà mình chưa biết nên không làm nổi.
Hôm nay thầy chỉ các em một cách suy nghĩ trước bài toán khó. Đó là thật sự bình tĩnh, tự tin tách bài toán khó thành từng vấn đề nhỏ, đơn giản mà mình giải quyết tốt. Thầy tạm gọi là dùng dao mỗ trong toán. hẹn các em tuần sau thầy sẽ phân tích bài toán ".
Dĩ nhiên sau đó thầy đã giải bài toán theo hướng thầy đã nêu; và bọn mình cảm nhận sao bài toán dể thế mà mình không nghĩ ra.
Điều nầy ghi lại cho mình 1 dấu ấn mãi mãi không phai.
Có thể không bao giờ mình là người giỏi toán, nhưng đối mặt với mọi vấn đề trong cuộc sống, mình luôn làm theo hướng thầy dạy.
"phân tích vấn đề lớn thành từng mảnh nhỏ rồi xử lí."
Kĩ năng dùng "dao mổ" luôn được mình tôi luyện.
Mãi mãi tri ân người thầy đã cho con một báu vật hữu ích theo chân con suốt đời./.

[castle3010]

kĩ niệm nhớ mãi của tuhiep.
Hôm nay bão, nghỉ sớm. Mình kể các bạn mẩu chuyện sau mình tạm gọi tựa là "kĩ thuật dùng dao y khoa trong toán".
Ngày học lớp 10 có 1 bạn học cùng lớp đem đề toán ở 1 trung tâm chuyên toán nào đó, vào lớp nhờ thầy giảng. Thầy xem xong,trầm ngâm suy nghĩ rồi bảo:" học hết tiết học đến giờ nghĩ thầy nói". Chấm dứt tiết học, đến giờ ra chơi, cả lớp ngồi lại chờ nghe thầy giảng.
Lời thầy: "các em nhìn bài toán rất khó, lòng các em bối rối. Các em nghĩ có 1 kĩ xão, một bí quyết gì mà mình chưa biết nên không làm nổi.
Hôm nay thầy chỉ các em một cách suy nghĩ trước bài toán khó. Đó là thật sự bình tĩnh, tự tin tách bài toán khó thành từng vấn đề nhỏ, đơn giản mà mình giải quyết tốt. Thầy tạm gọi là dùng dao mỗ trong toán. hẹn các em tuần sau thầy sẽ phân tích bài toán ".
Dĩ nhiên sau đó thầy đã giải bài toán theo hướng thầy đã nêu; và bọn mình cảm nhận sao bài toán dể thế mà mình không nghĩ ra.
Điều nầy ghi lại cho mình 1 dấu ấn mãi mãi không phai.
Có thể không bao giờ mình là người giỏi toán, nhưng đối mặt với mọi vấn đề trong cuộc sống, mình luôn làm theo hướng thầy dạy.
"phân tích vấn đề lớn thành từng mảnh nhỏ rồi xử lí."
Kĩ năng dùng "dao mổ" luôn được mình tôi luyện.
Mãi mãi tri ân người thầy đã cho con một báu vật hữu ích theo chân con suốt đời./.
Hay quá, cảm ơn bạn nhiều

[tuhiep]

bài toán test bi vỡ.
gọi b là số bi, N: số tầng,k: số lần thử.
trong chuổi cấp số nhân 1 2 4 8 ...,mình chọn ra b phần tử.
ex: b=2 chọn ra 1.2
b=3 chọn ra 1.2.4
b=4 chọn ra 1.2.4.8
sau đó viết tiếp vào chuổi số trên cấp số cộng với số cuối dãy số trên là số hạng đầu, công sai là số liền trước như sau
b=2 => 1.2.3.4.5 ...
b=3 => 1.2.4.6.8.10 ...
b=4 => 1.2.4.8.12.16.20 ...
vậy dãy số có 2 phần: phần đầu là cấp số nhân, có số phần tử là b, phần sau là cấp số cộng.
số cuối cấp số nhân là số tầng trong bước nhãy test lần cuối; số phía trước là số tầng cần chọn để test kiểm tra.
gọi S là tổng của dãy số, và k là số phần tử của dãy.
chọn S(k) sao cho = hay lớn gần nhất so với N.
cụ thể: b=4, N=100, lấy ra dãy số:
1.2.4.8.12.16.20.24.28 dãy số S (9 số hạng , có S(9)=115);chọn k=9
lần đầu chọn tầng 28 thử bi, nếu bi vỡ thì lần 2 xuống tầng 4 test, lần 2 không vỡ thì lên tầng 8 test, lần 2 bi vỡ thì xuống tầng 2 test...
nếu lần 1 không vỡ, thì chọn tầng 52 test lần 2 (bước lên 24 tầng nữa. Vậy các bạn hiểu ý nghĩa cấp số cộng trong dãy số S ).
cứ thế các bạn sẽ test ra tầng nào là đáp án bài toán,với tối đa 9 lần test.
Hi vọng các bạn hài lòng.

[RDSS]

bài toán test bi vỡ.
gọi b là số bi, N: số tầng,k: số lần thử.
trong chuổi cấp số nhân 1 2 4 8 ...,mình chọn ra b phần tử.
ex: b=2 chọn ra 1.2
b=3 chọn ra 1.2.4
b=4 chọn ra 1.2.4.8
sau đó viết tiếp vào chuổi số trên cấp số cộng với số cuối dãy số trên là số hạng đầu, công sai là số liền trước như sau
b=2 => 1.2.3.4.5 ...
b=3 => 1.2.4.6.8.10 ...
b=4 => 1.2.4.8.12.16.20 ...
vậy dãy số có 2 phần: phần đầu là cấp số nhân, có số phần tử là b, phần sau là cấp số cộng.
số cuối cấp số nhân là số tầng trong bước nhãy test lần cuối; số phía trước là số tầng cần chọn để test kiểm tra.
gọi S là tổng của dãy số, và k là số phần tử của dãy.
chọn S(k) sao cho = hay lớn gần nhất so với N.
cụ thể: b=4, N=100, lấy ra dãy số:
1.2.4.8.12.16.20.24.28 dãy số S (9 số hạng , có S(9)=115);chọn k=9
lần đầu chọn tầng 28 thử bi, nếu bi vỡ thì lần 2 xuống tầng 4 test, lần 2 không vỡ thì lên tầng 8 test, lần 2 bi vỡ thì xuống tầng 2 test...
nếu lần 1 không vỡ, thì chọn tầng 52 test lần 2 (bước lên 24 tầng nữa. Vậy các bạn hiểu ý nghĩa cấp số cộng trong dãy số S ).
cứ thế các bạn sẽ test ra tầng nào là đáp án bài toán,với tối đa 9 lần test.
Hi vọng các bạn hài lòng.

Mình thấy vẫn chưa hợp lý.

[tuhiep]

"bài toán test bi vỡ.
cụ thể: b=4, N=100, lấy ra dãy số:
1.2.4.8.12.16.20.24.28 dãy số S (9 số hạng , có S(9)=115);chọn k=9"
mình thấy lỗi. khi b=4
khi thừa 1 test thì không tăng theo cấp số cộng mà phức tạp như sau.
1.2.4.8.15.26.42.64.
như vậy với b=4 và N=98 thì chỉ 7 lần thử. với N=100 thêm 1 lần thử hơi phí.

[RDSS]

"bài toán test bi vỡ.
cụ thể: b=4, N=100, lấy ra dãy số:
1.2.4.8.12.16.20.24.28 dãy số S (9 số hạng , có S(9)=115);chọn k=9"
mình thấy lỗi. khi b=4
khi thừa 1 test thì không tăng theo cấp số cộng mà phức tạp như sau.
1.2.4.8.15.26.42.64.
như vậy với b=4 và N=98 thì chỉ 7 lần thử. với n=100 thêm 1 lần thử hơi phí.

Từ 99-128 tầng là phải mất 8 lần thử bạn ạ.

[tuhiep]

"bài toán test bi vỡ.
cụ thể: b=3, lấy ra dãy số:
1.2.4.7.11.16.22.29.37.
với N=92 thì 8 lần thử, N từ 93 đến 129 thì thêm 1 lần thử nữa.

với b=4 thì mình nói cùng ý bạn mà.
bạn viết "Từ 99-128 tầng là phải mất 8 lần thử bạn ạ."
mình viết "như vậy với b=4 và N=98 thì chỉ 7 lần thử. với N=100 thêm 1 lần thử hơi phí." chữ N mình gõ nhầm là n.

mình vội vàng nghĩ các bước thử bi không vở là cấp số cộng. xét kĩ mới thấy là dãy số phức hợp./.
cám ơn nhiều.

[RDSS]

"bài toán test bi vỡ.
cụ thể: b=3, lấy ra dãy số:
1.2.4.7.11.16.22.29.37.
với N=92 thì 8 lần thử, N từ 93 đến 129 thì thêm 1 lần thử nữa.

với b=4 thì mình nói cùng ý bạn mà.
bạn viết "Từ 99-128 tầng là phải mất 8 lần thử bạn ạ."
mình viết "như vậy với b=4 và N=98 thì chỉ 7 lần thử. với N=100 thêm 1 lần thử hơi phí." chữ N mình gõ nhầm là n.

mình vội vàng nghĩ các bước thử bi không vở là cấp số cộng. xét kĩ mới thấy là dãy số phức hợp./.
cám ơn nhiều.

Tóm lại là hai bi, nhà 105 tầng cần 14 lần thử
Ba bi, nhà 186 tầng cần 9 lần thử. Không hiểu có nhầm ở đâu không?

[RDSS]

"bài toán test bi vỡ.
cụ thể: b=3, lấy ra dãy số:
1.2.4.7.11.16.22.29.37.
với N=92 thì 8 lần thử, N từ 93 đến 129 thì thêm 1 lần thử nữa.
.

Ba bi, 8 lần thử thì nhà có thể 128 tầng bạn ạ.

[tuhiep]

'gởi RDSS
"Ba bi, 8 lần thử thì nhà có thể 128 tầng bạn ạ."

2 bi, 105 tầng, 14 thử.
3 bi,92 tầng cần 8 lần thử; 129 tầng thì 9 lần thử
4 bi,98 tầng thì 7 lần thử; 162 tầng thì 8 lần thử.
bạn thử lại xem, mình xét kĩ rồi mà.
mình nghĩ không thể có: ""Ba bi, 8 lần thử thì nhà có thể 128 tầng bạn ạ.""

[RDSS]

'gởi RDSS
"Ba bi, 8 lần thử thì nhà có thể 128 tầng bạn ạ."

2 bi, 105 tầng, 14 thử.
3 bi,92 tầng cần 8 lần thử; 129 tầng thì 9 lần thử
4 bi,98 tầng thì 7 lần thử; 162 tầng thì 8 lần thử.
bạn thử lại xem, mình xét kĩ rồi mà.
mình nghĩ không thể có: ""Ba bi, 8 lần thử thì nhà có thể 128 tầng bạn ạ.""

Tôi nghĩ là tôi tính đúng đấy Bác ạ.

[tuhiep]

'gởi RDSS
"Ba bi, 8 lần thử thì nhà có thể 128 tầng bạn ạ."
vậy mình phải chờ các bạn giúp giùm thôi.

[tuhiep]

'gởi RDSS
"Ba bi, 8 lần thử thì nhà có thể 128 tầng bạn ạ."
vậy mình phải chờ các bạn giúp giùm thôi.

[RDSS]

'gởi RDSS
"Ba bi, 8 lần thử thì nhà có thể 128 tầng bạn ạ."
vậy mình phải chờ các bạn giúp giùm thôi.

Xin lỗi Bác! Tôi tính nhầm. Đúng là: 2 bi, 106 tầng, 14 lần thử.
3 bi, 93 tầng, 8 lần thử. 9 lần thử, 130 tầng.
4 bi, 99 tầng, 7 lần thử. 8 lần thử, 163 tầng.

[ThanhLongBin]

Chào hai bạn RDSS và Tuhiep,
Mình vừa đi công tác về thấy các bạn tranh luận sôi nổi quá!
Phải công nhận, "bài toán thử bi" ở dạng tổng quát với số tầng=N và số bi=b bất kỳ đã vượt qua cái tầm "đố vui giải trí" rồi.
Mình rất thích ý tưởng của Tuhiep về dãy số "cấp số nhân" và kéo dài bằng "cấp số cộng".
Mình thấy cả hai bạn đều vô tình hay cố ý bỏ qua một yêu cầu của đầu bài là "Phải chứng minh số lần thử là nhỏ nhất"!
Để khỏi mất công tìm lại các trang trước, mình trình bày ngắn gọn phương pháp tạo dãy số của mình
Với mọi b>=2.
Gọi N[b,i] là phần tử thứ i của dãy với số bi=b cho trước. Sau này mình sẽ dùng dấu "[]" để đánh chỉ số, các bạn đừng nhầm với cách ký hiệu phần nguyên nhé.
N[b,i] = {i*(i+1)*..(i+b-2)}/{1*2...*(b-1)}. Cả tử số và mẫu số của phân số này là các tích của (b-1) số nguyên liên tiếp.
Gọi n là số phần tử của dãy.
S[b,n] là tổng của dãy n phần tử với số bi=b
Ko khó lắm có thể chứng minh rằng:
S[b,n]= {n*(n+1)*..(n+b-2)*(n+b-1)}/{1*2...*(b-1)*b}. Cả tử số và mẫu số của phân số này là các tích của b số nguyên liên tiếp. Các bạn thấy sự tương đồng N[b,n] với S[b,n] không? Nó đây này: S[b,n]=N[b+1,n] !!!
Ví dụ cụ thể luôn:
1. b=2=> N[2,i]=i.
Dãy số có dạng: 1,2,3,..,n
S[2,n]=n*(n+1)/2.
Cho n=14 => S[2,14]=105
Sau số lần thử = n =14, số tầng cao nhất tìm dc là 105. Đây là "bài toán 2 bi mà Tuhiep đã giải!
2. b=3 => N[3,i]=i*(i+1)/2
Dãy số có dạng: 1,3,6,..,n*(n+1)/2
S[3,n]=n*(n+1)*(n+2)/6.
Cho n=8 => S[3,8]= 8*9*10/6=120
Sau số lần thử = n+1 =9, (n+1 vì vỡ mất 1 hòn bi để trở thành bài toán 2 bi)
Số tầng cao nhất tìm dc là 120
3. b=4 => N[4,i]=i*(i+1)*(i+2)/6
Dãy số có dạng: 1,4,10,..,n*(n+1)*(n+2)/6
S[4,n]=n*(n+1)*(n+2)*(n+3)/24.
Cho n=6 => S[4,6]= 6*7*8*9/24=126
Sau số lần thử = n+2 =8,(n+2 vì vỡ mất 2 hòn bi để trở thành bài toán 2 bi)
Số tầng cao nhất tìm dc là 126.

[RDSS]

Chào hai bạn RDSS và Tuhiep,
Mình vừa đi công tác về thấy các bạn tranh luận sôi nổi quá!
Phải công nhận, "bài toán thử bi" ở dạng tổng quát với số tầng=N và số bi=b bất kỳ đã vượt qua cái tầm "đố vui giải trí" rồi.
Mình rất thích ý tưởng của Tuhiep về dãy số "cấp số nhân" và kéo dài bằng "cấp số cộng".
Mình thấy cả hai bạn đều vô tình hay cố ý bỏ qua một yêu cầu của đầu bài là "Phải chứng minh số lần thử là nhỏ nhất"!
Để khỏi mất công tìm lại các trang trước, mình trình bày ngắn gọn phương pháp tạo dãy số của mình
Với mọi b>=2.
Gọi N[b,i] là phần tử thứ i của dãy với số bi=b cho trước. Sau này mình sẽ dùng dấu "[]" để đánh chỉ số, các bạn đừng nhầm với cách ký hiệu phần nguyên nhé.
N[b,i] = {i*(i+1)*..(i+b-2)}/{1*2...*(b-1)}. Cả tử số và mẫu số của phân số này là các tích của (b-1) số nguyên liên tiếp.
Gọi n là số phần tử của dãy.
S[b,n] là tổng của dãy n phần tử với số bi=b
Ko khó lắm có thể chứng minh rằng:
S[b,n]= {n*(n+1)*..(n+b-2)*(n+b-1)}/{1*2...*(b-1)*b}. Cả tử số và mẫu số của phân số này là các tích của b số nguyên liên tiếp. Các bạn thấy sự tương đồng N[b,n] với S[b,n] không? Nó đây này: S[b,n]=N[b+1,n] !!!
Ví dụ cụ thể luôn:
1. b=2=> N[2,i]=i.
Dãy số có dạng: 1,2,3,..,n
S[2,n]=n*(n+1)/2.
Cho n=14 => S[2,14]=105
Sau số lần thử = n =14, số tầng cao nhất tìm dc là 105. Đây là "bài toán 2 bi mà Tuhiep đã giải!
2. b=3 => N[3,i]=i*(i+1)/2
Dãy số có dạng: 1,3,6,..,n*(n+1)/2
S[3,n]=n*(n+1)*(n+2)/6.
Cho n=8 => S[3,8]= 8*9*10/6=120
Sau số lần thử = n+1 =9, (n+1 vì vỡ mất 1 hòn bi để trở thành bài toán 2 bi)
Số tầng cao nhất tìm dc là 120
3. b=4 => N[4,i]=i*(i+1)*(i+2)/6
Dãy số có dạng: 1,4,10,..,n*(n+1)*(n+2)/6
S[4,n]=n*(n+1)*(n+2)*(n+3)/24.
Cho n=6 => S[4,6]= 6*7*8*9/24=126
Sau số lần thử = n+2 =8,(n+2 vì vỡ mất 2 hòn bi để trở thành bài toán 2 bi)
Số tầng cao nhất tìm dc là 126.

Chào bạn! Mình hiểu ý bạn. Nhưng bạn tính e rằng không đúng vì: 2 bi, 106 tầng, 14 lần thử.
3 bi, 93 tầng, 8 lần thử, 93 tầng. 9 lần thử, 130 tầng.
4 bi, 99 tầng, 7 lần thử. 8 lần thử, 163 tầng.

[ThanhLongBin]

Chào bạn! Mình hiểu ý bạn. Nhưng bạn tính e rằng không đúng vì: 2 bi, 106 tầng, 14 lần thử.
3 bi, 93 tầng, 8 lần thử, 93 tầng. 9 lần thử, 130 tầng.
4 bi, 99 tầng, 7 lần thử. 8 lần thử, 163 tầng.
Theo mình hiểu, có thể tồn tại nhiều cách thử bi cho kết quả (số lần thử) như nhau!
Cách của mình cũng chỉ là một trong nhiều cách khác có thể có mà thôi!
Chính xác ra, để dễ so sánh các phương pháp khác nhau, chúng ta nên đặt lại bài toán hơi khác đi, ví dụ như sau:
"Cho số bi =b >=2, số lần thử n bất kỳ, tìm cách thử bi ứng với tòa nhà có số tầng cao nhất".
Vì mình tính nhẩm (+,- các số có nhiều chữ số! :D ) rất kém, nên có thói quen phải đưa ra công thức tổng quát, khi áp số liệu cụ thể vào thì rất khó sai.
Mình đã viết là rất thích ý tưởng tạo dãy của bạn Tuhiep, nhưng ko thấy bạn ấy đưa ra công thức tổng quát cuối cùng (vì Tuhiep hình như có mấy phương án hơi khác nhau), nên mình chưa kiểm tra dc kết quả như bạn nói.
Cách kiểm tra chéo với số bi cụ thể =2,3,4 như hai bạn đang làm chưa đủ để kết luận phương pháp nào là tối ưu. Hoàn toàn có thể xảy ra trường hợp, với b=3,4 thì cách của Tuhiep là tốt nhất, khi b tăng lên đến giá trị nào đó thì ta lại phải áp dụng cách khác thì sao? Ví dụ như 2 hàm số x*2 và x. Khi x<1 thì x^2 luôn <x, nhưng khi x tăng lên >1 thì xảy ra điều ngược lại!
Công thức tổng quát của mình với S[b,n] là hàm tăng theo kiểu "n-giai thừa", một loại hàm số có độ gia tăng rất khủng. Giá mà hai bạn cũng đưa ra dc công thức tổng quát thì ta dễ đánh giá hơn.

Tuy vậy, với trường hợp 2 bi, 14 lần thử thì chính Tuhiep đã chứng minh rồi, số tầng cao nhất là:
1+2+3+..+14= 14*15/2=105.
Nhưng bạn lại viết : " 2 bi, 106 tầng, 14 lần thử" !
Bạn chỉ hộ, mình có tính nhầm ko ? Tks.

[RDSS]

Theo mình hiểu, có thể tồn tại nhiều cách thử bi cho kết quả (số lần thử) như nhau!
Cách của mình cũng chỉ là một trong nhiều cách khác có thể có mà thôi!
Chính xác ra, để dễ so sánh các phương pháp khác nhau, chúng ta nên đặt lại bài toán hơi khác đi, ví dụ như sau:
"Cho số bi =b >=2, số lần thử n bất kỳ, tìm cách thử bi ứng với tòa nhà có số tầng cao nhất".
Vì mình tính nhẩm (+,- các số có nhiều chữ số! :D ) rất kém, nên có thói quen phải đưa ra công thức tổng quát, khi áp số liệu cụ thể vào thì rất khó sai.
Mình đã viết là rất thích ý tưởng tạo dãy của bạn Tuhiep, nhưng ko thấy bạn ấy đưa ra công thức tổng quát cuối cùng (vì Tuhiep hình như có mấy phương án hơi khác nhau), nên mình chưa kiểm tra dc kết quả như bạn nói.
Cách kiểm tra chéo với số bi cụ thể =2,3,4 như hai bạn đang làm chưa đủ để kết luận phương pháp nào là tối ưu. Hoàn toàn có thể xảy ra trường hợp, với b=3,4 thì cách của Tuhiep là tốt nhất, khi b tăng lên đến giá trị nào đó thì ta lại phải áp dụng cách khác thì sao? Ví dụ như 2 hàm số x*2 và x. Khi x<1 thì x^2 luôn <x, nhưng khi x tăng lên >1 thì xảy ra điều ngược lại!
Công thức tổng quát của mình với S[b,n] là hàm tăng theo kiểu "n-giai thừa", một loại hàm số có độ gia tăng rất khủng. Giá mà hai bạn cũng đưa ra dc công thức tổng quát thì ta dễ đánh giá hơn.

Tuy vậy, với trường hợp 2 bi, 14 lần thử thì chính Tuhiep đã chứng minh rồi, số tầng cao nhất là:
1+2+3+..+14= 14*15/2=105.
Nhưng bạn lại viết : " 2 bi, 106 tầng, 14 lần thử" !
Bạn chỉ hộ, mình có tính nhầm ko ? Tks.

Vì theo đề là bi phải vỡ nên đáp số theo mình là 106 cho hai bi và 14 lần thử. Mình nghĩ là Bác TuHiep cung đồng ý như vậy. Còn trường hợp tổng quát n bi, k lần thử và N tầng thì mình chưa tìm ra. Tìm thêm trường hợp 5 bi đi bạn, sau đó từ các trường hợp riêng suy ra trường hợp tổng quát vậy.

[RDSS]

Nếu không khó trả lời thì bạn và Bác TuHiep sống ở đâu vậy? Mình thì lang thang ở Châu Âu gần 20 năm rồi mà chưa có điều kiện về thăm.

[ThanhLongBin]

Gửi Tuhiep,
Bạn đã viết:" b=4 khi thừa 1 test thì không tăng theo cấp số cộng mà phức tạp như sau:
1.2.4.8.15.26.42.64."
Theo mình hiểu, với b>=2, n>b, dãy số có n phần thử của bạn có dạng tổng quát sau:
Với b phần tử đầu: 2^0, 2^1,..,2^(b-1)
Phần tử thứ b+1 = tổng b cái đầu kia= 2^b-1
Còn tiếp theo, từ phần tử thứ b+2 trở đi, luôn bằng tổng 2 phần tử trước đó và +1. Đúng ko?
Nếu vậy, phần thứ 2 của dãy ko phải là "cấp số cộng" đâu! Nó là một dạng của dãy Fibonaci nổi tiếng đấy!
Trên đây chỉ là phỏng đoán của mình, còn trong thực tế, dãy số ví dụ trên của bạn không thỏa mãn tính chất này!
Bạn thử mô tả cho nình hiểu lại nhé! Thanks!

[ThanhLongBin]

Nếu không khó trả lời thì bạn và Bác TuHiep sống ở đâu vậy? Mình thì lang thang ở Châu Âu gần 20 năm rồi mà chưa có điều kiện về thăm.
Với tôi thì ko vấn đề gì.
Tôi hiện sống và làm việc ở Hà nội. Tôi cũng có dạo du học ở Nga, cũng hơn 30 năm rồi. Thỉnh thoảng đi công tác cũng có dịp qua Châu Âu vài ngày.
Ta chắc cũng tầm tuổi , nên chăng chuyển sang xưng hô "bác, tôi" cho tiện nhé?
Chúc bác luôn vui.

[tuhiep]

'gởi RDSS & ThanhLongBien
mình sống ở phía nam tp HCM, nơi mà vào mùa nầy nước ngập minh mông phủ cả đường đi. Người dân chổ mình rất mong quốc sách chống ngập phát huy tác dụng.
Bạn RDSS thêm 1 tầng trong cách tính tổng, mình đã nghĩ đến, nhưng không quyết được vì tầng thêm vào sẽ nằm sát trên lần test cuối. kết quả nầy dù bi vở hay 0 thì không kết luận gì được vì đề đâu có xác định là tầng cuối bi vở. bi có quyền tốt tuyệt vời mà.
dãy số mà mình tính được có dạng dể nhớ, dể viết ra nhưng không viết ngay được. Nó giúp ta tính tổng của k số hạng 1 dãy rất nhanh.
S(k) cũa 1 dãy nào đó thì bằng số hạng (k+1) của dãy liền dưới trừ 1.
cách lập dãy cũa mình như sau:
b=2=> 1.2.3.4. 5.06.07.08.09.10.11....
b=3=> 1.2.4.7.11.16.22.29.37.46.56 ...
b=4=> 1.2.4.8.15.26.42.64.93........
b=5=> 1.2.4.8.16.31.57.99.163....
b=6=> 1.2.4.8.16.32.63.120.219...

mỗi số hạng viết ra bằng cách cộng số hạng liền trước nó với số liền trên (cùng cột với số liền trước).
công thức tính tổng thì không cần thiết vì mình đã nói ở trên.
nhưng tính chắc phải nhọc công.
b=3=> S(k)=1!+2!+3!+...+(k-1)!+k (không giai thừa)
b=4=> S(k)=(k-2)1!+(k-3)2!+(k-4)3!+..+2(k-3)!+1(k-2)!+(k-1)!+k ( không giai thừa )

Cm k tối thiểu với N và b cho trước là điều rõ ràng nhưng khó . Đơn giãn nhất là không sai thì là đúng.
Mình không khã năng tính tổng quát S,k,b ; nhưng bạn cho số cụ thể thì mình ghi ra được dãy số liên hệ.
Có dịp rổi mình sẽ kể về 2 chữ "liên hệ" giống như báu vật "dao mổ" vậy đó.

[sedbadrdmm]

tìm 2 viên bi có phóng xạ để làm giề :tlbuc

[RDSS]

'gởi RDSS & ThanhLongBien
mình sống ở phía nam tp HCM, nơi mà vào mùa nầy nước ngập minh mông phủ cả đường đi. Người dân chổ mình rất mong quốc sách chống ngập phát huy tác dụng.
Bạn RDSS thêm 1 tầng trong cách tính tổng, mình đã nghĩ đến, nhưng không quyết được vì tầng thêm vào sẽ nằm sát trên lần test cuối. kết quả nầy dù bi vở hay 0 thì không kết luận gì được vì đề đâu có xác định là tầng cuối bi vở. bi có quyền tốt tuyệt vời mà.
dãy số mà mình tính được có dạng dể nhớ, dể viết ra nhưng không viết ngay được. Nó giúp ta tính tổng cũa k số hạng 1 dãy rất nhanh.
S(k) cũa 1 dãy nào đó thì bằng số hạng (k+1) cũa dãy liền dưới trừ 1.
cách lập dãy cũa mình như sau:
b=2=> 1.2.3.4. 5.06.07.08.09.10.11....
b=3=> 1.2.4.7.11.16.22.29.37.46.56 ...
b=4=> 1.2.4.8.15.26.42.64.93........
b=5=> 1.2.4.8.16.31.57.99.163....
b=6=> 1.2.4.8.16.32.63.120.219...

mỗi số hạng viết ra bằng cách cộng số hạng liền trước nó với số liền trên (cùng cột).
công thức tính tổng thì không cần thiết vì mình đã nói ở trên.
nhưng tính chắc phải nhọc công.
b=3=> S(k)=1!+2!+3!+...+(k-1)!+k (không giai thừa)
b=4=> S(k)=(k-2)1!+(k-3)2!+(k-4)3!+..+2(k-3)!+1(k-2)!+(k-1)!+k ( không giai thừa )

Cm k tối thiểu với N và b cho trước là điều rõ ràng nhưng khó . Đơn giãn nhất là không sai thì là đúng.
Mình không khã năng tính tổng quát S,k,b ; nhưng bạn cho số cụ thể thì mình ghi ra được dãy số liên hệ.
Có dịp rổi mình sẽ kể về 2 chữ "liên hệ" giống như báu vật "dao mổ" vậy đó.

Muốn tìm công thức cho b bi, k lần thử, N tầng mà thấy khó quá!

[RDSS]

'gởi RDSS & ThanhLongBien
cách lập dãy cũa mình như sau:
b=2=> 1.2.3.4. 5.06.07.08.09.10.11....
b=3=> 1.2.4.7.11.16.22.29.37.46.56 ...
b=4=> 1.2.4.8.15.26.42.64.93........
b=5=> 1.2.4.8.16.31.57.99.163....
b=6=> 1.2.4.8.16.32.63.120.219...

b=3=> S(k)=1!+2!+3!+...+(k-1)!+k (không giai thừa)
b=4=> S(k)=(k-2)1!+(k-3)2!+(k-4)3!+..+2(k-3)!+1(k-2)!+(k-1)!+k ( không giai thừa )

Cm k tối thiểu với N và b cho trước là điều rõ ràng nhưng khó . Đơn giãn nhất là không sai thì là đúng.
Mình không khã năng tính tổng quát S,k,b ; nhưng bạn cho số cụ thể thì mình ghi ra được dãy số liên hệ.
Có dịp rổi mình sẽ kể về 2 chữ "liên hệ" giống như báu vật "dao mổ" vậy đó.

Dãy của bạn không đúng, vì nó còn phụ thuộc vào k(số lần thử nữa).

[tuhiep]

'gởi RDSS
"Dãy của bạn không đúng, vì nó còn phụ thuộc vào k(số lần thử nữa)."
mỗi dãy số tương ứng với b cho trước.
trên 1 dãy số, với mỗi N tôi xác định 1 k tối thiểu; hoặc với 1 k đã biết tôi xác định N tối đa (mỗi dãy số là sự quan hệ giữa k và N, với 1 b đã biết).
Trên bảng nầy , với 1 số N đã biết tôi cũng xác định được sự quan hệ giữa b và k ( vì tính chất bất kỳ số hạng k cũa dãy nào cũng bằng S(k-1) dãy liền trên cộng 1)

[RDSS]

'gởi RDSS
"Dãy của bạn không đúng, vì nó còn phụ thuộc vào k(số lần thử nữa)."
mỗi dãy số tương ứng với b cho trước.
trên 1 dãy số, với mỗi N tôi xác định 1 k tối thiểu; hoặc với 1 k đã biết tôi xác định N tối đa (mỗi dãy số là sự quan hệ giữa k và N, với 1 b đã biết).
Trên bảng nầy , với 1 số N đã biết tôi cũng xác định được sự quan hệ giữa b và k ( vì tính chất bất kỳ số hạng k cũa dãy nào cũng bằng S(k-1) dãy liền trên cộng 1)

b=4, k=8=>1,2,4,6,11,16,22,38,49,56,62,64,80,91,98,102,104,106,...132....
Còn bỏ qua các số trung gian thì: ...22,64,106,132...

[tuhiep]

'gởi RDSS
"b=4,k=8=>1,2,4,6,11,16,22,38,49,56,62,64,80,91,98,102,104,106,...132....
Còn bỏ qua các số trung gian thì: ...22,64,106,132..."
chưa hiểu ý bạn.

với b=4, dãy số mình suy ra là:
b=4=> 1.2.4.8.15.26.42.64.93........
b=5=> 1.2.4.8.16.31.57.99.163..
kèm dãy b=5 để tiện xác định N (số tầng)

không cần tính các số trung gian, vì số liền trái là số tầng lên (bi không vở), hay số tầng xuống nếu bi vở.
đường chéo lên bên trái là các số liên hệ khi bi thử bị vở.
còn tính chất gì nữa thì mình chưa khám phá ra.

[RDSS]

'gởi RDSS
"b=4,k=8=>1,2,4,6,11,16,22,38,49,56,62,64,80,91,98,102,104,106,...132....
Còn bỏ qua các số trung gian thì: ...22,64,106,132..."
chưa hiểu ý bạn.

với b=4, dãy số mình suy ra là:
b=4=> 1.2.4.8.15.26.42.64.93........
b=5=> 1.2.4.8.16.31.57.99.163..
.

Với 4 bi 8 lần thử thì lần thử đầu là 64, nếu vỡ thử tầng 22, không vỡ thử 106 rồi 132...Vì thế mình không hiểu sao lại có 42 và 93 trong dãy của bạn.

[tuhiep]

với b=4, dãy số mình suy ra là:
b=4=> 1.2.4.8.15.26.42.64.93........
b=5=> 1.2.4.8.16.31.57.99.163..
"Với 4 bi 8 lần thử thì lần thử đầu là 64, nếu vỡ thử tầng 22, không vỡ thử 106 rồi 132...Vì thế mình không hiểu sao lại có 42 và 93 trong dãy của bạn."
Với 4 bi 8 lần thử thì lần thử đầu là 64, nếu vỡ thử tầng 22(64-42).
không vỡ thử 106 (64+42),nếu không vở đến 132(106+26).
số 93 ứng với b=4 và k=9 thử lần đầu ở tầng 93 và N từ 163 đến 255.
bạn nhìn bảng của mình trục tung là b, trục hoành là k.

[RDSS]

Tìm mãi mới thấy sự phụ thuộc như sau giữa N tầng và k lần thử:
2 bi=> N=k*(k+1)/2
3 bi=> N=(k^3+5k)/6
4 bi=>?????

[ThanhLongBin]

Tìm mãi mới thấy sự phụ thuộc như sau giữa N tầng và k lần thử:
2 bi=> N=k*(k+1)/2
3 bi=> N=(k^3+5k)/6
4 bi=>?????
Chào bác RDSS,
Té ra bác vẫn còn "sâu nặng" với bài toán này!
Tôi sẽ cố cùng bác với bác Tuhiep làm cái công thức "gần như tổng quát" vậy.
Trước hết, cần nhắc lại là phương pháp xây dựng dãy số như trên là của bác Tuhiep, nên tôi xin mạo muội lấy chữ cái H để đặt tên cho dãy số. :D
Với số bi=b, n là số thứ tự của số hạng thứ n trong dãy, H(b,n) là giá trị của số hạng ấy.
Ta chỉ xét b>=2.
Với mọi b, ta luôn có:
H(b,1)=1
H(b,2)=2.
Ta gọi, S(b,k)= tổng các số H(b,n) với n=1..k. Số S(b,k) này chính là số tầng N ứng với số bi =b, và số lần thử =k.
Như bác Tuhiep mô tả, quan hệ đệ quy của các số H(b,n) có dạng:
H(b+1,n+1)=H(b+1,n)+H(b,n).....(1) (Đánh sô công thức cho dễ tìm thôi!)
=> H(b+1,n+1)= S(b,n)+1........(2)
Cho n chạy từ 1 đến k và cộng các đẳng thức (2) lại ta có:
=> S(b+1,k+1)= Tổng [S(b,n); n=1..k] + k+1
Hoặc tương đương:
S(b+1,k)= Tổng [S(b,n); n=1..k-1] + k ...(3)

Ta đã biết
S(2,n)=n(n+1)/2= C(2,n+1) là "Tổ hợp chập 2 của (n+1).
Các bạn nhớ lại công thức: "Tổng các tổ hợp có cùng chập" nhé:
Tổng [C(m,n+m-1), n=1..k-1]=C(m+1,k+m] (4)

Với b= 2:
S(2,k)=k(k+1)/2 =C(2,k+1).
Với b=3:
từ (3) và (4) =>
S(3,k)= Tổng [C(2,n+1);n=1..k-1] +k = C(3,k+1)+C(1,k)= (k-1)k(k+1)/6 +k (5)
Công thức này rút gọn lại thành S(3,k)=k(k^2+5)/6 như bác RDSS đã viết trên.
Còn tôi thì muốn giữ nguyên kết quả (5) để tính "tổng các tổ hợp có cùng chập" cho trường hợp b=4!
Với b=4:
Ta lại áp dụng (3) và (4) để lấy tổng (5):
S(4,k)= C(4,k+2) + C(2,k+1) + C(1,k).

Với mọi b>=4 , công thức tổng quát có dạng:

S(b,k)= C(b,k+b-2) + Tổng [C(i,k+i-1); i=1..(b-2)] (6). (Công thức này tôi mới sửa lại hôm nay, Nov. 12)
Tôi cố tình không rút gọn các biểu thức C(..,..) để tiện áp dụng công thức (4).
Trình bày hơi dài, thế nào cũng bị bác Tuhiep "phê bình" đây! :D

[RDSS]

Chào bác RDSS,
S(3,k)= Tổng [C(2,n+1);n=1..k-1] +k = C(3,k+1)+C(1,k)= (k-1)k(k+1)/6 +k (5)
Công thức này rút gọn lại thành S(3,k)=k(k^2+5)/6 như bác RDSS đã viết trên.
Còn tôi thì muốn giữ nguyên kết quả (5) để tính "tổng các tổ hợp có cùng chập" cho trường hợp b=4!
Với b=4:
Ta lại áp dụng (3) và (4) để lấy tổng (5):
S(4,k)= C(4,k+2) + C(2,k+1) + C(1,k).

Với mọi b>=4 , công thức tổng quát có dạng:

S(b,k)= C(b,k+b-2) + Tổng [C(i,k+i-1); i=1..(b-2)] (6). (Công thức này tôi mới sửa lại hôm nay, Nov. 12)
Tôi cố tình không rút gọn các biểu thức C(..,..) để tiện áp dụng công thức (4).
Trình bày hơi dài, thế nào cũng bị bác Tuhiep "phê bình" đây! :D

Tôi tính ra cho 4 bi như sau:
4 bi=>N=(k^4-2k^3+11k^2+14k)/24
Của Bác là:
4 bi=>N=(k^4+2k^3+11k^2-34k)/24
Không hiểu ai tính chính xác hơn?

[tuhiep]

Gởi ThanhLongBien
Bài viết trên thật hay. duy công thức (4)mình thật sự không biết
"Các bạn nhớ lại công thức: "Tổng các tổ hợp có cùng chập" nhé:
Tổng [C(m,n+m-1), n=1..k-1]=C(m+1,k+m] (4)".
bạn nhìn vấn đề ở góc nhìn đại số rất hay. Thoả mãn tầm nhìn vươn lên của toán.
Ở đây mình nêu 1 cách nhìn khác. góc nhìn hình học.
bảng số lập ra theo cách mình làm có gì đó tựa như tam giác Pascal.
Thêm 1 hàng số 1 trên cùng ứng với b=1 nữa là trọn bảng.
ứng với 1 cặp (k,b) ta có 1 vị trí trên bảng. liền trái là (k-1,b),và trên liền trái nầy (k-1,b-1).
ở mỗi vị trí thử bi, tuỳ bi không vở hay vở, bạn bước qua vị trí liền trái hay vitri (k-1,b-1).
Như vậy bạn giải quyết bài toán mà không phải suy nghĩ thêm gì.
Điều nầy sẽ tượng tự như ý nghĩa hình học trong ứng dụng hệ thức Newton.
Cám ơn bạn RDSS đã cho mình một bài toán rất vui, gợi nhiều kĩ niệm thuở học trò.

[ThanhLongBin]

Gởi ThanhLongBien
Bài viết trên thật hay. duy công thức (4)mình thật sự không biết
"Các bạn nhớ lại công thức: "Tổng các tổ hợp có cùng chập" nhé:
Tổng [C(m,n+m-1), n=1..k-1]=C(m+1,k+m] (4)".
bạn nhìn vấn đề ở góc nhìn đại số rất hay. Thoả mãn tầm nhìn vươn lên của toán.
Ở đây mình nêu 1 cách nhìn khác. góc nhìn hình học.
bảng số lập ra theo cách mình làm có gì đó tựa như tam giác Pascal.
Thêm 1 hàng số 1 trên cùng ứng với b=1 nữa là trọn bảng.
ứng với 1 cặp (k,b) ta có 1 vị trí trên bảng. liền trái là (k-1,b),và trên liền trái nầy (k-1,b-1).
ở mỗi vị trí thử bi, tuỳ bi không vở hay vở, bạn bước qua vị trí liền trái hay vitri (k-1,b-1).
Như vậy bạn giải quyết bài toán mà không phải suy nghĩ thêm gì.
Điều nầy sẽ tượng tự như ý nghĩa hình học trong ứng dụng hệ thức Newton.
Cám ơn bạn RDSS đã cho mình một bài toán rất vui, gợi nhiều kĩ niệm thuở học trò.

Chào hai Bác Tuhiep và RDSS,
Tôi cũng đã định có lời cám ơn bác RDSS nhưng bác Tuhiep đã đi trước một bước!
Vậy thì cứ cám ơn cả hai bác đã cùng tôi chia sẻ vài phút thư giãn, giúp ta trẻ lại cái thuở học trò...
Bài toán vui này ko ngờ lại hàm chứa nhiều ý tưởng sâu xa: hình học, toán tổ hợp, chuỗi số Fibonaci...
Công thức (4) ấy, bác Tuhiep chỉ cần 5 phút vô wiki kiểm tra tính chất của nhị thức Newton là thấy ngay. Còn nếu mạng chậm, thì bác cứ chứng minh bằng quy nạp theo k (với m cố định bất kỳ) thì chỉ mất có 2 phút thôi! :D :D :D.

Công thức (6) có thể chưa chính xác, tôi sẽ kiểm tra lại và cố rút gọn nếu có thể, nên bác RDSS chịu khó đợi mấy bữa nhé!
Chúc hai bác luôn vui khỏe và yêu đời.

[tuhiep]

gởi ThanhLongBien
"Tổng [C(m,n+m-1), n=1..k-1]=C(m+1,k+m] (4)"
mình dùng cách qui nạp như bạn chỉ thì nhận thấy là:
Tổng [C(m,n+m-1), n=1..k]=C(m+1,k+m] (4b) n=1...k
bạn xem lại mình ghi chuẩn không?
cám ơn trước.

[tuhiep]

gởi RDSS
"RDSS ghi:
Tôi tính ra cho 4 bi như sau:
4 bi=>N=(k^4-2k^3+11k^2+14k)/24
Của Bác là:
4 bi=>N=(k^4+2k^3+11k^2-34k)/24
Không hiểu ai tính chính xác hơn?"
còn trên bảng của mình là:
b=4 với k lần lượt 6,7,8,9 => N(max)= 56;98;162;255
nào cùng xem độ chính xác nhe.

[tuhiep]

gởi ThanhLongBien
rổi 1 chút mình tính 1 phần sau:
=> H(b+1,n+1)= S(b,n)+1........(2)
Cho n chạy từ 1 đến k và cộng các đẳng thức (2) lại ta có:
=> S(b+1,k+1)= Tổng [S(b,n); n=1..k] + k+1
Hoặc tương đương:
S(b+1,k)= Tổng [S(b,n); n=1..k-1] + k ...(3) rất chuẩn.

mình đang xem lại cách tính của bạn.
bây giờ là KQ:
S(2,k)=C(2,k+1)
S(3,k)=C(3,k+1)+k......ghi lại _____S(3,k)=C(3,k+1)+C(1,k)
S(4,k)=C(4,k+1)+C(2,k)+k.ghi lại S(4,k)=C(4,k+1)+C(2,k)+C(1,k)
hivong sẽ có S(k,b).

dự trù :
S(b,k)=C(b,k+1)+C(b-2,k)+C(b-3,k)+...+C(1,k)

các bạn có hi vọng như mình không?
đi uống cafe chờ KQ.

[RDSS]

gởi RDSS
"RDSS ghi:
Tôi tính ra cho 4 bi như sau:
4 bi=>N=(k^4-2k^3+11k^2+14k)/24
Của Bác là:
4 bi=>N=(k^4+2k^3+11k^2-34k)/24
Không hiểu ai tính chính xác hơn?"
còn trên bảng của mình là:
b=4 với k lần lượt 6,7,8,9 => N(max)= 56;98;162;255
nào cùng xem độ chính xác nhe.

Xin lỗi các bác!
Tôi viết nhầm công thức của Bác ThanhLongBin. Đúng ra là:
4 bi=>N=(k^4+2k^3+11k^2+34k)/24
Thấy các số của tôi với của Bác trùng nhau đấy Bác TuHiep ạ.

[RDSS]

gởi ThanhLongBien
rổi 1 chút mình tính 1 phần sau:
=> H(b+1,n+1)= S(b,n)+1........(2)
Cho n chạy từ 1 đến k và cộng các đẳng thức (2) lại ta có:
=> S(b+1,k+1)= Tổng [S(b,n); n=1..k] + k+1
Hoặc tương đương:
S(b+1,k)= Tổng [S(b,n); n=1..k-1] + k ...(3) rất chuẩn.

mình đang xem lại cách tính của bạn.
bây giờ là KQ:
S(2,k)=C(2,k+1)
S(3,k)=C(3,k+1)+k......ghi lại _____S(3,k)=C(3,k+1)+C(1,k)
S(4,k)=C(4,k+1)+C(2,k)+k.ghi lại S(4,k)=C(4,k+1)+C(2,k)+C(1,k)
hivong sẽ có S(k,b).

dự trù :
S(b,k)=C(b,k+1)+C(b-2,k)+C(b-3,k)+...+C(1,k)

các bạn có hi vọng như mình không?
đi uống cafe chờ KQ.

Tôi tính thế này:
S(4,k)=C(4,k)+C(3,k)+C(2,k)+C(1,k)=k!/4!(k-4)!+k!/3!(k-3)!+k!/2!(k-2)!+k!/1!(k-1)=k(k-1)(k-2)(k-3)/24+k(k-1)(k-2)/6+k(k-1)/2+k=k^4-2k^3+11k^2+14k.
Không hiểu tại sao các bác bỏ đi C(3,k) nhỉ?

Theo tôi là thế này chứ:
S(1,k)=C(1,k)
S(2,k)=C(2,k)+S(1,k)
S(3,k)=C(3,k)+S(2,k)
S(4,k)=C(4,k)+S(3,k)
....
S(b,k)=C(b,k)+S(b-1,k)

Dân miền trong sao không đi uống rượu mà lại uống cafe vậy Bác?

[tuhiep]

gởi RDSS
bạn sữa chuẩn rồi, sao bác không chuẩn luôn:
"Theo tôi là thế này chứ:
S(1,k)=C(1,k)
S(2,k)=C(2,k)+S(1,k)
S(3,k)=C(3,k)+S(2,k)
S(4,k)=C(4,k)+S(3,k)
....
S(b,k)=C(b,k)+S(b-1,k)"

sao không là :
S(b,k)=C(b,k)+C(b-1,k)+C(b-2,k)+...C(1,k)
vì :
C(b,k+1)=C(b,k)+C(b-1,k)
Cùng nhau hi vọng đúng nhé.
Mình không bao giờ uống rượu, vì bị dị ứng rượu.
bạn bè nói mình là người kì lạ, dân đi biển mà không biết uống rượu.
Để chống rét buốt mà phải nhảy xuống nước thì mình hớp 1 ngụm nước mắm. Uống một ngụm rượu là đi tong luôn.
Điều nầy mình không biết tại sao, vì 1 ngụm nhỏ rượu là mình ngất rồi.
Những người quen không ai dám mời mình rượu vì sợ đền nhân mạng.

[ThanhLongBin]

gởi ThanhLongBien
"Tổng [C(m,n+m-1), n=1..k-1]=C(m+1,k+m] (4)"
mình dùng cách qui nạp như bạn chỉ thì nhận thấy là:
Tổng [C(m,n+m-1), n=1..k]=C(m+1,k+m] (4b) n=1...k
bạn xem lại mình ghi chuẩn không?
cám ơn trước.
Cám ơn bác Tuhiep đã hiệu chỉnh lại công thức (4). Đúng là trong cái tổng ấy, n phải chạy từ 1 tới k, ko hiểu sao, tôi lại viết có (k-1)! Chắc là dấu hiệu của tuổi già chăng?
Cám ơn bác lần nữa!

[ThanhLongBin]

Gửi hai bác Tuhiep và RDSS,
Công thức cuối cùng của bác Tuhiep hoàn toàn đúng, có thể kiểm tra bằng quy nạp!
S(b,k)=C(b,k+1)+C(b-2,k)+C(b-3,k)+...+C(1,k) (6*)
Xin có đôi câu nôm na:
Chúc mừng hai bác,
Chúc mừng chúng ta!
Tự đặt ra bài toán !?
Rùi giải mãi cũng ra!
Ura! Ura ! Ura!!!

Hai bác có dịp ra Hà nội, thì xin được mời ly rượu hoặc nhâm nha chút cafe mặc dù hai khoản này tui chẳng rành lắm. Mobile của tôi: (++84)98-327-1959. Với bác Tuhiep thì khi gọi bỏ số (++84) và thêm vô số "0" ở đầu là ổn vì bác đang ở VN mà. Hè năm 2012, tôi cùng gia đình đi "phượt" qua Miền Tây Nam bộ, nếm kẹo dừa ở Mỹ Tho, chén hết 1 quả sầu riêng 4kg ở cái cù lao gì ko nhớ trên Sông Hậu, gần Cần Thơ.... Đất Phương Nam quả là "Địa linh Nhân kiệt"!!!
Bác RDSS vừa lái xe đường trường tận trời Âu, vừa giải toán, thì khi nghỉ ngơi, làm ly rượu thuốc với đĩa chả chó kèm dồi rán qua lửa hơi cháy cạnh sẽ hồi phục công lực rất nhanh đó! :D :D :D
Chúc hai bác luôn vui!!!
ThanhLongBin kính!

[tuhiep]

gởi ThanhLongBien
"Công thức cuối cùng của bác Tuhiep hoàn toàn đúng, có thể kiểm tra bằng quy nạp!
S(b,k)=C(b,k+1)+C(b-2,k)+C(b-3,k)+...+C(1,k) (6*)"

mình viết lỗi rồi, viết như bạn RDSS gợi ý mới chuẩn:
S(b,k)=C(b,k)+C(b-1,k)+C(b-2,k)+C(b-3,k)+...+C(1,k) (6*)
dù sao 3 cây chụm lại cũng lên cái gò.
nhờ bạn ThanhLongBien nhiều mình mới có điều kiện suy luận được.

[ThanhLongBin]

gởi ThanhLongBien
"Công thức cuối cùng của bác Tuhiep hoàn toàn đúng, có thể kiểm tra bằng quy nạp!
S(b,k)=C(b,k+1)+C(b-2,k)+C(b-3,k)+...+C(1,k) (6*)"

mình viết lỗi rồi, viết như bạn RDSS gợi ý mới chuẩn:
S(b,k)=C(b,k)+C(b-1,k)+C(b-2,k)+C(b-3,k)+...+C(1,k) (6*)
dù sao 3 cây chụm lại cũng lên cái gò.
nhờ bạn ThanhLongBien nhiều mình mới có điều kiện suy luận được.

Gửi hai bác Tuhiep, RDSS,
Công thức cuối cùng của hai bác mới là đúng, tôi lại bỏ qua một lỗi nữa rùi!
S(b,k)=C(b,k)+C(b-1,k)+C(b-2,k)+C(b-3,k)+...+C(1,k) (6**)
Công thức này hình như ko rút gọn dc ở dạng tổng quát thì phải?
Lấy hình ảnh "Tam giác Pascal" của bác Tuhiep để minh họa, thì kết quả có dạng là "Tổng b phần tử liên tiếp, trừ phần tử đầu tiên C(0,k), cùng nằm trên hàng thứ k của Tam giác Pascal"!!!
Ta biết 2 tính chất của Tam giác này:
1. Tổng mỗi hàng thứ k =2^k
2. Đối xứng gương: C(b,k)=C(k-b,k)
Trong trường hợp đặc biệt, khi k là số lẻ , và b =(k-1)/2 thì S(b,k) = nửa tổng cả hàng k trong Tam giác trừ đi 1 vì ta phải thêm số C(0,k)=1 vào cho đủ nửa hàng, tức là:
S(b=(k-1)/2,k)=S((k-1)/2,k) = 2^k-1 !!!!

Các bác thử kiểm tra hộ ví dụ sau:
Với 9 lần thử và ta có số bi b=(9-1)/2=4 thì số tầng sẽ là S(4,9)=2^9-1= 511 !!!
Tương tự ta có nhiều kết quả rất gọn:
S(5,11)=2047
S(6,13)=8191
.....

[RDSS]

Gửi hai bác Tuhiep, RDSS,
Công thức cuối cùng của hai bác mới là đúng, tôi lại bỏ qua một lỗi nữa rùi!
S(b,k)=C(b,k)+C(b-1,k)+C(b-2,k)+C(b-3,k)+...+C(1,k) (6**)
Công thức này hình như ko rút gọn dc ở dạng tổng quát thì phải?
Lấy hình ảnh "Tam giác Pascal" của bác Tuhiep để minh họa, thì kết quả có dạng là "Tổng b phần tử liên tiếp, trừ phần tử đầu tiên C(0,k), cùng nằm trên hàng thứ k của Tam giác Pascal"!!!
Ta biết 2 tính chất của Tam giác này:
1. Tổng mỗi hàng thứ k =2^k
2. Đối xứng gương: C(b,k)=C(k-b,k)
Trong trường hợp đặc biệt, khi k là số lẻ , và b =(k-1)/2 thì S(b,k) = nửa tổng cả hàng k trong Tam giác trừ đi 1 vì ta phải thêm số C(0,k)=1 vào cho đủ nửa hàng, tức là:
S(b=(k-1)/2,k)=S((k-1)/2,k) = 2^k-1 !!!!

Các bác thử kiểm tra hộ ví dụ sau:
Với 9 lần thử và ta có số bi b=(9-1)/2=4 thì số tầng sẽ là S(4,9)=2^9-1= 511 !!!
Tương tự ta có nhiều kết quả rất gọn:
S(5,11)=2047
S(6,13)=8191
.....

Không đúng Bác ạ.

[tuhiep]

Gửi ThanhLongBin
"S((k-1)/2,k) = 2^k-1 !!!! với k lẽ"
chỉnh 1 chút là đúng ngay:
S((k-1)/2,k) = 2^(k-1) -1
bạn nhiều ý tưởng thật.

[ThanhLongBin]

Gửi ThanhLongBin
"S((k-1)/2,k) = 2^k-1 !!!! với k lẽ"
chỉnh 1 chút là đúng ngay:
S((k-1)/2,k) = 2^(k-1) -1
bạn nhiều ý tưởng thật.
Cám ơn bác đã sửa dùm. Hình như tui có "duyên ngầm" với các lỗi kiểu "+/-1" thì phải ?!
Mặt khác, tôi luôn có các quí nhân phù trợ, nên lỗi luôn dc tìm ra ngay! :D :D :D
Đã sai thì sửa lại cho đúng:
S(4,9)= 255
S(5,11)= 1023
S(6,13)= 4095.

[ThanhLongBin]

Bổ đề "Min of Max" !!!!
Để giải quyết triệt để Bài toán "Thử bi" ta sẽ chứng minh Phương pháp "Dãy số H(b,k) " của bác Tuhiep (Tạm gọi là H-selection !) luôn cho số lần thử là nhỏ nhất và bằng chính k!
Trước hết , mời các bác chứng minh hộ Bổ đề "Min of Max" dc mô tả như sau:
Cho trước m số tự nhiên Q={q1,q2,..qm} xếp trong m ô dc đánh số i=1...m.
Với mỗi hoán vị bất kỳ P={p1,p2..pm} của Q, ta tìm số sau:
Val(P)= max of {i+pi); với i=1...m.
CMR: Khi Val(P) đạt giá trị nhỏ nhất trong các khả năng có thể thì :
p1>=p2>=p3>=...>=pm (*)

Tức là, điều kiện min của Val(P) xảy ra khi hoán vị {pi} là một dãy số giảm dần!

Các bác có thể dùng phép phản chứng, giả thiết rằng tìm dc 1 hoán vị P={p(i),i=1...m} nào có Val(P) là nhỏ nhất nhưng không thỏa mãn điều kiện (*), tức là tồn tại 1 vị trí thứ j nào đó, ở đó p(j)<p(j+1) thì ta sẽ tìm dc 1 hoán vị khác P' có Val(P')< Val(P)!
Xin mời hai bác xuất chiêu!

[RDSS]

Bổ đề "Min of Max" !!!!
Để giải quyết triệt để Bài toán "Thử bi" ta sẽ chứng minh Phương pháp "Dãy số H(b,k) " của bác Tuhiep (Tạm gọi là H-selection !) luôn cho số lần thử là nhỏ nhất và bằng chính k!
Trước hết , mời các bác chứng minh hộ Bổ đề "Min of Max" dc mô tả như sau:
Cho trước m số tự nhiên Q={q1,q2,..qm} xếp trong m ô dc đánh số i=1...m.
Với mỗi hoán vị bất kỳ P={p1,p2..pm} của Q, ta tìm số sau:
Val(P)= max of {i+pi); với i=1...m.
CMR: Khi Val(P) đạt giá trị nhỏ nhất trong các khả năng có thể thì :
p1>=p2>=p3>=...>=pm (*)

Tức là, điều kiện min của Val(P) xảy ra khi hoán vị {pi} là một dãy số giảm dần!

Các bác có thể dùng phép phản chứng, giả thiết rằng tìm dc 1 hoán vị P={p(i),i=1...m} nào có Val(P) là nhỏ nhất nhưng không thỏa mãn điều kiện (*), tức là tồn tại 1 vị trí thứ j nào đó, ở đó p(j)<p(j+1) thì ta sẽ tìm dc 1 hoán vị khác P' có Val(P')< Val(P)!
Xin mời hai bác xuất chiêu!

Bài toán của Bác nhìn qua thấy khó quá. Chắc là toán cao cấp rồi và có lẽ phải tìm sách toán đọc lại. Còn bản thân dãy số S(b,k) là chứng minh rồi chứ Bác.Chỉ cần tìm algorithm cho lần ném đầu là xong.Còn công thức của dãy số có lẽ không rút gọn được thì phải.

[ThanhLongBin]

Bài toán của Bác nhìn qua thấy khó quá. Chắc là toán cao cấp rồi và có lẽ phải tìm sách toán đọc lại. Còn bản thân dãy số S(b,k) là chứng minh rồi chứ Bác.Chỉ cần tìm algorithm cho lần ném đầu là xong.Còn công thức của dãy số có lẽ không rút gọn được thì phải.

Bác RDSS lại quên mất đầu bài ban đầu rồi! :D
Cụ thể là, với 2 hòm bi và tòa nhà 100 tầng, chúng ta phải tìm ra thuật toán "Thử bi" có Số lần thử nhỏ nhất!
Với thuật toán lập dãy số của bác Tuhiep, ta có dãy số: 14,13,12,...2,1. Và ta đã chứng minh chỉ mất 14 lần thử là OK. (1)
Sau đó, ta tổng quá hóa sô bi =b, số lần thử = k để tìm ra dc số tầng cao nhất có thể kiểm tra chính là S(b,k) như ta đã làm!
Cả tôi, bác Tuhiep và bác đều tin rằng với đầu bài b=2,N=100 thì với cách làm trên, chỉ mất ko quá 14 lần thử bi cho mọi trường hợp. Chúng ta đều tin rằng số lần thử ít nhất là 14, nhưng chưa chứng minh dc nó!
Ta sẽ bắt đầu lại với bài toán 2 bi và số tầng cho trước N=k(k+1)/2.
Kịch bản của tôi như sau:
1. Ta lấy m số tự nhiên bất kỳ, thỏa mãn q(1)+q(2)+ +qm)=N. Dãy số {q(i)} này ứng với lần thử bi #1 cho đến khi nó vỡ thì thôi!
2.Giả sử bi #1 bị vỡ ở lần thử số j, khi đó ta chỉ cần dùng bi #2 thêm q(j)-1 lần thử, trong trường hợp xấu nhất. Với tình huống này, số lần thử tổng cộng là j+q(j)-1
3. Ta tìm số lớn nhất trong các số j+q(j)-1 khi cho j chạy từ 1 đến m. Số đó ứng với nhóm Q với m phần tử, tạm gọi là Val(Q,m)
4. Hoán vị các q(i) nêu trên, tìm giá trị nhỏ nhất của Val (Q,m). Áp dụng Bổ đề Min-Max để suy ra quy luật của q(i)=> Tìm ra giá trị nhỏ nhất với m cho trước: min(Val(Q,m))= F(m) nào đó!
5. Cho m chạy 1..N, tìm F(m) nhỏ nhất! Tôi tin rằng, đó chính là "dãy số Tuhiep" H(2,k)!!!!
Ngày xưa, ông Langland cũng chỉ đưa ra 1 cái Bổ đề tưởng rằng nho nhỏ, ai ngờ hơn 50 năm ko ai chứng minh dc. Chỉ đến tận năm 2008, GS Ngô Bảo Châu mới trình bày dc lời giả tổng quat sau đó ẵm dc cái giải Field! :D :D :D

[RDSS]

Bác RDSS lại quên mất đầu bài ban đầu rồi! :D
Cụ thể là, với 2 hòm bi và tòa nhà 100 tầng, chúng ta phải tìm ra thuật toán "Thử bi" có Số lần thử nhỏ nhất!
Với thuật toán lập dãy số của bác Tuhiep, ta có dãy số: 14,13,12,...2,1. Và ta đã chứng minh chỉ mất 14 lần thử là OK. (1)
Sau đó, ta tổng quá hóa sô bi =b, số lần thử = k để tìm ra dc số tầng cao nhất có thể kiểm tra chính là S(b,k) như ta đã làm!
Cả tôi, bác Tuhiep và bác đều tin rằng với đầu bài b=2,N=100 thì với cách làm trên, chỉ mất ko quá 14 lần thử bi cho mọi trường hợp. Chúng ta đều tin rằng số lần thử ít nhất là 14, nhưng chưa chứng minh dc nó!


Có thể Bác đúng. Cần suy nghĩ lại vậy. Nhưng chẳng lẽ không áp dụng phương pháp quy nạp được? Nghĩa là từ trường hợp riêng=>trường hợp chung? Trong trường hợp riêng thì toán học đâu có cấm thử tất cả các các phương án có thể. Ví dụ 2 bi, 100 tầng thì sau khi thử hết ta thấy là k=14 là số nhỏ nhất rồi.

[tuhiep]

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.

[RDSS]

gởi RDSS & ThanhLongBien
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).



Mình dịch qua google thấy viết là quy nạp nên mình viết vậy, không hiểu có chính xác không?

[MRAQ2000]

Đọc các bài viết của các bác RDSS - ThanhLongBien - Tuhiep mà kính nể quá. Các bác đang dùng toán (hoặc là cái gì đó) để nhét vào Góc mỹ nhân :lamdang, thán phục - than phục bội phần :baiphuc1.

[RDSS]

gởi RDSS & ThanhLongBien
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).


Thấy dịch ra tiếng việt có mấy từ như: cảm ứng, khởi, quy nạp , nhưng từ quy nạp là khó hiểu nhất nên mình chọn đấy bạn. Để chứng tỏ là mình hiểu biết nhiều!

[RDSS]

Đọc các bài viết của các bác RDSS - ThanhLongBien - Tuhiep mà kính nể quá. Các bác đang dùng toán (hoặc là cái gì đó) để nhét vào Góc mỹ nhân :lamdang, thán phục - than phục bội phần :baiphuc1.

Biết làm sao được Bác, khi mà chủ đề nằm ở đây rồi, còn admin không chịu chuyển đi.Nhưng về một góc độ nào đó toán học cũng hút hồn không kém gì mỹ nhân đâu!

[RDSS]

Các bác đoán xem đây là nguyên tố gì nhé:
Nguyên tố : 115 .

Ký hiệu : Fm

Người tìm ra : Adam

Khối lượng nguyên tử : 60 kg; đồng vị có thể từ 40 đến 250 kg .

Phổ biến : Rất phổ biến .

Tính chất vật lý:
Mềm ra nhờ một số tác động nhất định.
Có thể sôi hoặc lạnh một cách bất ngờ mà không có sự tác động từ bên ngoài.
Hệ số giãn nở : tăng theo thời gian.
Lõm vào và nở ra ở một số nơi khi có sức ép.

Tính chất hóa học .
Có phản ứng rất tốt với Au, Ag, Pt và các kim loại hiếm khác hay với đá quý như kim cương, hồng ngọc.....
Hấp thụ các chất đắt tiền với số lượng lớn.
Đột nhiên có thể phát nổ .
Nhanh chóng bão hòa với ethanol.
Mức độ tích cực thay đổi tùy theo thời gian trong ngày .

ÁP DỤNG .
Được sử dụng rộng rãi cho mục đích trang trí, đặc biệt là trong xe thể thao.
Là chất làm sạch và tẩy rửa rất hiệu quả.
Có khả năng giúp thư giãn và giảm căng thẳng nếu biết sử dụng.

Phản ứng xác định.
Sẽ đổi thành màu xanh hoặc tím, đỏ... nếu có một mẫu chất lượng cao hơn bên cạnh.

CẦN LƯU Ý!!!
Khi rơi vào tay người thiếu kinh nghiệm là một mối nguy hiểm nghiêm trọng!!!
Không được phép giữ nhiều hơn một mẫu. Tuy nhiên cũng có thể giữ số lượng các mẫu nhiều tùy ý, nhưng bắt buộc phải cách ly chúng rất xa nhau để chúng không tương tác với nhau.

[ThanhLongBin]

Các bác đoán xem đây là nguyên tố gì nhé:
Nguyên tố : 115 .

Ký hiệu : Fm

Người tìm ra : Adam

Khối lượng nguyên tử : 60 kg; đồng vị có thể từ 40 đến 250 kg .

Phổ biến : Rất phổ biến .

Tính chất vật lý:
Mềm ra nhờ một số tác động nhất định.
Có thể sôi hoặc lạnh một cách bất ngờ mà không có sự tác động từ bên ngoài.
Hệ số giãn nở : tăng theo thời gian.
Lõm vào và nở ra ở một số nơi khi có sức ép.

Tính chất hóa học .
Có phản ứng rất tốt với Au, Ag, Pt và các kim loại hiếm khác hay với đá quý như kim cương, hồng ngọc.....
Hấp thụ các chất đắt tiền với số lượng lớn.
Đột nhiên có thể phát nổ .
Nhanh chóng bão hòa với ethanol.
Mức độ tích cực thay đổi tùy theo thời gian trong ngày .

ÁP DỤNG .
Được sử dụng rộng rãi cho mục đích trang trí, đặc biệt là trong xe thể thao.
Là chất làm sạch và tẩy rửa rất hiệu quả.
Có khả năng giúp thư giãn và giảm căng thẳng nếu biết sử dụng.

Phản ứng xác định.
Sẽ đổi thành màu xanh hoặc tím, đỏ... nếu có một mẫu chất lượng cao hơn bên cạnh.

CẦN LƯU Ý!!!
Khi rơi vào tay người thiếu kinh nghiệm là một mối nguy hiểm nghiêm trọng!!!
Không được phép giữ nhiều hơn một mẫu. Tuy nhiên cũng có thể giữ số lượng các mẫu nhiều tùy ý, nhưng bắt buộc phải cách ly chúng rất xa nhau để chúng không tương tác với nhau.
Ủng hộ "Phát minh" của bác RDSS.
Bổ sung một số tính chất mới:
1. Lý học
- Chịu tác động theo chu kỳ vận động của Mặt Trăng. Lực tương tác này khác hẳn với 4 loại tương tác đã biết: Điện-Từ, tương tác mạnh, tương tác yếu và lựuc hấp dẫn.
- Có khả năng phân rã thành nhiều "nhân bản" không biết trước với một lượng "xúc tác" rất không đáng kể. Phản ứng "phân rã" không tuân thủ Định luật bảo toàn khối lượng của M.Lomonosov
2. Hóa học
- Tham gia phản ứng "Ô-xy hóa khử" khi gặp nguyên tố M trong môi trường phù hợp. Sản phẩm của phản ứng là nhiệt + nước + tiếng ồn!

Mời các bạn nghiên cứu và bổ sung tiếp .... :D :D :D

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

[tuhiep]

gởi ThanhLongBien
"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é! "
mình dùng qui nạp chứng minh bảng "H" đúng với k nhỏ nhất trong cách thử bi với N tầng đó chứ.

mình trình bày sơ lại nhé.Gốc số 1 hàng b=1 và cột k=1 là tuyệt đối đúng; b=1 và N=1 thì k=1 là hiển nhiên.
cột k=1, cũng quá đúng; vì b nhiều cũng vô ích, vì N=1 chỉ cần k=1 là xong.
dòng b=1, vẫn đúng với N=S(1.k)với k=N,có bao nhiêu tầng cần bấy nhiêu lần thử. vì chọn k<N thì không thử hết được(gọi k=N là đúng cho tiện,nghĩa là k<>N là thừa hoặc thiếu).
H(b+1,k+1)=H(b+1,k)+H(b,k)=>H(b+1,k+1)=S(b,k)+1 ......(1)
và chọn N(max)=S(b,k) là cách phải chọn để k đúng (theo ý trên) mà mình phải chứng minh.

Mình dùng qui nạp chứng minh bảng mình đúng; và chọn N(max)=S(b,k) là cách chọn k đúng như sau.
Ta có N tầng và b bi, chọn tầng x thử lần 1. Chỉ có 2 tình huống xãy ra: bi vở hoặc bi không vở.
bi vở: ta còn (x-1)tầng phải thử với (b-1)bi.nên (x-1)=S(b-1,k-1).
bi không vở N-x=S(b,k-1).
vậy N=S(b,k-1)+S(b-1,k-1)+1
=> N=S(b,k-1)+H(b,k)=S(b,k)=H(b+1,k+1)-1.
vậy chọn k đúng.
Mình chứng minh bảng "H" đúng là ý nầy đấy.

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

[ThanhLongBin]

gởi ThanhLongBien
"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é! "
mình dùng qui nạp chứng minh bảng "H" đúng với k nhỏ nhất trong cách thử bi với N tầng đó chứ.

mình trình bày sơ lại nhé.Gốc số 1 hàng b=1 và cột k=1 là tuyệt đối đúng; b=1 và N=1 thì k=1 là hiển nhiên.
cột k=1, cũng quá đúng; vì b nhiều cũng vô ích, vì N=1 chỉ cần k=1 là xong.
dòng b=1, vẫn đúng với N=S(1.k)với k=N,có bao nhiêu tầng cần bấy nhiêu lần thử. vì chọn k<N thì không thử hết được(gọi k=N là đúng cho tiện,nghĩa là k<>N là thừa hoặc thiếu).
H(b+1,k+1)=H(b+1,k)+H(b,k)=>H(b+1,k+1)=S(b,k)+1 ......(1)
và chọn N(max)=S(b,k) là cách phải chọn để k đúng (theo ý trên) mà mình phải chứng minh.

Mình dùng qui nạp chứng minh bảng mình đúng; và chọn N(max)=S(b,k) là cách chọn k đúng như sau.
Ta có N tầng và b bi, chọn tầng x thử lần 1. Chỉ có 2 tình huống xãy ra: bi vở hoặc bi không vở.
bi vở: ta còn (x-1)tầng phải thử với (b-1)bi.nên (x-1)=S(b-1,k-1).
bi không vở N-x=S(b,k-1).
vậy N=S(b,k-1)+S(b-1,k-1)+1
=> N=S(b,k-1)+H(b,k)=S(b,k)=H(b+1,k+1)-1.
vậy chọn k đúng.
Mình chứng minh bảng "H" đúng là ý nầy đấy.

Tôi thấy cách bác làm như vậy là thiếu chặt chẽ.
Ta có đầu vào là số bi=b, số tầng =N.
Bác có thể cố định số N và quy nạp theo b, tức là cho b chạy. Khi đó, số k là một con số hoàn toàn xác định theo cặp số (b,N) thỏa mãn điều kiện:
S(b,k-1) < N <=S(b,k); với S(b,k) theo công thức đã biết.
Như vậy, k =k(b,N) là một hàm của 2 biến b,N
Theo phương pháp Quy nạp, bác phải làm 3 bước:
1. Kiểm tra với b=1,2... Số giá trị cụ thể của b cần kiểm tra phụ thuộc vào phương pháp chứng minh ở Bước#3 sau này.
2. Giả thiết rằng "Điều phải chứng minh" đã đúng với mọi giá trị b <= B bất kỳ!
3. Cần phải CM rằng, "Điều phải chứng minh" cũng đúng với b=B+1 dựa trên giả thiết trên.
Trong cách làm của bác, số N tự nhiên lại bị "trói" bằng những giá trị dạng N=S(b,k), trong khi đó, ta phải CM với N bất kỳ cơ mà!
Tiếp nữa, khi N cố định, b tăng 1 đơn vị ,tức là b=B+1, thì k(b,N) cũng thay đổi và khá phức tạp đấy!

[RDSS]

Tôi thấy cách bác làm như vậy là thiếu chặt chẽ.
Ta có đầu vào là số bi=b, số tầng =N.
Bác có thể cố định số N và quy nạp theo b, tức là cho b chạy. Khi đó, số k là một con số hoàn toàn xác định theo cặp số (b,N) thỏa mãn điều kiện:
S(b,k-1) < N <=S(b,k); với S(b,k) theo công thức đã biết.
Như vậy, k =k(b,N) là một hàm của 2 biến b,N
Theo phương pháp Quy nạp, bác phải làm 3 bước:
1. Kiểm tra với b=1,2... Số giá trị cụ thể của b cần kiểm tra phụ thuộc vào phương pháp chứng minh ở Bước#3 sau này.
2. Giả thiết rằng "Điều phải chứng minh" đã đúng với mọi giá trị b <= B bất kỳ!
3. Cần phải CM rằng, "Điều phải chứng minh" cũng đúng với b=B+1 dựa trên giả thiết trên.
Trong cách làm của bác, số N tự nhiên lại bị "trói" bằng những giá trị dạng N=S(b,k), trong khi đó, ta phải CM với N bất kỳ cơ mà!
Tiếp nữa, khi N cố định, b tăng 1 đơn vị ,tức là b=B+1, thì k(b,N) cũng thay đổi và khá phức tạp đấy!

Bác nói vậy thì em sẽ nghĩ kỹ hơn lời giải của Bác TuHiep vậy. Nhưng về nguyên tắc em thấy Bác TuHiep trình bày vậy là đúng đấy chứ.

[tuhiep]

cm qui nạp
"Ta có N tầng và b bi, chọn tầng x thử lần 1. Chỉ có 2 tình huống xãy ra: bi vở hoặc bi không vở.
bi vở: ta còn (x-1)tầng phải thử với (b-1)bi.nên (x-1)=S(b-1,k-1).
bi không vở N-x=S(b,k-1).
vậy N=S(b,k-1)+S(b-1,k-1)+1".

mình chứng minh k nhỏ nhất thoả mãn 1 N đã biết theo từng mảng nên khó hiểu rồi.
với b,k đã biết Nmax=S(b,k)hay Nmax=H(b+1,k+1)-1 là kết quả chứ không là trói buột.
Trở lại bảng "H", hàng b=1, và cột k=1 là kết quả đúng trực quan.
với b=2 và k=2 thì : chọn tầng x thử lần 1,vì chỉ còn k=1, nên phía trên tối đa chỉ còn 1 tầng, phía dưới cũng chỉ 1 tầng. vậy Nmax=3.
với b=2 và k=3 thì : chọn tầng x thử lần 1,các tầng phía dưới x chỉ có b=1 và k=2 nên tối đa chỉ có 2 tầng, tầng phía trên x tối đa 3 tầng (vì b=2,k=2) . vậy Nmax=6=Nmax(b=2,k=2)+Nmax(b=1,k=2)+1
tôi đề nghị viết ở vị trí H(b=2,k=4) có giá trị là S(1,k-1)+1=4.
tôi thực nghiệm chọn tầng x thử và kq: Nmax(b=2,k=4)=Nmax(b=2,k=3)+Nmax(b=1,k=3)+1=6+3+1=10=Nmax(b=2,k=3)+H(b=2,k=4).
Với cách viết H(b,k)=S(b-1,k-1)+1 tôi CM được H(b,k)=H(b,k-1)+H(b-1,k-1) cho dể khi lập bảng "H".
trên là giới thiệu bảng "H", và với cách kí hiệu như bạn ThanhLongBien đề nghị.

Tới đây tôi đề nghị công thức với b cho trước thì Nmax tương ứng k lần thử là Nmax(b,k)=S(b,k) "dpcm"
với b=1, trực quan thấy "dpcm" đúng.
với b=2, k=1 "dpcm" đúng; nếu "dpcm" đúng đến k=n, thì ta có:
Nmax(2,n+1)=Nmax(2,n)+Nmax(1,n)+1 ...(KQ việc chọn 1 tầng x để thử lần 1)
Nmax(2,n+1)=S(2,n)+S(1,n)+1=S(2,n)+H(2,n+1)=S(2,n+1).
vậy dòng b=2 có "dpcm" đúng.
tương tự, nếu b=n đúng tôi chứng minh dể dàng "dpcm" đúng với b=n+1.
vậy Nmax(b,k)=S(b,k).

[ThanhLongBin]

cm qui nạp
"Ta có N tầng và b bi, chọn tầng x thử lần 1. Chỉ có 2 tình huống xãy ra: bi vở hoặc bi không vở.
bi vở: ta còn (x-1)tầng phải thử với (b-1)bi.nên (x-1)=S(b-1,k-1).
bi không vở N-x=S(b,k-1).
vậy N=S(b,k-1)+S(b-1,k-1)+1".

mình chứng minh k nhỏ nhất thoả mãn 1 N đã biết theo từng mảng nên khó hiểu rồi.
với b,k đã biết Nmax=S(b,k)hay Nmax=H(b+1,k+1)-1 là kết quả chứ không là trói buột.
Trở lại bảng "H", hàng b=1, và cột k=1 là kết quả đúng trực quan.
với b=2 và k=2 thì : chọn tầng x thử lần 1,vì chỉ còn k=1, nên phía trên tối đa chỉ còn 1 tầng, phía dưới cũng chỉ 1 tầng. vậy Nmax=3.
với b=2 và k=3 thì : chọn tầng x thử lần 1,các tầng phía dưới x chỉ có b=1 và k=2 nên tối đa chỉ có 2 tầng, tầng phía trên x tối đa 3 tầng (vì b=2,k=2) . vậy Nmax=6=Nmax(b=2,k=2)+Nmax(b=1,k=2)+1
tôi đề nghị viết ở vị trí H(b=2,k=4) có giá trị là S(1,k-1)+1=4.
tôi thực nghiệm chọn tầng x thử và kq: Nmax(b=2,k=4)=Nmax(b=2,k=3)+Nmax(b=1,k=3)+1=6+3+1=10=Nmax(b=2,k=3)+H(b=2,k=4).
Với cách viết H(b,k)=S(b-1,k-1)+1 tôi CM được H(b,k)=H(b,k-1)+H(b-1,k-1) cho dể khi lập bảng "H".
trên là giới thiệu bảng "H", và với cách kí hiệu như bạn ThanhLongBien đề nghị.

Tới đây tôi đề nghị công thức với b cho trước thì Nmax tương ứng k lần thử là Nmax(b,k)=S(b,k) "dpcm"
với b=1, trực quan thấy "dpcm" đúng.
với b=2, k=1 "dpcm" đúng; nếu "dpcm" đúng đến k=n, thì ta có:
Nmax(2,n+1)=Nmax(2,n)+Nmax(1,n)+1 ...(KQ việc chọn 1 tầng x để thử lần 1)
Nmax(2,n+1)=S(2,n)+S(1,n)+1=S(2,n)+H(2,n+1)=S(2,n+1).
vậy dòng b=2 có "dpcm" đúng.
tương tự, nếu b=n đúng tôi chứng minh dể dàng "dpcm" đúng với b=n+1.
vậy Nmax(b,k)=S(b,k).
Gửi bác Tuhiep,
Tôi rất khâm phục nhậy cảm toán học của bác.
Như ở các comment trước, tôi chưa từng viết rằng bác làm sai hay cách làm của bác khó hiểu! Cả tôi và bác RDSS đều hiểu mà.
Tôi chỉ muốn thấy sự chặt chẽ trong cách trình bày của bác mà thôi!
Có mấy điểm cần lưu ý trong lời giải của bác, nếu muốn đề cao tính logic của Toán học:
1. Chúng ta có 2 bài toán:
Bài 1 của bác RDSS: Cho trước (b,N), CMR số lần thử ít nhất là k, với k thỏa mãn:
S(b,k-1) < N <= S(b,k). Số k này luôn tồn tại và duy nhất với mọi cặp (b,N).
Bài 2 (của bác Tuhiep): Cho cặp số (b,k). CMR số tầng nhiều nhất có thể kiểm tra Nmax = S(b,k)
Về mặt cảm tính, 2 bài này hoàn toàn tương đương nhau, chỉ cần giải dc 1 bài là bài kia ko cần CM.
Tuy vậy, bác vẫn cần một chút biện luận để chứng minh tính chất tương đương này!
Tôi đã có kinh nghiệm "xương máu" với trường hợp tương tự. Hồi ấy, trong bài thi học sinh giỏi toán toàn Miền Bắc (trước năm 75), tôi bỏ qua cái khâu "biện luận tương đương" nên bị các thày trừ đi 1 điểm, kết quả là thiếu đúng 1/2 điểm thì dc Giải 3! Sau này thì chẳng còn cơ hội dc đi thi nữa! :D :D :D
2. Phép Quy nạp Toán học:
Bác đã áp dụng hoàn toàn đúng và logic khi CM Nmax(2,k) = S(2,k) với mọi k.
Với phần quy nạp theo b thì tính huống không như bác viết
"tương tự, nếu b=n đúng tôi chứng minh dể dàng "dpcm" đúng với b=n+1"
Nếu trong bài thi Toán (cái ông ThanhLongBin này có tính xấu hay mang Bài thi ra dọa người ta ! :D ), bác viết vậy thì sẽ bị phê là "ngộ nhận"!
Câu chuyện là như thế này:
Bước 1: Kiểm tra với b=2. Như đã CM, Nmax(2,k) = S(2,k) với mọi k.
Bước 2: Giả thiết rằng, với n bất kỳ:
Nmax(n,k) = S(n,k) với mọi k.
Bước 3: Ta cần CM : Nmax(n+1,k)=S(n+1,k).
Theo cách làm của bác, ta thử bi #1 ở tầng thứ x(1)=H(n+1,k).
Có 2 tình huống:
a. Bi vỡ: ta còn n bi với k-1 lần thử. Từ giả thiết ở bước 2, với số bi còn lại đúng = n, ta hoàn toàn rút ra dc dpcm.
b. Bi ko vỡ: Ta vẫn còn (n+1) bi và (k-1) lần thử. Bây giờ, Giả thiết #2 chẳng giúp gì dc ta, ta phải thử tiếp ở tầng x(2)= x(1) + H(n+1,k-1). lại có 2 tình huống "vỡ hoặc ko vỡ bi". Nếu vỡ thì lại theo Giả thiết #2 còn ko thì lại thử tiếp với x(3)=x(2)+ H(n+1,k-2).. Thao tác này có thể phải lặp lại k lần với 2*k tình huống có thể!!!
Ta cứ liệt kê ra hết các tình huống và dùng các tính chất đã dc CM của dãy H(b,k) và S(b,k)=> dpcm. Tôi và bác đều tin vậy, nhưng "các thày khắt khe" sẽ vẫn trừ điểm, nhưng chắc chỉ trừ 1/2 điểm thôi! :D :D :D
Như vậy, tôi đã chỉ ra sự khác biệt giữa quy nạp theo số lần thử và quy nạp theo số bi!

Bây giờ, ta chia tay với mấy "ông thầy khó tính" kia và chỉ giữa chúng ta với nhau, tôi trịnh trọng tuyên bố:
Bác Tuhiệp đã giải quyết trọn ven Bài toán thử bi ở trường hợp tổng quát! Xin chúc mừng bác.
Xin dc mời bác 1 ly cafe G7 3-in-1!
Chúc bác và các bạn hữu trên Diễn đàn TLKD một kỳ nghỉ cuối tuần vui vẻ!!!!
ThanhLongBin kính bút.

***********************************************************
Epilogue-Khúc vĩ thanh
Xin nhấn mạnh, tôi rất ấn tượng với "Dãy số Tuhiep H(b,k)".
Xin viết lại cho các bạn hữu tiện theo dõi:
H(1,k)=1;
H(2,k)=k;
H(b+1,k+1)=H(b+1,k) +H(b,k);
Tôi tin rằng, ai từng có "duyên nợ" với Toán đều ít nhiều cảm nhận dc cái đẹp của dãy số này.
Ngày xưa, nhà toán học Fibonacci nổi danh cũng nhờ dãy số 0,1,1,2,3,5,8,... F(n+1)=F(n)+F(n-1)....có tỷ số F(n+1)/F(n) hội tụ ở 1 giá trị duy nhất khi n tiến tới vô cùng. Đó chính là Tỷ số Hoàng kim (Golden Ratio), dc áp dụng trong nhiều kiến trúc tự nhiên cũng như nhân tạo!!!!
Xem: http://en.wikipedia.org/wiki/Golden_ratio#Relationship_to_Fibonacci_sequence
hoặc xem: http://vi.wikipedia.org/wiki/T%E1%BB%B7_l%E1%BB%87_v%C3%A0ng
Bác Tuhiep có quyền đăng ký "Bản quyền phát minh" nếu chưa ai tìm ra dãy H(b,k).
Dãy Fibonacci có công thức tổng quát:
F(n) = (Phi^n-(1-Phi)^n)/sqrt(5); với Phi là Tỷ số Hoàng kim = (1+sqrt(5))/2, sqrt(x) là căn bậc 2 của x.
Như vậy, H(b,k) cũng có thể có công thức tổng quát ở dạng Đa thức !?
Hình như tôi đang đẩy câu chuyện đi quá xa chăng?
Các bạn khác nghĩ gì về "Tỷ số Tuhiep", nếu có? Tôi xin mạn phép đặt tên trước là "Tỷ số Bạch kim" !!!!

[tuhiep]

gởi ThanhLongBien
"Với phần quy nạp theo b thì tính huống không như bác viết
"tương tự, nếu b=n đúng tôi chứng minh dể dàng "dpcm" đúng với b=n+1"
Nếu trong bài thi Toán (cái ông ThanhLongBin này có tính xấu hay mang Bài thi ra dọa người ta ! ), bác viết vậy thì sẽ bị phê là "ngộ nhận"!
Câu chuyện là như thế này:
Bước 1: Kiểm tra với b=2. Như đã CM, Nmax(2,k) = S(2,k) với mọi k.
Bước 2: Giả thiết rằng, với n bất kỳ:
Nmax(n,k) = S(n,k) với mọi k.
Bước 3: Ta cần CM : Nmax(n+1,k)=S(n+1,k).
Theo cách làm của bác, ta thử bi #1 ở tầng thứ x(1)=H(n+1,k).
Có 2 tình huống:
a. Bi vỡ: ta còn n bi với k-1 lần thử. Từ giả thiết ở bước 2, với số bi còn lại đúng = n, ta hoàn toàn rút ra dc dpcm.
b. Bi ko vỡ: Ta vẫn còn (n+1) bi và (k-1) lần thử. Bây giờ, Giả thiết #2 chẳng giúp gì dc ta, ta phải thử tiếp ở tầng x(2)= x(1) + H(n+1,k-1). lại có 2 tình huống "vỡ hoặc ko vỡ bi". Nếu vỡ thì lại theo Giả thiết #2 còn ko thì lại thử tiếp với x(3)=x(2)+ H(n+1,k-2).. Thao tác này có thể phải lặp lại k lần với 2*k tình huống có thể!!!"
xem ra phải qui nap thật tỉ mỉ rồi:

[tuhiep]

"dpcm"
"Bước 2: Giả thiết rằng, với n bất kỳ:
Nmax(n,k) = S(n,k) với mọi k.
Bước 3: Ta cần CM : Nmax(n+1,k)=S(n+1,k) với mọi k.
Theo cách làm của bác, ta thử bi #1 ở tầng thứ x(1)=H(n+1,k)."

khi có Nmax(n,k) = S(n,k) với mọi k. Ta cần CM : Nmax(n+1,k)=S(n+1,k) với mọi k.
Mình chứng minh như sau;
Nmax(n+1,1)=S(n+1,1)=1 (điều tất nhiên vì k=1 mà).khi k đúng ở 1 giá tri m bất kỳ.nghĩa là ta có Nmax(n+1,m)=S(n+1,m) tôi phải cm Nmax(n+1,m+1)=S(n+1,m+1). lấy 1 bi ra thử tầng x ta có ngay:
Nmax(n+1,m+1)=Nmax(n+1,m)+Nmax(n,m)+1 (như trên đã làm)
Nmax(n+1,m+1)=S(n+1,m)+S(n,m)+1=S(n+1,m)+H(n+1,m+1)=S(n+1,m+1) "dpcm"
vậy :
Nmax(n+1,k)=S(n+1,k) với mọi k
phép qui nạp với 2 biến b,k lần lượt chạy như trên có làm bạn hài lòng không.?
bây giờ chuẩn bị xem trận cờ TLKD Quí Tỵ tranh 3-4 rồi

[ThanhLongBin]

"dpcm"
"Bước 2: Giả thiết rằng, với n bất kỳ:
Nmax(n,k) = S(n,k) với mọi k.
Bước 3: Ta cần CM : Nmax(n+1,k)=S(n+1,k).
Theo cách làm của bác, ta thử bi #1 ở tầng thứ x(1)=H(n+1,k)."

khi có Nmax(n,k) = S(n,k) với mọi k. Ta cần CM : Nmax(n+1,k)=S(n+1,k).
Mình chứng minh như sau;
Nmax(n+1,1)=S(n+1,1)=1 (điều tất nhiên vì k=1 mà).khi k đúng đến 1 giá tri m bất kỳ Nmax(n+1,m)=S(n+1,m) tôi phải cm Nmax(n+1,m+1)=S(n+1,m+1). lấy 1 bi ra thử tầng x ta có ngay:
Nmax(n+1,m+1)=Nmax(n+1,m)+Nmax(n,m)+1 (như trên đã làm)
Nmax(n+1,m+1)=S(n+1,m)+S(n,m)+1=S(n+1,m)+H(n+1,m+1)=S(n+1,m+1) "dpcm"
vậy :
Nmax(n+1,k)=S(n+1,k)
Một lần nữa, bác lại có lời giải rất tuyệt!
Nếu có danh hiệu "Số học Đặc cấp Đại sư" tôi xin đề cử cho bác đầu tiên! :D

[RDSS]

Gửi bác Tuhiep,
Bây giờ, ta chia tay với mấy "ông thầy khó tính" kia và chỉ giữa chúng ta với nhau, tôi trịnh trọng tuyên bố:
Bác Tuhiệp đã giải quyết trọn ven Bài toán thử bi ở trường hợp tổng quát! Xin chúc mừng bác.
Xin dc mời bác 1 ly cafe G7 3-in-1!
Chúc bác và các bạn hữu trên Diễn đàn TLKD một kỳ nghỉ cuối tuần vui vẻ!!!!
ThanhLongBin kính bút.


Nhà toán học ThanhLongBin nói đúng rồi thì khỏi tranh cãi nữa. Nhưng algorithm cho các lần ném bi chưa có!!!!

[ThanhLongBin]

Nhà toán học ThanhLongBin nói đúng rồi thì khỏi tranh cãi nữa. Nhưng algorithm cho các lần ném bi chưa có!!!!

Chào bác RDSS,
Tại vì topic này kéo dài quá, nên chính bác là chủ cũng quên mất cả các kết quả trung gian!!! :D
Bác Tuhiep, có sự góp sức nho nhỏ của 2 ta, đã trình bày algorithm "Thả bi" lâu lâu rồi.
Đó chính là "Dãy số Tuhiep H(b,k)" sắp trở thành "Danh bất hư truyền"! Tôi rất hy vọng chưa có ai kịp nghĩ ra dãy số này trước bác ấy đâu!
Ở bài viết cuối, bác ấy dùng Phép quy nạp (Induction) để chứng minh đó là cách thử bi hiệu quả nhất với mọi cặp số (b,k)!

Bác RDSS chắc còn mải bình luận chiến thắng bất ngờ của Thần đồng GM Magnus Carlsen chứ gì?
Tôi đã đọc bản dịch rất hay của bác bài phân tích của GM E.Свешников về phong cách khai cuộc của Magnus. Bác có trình tiếng Nga và hiểu biết về cờ Vua quá cao. Chắc đã có thời ăn nhiều "bánh mì với muối" cũng như mất nhiều thời gian cho Tạp chí "64" (Tạp chí Cờ Vua) ở đất Nga ?. Hồi những năm đầu 80, tôi cũng hay lang thang ở Công viên Izmailovski-Moscow để coi M.Tal đánh "Blitz". Ở đó, có Giải cờ chớp Chủ nhật hàng tuần vào mùa Hè. Hầu như lần nào cũng thấy Михаил Нехемьевич ẵm cái ấm Samovar (là cái Cup đấy) mang về nhà! Ah! Too long ago!
PS. Nhờ bác sửa hộ cái chữ "Nhà toán học ThanhLongBin" nhé. Tôi bỏ học toán ngay từ hồi vào đại học mà. Với tôi, toán như "người yêu cũ" vậy. Các cụ nhà ta hay nói, "Tình cũ không rủ cũng đến", ấy là ứng với tôi chăng?

[RDSS]

Chào bác RDSS,
Tại vì topic này kéo dài quá, nên chính bác là chủ cũng quên mất cả các kết quả trung gian!!! :D
Bác Tuhiep, có sự góp sức nho nhỏ của 2 ta, đã trình bày algorithm "Thả bi" lâu lâu rồi.
Đó chính là "Dãy số Tuhiep H(b,k)" sắp trở thành "Danh bất hư truyền"! Tôi rất hy vọng chưa có ai kịp nghĩ ra dãy số này trước bác ấy đâu!
Ở bài viết cuối, bác ấy dùng Phép quy nạp (Induction) để chứng minh đó là cách thử bi hiệu quả nhất với mọi cặp số (b,k)!

Bác RDSS chắc còn mải bình luận chiến thắng bất ngờ của Thần đồng GM Magnus Carlsen chứ gì?
Tôi đã đọc bản dịch rất hay của bác bài phân tích của GM E.Свешников về phong cách khai cuộc của Magnus. Bác có trình tiếng Nga và hiểu biết về cờ Vua quá cao. Chắc đã có thời ăn nhiều "bánh mì với muối" cũng như mất nhiều thời gian cho Tạp chí "64" (Tạp chí Cờ Vua) ở đất Nga ?. Hồi những năm đầu 80, tôi cũng hay lang thang ở Công viên Izmailovski-Moscow để coi M.Tal đánh "Blitz". Ở đó, có Giải cờ chớp Chủ nhật hàng tuần vào mùa Hè. Hầu như lần nào cũng thấy Михаил Нехемьевич ẵm cái ấm Samovar (là cái Cup đấy) mang về nhà! Ah! Too long ago!
PS. Nhờ bác sửa hộ cái chữ "Nhà toán học ThanhLongBin" nhé. Tôi bỏ học toán ngay từ hồi vào đại học mà. Với tôi, toán như "người yêu cũ" vậy. Các cụ nhà ta hay nói, "Tình cũ không rủ cũng đến", ấy là ứng với tôi chăng?

Phải đọc lại vậy. Em không nhớ algorithm của Bác TuHiep. Còn đang buồn vì Anand thua thì đúng hơn. Tiếng nga em biết tốt nhưng tiếng việt lại kém. Tạp chí “64” ngày xưa tất nhiên là đọc rồi nhưng sức cờ của em kém lắm. Không được may mắn xem Tal chơi như Bác. “Nhà toán học” là không bỏ được rồi vì thích toán từ nhỏ là vào máu rồi Bác.

[kien1706]

lâu lâu không vào diễn đàn thấy mấy bác vẫn nhiệt tình post các bài toán :D. Thấy hay hay mà có vẻ hơi ít người tham gia vẫn 2 bác tuhiep với RDSS. mà nghe các bác nói thì chắc cũng khá khá tuổi rồi, chắc em phải gọi bằng chú mất. Các bác tuhiep với RDSS có thể tiết lộ tuổi dc ko . Em mỏ bát nhé em mới 27 tuổi :D. Em cúng khoái toán nhưng thấy các bác nhiều tuổi còn chịu khó đầu tư tìm tòi giải toán, em rất khâm phục !!

[RDSS]

lâu lâu không vào diễn đàn thấy mấy bác vẫn nhiệt tình post các bài toán :D. Thấy hay hay mà có vẻ hơi ít người tham gia vẫn 2 bác tuhiep với RDSS. mà nghe các bác nói thì chắc cũng khá khá tuổi rồi, chắc em phải gọi bằng chú mất. Các bác tuhiep với RDSS có thể tiết lộ tuổi dc ko . Em mỏ bát nhé em mới 27 tuổi :D. Em cúng khoái toán nhưng thấy các bác nhiều tuổi còn chịu khó đầu tư tìm tòi giải toán, em rất khâm phục !!

Mình 45 tuổi, gọi anh là được. Giải toán vui cho đầu óc thoải mái một chút thôi.

[tuhiep]

gởi kien1706
đã 30 năm không có dịp nhìn lại toán, thấy cũng vui. bây giờ mình đang sống ở tuổi 59, còn trẽ chán mà. Vui là 9.

[ThanhLongBin]

Mình 45 tuổi, gọi anh là được. Giải toán vui cho đầu óc thoải mái một chút thôi.
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.
Tôi ở ngoài Hà nội, bác Tư chắc đang hóng gió Sông Tiền còn bác RD lại phiêu lãng tận trời Âu.
Mượn lời một bậc tiền nhân để tức cảnh:
Quan san muôn dặm một nhà
Bốn phương "yêu Toán" đều là anh em...
Các bác và bạn kien1706 có nghĩ vậy không?

[ThanhLongBin]

Gửi RDSS,
Tôi mới học dc cách dùng FlashChess để post biên bản 1 van cờ Vua. Nếu như bác đã biết rồi thỉ coi như chưa đọc bài này nhé! :D
Lưu ý: Biên bản phải ghi đúng định dạng PGN (Portable Game Notation). Chi tiết xem ở đây: http://en.wikipedia.org/wiki/Portable_Game_Notation.
Để xem và Replay dc biên bản, PC của bác phải cái Adobe Flash Player.
Trang Web này đã cài sẵn bản Java ChessFlash của Glenn Wilson V2.14 có rất nhiều hạn chế nhất là không chấp nhận các thông tin phụ (comment, tiêu đề, thông tin Player...) của PGN format nên bác phải bỏ hết đi, chỉ để lại các thông tin về nước đi thôi!!!
Copy toàn bộ biên bản, chèn giữa 3 từ khóa của Flash như thế này:
{Flashchess},....... {/Flashchess}
Nhớ thay dấu "{" và "}' bằng dấu tương ứng "[" và "]"

Ví dụ một ván đấu có thể xảy ra trong tương lai:
Event "Super Final Match"
Site "Internet Online"
Date "2014.11.7"
Round "29"
White "RDSS, --"
Black "ThanhLong, Bin"
Debute: Ruy Lopez Defense
Result "1/2-1/2"
1. e4 e5 2. Nf3 Nc6 3. Bb5 a6 4. Ba4 Nf6 5. O-O Be7 6. Re1 b5 7. Bb3 d6 8. c3 O-O 9. h3 Nb8 10. d4 Nbd7 11. c4 c6 12. cxb5 axb5 13. Nc3 Bb7 14. Bg5 b4 15. Nb1 h6 16. Bh4 c5 17. dxe5 Nxe4 18. Bxe7 Qxe7 19. exd6 Qf6 20. Nbd2 Nxd6 21. Nc4 Nxc4 22. Bxc4 Nb6 23. Ne5 Rae8 24. Bxf7+ Rxf7 25. Nxf7 Rxe1+ 26. Qxe1 Kxf7 27. Qe3 Qg5 28. Qxg5 hxg5 29. b3 Ke6 30. a3 Kd6 31. axb4 cxb4 32. Ra5 Nd5 33. f3 Bc8 34. Kf2 Bf5 35. Ra7 g6 36. Ra6+ Kc5 37. Ke1 Nf4 38. g3 Nxh3 39. Kd2 Kb5 40. Rd6 Kc5 41. Ra6 Nf2 42. g4 Bd3 43. Re6

[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 RDSS
nó không là 1 bài mà rải từng bước.
khi mình nêu cách lập bảng, lấy kết quả làm tiền đề nên gây hiểu nhầm.
khởi đầu H(b+1,k+1)=S(b,k)+1; khi viết bảng vài hàng mình nhận ra H(b+1,k+1) là tổng 2 số liền trước trái và liền trước trên để viết tiếp cho nhanh. Mình nhận ra Nmax(b,k)=S(b,k) và dùng KQ nầy trả lời cho bạn (vì chỉ cần nêu đáp án đúng thôi mà).
Khi tìm S(b,k) thì áp đặt Nmax(b,k)=S(b,k)"*"; bạn ThanhLongBien đã nhận ra điều nầy.
vậy mình phải chứng minh "*" đúng mới được.
do vậy bạn xem lại 2 hay 3 bài viết của mình.

về cờ vua thì mình mù tịt. Phần mềm cờ tướng thì mình thích dùng ccbridge thôi. soft nầy có nhiều tính ưu mà mình thích,và cần.
cái dở là dùng test các nước đi thử nghiệm, nên mình dùng 1 soft nữa cho việc nầy.
soft test các nước đi thử nghiệm kẹt ở chổ bản quyền, nên mình chỉ dùng soft share thôi (thường là lạc hậu rồi), nên khã năng phân tích nước đi còn kém.

[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]

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)

:D :D :D

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é!)

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

[tuhiep]

bảng "H"
mình vừa nhìn thấy bảng "H" và tam giác Pascal có mối quan hệ đấy.
trong 1 cột của bảng"H" hiệu của số dưới trừ số liền trên là 1 dãy số tương ứng với 1 hàng của tam giác Pascal.
mà mỗi hàng cũa tg Pascal là 1 dãy số của hệ thức Newton.

[ThanhLongBin]

bảng "H"
mình vừa nhìn thấy bảng "H" và tam giác Pascal có mối quan hệ đấy.
trong 1 cột của bảng"H" hiệu của số dưới trừ số liền trên là 1 dãy số tương ứng với 1 hàng của tam giác Pascal.
mà mỗi hàng cũa tg Pascal là 1 dãy số của hệ thức Newton.
Em ko thấy vậy, bác ạ.
Trong Tam giác Pascal, ở mỗi hàng n, số cột luôn bị hạn chế và = n+1 !
Còn bảng H(b,k), hai chỉ số b,k hoàn toàn độc lập với nhau!
Em vẫn thấy có cái gì đó liên hệ giữa Dãy H(b,k) và Dãy Fibonacci!

[ThanhLongBin]

Em viết chưa hết ý: Đúng là chúng ta đã chứng minh tính chất này:
S(b,k+1) = Tổng (C(n,n+k-1), n=0..b)!
Khi đó, em viết sai dấu +/-1 , bác đã sửa cho em. Đúng ko? :D
Trong đó C(i,j) chính là các hệ số của Tam giác Pascal mà!

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

[RDSS]

Em ko thấy vậy, bác ạ.
Trong Tam giác Pascal, ở mỗi hàng n, số cột luôn bị hạn chế và = n+1 !
Còn bảng H(b,k), hai chỉ số b,k hoàn toàn độc lập với nhau!
Em vẫn thấy có cái gì đó liên hệ giữa Dãy H(b,k) và Dãy Fibonacci!

Em lại không thấy sự lien hệ nào giữa hai dãy số này Bác ạ.

[ThanhLongBin]

Em lại không thấy sự lien hệ nào giữa hai dãy số này Bác ạ.

Mình thử cái này nhé:
Dãy H(b,k) dc dựng trên cở sở 3 Tiên đề
TĐ#1:
H(1,k)=1 với mọi k ;
TĐ#2:
:H(b,1)= 1 với mọi b
TĐ#3:
Với b,k >=1 bất kỳ
H(b+1,k+1)= H(b+1,k) +H(b,k).
Mình gọi là Tiên đề vì bác Tư coi mấy quan hệ này là không cần chứng minh.

Mình quan tâm nhất đến TĐ#3 vì nó có vẻ quan trọng nhất, có nhiều ảnh hưởng nhất! Cảm tính thôi nhé! :D
Giả thiết, tồn tại 1 số a nào đó có tính chất sau:
a^2 = a+1 (1)
Đây là phương trình bậc 2 có 2 nghiệm là
a1,a2 = (1+/- sqrt(5))/2 (2).
Nhân 2 vế (1) với số a^(b+k) ta dc:
a^(b+k+2)=a*(b+k+1) + a^(b+k) (3).
Xét dãy U(b,k) =a^(b+k) (3*).
Từ (3) => U(b+1,k+1) = U(b+1,k) + U(b,k); với mọi cặp (b,k) (4).
Bạn có thấy (4) và TĐ#3 chẳng có gì khác nhau cả? :D
Tuy vậy, dãy U(b,k) chưa phải là dãy H(b,k) vì chưa thỏa mãn 2 TĐ còn lại!
Ta thay a= a1,a2 trong (3*) và nhận dc 2 dãy U1(b,k) và U2(b,k) khác nhau.
Dễ dàng thấy, với mọi cặp số thực bất kỳ (r1,r2), dãy số sau đây:
R(b,k) =r1*U1 + r2*U2 cũng thỏa mãn TĐ#3.
Mình hy vọng, có thể tìm dc cặp số (r1,r2) thích hợp, để R(b,k) cũng thỏa mãn 2 TĐ còn lại thì ta sẽ nhận dc Công thức tổng quát của H(b,k) ở dạng đa thức !!!! Hay chưa???

Trong trường hợp đặc biệt, với r1=-r2= 1/sqrt(5),
dãy số R ta gọi là RD, có dạng:
R(b,k)= RD(n=b+k)= (a1^n -a2^n)/sqrt(5) (5).
Dãy RD(n) có mấy tính chất rất hay:
1.RD(0)=0.
2.RD(1)=1.
3.RD(2)=1.
...RD(n+2)=RD(n+1) + RD(1)

Đây chính là dãy Fibonacci nổi tiếng mà!!! :D :D :D

Mình nhờ RDSS tìm hộ cặp số kỳ diệu (r1,r2) để biến cái dãy R(b,k) thành dãy H(b,k) !!!!

[ThanhLongBin]

Lời dẫn: Bài toán vui này đã đăng từ trước nhưng vẫn chưa có ai giải. Sau khi Diễn đàn bị mất khá nhiều dữ liệu kể cả bài viết này, vậy xin phép đăng lại cho anh em cùng thư giãn.

Đầu bài: Có 46 bụi cây xếp thành vòng tròn. Trên mỗi bụi cây có 1 chú chim sâu đang đậu.Các chú chim này rất vui tính: tại mỗi thời điểm bất kỳ, có đúng 2 chú chim sâu bay sang bụi cây ở ngay bên cạch nhưng theo chiều bay ngược nhau: một con theo chiều kim đồng hồ, con kia theo chiều ngược lại.
Chứng minh rằng, không bao giờ xảy ra tình huống để có tất cả các chú chim sâu đậu trên cùng một bụi cây!
Mời các bạn yêu cờ-yêu toán cùng giải trí nhé!

[ThanhLongBin]

Lời dẫn: Bài toán vui này đã đăng từ trước nhưng vẫn chưa có ai giải. Sau khi Diễn đàn bị mất khá nhiều dữ liệu kể cả bài viết này, vậy xin phép đăng lại cho anh em cùng thư giãn.

Đầu bài: Có 46 bụi cây xếp thành vòng tròn. Trên mỗi bụi cây có 1 chú chim sâu đang đậu.Các chú chim này rất vui tính: tại mỗi thời điểm bất kỳ, có đúng 2 chú chim sâu bay sang bụi cây ở ngay bên cạch nhưng theo chiều bay ngược nhau: một con theo chiều kim đồng hồ, con kia theo chiều ngược lại.
Chứng minh rằng, không bao giờ xảy ra tình huống để có tất cả các chú chim sâu đậu trên cùng một bụi cây!
Mời các bạn yêu cờ-yêu toán cùng giải trí nhé!

Chào bác Tư, chào bạn RDSS và tất cả các bạn trong Diễn đàn.
Lâu quá rồi, vì nhiều lẽ khác nhau, nay tôi mới có dịp quay lại Diễn đàn.
Té ra bài vở vẫn còn mà người cũ chẳng thấy còn ai!
Nhẽ chăng, mạng ảo cũng như trong đời thực, hợp rồi lại tan , tan rồi lại hợp theo lẽ thường tình!
Mong lắm một phản hồi dù rất nhỏ của bác Tư và bạn RDSS!

Quay lại Bài "Những chú chim sâu..." một tí. Có lẽ cách trình bày đầu bài chưa dc rõ ràng, nay xin phép bổ sung cho thêm phần tường minh:
Đầu bài:
Có 46 bụi cây xếp thành vòng tròn và 1 cậu bé đứng thổi còi! Trên mỗi bụi cây có 1 chú chim sâu đang đậu.Các chú chim này rất vui tính: Mỗi khi cậu bé thổi 1 tiếng còi, thì có đúng 2 chú chim sâu bất kỳ, đang ở các bụi cây bất kỳ (có thể ở cùng 1 bụi cây cũng được!) , bay sang bụi cây ở ngay bên cạch nhưng theo chiều bay ngược nhau: một con theo chiều kim đồng hồ, con kia theo chiều ngược lại.
Chứng minh rằng, không bao giờ xảy ra tình huống để có tất cả các chú chim sâu đậu trên cùng một bụi cây!

Cái "cậu bé thổi còi" ở đây đóng vai trò giữ nhịp, đồng bộ các chuyến bay tới, bay lui của lũ chim mà thôi!!!!

Rất mong hồi âm

[nghiepdu]

Em xin giải bài này bằng phương pháp giới tính như sau. Giả sử tại trạng thái ban đầu 46 con chim xếp xen kẽ đực cái. Vậy có 23 con cái và 23 con đực. Giả sử tiếp mỗi một lần nhảy đều khiến con chim thay đổi giới tính của mình: đực thành cái, và cái thành đực. Dễ thấy các con trên cùng 1 cây luôn có cùng giới tính. Mỗi lần nhảy đều rơi vào 1 trong các tình huống sau:
- 2 con đực nhảy thành 2 con cái
- 2 con cái nhảy thành 2 con đực
- 1 con cái và 1 con đực nhảy thành 1 con đực và 1 con cái
Trong mọi trường hợp thì số con đực và số con cái ko thay đổi tính chẵn lẻ. Khi 46 con chui vào cùng 1 cây thì nó sẽ là 46 con cái hoặc 46 con đực. Vậy số đực cái khác tính chẵn lẻ với số đực cái ban đầu. Điều này ko thể xảy ra.

[ThanhLongBin]

Chào bạn nghiepdu. Chúc mừng bạn đã có lời giải rất hay và độc đáo.
Bài toán này tôi đã đăng ở Diễn đàn gần 4 tháng rồi, rất may là nhờ có bạn, nay đã có lời giải!
Bạn thử xét trường hợp tổng quát với số chim n=2k bất kỳ xem sao nhé? Lưu ý, trong đầu bài, có 1 điều kiện mà bạn chưa cần dùng đến với với trường hợp n=46.
"một con bay theo chiều kim đồng hồ, con kia theo chiều ngược lại"

[zzz]

Bạn thử xét trường hợp tổng quát với số chim n=2k bất kỳ xem sao nhé? Lưu ý, trong đầu bài, có 1 điều kiện mà bạn chưa cần dùng đến với với trường hợp n=46.
"một con bay theo chiều kim đồng hồ, con kia theo chiều ngược lại"

Với n=4*m + 2 thì dùng cách đánh dấu âm dương được, còn n = 4*m (nghĩa là k chẵn) thì cách âm dương không dùng được, lúc đó kết hợp với giả thiết "hai con bay ngược chiều" thì có lẽ cũng sẽ không thoả, nhưng phải dùng một biểu diễn tập hợp đó ở một đặc trưng khác để sao cho thực hiện phép biến đổi thì trạng thái giữ nguyên đặc trưng đó nhưng đặc trưng đó sẽ không thoả ở trạng thái đích (đánh dấu "âm dương" hay "đực cái" là một đặc trưng để giải trường hợp trên).

Đó có lẽ là nguyên lý chung để giải các bài toán dạng này.

[ThanhLongBin]

Chào bác zzz,
Lâu lâu mới quay lại thăm Diễn đàn, thấy bác vẫn phong độ như xưa.
Về bài toán này, mấu chốt chính là ở cách xây dựng "Hàm đánh giá" với đặc trưng như bác đã viết.
Bác thử cho vài gợi ý nhé?
Chúc vui.

[MRAQ2000]

Chào các bạn.

Mình có 1 hướng giải cho trường hợp tổng quát n=2*k.
Trước hết gọi mc(k) là số chim lớn nhất trên 1 bụi cây, ta dễ chứng minh được mc(k)+2 >= mc(k+1)
Giờ dùng phép qui nạp
- Dễ thấy bài toán đúng với k=1 (n=2)
- Giả sử bài toán đung với k, tức là mc(k) < 2*k => mc(k+1) < 2*(k+1) => bài toán đúng với k+1.
Vậy bài toán đúng với mọi trường hợp.

[nghiepdu]

Lúc đầu tôi cũng nghĩ có thể dùng quy nạp, nhưng sau thấy ko có cách nào lồng 1 vòng tròn 2*n cây vào trong 1 vòng tròn 2*n+2 cây (vì các cây đòi hỏi phải liên tiếp) nên nghĩ là khó vận dụng. Như bác Thanhlong đã viết, với số cây chẵn lời giải cần phải sử dụng chi tiết "nhảy ngược chiều và nhảy cùng chiều", sau đây là một đề xuất lời giải.
Đánh số các cây theo chiều kim đồng hồ theo thứ tự 0,1,2,…,n,-n+1,-n+2,…,-2,-1. Trục 0 và n giống như trục 12h-6h trên đồng hồ.
Giả sử lúc đầu mỗi con chim chỉ có 1 chân. Giả sử nếu nhảy theo chiều kim đồng hồ số chân giảm đi 1, nếu nhảy ngược chiều kim đồng hồ số chân tăng lên 1.
Mỗi 1 lần nhảy có 1 con chim tăng lên 1 chân, 1 con chim giảm đi 1 chân nên tổng số chân chim không đổi là 2*n.
Không mất tính tổng quát giả sử sẽ có lúc tất cả các con chim gặp nhau ở cây 0.
Con chim ở cây i, khi hội tụ ở 0 sẽ có số chân là 1+ i + h*2*n, với h là hệ số có thể âm có thể dương, tùy theo con chim nhảy về 0 rồi lại nhảy thêm vài vòng tròn xuôi ngược.

Như vậy khi tính tổng số chân chim tại vị trí 0 thì nó sẽ là 2*n + n + x*2*n. Sở dĩ +n đó là vì các cặp (1, -1), (2, -2),… triệt tiêu cho nhau, và con dư một con ở cây n vị trí 6h. Nói tóm lại tổng số chân chim là n + bội số của 2*n. Nhưng số này lại bằng 2*n ko đổi. Điều này ko thể xảy ra vì n không chia hết cho 2*n.

[ThanhLongBin]

Chào các bạn.

Mình có 1 hướng giải cho trường hợp tổng quát n=2*k.
Trước hết gọi mc(k) là số chim lớn nhất trên 1 bụi cây, ta dễ chứng minh được mc(k)+2 >= mc(k+1)
Giờ dùng phép qui nạp
- Dễ thấy bài toán đúng với k=1 (n=2)
- Giả sử bài toán đung với k, tức là mc(k) < 2*k => mc(k+1) < 2*(k+1) => bài toán đúng với k+1.
Vậy bài toán đúng với mọi trường hợp.

Chào bạn MRAQ2000,
Phương pháp Quy nạp của bạn là một lựa chọn rất tự nhiên. Tuy vậy, khâu quan trọng nhất là phải CMR:
mc(k+1) < mc(k)+2
thì bạn lại chỉ suy diễn, coi đó là hiển nhiên!
Bạn thử chứng minh điều đó một cách chặt chẽ hơn nhé!

[ThanhLongBin]

Lúc đầu tôi cũng nghĩ có thể dùng quy nạp, nhưng sau thấy ko có cách nào lồng 1 vòng tròn 2*n cây vào trong 1 vòng tròn 2*n+2 cây (vì các cây đòi hỏi phải liên tiếp) nên nghĩ là khó vận dụng. Như bác Thanhlong đã viết, với số cây chẵn lời giải cần phải sử dụng chi tiết "nhảy ngược chiều và nhảy cùng chiều", sau đây là một đề xuất lời giải.
Đánh số các cây theo chiều kim đồng hồ theo thứ tự 0,1,2,…,n,-n+1,-n+2,…,-2,-1. Trục 0 và n giống như trục 12h-6h trên đồng hồ.
Giả sử lúc đầu mỗi con chim chỉ có 1 chân. Giả sử nếu nhảy theo chiều kim đồng hồ số chân giảm đi 1, nếu nhảy ngược chiều kim đồng hồ số chân tăng lên 1.
Mỗi 1 lần nhảy có 1 con chim tăng lên 1 chân, 1 con chim giảm đi 1 chân nên tổng số chân chim không đổi là 2*n.
Không mất tính tổng quát giả sử sẽ có lúc tất cả các con chim gặp nhau ở cây 0.
Con chim ở cây i, khi hội tụ ở 0 sẽ có số chân là 1+ i + h*2*n, với h là hệ số có thể âm có thể dương, tùy theo con chim nhảy về 0 rồi lại nhảy thêm vài vòng tròn xuôi ngược.

Như vậy khi tính tổng số chân chim tại vị trí 0 thì nó sẽ là 2*n + n + x*2*n. Sở dĩ +n đó là vì các cặp (1, -1), (2, -2),… triệt tiêu cho nhau, và con dư một con ở cây n vị trí 6h. Nói tóm lại tổng số chân chim là n + bội số của 2*n. Nhưng số này lại bằng 2*n ko đổi. Điều này ko thể xảy ra vì n không chia hết cho 2*n.
Hoan hô bạn nghiepdu !
Bạn có rất nhiều sáng kiến kết hợp Toán học với Sinh học! Ở lần trước, bạn có kế hoạch "chuyển đổi giới tính" rất táo bạo cho các chú chim vui tính. Còn lần này, bạn chỉ định "cưa chân, vặt cánh" chúng mà thôi! :D :D :D
Với phương án mới này, có vẻ như bạn đã rất gần với lời giải rồi đấy!
Tuy vậy, trong lập luận của bạn còn vài điểm chưa phù hợp với yêu cầu của Bài toán:
1. Cách đánh số của bạn chưa rõ ràng: " 0,1,2,…,n,-n+1,-n+2,…,-2,-1.". Hình như số các bụi cây sẽ không bằng 2n đâu!!!!
2. Lập luận về số chân của lũ chim: "tổng số chân chim tại vị trí 0 thì nó sẽ là 2*n + n + x*2*n". Điều này chưa đúng!
Bạn sắp đến đích rùi, cố lên!!!

[MRAQ2000]

Tôi đã chứng minh được mc(k) = 2k-1 với 1 sự thỏa mái hơn nhiều: mối lần (phải có) 2 con chim bay đến 2 bụi cây khác với chiều bay cũng thỏa mái luôn. Như bạn Nghiepdu nói khó dùng phép quy nạp (trong trường hợp bài toán gốc) thì ta sẽ cởi bỏ những ràng buộc đó và được kết quả mạnh hơn nhiều. Bài toán cũng có thể mở rộng với 3, 4 , ... con chim bay với số bụi cây là 3k, 4k, ...
Bạn Nghiepdu có cách giải với n=46 rất thú vị làm tôi nhớ đến bài toán "Vừa gà vừa chó, bó lại cho tròn ..."

[ThanhLongBin]

Tôi đã chứng minh được mc(k) = 2k-1 với 1 sự thỏa mái hơn nhiều: mối lần (phải có) 2 con chim bay đến 2 bụi cây khác với chiều bay cũng thỏa mái luôn. Như bạn Nghiepdu nói khó dùng phép quy nạp (trong trường hợp bài toán gốc) thì ta sẽ cởi bỏ những ràng buộc đó và được kết quả mạnh hơn nhiều. Bài toán cũng có thể mở rộng với 3, 4 , ... con chim bay với số bụi cây là 3k, 4k, ...
Bạn Nghiepdu có cách giải với n=46 rất thú vị làm tôi nhớ đến bài toán "Vừa gà vừa chó, bó lại cho tròn ..."
Lập luận của bạn khi quy nạp chưa chắc chắn ở chỗ này đây:
1. Bạn giả thiết rằng mc(k)=2k-1. Tức là với 2k con chim, không bao giờ có quá 2k-1 con trên cùng 1 bụi cây. Như vậy hoàn toàn có thể xảy ra trường hợp có đúng 2k-2 con trên 1 bụi, 2 con còn lại ở bụi cây khác cạnh đấy!
2. Với n=2(k+1), lại có thêm 2 con nữa đang ở bụi cây "khác thứ 2". Như vậy, trên 3 bụi cây liền nhau, số chim hoàn toàn có thể là: 2, 2(k-1), 2. Tình huống này không mâu thuẫn với giả thiết mc(k)=2k-1.
3. Sau 2 nhịp thổi còi tiếp theo, 4 con lẻ kia dễ dàng bay về bụi cây ở giữa, và số chim đậu ở đó là 2(k+1)!!!!


Đề xuất tổng quát hóa bài toán với 3,4,.. con chim bay đồng thời với 3k,4k,.... bụi cây của bạn e rằng hơi "thoải mái" quá, nhất là khi đó chiều bay cũng "thoải mái" luôn!
Ví dụ, với 3 con trên 3 bụi cây
1. Nhịp thứ 1: 1,1,1
2. Nhịp thứ 2: 0,2,1
3. Nhịp thứ 3: 3,0,0

Mời bạn phân tích tiếp nhé!