Задача 107633
|
|
 |
Условие
Антиквар приобрёл 99 одинаковых по виду старинных монет. Ему сообщили, что ровно одна из монет — фальшивая — легче настоящих (а настоящие весят одинаково). Как, используя чашечные весы без гирь, за 7 взвешиваний выявить фальшивую монету, если антиквар не разрешает никакую монету взвешивать более двух раз ?Решение
Сначала положим на две чаши весов по 13 монет, затем (если весы находятся в равновесии) уберём их и положим по 11 из ещё не бравшихся, затем по 9,7,5,3 и 1 до тех пор, пока одна из чаш не перевесит.Если такого не произойдёт, то после седьмого взвешивания (когда на чашах весов будет всего по одной монете) останется всего одна монета, которая во взвешиваниях не участвовала. Она и является фальшивой.
Если при каком-то взвешивании какая-то чаша перевесила, значит фальшивая монета лежит в другой чаше. Общее количество монет в этой чаше обозначим 2k + 1 (мы каждый раз кладём на одну чашу нечётное число монет), при этом мы уже использовали 7 – k взвешиваний, причём каждая монета взвешивалась не более одного раза. Поэтому осталось найти фальшивую монету в группе из (2k + 1) монет за k взвешиваний, взвешивая каждую монету не более одного раза. Для этого можно разбить все монеты в группе, кроме одной, разбить на k пар и последовательно сравнивать веса монет каждой пары. Если при каком-то взвешивании равновесие нарушится, то более лёгкая монета и является фальшивой. В противном случае, фальшивая монета — оставшаяся без пары.
