Двенадцать монет
*
Имеется 12 одинаковых на вид монет, одна из которых фальшивая, но неизвестно, легче она или тяжелее, чем другие. За 3 взвешивания на весах без гирь найдите фальшивую.
Занумеруем наши монеты числами от 1 до 12. Алгоритм (ветвящийся) следующий:
Производим 1-е взвешивание. Кладём на чаши наборы 1, 2, 3, 4 и 5, 6, 7, 8. Возможны два случая:
Весы в равновесии. Это значит, что фальшивая среди оставшихся с 9 до 12 монет. Сравниваем монеты 9 и 10 с 1 и 2. Возможны 2 варианта:
Если равновесие, то фальшивая одна из двух — 11 или 12. Сравниваем монету 11 с монетой 1. Если равновесие, то фальшивая монета 12, в противном случае фальшивая монета 11.
Если равновесия нет, то фальшивая — одна из 9 и 10, причем известно даже, легче она или тяжелее настоящей. Аналогично предыдущему случаю, фальшивая монета находится сравнением монеты 9 с монетой 1. (Либо можно просто сравнить 9 и 10 между собой, так как мы уже знаем, легче фальшивая монета или тяжелее.)
(основной случай). Чаша А легче, значит, фальшивая монета среди взвешиваемых. Производим 2-е взвешивание. Кладём на чаши наборы 9, 10, 11, 4 и 1, 2, 3, 8. Возможны три случая.
Чаша А по-прежнему легче. Тогда фальшивая одна из двух монет: 4 или 8 (их положение не менялось). И достаточно одного взвешивания для её обнаружения.
Весы уравновесились. Фальшивая одна из монет 5, 6, 7, причём она тяжелее настоящей. Сравниваем монеты 5 и 6. Если они равны по весу, то фальшивая монета 7, в противном случае фальшивая та из них, которая оказалась тяжелее.
Легче стала чаша Б. Фальшивая одна из монет 1, 2, 3, и она легче настоящей. Аналогично предыдущему варианту, фальшивая монета определяется сравнением монет 1 и 2.
Комментарии
Неправильный вариант ответа мы не знаем монета тяжелее или легче
А если 1 куча тоесть 1234 больше 5678 ТО дайте мне решение на этот вопрос
Руслан, приведённое решение является правильным, хотя, возможно, и не максимально подробным. Знать заранее, тяжелее фальшивая монета настоящей или легче, не нужно, и, как видно из решения, даже после трёх взвешиваний это не всегда становится ясным. Случай, когда чаша А оказывается тяжелее чаши Б, полностью аналогичен основному случаю №2 с точностью до перенумерования монет. Фактически, вы можете просто положить на чаши весов по 4 монеты, а затем, если одна чаша окажется легче другой, занумеровать монеты в более лёгкой чаше числами от 1 до 4, монеты в более тяжёлой чаше — числами от 5 до 8, о оставшиеся в стороне монеты — числами от 9 до 12. Так вы всегда сможете в точности воспроизвести вариант №2.
Тут совершенно неважно, тяжелее или легче фальшивая монета-предположим, что легче. Делим монеты на 3 части по 4 монеты. Ч1, Ч2, Ч3. Взвешиваем Ч1 и Ч2. Если равновесие - фальшмонета в Ч3, если неравновесие - она или в Ч1, или в Ч2. Берём ту часть, которая с фальшмонетой и из неё по две монеты кладём на весы. Из лёгкой половины взвешиваем две монеты, одна из которых легче. Вот и всё-3 взвешивания.
Very valid, pithy, succcnit, and on point. WD.
Добавить комментарий