Ý tưởng chính (tóm tắt ngắn): mỗi quả cân (1,2,4,8) khi được mượn phải tham gia liên tiếp vào các lần cân cho đến khi ta bỏ nó (nếu bỏ rồi muốn dùng lại sẽ phải mượn lại và trả tiền tiếp). Nếu ta xếp thứ tự cân các viên (tương ứng với các số 1..15 ở dạng nhị phân) hợp lý thì tổng số lần mượn (mỗi lần mượn một quả cân tính là 100 đồng) sẽ tối thiểu. Bài toán tương đương: sắp xếp 15 mã nhị phân (1..15) để tổng số lần chuyển từ 0 → 1 trên bốn bit là nhỏ nhất.

Kết quả tối ưu tìm được:

• Số lần phải mượn tổng cộng = 8 (tức 8 quả cân-mượn trong cả quá trình).
• Chi phí tối thiểu = 8 × 100 = 800 đồng.

Một thứ tự cân cụ thể đạt chi phí này (mỗi viên được cân một lần theo thứ tự):
1, 3, 2, 6, 4, 5, 7, 15, 11, 9, 13, 12, 14, 10, 8 (đơn vị carat).

Phân tích ngắn (ví dụ theo thứ tự trên):

• Lần 1 cân viên 1: mượn quả cân 1 → +100
• Lần 2 cân viên 3: mượn quả cân 2 → +100 (tổng 200)
• Lần 3 cân viên 2: chỉ cần 2 (không mượn thêm)
• Lần 4 cân viên 6: mượn quả cân 4 → +100 (tổng 300)
• Lần 5 cân viên 4: chỉ cần 4
• Lần 6 cân viên 5: phải mượn lại quả cân 1 → +100 (tổng 400)
• Lần 7 cân viên 7: mượn lại quả cân 2 → +100 (tổng 500)
• Lần 8 cân viên 15: mượn quả cân 8 → +100 (tổng 600)
• Lần 9–10–11…15: còn lại mượn thêm 4 hoặc 2 vào những lúc cần, tổng cộng 2 mượn nữa → tổng mượn = 8 → 800 đồng.

Kết luận: Ít nhất phải trả 800 đồng để kiểm tra trọng lượng của tất cả 15 viên kim cương