А вот еще про взвешивания

Borr · Post by **Borr** » 16 Oct 2001 11:08

Не сложная, но интересная...

Есть двадцать достаточно больших мешков с монетами. В одном из них все монеты фальшивые. Про фальшивую монету известно, что она по весу отличается от настоящей ровно в два раза.

Имеются рычажные весы. Требуется найти мешок с фальшивыми монетами за ОДНО взвешивание.
Взвешивание определяется так - вы можете загрузить одну чашку весов, потом добавляя монеты на другую чашку, уравновесить весы. Снимать уже положенные монеты нельзя, загружать чашки частями и по-очереди нельзя.

Vovka · Post by **Vovka** » 16 Oct 2001 13:11

<BLOCKQUOTE>quote:<HR>Originally posted by Borr:
Не сложная, но интересная...

Есть двадцать достаточно больших мешков с монетами. В одном из них все монеты фальшивые. Про фальшивую монету известно, что она по весу отличается от настоящей ровно в два раза.

Имеются рычажные весы. Требуется найти мешок с фальшивыми монетами за ОДНО взвешивание.
Взвешивание определяется так - вы можете загрузить одну чашку весов, потом добавляя монеты на другую чашку, уравновесить весы. Снимать уже положенные монеты нельзя, загружать чашки частями и по-очереди нельзя.<HR></BLOCKQUOTE>

Положим на первую чашку 1 монету из первого мешка, 2 из второго и т.д. до 20. Если бы все монеты были настоящими, вес мешка был бы (1+20)*20/2 наст. монет. Путь в мешке x монеты фальшивые. Тогда вес этих монет будет (1+20)*20/2 – x/2 монет. Теперь добавляем на вторую чашку монеты по одной из какого-то одного мешка, пока чашки не сравняются. Подсчитываем число монет на второй чашке, пусть это w. Решаем уравнение

(1+20)*20/2 – x/2 = w

относительно x.

Если же мы выложили на вторую чашку (1+20)*20/2 монет, а первая всё ещё перевешивает, то мешок, из которого брали монеты на вторую чашку, фальшивый.

Я сначала почему-то решил класть 1 монету из первого мешка, 2 из второго, 8 из третьего, 16 из четвёртого и т.д. – по пормуле 2**n. Потом понял, что возможна любая формула, при которой можно составить приведённое выше уравнение, выбрал f(n) = n как наиболее простую.

Vovka · Post by **Vovka** » 16 Oct 2001 13:14

Упс, поправочка. При формуле

f(n) = n

Полученное уравнение допускает дробное решение, что практически неудобно. Пусть будет

f(n) = 2n

viv · Post by **viv** » 16 Oct 2001 15:47

Ребята - будьте проще - зачем вообще нужны весы для того чтобы из 20 достаточно больших ( как говориться в условии ) мешков найти один который явно в 2 раза легче любого другого ?

Vovka · Post by **Vovka** » 16 Oct 2001 17:29

<BLOCKQUOTE>quote:<HR>Originally posted by viv:
Ребята - будьте проще - зачем вообще нужны весы для того чтобы из 20 достаточно больших ( как говориться в условии ) мешков найти один который явно в 2 раза легче любого другого ?<HR></BLOCKQUOTE>

Так никто ведь не сказал о том, что кол-во монет в мешках одинаковое.

Shin · Post by **Shin** » 16 Oct 2001 18:00

<BLOCKQUOTE>quote:<HR>Originally posted by Vovka:

Я сначала почему-то решил класть 1 монету из первого мешка, 2 из второго, 8 из третьего, 16 из четвёртого и т.д. – по пормуле 2**n. <HR></BLOCKQUOTE>

Да, нехилые мешочки должны быть [img:e552c236d1]images/smiles/icon_smile.gif[/img:e552c236d1]
1 мегамонета при весе даже в 1 грамм на единицу будет весить больше тонны [img:e552c236d1]images/smiles/icon_smile.gif[/img:e552c236d1]

viv · Post by **viv** » 16 Oct 2001 18:51

<BLOCKQUOTE>quote:<HR>Originally posted by Vovka:


Так никто ведь не сказал о том, что кол-во монет в мешках одинаковое.<HR></BLOCKQUOTE>

ок - раз так то просто грубо по горсти монет с каждого мешка сравнить в любом случае при такой разнице весов ( аж в 2 раза ) бежать за весами - просто нелепо )) - тем более решать уравнения )

Borr · Post by **Borr** » 17 Oct 2001 20:13

Ну, я же говорил что просто - именно так - 2 из первого, 4 из второго, потом 6, 8, ....

Borr · Post by **Borr** » 17 Oct 2001 20:16

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