Есть 68 монет, все они разные по весу. Как за 100 взвешиваний найти самую легкую и самую тяжелую?
Ответ: Взвешиваем попарно все монеты, легкие откладываем в одну кучку, тяжелые - в другую, всего получается 34 взвешивания. В первой кучке взвешиваем по очереди все монеты с наиболее легкой на данный момент, т.е. если попадается более легкая, то следующие монеты взвешиваются уже с ней, и так 33 раза. С правой кучкой - то же самое, но только выявляем наиболее тяжелую монету, также 33 взвешивания. Итого - ровно 100 взвешиваний.
Комментарии
Если взвешивать на обычных весах, то понадобится 68 взвешиваний. Опять неточная формулировка.
взвешиваем 34 раза монетки с распределением на более лёгкие и тяжелые попарно, затем взвешиваем среди более лёгких по одной , выбирая саамую лёгкую для дальнейшего взвешивания аж 33 раза и таким же образом с тяжелыми . только выбирая потяжелее 33 раза . в итоге находим за 34+33+33=100 взвешиваний более легкую и более тяжелую монетку.
но монеты могут найтись раньше, чем 33 раза. и тогда это будет еще быстрей
Могут найтись, но быстрее не будет. Надо же убедиться, что они самые легкие.
Для определения самого легкого или самого тяжелого "попарно" (2 и 2) взвешивать нельзя, т.к. если самая легкая попадает в пару к самой тяжелой, то эта пара будет отнесена только в одну категорию - либо в легкие, либо в тяжелые. Далее взвешивать уже бесполезно - правильного решения не найти.
Это решение напрашивается сразу, но не обязательно самая легкая монета будет в той куче, где легкие "пары" монет.
Обязательно. Самую легкую монету перевесит любая из монет, следовательно она обязательно попадет в "легкую" кучку. Аналогично, самая тяжелая монета перевесит любую из монет, поэтому неизбежно окажется в "тяжелой" кучке. ))
взвесить с помощью электронных весов по 1 монете, записав вес. И не надо еще 32 глупых взвешивания делать :))))
Допустим самая легкая монетка весит 5 грамм, а самая тяжелая 10 грамм. Мы взвешиваем по парно все монеты, и нам попадается следующая комбинация - 5 и 10 граммовые монеты оказались на одной чаше весов, а на другой обе 8ми граммовые монеты (то есть где-то из середины по весу. Пятнадцать против шестнадцати и мы откладываем самую тяжелую монетку к легким и большее ее не определим. В итоге задачу таким способом решить нельзя.
Адаро, вы о чем? Мы не кладем больше одной монеты на каждую сторону весов :)
Можно найти и за 7 взвешиваний
Можно за 96 найти. За 34 раза распределяем монеты на две кучки - более легкие и более тяжелые. Затем так же распределяем каждую кучку, получается по 16 взвешиваний. Потом эти кучки делим еще на 2 (по 8 взвешиваний) и еще на 2 (по 4 взвешивания), и еще на 2 (по 2 взвешивания), и наконец выбираем из двух пар самую легкую и самую тяжелую (по 1 взвешиванию). Итого: 34 + (16 * 2) + (8 * 2) + (4 * 2) + (2 * 2) + (1 * 2) = 96
Mojno 3a 68 naiti. V3vesit vse po o4eredi, 3apisivaia kajdyju. Potom vi yje dogadalis.
a ja woobsche na glas mogu opredelitj))
В задании обязательно надо указывать что весы с 2-мя чашами, иначе я смог бы взвесить и за68 взвешиваний)