С помощью чашечных весов без гирь требуется найти 7 настоящих монет в куче из 63 монет. При этом известно, что там присутствует всего 7 фальшивых монет. Все настоящие монеты весят одинаково. Также одинаково между собой весят и все фальшивые. Однако, вес фальшивой меньше веса настоящей. Как найти нужные монеты всего за три взвешивания?
update
Первым правильно ответил Илья.Ответ
1. Положим на чаши весов по 31 монете. Если весы в равновесии, то отложена фальшивая и на каждой чаше по 3 фальшивых монеты. Если одна из чаш тяжелее, то на ней не более трёх фальшивых монет. То есть, после первого взвешивания мы определили 31 монету, среди которых не более трёх фальшивых.
2. Полученные после первого взвешивания монеты разделим на две кучки по 15 монет и положим их на две чаши весов, а оставшуюся монету отложим. В результате второго взвешивания можно определить 15 монет среди которых будет не более одной фальшивой.
3. Полученные после второго взвешивания монеты разделим на две кучки по 7 монет, которые будем сравнивать на весах, а оставшуюся монету опять откладываем. Если весы в равновесии, то на обоих чашах по 7 настоящих монет. Если весы не в равновесии, то настоящие монеты будут на чаше, которая окажется тяжелее.
2. Полученные после первого взвешивания монеты разделим на две кучки по 15 монет и положим их на две чаши весов, а оставшуюся монету отложим. В результате второго взвешивания можно определить 15 монет среди которых будет не более одной фальшивой.
3. Полученные после второго взвешивания монеты разделим на две кучки по 7 монет, которые будем сравнивать на весах, а оставшуюся монету опять откладываем. Если весы в равновесии, то на обоих чашах по 7 настоящих монет. Если весы не в равновесии, то настоящие монеты будут на чаше, которая окажется тяжелее.
Из этой же серии - про 12 монет и одну фальшивую.
1 взвешивание: сравниваем две кучки по 31 монете. Если веса равны, то с каждой стороны по 3 фальшивых ровно. Если не равны, то в кучке большего веса не больше трех фальшивых монет.
ОтветитьУдалитьПосле первого взвешивания имеем группу из 31 монеты, в которой не более 3х фальшивых.
Дальше поступаем аналогично.
2 взвешивание: сравниваем две кучки по 15 монет (из группы, выбранной первым взвешиванием). Если веса равны, то на каждой чашке не более одной фальшивой, а если не равны - то на более тяжелой не более одной фальшивой.
После второго взвешивания имеем кучку из 15 монет, в которой не более одной фальшивой.
3 взвешивание: из этой кучки выбираем две подкучки по 7 и сравниваем.
Если веса равны, то все 14 настоящие. Если нет, то более тяжелая кучка состоит из настоящих монет.
У меня такой же ответ!
Удалитьможно поделить монеты на 9 кучек по 7 монет в 2х кучках минимум будут только настояшие монеты, дальше ишем самую тяжелую кучку
ОтветитьУдалитьНе годится. Допустим, на первых двух взвешиваниях вышло равенство. В задаче о поиске одной тяжелой монеты среди 9 это означает, что еще не взвешенная монета и есть искомая. Здесь же количество вариантов удручает, и третье взвешивание не поможет сильно их сузить.
УдалитьАлгоритм подразумевает (это же он имеется в виду?), что мы сравним сначала суммарные веса кучек 1, 2, 3 с тройкой 4, 5, 6, а при равенстве кладем на весы кучки 7 и 8.
Но это может произойти в огромном числе случаев, достаточно привести несколько (по количеству фальшивок в кучке по порядку номеров):
А) 0-0-0=0-0-0=0-0-7
Б) 0-0-0=0-0-0=3-3-1
В) 1-1-1=1-1-1=0-0-1
Г) 0-0-1=0-0-1=2-2-1
Д) 0-0-2=1-1-0=0-0-3
Вроде так тоже получается, если на 9 кучек разделить и их потом не перемешивать. Но действовать, конечно, нужно иначе: первым взвешиванием на каждую чашку весов положить по 4 кучки, т.е. по 28 монет. Очевидно, что на более тяжелой чашке есть по крайней мере одна семерка, состоящая из настоящих монет. Если равенство, то такая семерка есть на каждой чашке.
УдалитьВторым взвешиванием сравниваем две пары семерок с более тяжелой (или любой) чашки. Поскольку на эти четыре семерки не более трех тяжелых монет, то опять более тяжелая чашка (или любая при равенстве) содержит по крайней мере одну настоящую семерку.
Третьим взвешиванием сравниваем две семерки и выбираем более тяжелую.
Это очень близко к тому решению, что я написал выше, только чуть-чуть другое :)