Bài 3: Cần phải cân bao nhiêu lần bằng một chiếc cân 2 đĩa để tìm đồng xu giả trong 4 đồng xu (biết có 3 đồng thật, một đồng giả). Biết đồng xu giả có trọng lượng nhẹ hơn hoặc nặng hơn các đồng xu thật. Mô tả thuật toán tìm đồng xu giả với số lần cân tìm được.

Lời giải:

Có ba khả năng xảy ra đối với mỗi lần cân:

-         2 đĩa có trọng lượng như nhau

-         Đĩa thứ nhất nặng hơn đĩa thứ 2

-         Và đĩa thứ nhất nhẹ hơn đĩa thứ 2.

Do đó cây quyết định cho một dãy các lần cân là cây 3 – phân, và có ít nhất 4 lá trong cây quyết định vì có 4 kết cục có thể và mỗi kết cục phải được biểu diễn bằng ít nhất 1 lá. Số lần cân nhiều nhất để xác định đồng xu giả là chiều cao của cây 3 – phân. Theo định lý 4 phần 2 thì h = [log31] = [log34] = 2.

Thủ tục cân như sau:

-         Đầu tiên cân đồng xu 1 với đồng xu 2, nếu chúng bằng nhau thì cân đồng xu 1 với đồng xu 3. Nếu đồng xu 1 và 3 bằng nhau thì đồng xu giả là đồng xu 4. Nếu đồng xu 1 khác đồng xu 3 thì đồng xu 3 là đồng xu giả.

-         Nếu đồng xu 1 khác đồng xu 2 thì ta cân đồng xu 1 với đồng xu 3. Nếu đồng xu 1 và đồng xu 3 bằng nhau thì đồng xu 2 là giả. Còn nếu không cân bằng thì đồng xu 1 là giả.