16 монет и гирька, задача на алгоритм

[Руст]

Для 16 точно не хватает 3 взвешиваний. Однако с гирями можно уменьшит количество взвешиваний для некоторого количества (например для $\frac{3^n-1}{2}$), чем без гирь. При взвешивании с гирями мы получаем дополнительную информацию, тяжелее или легче фальшивая монета. Правда я упустил, что для получения дополнительной информации требуется гири поставить в отдельную чашу. Например для 13 монет. Вначале 9 монет взвешиваем с помощью гирь. Если нет равенства мы уже знаем, тяжелее или легче фальшивая и она среди этих девяти. Дальше требуется только два взвешивания. В противном случае аналогично взвешиваем три монеты из оставшихся 4.

[Senik]

Была нам задана задачка давно-давно :
Определить из 12-ти монет одну фальшивую при помощи трёх взвешиваний. (без гирь) , причем неизвестно, фальшивая монета тяжелее или легче . Решили ...
Правда повозится пришлось

[Xenia1996]

Senik в сообщении #434851 писал(а):

Была нам задана задачка давно-давно :
Определить из 12-ти монет одну фальшивую при помощи трёх взвешиваний. (без гирь) , причем неизвестно, фальшивая монета тяжелее или легче . Решили ...
Правда повозится пришлось

Вот эта?

Или вот эта?

[maxal]

Про оценки на количество монет при фиксированном количестве взвешиваний - см. topic745.html

[Senik]

Xenia1996 в сообщении #434890 писал(а):

Вот эта? Или вот эта?

Эта , эта . Надо-же , не все еще забыто !