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

Задача с 9 монетами и фальшивой среди них — классическая головоломка. Нужно определить минимальное число взвешиваний на весах без гирь, чтобы найти фальшивую монету (которая легче или тяжелее).

Для 9 монет минимальное число взвешиваний — 2.

Обоснование:

• Каждое взвешивание может иметь 3 результата: левая чаша тяжелее, правая тяжелее, или равенство.
• За k взвешиваний можно различить до 3^k вариантов.
• Нужно различить 2n вариантов (каждая монета может быть легче или тяжелее), то есть 2*9=18 вариантов.
• 3^2=9 < 18, недостаточно.
• 3^3=27 >= 18, значит 3 взвешивания достаточно.

Однако для 9 монет с неизвестным типом фальшивой (легче или тяжелее) минимальное число взвешиваний — 3.

Если же известно, что фальшивая монета легче (или тяжелее), то 2 взвешивания достаточно.

Пример стратегии для 3 взвешиваний:

• Разделить 9 монет на 3 группы по 3.
• Взвесить две группы.
• В зависимости от результата выбрать подозрительную группу и повторить процедуру.

Таким образом, минимальное число взвешиваний для 9 монет с неизвестным типом фальшивой — 3.