Đáp án bài toán "Robinson cân đá"

Đề bài:

Sau một thời gian sống trên đảo hoang, Robinson Crusoe thu lượm được 32 hòn đá quý. Nhìn bề ngoài không thể phân biệt được hòn đá nào nặng hơn. Robinson Crusoe cũng không có cân đồng hồ để cân chính xác khối lượng các hòn đá mà chỉ có thể dùng cân đĩa để so sánh nặng nhẹ.

Hỏi Robinson Crusoe cần phải sử dụng ít nhất bao nhiêu lần cân để xác định được 2 hòn đá nặng nhất?

Lời giải:

Nếu đề bài cần xác định hòn đá nặng nhất thì Robinson cần 31 lần cân, vì mỗi một lần cân, anh ta loại được một hòn đá (không nặng nhất). Để tìm hòn đá nặng nhất, Robinson phải loại đi 31 hòn đá còn lại, do đó cần ít nhất 31 lần cân.

Để ý rằng trong quá trình cân, nếu Robinson ghi nhận lại các kết quả thì hòn đá nặng thứ nhì sẽ phải là một trong các hòn đá nhẹ hơn hòn đá nặng nhất. Robinson có thể bố trí cách cân để hòn đá nặng nhất chỉ cân với 5 hòn đá khác.

Cụ thể:

Lượt 1 cân 16 cặp, loại 16 còn 16.

Lượt 2 cân 8 cặp, loại 8 còn 8.

Lượt 3 cân 4 cặp, loại 4 còn 4.

Lượt 4 cân 2 cặp, loại 2 còn 2.

Lượt 5 cân cặp hòn đá còn lại, loại 1 còn 1.

Robinson tìm được hòn đá nặng nhất sau: 16 + 8 + 4 + 2 + 1 = 31 lần cân.

Bây giờ Robinson còn 5 hòn đá nhẹ hơn hòn đá nặng nhất. Hòn đá nặng nhì phải nằm trong số này. Anh ta cần 4 lượt cân nữa để xác định hòn đá nặng nhất trong 5 hòn đá này.

Vậy Robinson cần: 31 + 4 = 35 lượt cân để tìm ra 2 hòn đá nặng nhất.