Cần bao nhiêu phép thử để tìm được một phế phẩm trong 81 sản phẩm sản xuất ra?

Có 81 sản phẩm được sản xuất ra, trong đó có một sản phẩm bị rỗng bên trong bằng hạt cát nên trở thành phế phẩm. Cần tìm ra phế phẩm ấy. Nhìn bằng mắt thường thì không thể nhận ra, nhưng vì bên trong bị rỗng nên phế phẩm nhẹ hơn chính phẩm. Vì vậy, ta có thể dùng cân để tìm. Vấn đề là cần ít nhất bao nhiêu lần cân?

Cách kiểm tra đơn giản là đặt hai sản phẩm lên hai đĩa cân. Nếu cân thăng bằng thì cả hai đều là chính phẩm; nếu cân lệch thì vật nhẹ hơn là phế phẩm. Với 3 sản phẩm, chỉ cần một lần cân là có thể tìm được phế phẩm: cân hai sản phẩm bất kỳ, nếu cân thăng bằng thì sản phẩm còn lại là phế phẩm; nếu cân lệch thì sản phẩm nhẹ hơn là phế phẩm.

Với 9 sản phẩm, không cần cân đến 9 lần. Ta chia chúng thành ba nhóm, mỗi nhóm 3 sản phẩm. Chọn hai nhóm bất kỳ đặt lên hai đĩa cân. Sau một lần cân, ta xác định được phế phẩm nằm ở nhóm nào. Sau đó áp dụng cách tìm phế phẩm trong 3 sản phẩm, ta chỉ cần thêm một lần cân nữa. Vậy với 9 sản phẩm, chỉ cần 2 lần cân.

Tương tự, với 81 sản phẩm, ta chia thành ba nhóm, mỗi nhóm 27 sản phẩm. Cân hai nhóm để xác định nhóm chứa phế phẩm. Lại chia nhóm đó thành ba nhóm 9 sản phẩm và tiếp tục cân. Sau đó chia tiếp thành nhóm 3 sản phẩm và cuối cùng cân để tìm ra sản phẩm nhẹ hơn. Tổng cộng chỉ cần 4 lần cân.

Nếu số sản phẩm là 3^n, thì số lần cân ít nhất cần dùng là n. Ví dụ, 81 = 3^4 nên cần 4 lần cân; 243 = 3^5 nên cần 5 lần cân; 729 = 3^6 nên cần 6 lần cân. Nếu số sản phẩm không đúng bằng lũy thừa của 3, ta cần điều chỉnh cách chia nhóm cho phù hợp.