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

[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é!
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"

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



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!