Bài toán xác định 1 đồng xu giả

Có 13 đồng xu trong đó có một đồng xu giả nhẹ hơn các đồng xu còn lại. Hỏi bằng chiếc cân 2 đĩa, có thể xác định được đồng xu giả sau ít nhất bao nhiêu lần cân? Giải thích rõ câu trả lời.
Giải:
Với 13 đồng xu ta chỉ cần 3 lần cân là đủ để xác định được
Giải thích:

Tách 13 đồng xu thành 3 nhóm mỗi nhóm có 4;4;5 đồng xu

cân hai nhóm có 4 đồng xu. 

Nếu hai nhóm bằng nhau thì trong 5 đồng xu có đồng xu giả. Tiếp tục tách 5 đồng xu thành 3 nhóm 2;2;1. Cân nhóm 2-2. Nếu bằng thì đồng còn lại là giả, Nếu không bằng thì trong hai nhóm 2-2 có 1 đồng xu giả. Tiếp tục tách nhóm 2 thành 1-1 đem cân ta sẽ tìm được đồng xu giả

Nếu  hai nhóm không bằng nhau thì trong hai nhóm 4 có 1 nhóm chứa đồng xu giả, Tách nhóm 4 thành 2-2 khi đó qua hai lần cân ta sẽ tìm được đồng xu giả.

Vậy cần tất cả là 3 bước để xác định được đòng xu giả.

Ghi chú:

Trong quá trình làm các bài toán dạng này tôi tổng hợp được cáchs tổng quát là: Với a là số đồng xu trong đó có một đồng xu giả, n là số lần cân ít nhất để xác định được đồng xu giả đó thì : a không vượt quá 3^n. ( Cái này bản thân thấy như vậy chứ chưa chứng minh tổng quát)

Ví dụ: Từ 9 đồng xu ta chỉ cần cân hai lần là đủ vì 9=3^2.

Từ 10 =>27 ta có thể cân 3 lần nhưng 28 thì không thể./. 

.....

Rất mong nhận đựợc sự trao đổi của các bạn đọc.