Для начала я дам Вам весы и девять монет (каждому ученику) Всем хватило? Хорошо. Теперь повторяйте мои действия. Сначала разделим монеты на три группы. В каждой-по три монете. Одну группу оставляем на столе, вторую кладём на одну сторону весов, третью на другую половину. Все положили? Хорошо. У меня чаши равны. Это значит, что фальшивка в группе, которая у меня на столе. Я вижу, у многих учеников та же ситуация. Теперь мы взвешиваем две монеты из третьей группы. Они тоже одинаковые на вес. Значит, третья фальшивая. Теперь я объясню для тех учеников, у которых при взвешивании двух групп монет весы показали неравенство. На той чаше, где веса меньше, лежит фальшивка. Теперь тоже взвесьте по две монеты.
Поскольку весы именно чашечные, то задача нахождения фальшивой монеты из N сводится к бинарному поиску - мы каждый раз делим исходную кучку пополам (или на три части, если пополам не делится), определяем ту, которая легче, затем поступаем с ней аналогично. И т.д. пока сравнение не сведется к 2-м монетам - более легкая из них и есть искомая. При этом для N монет нам понадобится log2(N) взвешиваний. Если N не степень двойки, то округление идет до ближайшей СЛЕДУЮЩЕЙ. Т.о. в нашем примере log2(N) = 4. Откуда N = 2^4 = 16. 16 монет.
