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

[tanlsth]

Cho $ 2001 $ viên bi có hình dạng kích thước giống hệt nhau nhưng trong đó có một viên có trọng lượng khác so với các viên còn lại.Hỏi cần ít nhất bao nhiêu lần cân (cân 2 đĩa) để có thể tìm ra được viên bi đó.
Tổng quát lên cho $ n $ viên bi

[1001001]

$\lceil log_{3}n \rceil$. C/m nhỏ nhất bằng qui nạp.

[tanlsth]

Em làm rõ hơn nữa đi
Đề trên còn thiếu yêu cầu là xác định được viên bi đó nặng hay nhẹ hơn so với các viên bi còn lại

[tanlsth]

Mà cái kết quả của em hình như chưa đúng rồi, phải cộng thêm 1 nữa

[lovemath_khtn]

phải là $[log2_n]+1$ chứ nhỉ?

[tanlsth]

Không đúng, không thể là $ [log_2n]+1 $ đâu.

[lovemath_khtn]

em tưởng cứ chia đôi ra,như thế quá rõ ràng mà
lần $1$ chia làm đôi
cứ thế đến $k$ mà $2^k\le n$,sai ở chỗ nào?

[tanlsth]

Ở đây là số lần ít nhất cơ mà

[1001001]

À em chưa đọc kĩ đề, tưởng viên bi đó nặng hơn chứ.

Bài viết đã được chỉnh sửa nội dung bởi 1001001: 03-07-2007 - 21:40

[1001001]

Đúng là chỉ cần cộng thêm 1 (chỉ cần 1 lần cân là đủ biết nặng hay nhẹ hơn).
Lời giải cụ thể cho bài toán đã biết trọng lượng viên bi lạ đây:
Giả sử số bi là $x$ thỏa $3^n < x \le 3^{n+1}$. Ta chứng minh qui nạp theo $n$. Bước chuyển từ $n$ sang $n+1$ được thực hiện thông qua các nhận xét sau:
_ Nếu số lần cân là ít nhât thì tại mỗi lần cân số bi chứa viên bi khác trọng luợng xác định được cũng phải là ít nhất (do nhận xét số bi càng ít thì số lần cân cần thiết sẽ càng ít).
_ Không thể chia số bi ra làm 4 nhóm mà qua 1 lần cân là biết ngay viên bi khác trọng luợng nằm ở nhóm nào (cái này c/m dễ).
Vậy ta chia số bi ra làm 3 nhóm, trường hợp xấu nhất là viên bi cần tìm nằm trong nhóm có số luợng nhiều nhất là $a$ thì $3a \ge n $ suy ra $a \ge \lceil n/3 \rceil $ (chú ý là luôn có thể chia ra làm 3 nhóm mà có 2 nhóm bằng nhau, còn nhóm còn lại hơn kém không quá 1, cân 2 nhóm bằng nhau để xác định). Sử dụng giả thiết qui nạp cho $a$.
Nếu chưa biết viên bi đó nặng hay nhẹ hơn thì ngay ở bước đầu tiên khi chia 3 nhóm ta chỉ cần thêm 1 lần cân để biết viên bi đó nặng hay nhẹ hơn rồi giải quyết như trên.
Vậy đáp số cuối cùng là $ \lceil log_3x \rceil + 1$

[HUYVAN]

Cho $ 2001 $ viên bi có hình dạng kích thước giống hệt nhau nhưng trong đó có một viên có trọng lượng khác so với các viên còn lại.Hỏi cần ít nhất bao nhiêu lần cân (cân 2 đĩa) để có thể tìm ra được viên bi đó.
Tổng quát lên cho $ n $ viên bi

Bài toán này đã được giải quyết trong cuốn Selected Problems and Theorems in Elementary Mathematics
Em biết một bài toán có hình thức gần giống với bài toán trên là:
Cho $n$ đống đá gồm $1, 2, ..., n$ hòn. Mỗi lần cho phép lấy ra từ một số đống đá nào đó một số đá như nhau. Hỏi cần ít nhất bao nhiêu lần để lấy hết đá

[manutd]

Bài toán này đã được giải quyết trong cuốn Selected Problems and Theorems in Elementary Mathematics
Em biết một bài toán có hình thức gần giống với bài toán trên là:
Cho $n$ đống đá gồm $1, 2, ..., n$ hòn. Mỗi lần cho phép lấy ra từ một số đống đá nào đó một số đá như nhau. Hỏi cần ít nhất bao nhiêu lần để lấy hết đá

giống sao được nhỉ? với lại anh chưa có quyển đó, em up lên đây được không?

[HUYVAN]

giống sao được nhỉ? với lại anh chưa có quyển đó, em up lên đây được không?

Thì em có nói là giống nhau 100% đâu, chỉ hơi hơi thôi mà
Cuốn này em không có ebook, chỉ có bản offline thôi

[kyoshiro_hp]

Thấy mọi người bàn luận sôi nổi quá táy máy tí. Ở topic này
http://diendantoanho...showtopic=20297
có 1 bài toán tương đương do anh emvaanh giải, mọi người tham khảo xem nhé.