Printable View
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 ?!Trích dẫn:
Gửi bởi tuhiep
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.
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.Trích dẫn:
Gửi bởi ThanhLongBin
Bác RDSS lại quên mất đầu bài ban đầu rồi! :DTrích dẫn:
Gửi bởi RDSS
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
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.Trích dẫn:
Gửi bởi 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.
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?Trích dẫn:
Gửi bởi tuhiep
Đọ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.
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!Trích dẫn:
Gửi bởi tuhiep
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!Trích dẫn:
Gửi bởi MRAQ2000
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.Trích dẫn:
Gửi bởi 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
Có lẽ bác hiểu nhầm ý tôi rồi!Trích dẫn:
Gửi bởi tuhiep
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?Trích dẫn:
Gửi bởi 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.Trích dẫn:
Gửi bởi ThanhLongBin
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.
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.
Chào bác RDSSTrích dẫn:
Gửi bởi 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?
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 đá.Trích dẫn:
Gửi bởi ThanhLongBin
Tôi thấy cách bác làm như vậy là thiếu chặt chẽ.Trích dẫn:
Gửi bởi tuhiep
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ứ.Trích dẫn:
Gửi bởi 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,Trích dẫn:
Gửi bởi 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
Một lần nữa, bác lại có lời giải rất tuyệt!Trích dẫn:
Gửi bởi tuhiep
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
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 ThanhLongBin
Chào bác RDSS,Trích dẫn:
Gửi bởi 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.Trích dẫn:
Gửi bởi ThanhLongBin
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.Trích dẫn:
Gửi bởi kien1706
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.
Chào bác RDSS và bác Tuhiep,Trích dẫn:
Gửi bởi RDSS
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?
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"
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ỉ?
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.
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.
Để tôi giúp bác Tư trình bày lại nhé.Trích dẫn:
Gửi bởi RDSS
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é!)
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".Trích dẫn:
Gửi bởi tuhiep
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.
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 ạ.Trích dẫn:
Gửi bởi tuhiep
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!