Задача на взвешивание монет.

[integral2009]

У нузимата есть 100 одинаковых по внешнему виду монет. Он знает, что стреди них 30 настоящих и 70 фальшивых. Кроме того, он знает, что массы всех настоящих монет одинаковы, а массы всех фальшивых монет -- разные, причем каждая фальшивая монета тяжелее настоящей, однако точные массы монет неизвестны.
Имеются двухчашечные весы без гирь, на которых можно за одно взвешивание сравнить массы двух групп, состоящих из одинакового количества монет.
За какое наименьшее количество взвешиваний на этих весах, нузимат может гарантированно найти хотя бы одну настоящую монету?

Самая легкая -- настоящая монета. Заглавные буквы -- название кучек, прописные -- количество монет в них.
Разбиваем на две кучки $A$ и $B$ по 50 монет.
1) Взвешиваем, для определенности будет результат $a\ge b$.
Значит в кучке $B$ будет $b\ge 15$ монет настоящих.
2) Взвешиваем по 25 монет из кучки $B$, получаем разбиение на $C$ и $E$.
Для определенности $c\ge e$, тогда в кучке $E$ будет $e\ge 8$ настоящих монет.
3) Рассматриваем кучку $E$, разбиваем ее на две кучки $F$ и $G$ по 12 монет в каждой, + еще одна отложенная монета.
Для определенности $f\ge g$, тогда в кучке $F$ будет $g\ge 4$ настоящие монеты.
4) Кучку $G$ разбиваем на $K$ и $L$ по шесть монет в каждой, для определенности $k\ge l$, тогда в кучке $L$ будет $l\ge 2$[/math] настоящих.
5) Кучку $L$ разбиваем на $M$ и $N$ по три монеты в каждой, для определенности $m\ge n$, тогда в кучке $N$ будет $n\ge 1$[/math] настоящая.
6) Берем кучку $N$ из трех монет. Выбираем две из них, взвешиваем. Если будет равенство, то это настоящие. Если одна будет легче, то она настоящая.
То есть 6 взвешиваний. Но как доказать, что число 6 нельзя уменьшить? Верно ли проведены рассуждения?

[Sender]

1) Может оказаться, что в $B$ вообще нет настоящих монет, но в $A$ фальшивые довольно-таки увесистые.

[Cash]

integral2009 в сообщении #1030095 писал(а):

1) Взвешиваем, для определенности будет результат $a\ge b$.
Значит в кучке $B$ будет $b>=15$ монет настоящих.

Это было бы верным, если бы фальшивые тоже весили одинаково. А так, например, в кучке $A$ лежит фальшивая монета с весом большим, чем все остальные вместе взятые. Тогда в кучке $B$ настоящих может и не быть.

Одинаково мыслим :)

[integral2009]

Спасибо! А как тогда поступить, это ведь существенно усложняет задачу.

Пока что могу грубо оценить сверху. Попарно взвешиваем монеты. Если хоть однажды наступит равновесие в паре, то это настоящие. Берем первые две, тяжелую в мусорку, легкую оставляем. Берем оставшуюся легкую и еще одну монету, далее тяжелую выкидываем. И так 99 взвешиваний максимум. Но ясно, что это число можно уменьшить (на мой взгляд)

[venco]

integral2009 в сообщении #1030105 писал(а):

Попарно взвешиваем монеты. Если хоть однажды наступит равновесие в паре, то это настоящие. Берем первые две, тяжелую в мусорку, легкую оставляем. Берем оставшуюся легкую и еще одну монету, далее тяжелую выкидываем. И так 99 взвешиваний максимум. Но ясно, что это число можно уменьшить (на мой взгляд)

А сколько всего фальшивых по условиям задачи?

[Cash]

И остается вопрос - как доказать, что монеты объединять бессмысленно.

[Утундрий]

http://elementy.ru/problems/1093