Среди 12 монет есть одна фальшивая. Фальшивая монета может быть как легче, так и тяжелее настоящей.
Какое минимальное количество взвешиваний необходимо сделать, чтобы определить фальшивую монету на весах с 2 чашками без гирь?
Ответ:
Потребуется три взвешивания.
Алгоритм поиска фальшивой монеты крайне прост и самоочевиден, но на всякий случай расскажу его.
Все монеты надо разделить на три кучки по четыре монеты.
Для первого взвешивания положим первые две кучки на чаши весов. При этом возможны такие варианты:
Весы в равновесии. Это означает, что на обеих чашках лежат настоящие монеты, а в третьей кучке одна из монет фальшивая. Надо определить, какая именно. Для этого кладём на одну чашку весов три настоящие монеты, а на другую чашку кладём три монеты из третьей кучки. Делаем второе взвешивание. Теперь варианты такие:
Весы в равновесии. Это означает, что все шесть монет на весах - настоящие, а фальшивая монета из третьей кучки - та, оставшаяся, которую не клали на весы.
Перевесила одна из чашек, то есть, на чашке, где лежат монеты из третьей кучки, есть фальшивая монета. Если перевесила чашка с настоящими монетами, значит фальшивая монета легче настоящих. Если перевесила чашка, где одна из монет фальшивая - значит фальшивая монета тяжелее настоящей. Определяем, какая из трёх монет фальшивая, делая третье взвешивание.
Одна из чашек оказалась легче, значит на одной из чашек есть фальшивая монета. В третьей же кучке все четыре монеты настоящие (допустим, первая кучка оказалась тяжелее второй. Если наоборот - в последующих действиях меняем кучки соответственно). Делаем второе взвешивание, кладя на одну чашку одну монету из первой кучки и три настоящих монеты; на вторую чашку кладём остальные 3 монеты из первой кучки и одну монету из второй кучки. Возможны варианты:
Весы в равновесии. Следовательно, фальшивая монета - одна из трёх остальных монет второй кучки, которые не участвовали во втором взвешивании. Фальшивая монета легче настоящих, ведь в первом взвешивании вторая кучка (та, где, как мы теперь знаем, есть фальшивая монета) оказалась легче. Находим её третьим взвешиванием.
Перевесила чашка весов с одной монетой из первой кучки. Это означает, что либо эта одна монета фальшивая и тяжелее настоящей, либо на второй чашке одна монета из второй кучки фальшивая и легче настоящей. Чтобы выяснить, какая из этих монет фальшивая, делаем третье взвешивание: сравниваем вес любой из этих двух монет с настоящей.
Перевесила чашка, где лежит три монеты из первой кучки. Это означает, что фальшивая монета находится среди трёх монет, взятых из первой кучки, и она тяжелее настоящей. Делаем третье взвешивание, чтобы определить фальшивую монету.
