Каково минимальное количество взвешиваний для нахождения фальшивой монеты среди 9?

2 взвешивания. Это классическая задача на поиск элемента с отличающимся весом с помощью весов-чаш.

Алгоритм (деление на три группы):

1. Первое взвешивание: Делим 9 монет на 3 группы по 3 монеты (A, B, C). Сравниваем группы A и B.
   • Если A == B, фальшивая монета в группе C.
   • Если A != B, фальшивая монета в более легкой группе (если известно, что фальшивая легче).
2. Второе взвешивание: Из группы с фальшивой монетой (3 монеты) взвешиваем любые две.
   • Если они равны, фальшивая — третья.
   • Если нет, фальшивая — более легкая.

Псевдокод (предполагаем, что фальшивая монета легче):

def find_fake_coin(coins):
    # 1-е взвешивание: сравниваем первые две группы по 3 монеты
    weight_a = sum(coins[0:3])
    weight_b = sum(coins[3:6])

    if weight_a == weight_b:
        suspect_group = coins[6:9]  # Группа C
        group_start_index = 6
    else:
        suspect_group = coins[0:3] if weight_a < weight_b else coins[3:6]
        group_start_index = 0 if weight_a < weight_b else 3

    # 2-е взвешивание: сравниваем две монеты из suspect_group
    if suspect_group[0] == suspect_group[1]:
        return group_start_index + 2  # Третья монета
    else:
        return group_start_index if suspect_group[0] < suspect_group[1] else group_start_index + 1

Почему 2? Каждое взвешивание дает 3 возможных результата (левая чаша легче, тяжелее, равны), что дает 3² = 9 возможных уникальных исходов, чего достаточно для идентификации одной монеты из 9.