Đề 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?
Hướng dẫn lời giải:
Để số lần cân ít nhất thì các lần cân luôn phải thực hiện theo quy tắc cân 1-1 (hòn đá) trên mỗi đĩa cân. Mỗi lần cân ta loại đi một hòn đá nhẹ hơn nên để chọn được một hòn đá nặng nhất từ 32 hòn đá ta phải loại đi 31 hòn đá tức là mất 31 lần cân. Giả sử sau 31 lần cân ta tìm được A là hòn đá nặng nhất. Chia các cặp cân như cách chia đấu loại trực tiếp Champion league hoặc Fide Worl Cup như sau:
Vòng 1: Có 16 cặp hòn đá được cân, gọi B là viên đá nhẹ hơn khi cân với A.
Lấy 16 hòn đá nặng hơn trong mỗi cặp cân để cân tiếp ở vòng 2.
Vòng 2: Có 8 cặp hòn đá được cân, gọi C là viên đá nhẹ hơn khi cân với A.
Lấy 8 hòn đá nặng hơn trong mỗi cặp cân để cân tiếp ở vòng 3.
Vòng 3: Có 4 cặp hòn đá được cân, gọi D là viên đá nhẹ hơn khi cân với A.
Lấy 4 hòn đá nặng hơn trong mỗi cặp cân để cân tiếp ở vòng 4.
Vòng 4: Có 2 cặp hòn đá được cân, gọi E là viên đá nhẹ hơn khi cân với A.
Lấy 2 hòn đá nặng hơn trong mỗi cặp cân để cân tiếp vòng 5.
Vòng 5: Có một cặp hòn đá được cân, gọi F là viên đá nhẹ hơn khi cân với A.
Sau vòng 5 ta có nhận xét quan trọng là hòn đá nặng thứ hai trong 32 hòn đá đã cho chính là viên đá nặng nhất trong 5 viên đá B, C, D, E, F (5 viên trong các cặp cân so sánh với A).
Tiếp tục mỗi lần cân ta loại đi một viên đá nhẹ hơn nên để chọn được viên nặng nhất từ 5 viên B, C, D, E, F ta phải loại đi 4 viên đá tức là mất thêm 4 lần cân.
Kết luận: Số lần cân ít nhất là 31 + 4 = 35 (lần cân)
Trần Phương
Phó giám đốc Trung tâm hỗ trợ phát triển tài năng