Viên bi
#1
Đã gửi 02-07-2007 - 18:49
Tổng quát lên cho $ n $ viên bi
Learn from yesterday,live for today,hope for tomorrow
The important thing is to not stop questioning
#2
Đã gửi 03-07-2007 - 07:34
#3
Đã gửi 03-07-2007 - 17:39
Đề 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
Learn from yesterday,live for today,hope for tomorrow
The important thing is to not stop questioning
#4
Đã gửi 03-07-2007 - 17:42
Learn from yesterday,live for today,hope for tomorrow
The important thing is to not stop questioning
#5
Đã gửi 03-07-2007 - 17:59
#6
Đã gửi 03-07-2007 - 19:32
Learn from yesterday,live for today,hope for tomorrow
The important thing is to not stop questioning
#7
Đã gửi 03-07-2007 - 20:09
lần $1$ chia làm đôi
cứ thế đến $k$ mà $2^k\le n$,sai ở chỗ nào?
#8
Đã gửi 03-07-2007 - 20:31
Learn from yesterday,live for today,hope for tomorrow
The important thing is to not stop questioning
#9
Đã gửi 03-07-2007 - 21:34
Bài viết đã được chỉnh sửa nội dung bởi 1001001: 03-07-2007 - 21:40
#10
Đã gửi 04-07-2007 - 07:44
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$
#11
Đã gửi 07-07-2007 - 16:59
Bài toán này đã được giải quyết trong cuốn Selected Problems and Theorems in Elementary MathematicsCho $ 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
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 đá
#12
Đã gửi 07-07-2007 - 21:11
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?
#13
Đã gửi 08-07-2007 - 19:25
Thì em có nói là giống nhau 100% đâu, chỉ hơi hơi thôi màgiống sao được nhỉ? với lại anh chưa có quyển đó, em up lên đây được không?
Cuốn này em không có ebook, chỉ có bản offline thôi
#14
Đã gửi 11-07-2007 - 16:16
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é.
2 người đang xem chủ đề
0 thành viên, 2 khách, 0 thành viên ẩn danh