подсчёт фальшивых монет

[iPhonograph]

У вас имеется 2^k монет, одинаковых на вид.
Среди них есть настоящие и более лёгкие фальшивые, все фальшивые весят одинаково.
Есть двухчашечные весы.
Требуется подсчитать количество фальшивых монет, выполнив O(k²) взвешиваний.

[Vyatkin_57]

Из 21 одинаковых по виду монет,одна монета по весу несколько отличается от других.Как за 2 взвешивания на чашечных весах без гирь определить, легче или тяжелее эта монета,чем остальные.

[Tim]

У вас имеется 2^k монет, одинаковых на вид.
Среди них есть настоящие и более лёгкие фальшивые, все фальшивые весят одинаково.
Есть двухчашечные весы.
Требуется подсчитать количество фальшивых монет, выполнив O(k²) взвешиваний.

Чего-то я не понял O(k²) это что? если 16 монет, то надо за 4^2 взвешиваний определить?

[iPhonograph]

Сформулируем так: нужно выполнить не более 100*k² взвешиваний

[Tim]

А решение можно, задолбался с логарифмами чего-то

[iPhonograph]

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

[iPhonograph]

подставаказка
Показать скрытый текст

Нужно свести задачу про 2^k монет к задаче про 2^k-1 монет.