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

и задачки для интервью.
Borr
Новичок
Posts: 33
Joined: 19 Feb 2001 10:01
Location: Estonia

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

Post by Borr »

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

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

Имеются рычажные весы. Требуется найти мешок с фальшивыми монетами за ОДНО взвешивание.
Взвешивание определяется так - вы можете загрузить одну чашку весов, потом добавляя монеты на другую чашку, уравновесить весы. Снимать уже положенные монеты нельзя, загружать чашки частями и по-очереди нельзя.
Vovka
Уже с Приветом
Posts: 1906
Joined: 14 Mar 2001 10:01

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

Post by Vovka »

<BLOCKQUOTE><font size="1" face="Arial, Verdana, Helvetica, sans-serif">quote:</font><HR>Originally posted by Borr:
<STRONG>Не сложная, но интересная...

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

Имеются рычажные весы. Требуется найти мешок с фальшивыми монетами за ОДНО взвешивание.
Взвешивание определяется так - вы можете загрузить одну чашку весов, потом добавляя монеты на другую чашку, уравновесить весы. Снимать уже положенные монеты нельзя, загружать чашки частями и по-очереди нельзя.</STRONG><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
Уже с Приветом
Posts: 1906
Joined: 14 Mar 2001 10:01

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

Post by Vovka »

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

f(n) = n

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

f(n) = 2n
User avatar
viv
Уже с Приветом
Posts: 816
Joined: 10 Apr 2000 09:01

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

Post by viv »

Ребята - будьте проще - зачем вообще нужны весы для того чтобы из 20 достаточно больших ( как говориться в условии ) мешков найти один который явно в 2 раза легче любого другого ?
Vovka
Уже с Приветом
Posts: 1906
Joined: 14 Mar 2001 10:01

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

Post by Vovka »

<BLOCKQUOTE><font size="1" face="Arial, Verdana, Helvetica, sans-serif">quote:</font><HR>Originally posted by viv:
<STRONG>Ребята - будьте проще - зачем вообще нужны весы для того чтобы из 20 достаточно больших ( как говориться в условии ) мешков найти один который явно в 2 раза легче любого другого ?</STRONG><HR></BLOCKQUOTE>

Так никто ведь не сказал о том, что кол-во монет в мешках одинаковое.
User avatar
Shin
Уже с Приветом
Posts: 5738
Joined: 04 Dec 2000 10:01
Location: MN -> Moscow -> Thailand

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

Post by Shin »

<BLOCKQUOTE><font size="1" face="Arial, Verdana, Helvetica, sans-serif">quote:</font><HR>Originally posted by Vovka:
<STRONG>
Я сначала почему-то решил класть 1 монету из первого мешка, 2 из второго, 8 из третьего, 16 из четвёртого и т.д. – по пормуле 2**n. </STRONG><HR></BLOCKQUOTE>

Да, нехилые мешочки должны быть [img:e552c236d1]images/smiles/icon_smile.gif[/img:e552c236d1]
1 мегамонета при весе даже в 1 грамм на единицу будет весить больше тонны [img:e552c236d1]images/smiles/icon_smile.gif[/img:e552c236d1]
User avatar
viv
Уже с Приветом
Posts: 816
Joined: 10 Apr 2000 09:01

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

Post by viv »

<BLOCKQUOTE><font size="1" face="Arial, Verdana, Helvetica, sans-serif">quote:</font><HR>Originally posted by Vovka:
<STRONG>

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

ок - раз так то просто грубо по горсти монет с каждого мешка сравнить в любом случае при такой разнице весов ( аж в 2 раза ) бежать за весами - просто нелепо )) - тем более решать уравнения )
Borr
Новичок
Posts: 33
Joined: 19 Feb 2001 10:01
Location: Estonia

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

Post by Borr »

Ну, я же говорил что просто - именно так - 2 из первого, 4 из второго, потом 6, 8, ....
Borr
Новичок
Posts: 33
Joined: 19 Feb 2001 10:01
Location: Estonia

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

Post by Borr »

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

Return to “Головоломки”