Trường hợp tổng quát có n viên bi cách làm như thế nào?

Câu hỏi 2. Trường hợp tổng quát có n viên bi cách làm như thế nào?


Trường hợp tổng quát có n viên bi cách làm như sau:

- Nếu n lẻ, n = 2k + 1, sau lần cân thứ nhất với mỗi bên k viên, hoặc tìm thấy ngay viên bi giả, hoặc biết bên nào có chứa bi giả và tiếp tục cân với k viên bi đó.
- Nếu n chẵn, n = 2k, sau lần cân thứ nhất, ta tìm được k viên bi chữa viên bi giả. Tổng quát, sau một lần cân, từ bài toán với n viên bi sẽ dẫn đến bài toán với [n/21 viên bi ([x] là phần nguyên của x). Khi bài toán dẫn đến còn hai hoặc ba viên bi thì chỉ cần một lần cân nữa sẽ tìm được viên bi giả.


Giải những bài tập khác

Bình luận

Giải bài tập những môn khác