Đáp án: 800 đồng (tức mượn tổng cộng 8 lần các quả cân).
Ý tưởng tóm tắt (mạch suy luận):
- Mỗi viên kim cương có trọng lượng nguyên từ 1 đến 15 — nghĩa là tương ứng đúng với mọi tập con khác rỗng của bốn quả cân \(1 , 2 , 4 , 8\) (vì mọi số \(1 \ldots 15\) có biểu diễn nhị phân duy nhất trên các bit 1,2,4,8). Để kiểm tra viên có đúng \(k\) carat hay không, ta phải đặt đúng tập con các quả cân có tổng = \(k\) lên báng cân đối diện với viên đó. Vậy nhiệm vụ tương đương với: “ghé thăm” tất cả 15 tập con khác rỗng của { 1 , 2 , 4 , 8 } {1,2,4,8}.
- Mỗi lần mượn một quả cân (tức chuyển một bit từ 0 sang 1 trong trạng thái “các quả cân đang để trên báng”), người mua trả 100 đồng. Nếu một quả cân bị bỏ ra và không tham gia trong lần cân kế tiếp thì người bán thu lại — tức nếu sau này muốn dùng lại quả cân đó phải mượn lại (lại trả 100 đồng). Do đó ta có thể mô hình hoá bài toán như sau: bắt đầu ở trạng thái \(0000\) (không quả cân trên báng), ta cần đi qua (visit) tất cả 15 trạng thái nhị phân khác rỗng; chi phí là 100 × (số lần một bit chuyển từ 0→1 trên toàn bộ đường đi). Mục tiêu: đi qua tất cả 15 trạng thái với tổng số chuyển 0→1 nhỏ nhất.
- Bằng lập luận tổ hợp (và xây dựng đường đi theo nguyên lý quy nạp trên chiều dài bit) ta có thể đạt được một cách đi sao cho tổng số chuyển 0→1 tối thiểu bằng \(2^{4 - 1} = 8\) (đối với 4 quả cân). (Có thể chứng minh chặt chẽ bằng quy nạp: với \(n\) quả cân tối thiểu là \(2^{n - 1}\); cho \(n = 1\) đúng, và từ đường đi tối ưu với \(n - 1\) quả cân ta mở rộng để được đường đi tối ưu cho \(n\) quả cân — chi tiết chứng minh là chuẩn trong bài toán “ghé thăm mọi tập con khác rỗng của hypercube với chi phí đếm số lần bật bit 0→1”.)
- Vậy ta phải mượn (tổng cộng, trên toàn bộ quá trình) 8 lần các quả cân (mỗi lần mượn một quả cân, có thể là quả cân trùng loại nhưng được tính từng lần mượn). Mỗi lần mượn mất 100 đồng ⇒ tổng chi phí tối thiểu = \(8 \times 100 = 800\) đồng.
