Всем, решить )) из пяти монет - две фальшивые. одна из фальшивых монет легче настоящей. а другая - на столько же тяжелее настоящей. объясните, как за три взвешивания на чашечных весах без гирь найти обе фальшивые монеты. заранее за понятный ответ: 3
Обозначим Л-легкую монету, Т-тяжелую, Н-настоящую. Берем 4 монеты, кладем по 2 на каждую чашу. Варианты НТ>НН, НЛ<НН, НН=ЛТ. Очевидно, что если чаши показывают равенство, значит легкая и тяжелая лежат в одной чаще, оставшаяся(пятая) монета, настоящая. Сравним заведомо настоящую с монетой из любой чаши весов. Если она равна по весу, то очевидно, что обе фальшивые лежат в другой чаще, если они не эквивалентны, то обе фальшивки лежат в выбранной группе. Далее, если чащи показали неравенство, тогда возможны два варианта. НТ>НН, НЛ<НН. Тогда оставщаяса монетка-точно фальшивая. И она либо Т, либо Л. Сравниваем заведомо фальшивую монету с любой. Логично, что если она будет тяжелее, то эта монета является фальшивой тяжелой, если легче-фальшивой легкой. Если она легкая. то фальшивая тяжелая находится в группе, которая после 1ого взвешивания оказалась тяжелее. Если после второго взвешивания нам показало, что заведомо фальшивая тяжелее, то вторая фальшивая находится в группе, которая показала после 1ого взвешивания, что она легче. Мы определили в какой группе лежит фальшивая монета, значит во второй группе лежит обе настоящии. Сравним одну из них с любой из первой группы, если они равны, то оставшаяся из первой группы-фальшивая, если не равны, то выбранная из первой группы.
Поскольку весы именно чашечные, то задача нахождения фальшивой монеты из N сводится к бинарному поиску - мы каждый раз делим исходную кучку пополам (или на три части, если пополам не делится), определяем ту, которая легче, затем поступаем с ней аналогично. И т.д. пока сравнение не сведется к 2-м монетам - более легкая из них и есть искомая. При этом для N монет нам понадобится log2(N) взвешиваний. Если N не степень двойки, то округление идет до ближайшей СЛЕДУЮЩЕЙ. Т.о. в нашем примере log2(N) = 4. Откуда N = 2^4 = 16. 16 монет.
Берем 4 монеты, кладем по 2 на каждую чашу. Варианты НТ>НН, НЛ<НН, НН=ЛТ.
Очевидно, что если чаши показывают равенство, значит легкая и тяжелая лежат в одной чаще, оставшаяся(пятая) монета, настоящая. Сравним заведомо настоящую с монетой из любой чаши весов. Если она равна по весу, то очевидно, что обе фальшивые лежат в другой чаще, если они не эквивалентны, то обе фальшивки лежат в выбранной группе.
Далее, если чащи показали неравенство, тогда возможны два варианта. НТ>НН, НЛ<НН.
Тогда оставщаяса монетка-точно фальшивая. И она либо Т, либо Л.
Сравниваем заведомо фальшивую монету с любой. Логично, что если она будет тяжелее, то эта монета является фальшивой тяжелой, если легче-фальшивой легкой. Если она легкая. то фальшивая тяжелая находится в группе, которая после 1ого взвешивания оказалась тяжелее. Если после второго взвешивания нам показало, что заведомо фальшивая тяжелее, то вторая фальшивая находится в группе, которая показала после 1ого взвешивания, что она легче. Мы определили в какой группе лежит фальшивая монета, значит во второй группе лежит обе настоящии. Сравним одну из них с любой из первой группы, если они равны, то оставшаяся из первой группы-фальшивая, если не равны, то выбранная из первой группы.