Có 1 tòa nhà 2006 tầng và 1 số i có tính chất: nếu ta thả 1 viên bi từ 1 tầng thấp hơn tầng thứ i thì viên đi đó không bị vỡ, còn nếu ta thả từ tầng cao hơn hoặc bằng i thì nó sẽ vỡ. Biết rằng trong tay chúng ta có 4 viên bi, hỏi có thể thả bi ít nhất là bao nhiêu lần để chắc chắn xác định được số i đó?
Đố vui toán học
Started By VŨ Thanh Tùng, 17-03-2006 - 05:28
#1
Posted 17-03-2006 - 05:28
#2
Posted 17-03-2006 - 22:56
Lấy 3 viên bi để sử dụng phương pháp "chia đôi để trị" ta tìm được một khoảng gồm
2006/(2^3) tầng liên tiếp mà chứa tầng cần tìm. Dùng viên còn lại thử lần lượt trong khoảng này từ thấp lên cao
Tóm lại : Trường hợp xấu nhất ta sẽ phải thử 2*2006/(2^3) tầng + 3 lần ban đầu
2006/(2^3) tầng liên tiếp mà chứa tầng cần tìm. Dùng viên còn lại thử lần lượt trong khoảng này từ thấp lên cao
Tóm lại : Trường hợp xấu nhất ta sẽ phải thử 2*2006/(2^3) tầng + 3 lần ban đầu
hoanglovely
#3
Posted 18-03-2006 - 16:13
lời giải của bác Hoang chắc chưa tối ưu đâu. Bài của Tùng khó quá
#4
Posted 21-03-2006 - 02:27
Gọi m là số lần ít nhất cần thả ứng với tòa nhà n tầng.
1)Làm trường hợp 2 viên bi trước: vì m là số lần cần thả nên phải thả phát đầu ở tầng m => phát 2 ở tầng m+(m-1) =>... Như thế m phải thỏa mãn m+(m-1)+...+1 >= n hay là m là số nhỏ nhất thỏa mãn C(2,m)>= n
2)3 viên bi: Phải thả bắt đầu ở tầng C(2,m-1)+1 => phát 2 ở tầng C(2,m-1)+C(2,m-2)+2 => ... Như thế m là số nhỏ nhất thỏa mãn C(2,m-1)+C(2,m-2)+...+C(2,2)+(m-2)>=n . Kí hiệu là f(3,m)=C(2,m-1)+C(2,m-2)+...+C(2,2)+(m-2).
3)4 viên bi: Phải thả bắt đầu ở tầng f(3,m-1)+1 =>... => f(3,m-1)+f(3,m-2)+...+f(3,3)+(m-3) >=n
Thuật toán này cho ta lời giải tối ưu.
1)Làm trường hợp 2 viên bi trước: vì m là số lần cần thả nên phải thả phát đầu ở tầng m => phát 2 ở tầng m+(m-1) =>... Như thế m phải thỏa mãn m+(m-1)+...+1 >= n hay là m là số nhỏ nhất thỏa mãn C(2,m)>= n
2)3 viên bi: Phải thả bắt đầu ở tầng C(2,m-1)+1 => phát 2 ở tầng C(2,m-1)+C(2,m-2)+2 => ... Như thế m là số nhỏ nhất thỏa mãn C(2,m-1)+C(2,m-2)+...+C(2,2)+(m-2)>=n . Kí hiệu là f(3,m)=C(2,m-1)+C(2,m-2)+...+C(2,2)+(m-2).
3)4 viên bi: Phải thả bắt đầu ở tầng f(3,m-1)+1 =>... => f(3,m-1)+f(3,m-2)+...+f(3,3)+(m-3) >=n
Thuật toán này cho ta lời giải tối ưu.
Edited by shinichi9htv, 21-03-2006 - 02:31.
#5
Posted 21-03-2006 - 04:07
Cách bác shinichi có vẻ đúng, nhưng bác xem lại phát.
Edited by VŨ Thanh Tùng, 21-03-2006 - 04:14.
1 user(s) are reading this topic
0 members, 1 guests, 0 anonymous users