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

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

Trích dẫn:

---

Gửi bởi 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).

---

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_...nacci_sequence
hoặc xem: http://vi.wikipedia.org/wiki/T%E1%BB...B%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" !!!!

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:

"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

Trích dẫn:

---

Gửi bở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).
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

Trích dẫn:

---

Gửi bởi ThanhLongBin

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ó!!!!

Trích dẫn:

---

Gửi bởi RDSS

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?

Trích dẫn:

---

Gửi bởi ThanhLongBin

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.

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

Trích dẫn:

---

Gửi bởi 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 !!

---

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.