Среди 9 монет, которые выглядят одинаково, есть одна фальшивая монета. Она имеет меньший вес, чем настоящая монета

  • 32
Среди 9 монет, которые выглядят одинаково, есть одна фальшивая монета. Она имеет меньший вес, чем настоящая монета. Мудрец имеет только весы с чашками, без гирь. Сколько минимальное количество взвешиваний потребуется мудрецу, чтобы определить, какая из 9 монет фальшивая?
Bublik
16
Чтобы определить фальшивую монету среди 9 монет, мы можем использовать подход, основанный на применении бинарного поиска. Давайте разделим эти монеты на 3 группы, содержащие по 3 монеты каждая. После первого взвешивания мы сможем определить, в какой из трех групп находится фальшивая монета.

Шаг 1: Поместите на весы 3 монеты из первой группы и 3 монеты из второй группы.

* Если весы сбалансированы, то фальшивая монета находится в третьей группе.
* Если весы не сбалансированы, мы знаем, что фальшивая монета находится в одной из групп, которая оказалась легче.

Шаг 2: Второе взвешивание. Возьмите 2 монеты из группы, которая оказалась легче на первом взвешивании, и поместите их на весы.

* Если весы снова сбалансированы, то фальшивая монета - третья из группы, которая не была взвешена.
* Если весы не сбалансированы, мудрец сможет сразу определить, какая из этих двух монет является фальшивой.

В итоге, минимально возможное количество взвешиваний, которое потребуется мудрецу, чтобы определить фальшивую монету среди 9 монет, равно 2.