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

[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!
Đã 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!
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!

[RDSS]

Bác RDSS lại quên mất đầu bài ban đầu rồi!
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 , thán phục - than phục bội phần .

[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 , thán phục - than phục bội phần .

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!