Chủ đề này có 8 trả lời

[anhminh]

Cho các đóng bi có số bi là http://dientuvietnam...i?1,2,...,n.Mỗi lần cho phép lấy đi số bi bằng nhau từ mỗi đống.
Hỏi cần ít nhất bao nhiêu lần mới lấy hết bi ?

[tmbtw]

Sau mỗi lần lấy bi,đống nào hết bi thi thôi chứ?Và nếu đống nào còn bi thì phải lấy (sau mỗi lần thực hiện lấy bi)?
Nếu vậy rõ ràng cần n lần mới lấy hết bi!

[chuyentoan]

đúng là sau n lần lấy thì hết bi nhưng chỉ cần http://dientuvietnam.net/cgi-bin/mimetex.cgi?[\log_2n]+1 lần cũng lấy được hết

[tmbtw]

Anh có thể nói rõ đề bài hơn được không?Cảm ơn

[chuyentoan]

Đề bài chính xác là như sau: Cho n đống bi có số bi tương ứng là 1,2,...,n. Một lấy lấy bi cho phép chọn một số đống nào đó và trong mỗi đống đã chọn đó ta lấy đi cùng một số viên bi. Hỏi cần ít nhất bao nhiêu lần lấy bi để lấy được hết bi.

[tmbtw]

+)Giả sử lần 1: lấy k bi từ 1 số đống nào đó (Tất nhiên các đống đó có số bihttp://dientuvietnam.net/cgi-bin/mimetex.cgi?\geq{k})Để số lần lấy bi là ít nhất ,thì rõ ràng ta lấy bi ở tất cả các đống có thể lấy(Là các đống có số bi là:k;k+1;...;n)Khi đó số bi còn lại ở các đống là:1;2;...;k-1;0;1;...;n-k;
Xét n chẵn( n lẻ tt)
TH1)http://dientuvietnam.net/cgi-bin/mimetex.cgi?k\leq{\dfrac{n}{2}}
KHi đó http://dientuvietnam.net/cgi-bin/mimetex.cgi?k>\dfrac{n}{2}
Khi đó :http://dientuvietnam.net/cgi-bin/mimetex.cgi?k-1\geq{\dfrac{n}{2}}
Tức là ,sau lần lấy bi thứ nhất ,số bi còn lại ở các đống ít nhất là :http://dientuvietnam.net/cgi-bin/mimetex.cgi?1;2;...;\dfrac{n}{2}
Lý luận tương tự. Nếu ta gọi q là số TN max t/m:http://dientuvietnam.net/cgi-bin/mimetex.cgi?2^{q}\leq{n} thì cần ít nhất q+1 lần lấy ,số bi còn lại ở tất cả các đống mới có thể là 0.
Hay cần ít nhất http://dientuvietnam...1;log_{2}{n}] 1 lần mới lấy hết được bi ở cả n đống
Mặt khác ,dễ dàng chỉ ra cách lấy bi t/m.

[chuyentoan]

Có thể không phân trường hợp cũng được. Nhận xét là nếu trước khi chuyển có http://dientuvietnam...n/mimetex.cgi?n loại đống khác nhau (hai đống được xem là cùng loại nếu có cùng số bi) thì sau khi chuyển có ít nhất http://dientuvietnam.net/cgi-bin/mimetex.cgi?\[\dfrac{n}{2}\] loại đống khác nhau.

[papillonhn]

Có thể không phân trường hợp cũng được. Nhận xét là nếu trước khi chuyển có http://dientuvietnam...n/mimetex.cgi?n loại đống khác nhau (hai đống được xem là cùng loại nếu có cùng số bi) thì sau khi chuyển có ít nhất http://dientuvietnam.net/cgi-bin/mimetex.cgi?\[\dfrac{n}{2}\] loại đống khác nhau.

Các bạn cho mình hỏi, loại toán này học ở sách nào vậy.

[chuyentoan]

Sách Việt Nam về loại toán này thi ít, mà có thì cũng không hay. Có một số cuốn của tác giả Nguyễn Hữu Điển cũng được. Tốt nhất nếu có thể thì bạn tìm một cuốn sách nước ngoài, chẳng hạn như Problems Solving Strategies, Mathematical Olympiad Challenge, ... Hoặc là lên mạng down đề thì Olympic về làm là có ngay mà