Из опыта советую не спешить, решать письменно. Головоломка «12 монет, 3 взвешивания» несколько раз возникала в моей жизни. Первый раз ее задал мне мой товарищ-олимпиадник, решил я ее после олимпиады и пришлось пару часиков поломать голову. И через несколько лет она далось мне не сразу. Если желаете решить самим — делайте на листочке.
Ниже будет разбор и этапы решения. Этапы проведут по универсальной методике решения задач, которая применима как к программированию, так и к жизни. Благодаря подходу решение головоломки станет простым.
Предлагаю вам, прежде чем читать предложить решение. У вас есть ответ? Проверенный?
Если бы это было программного обеспечения вопросы были бы следующие: «Вы запрограммировали, протестировали алгоритм? Рассмотрели тестовые случаи и проверили их?».
Как показывает опыт, чтобы решить требуется нарисовать дерево решений и проверить все 12 случаев.
1) Понижение энтропии (меры неопределенности) и ответы на вопросы:
- Что узнали на предыдущем шаге?
- Что снижает неопределённость?
- Какой информацией располагаем?
- Что еще нужно узнать?
Вопросы подходят для любой задачи, проектов. Ответы на них помогают в снижении рисков срыва сроков, перерасхода бюджета и получения нагоняя от начальства.
2) Декомпозиция. Подход от простого к сложному. Если подготовить решение простейших случаев, затем использовать их для решения задачи (алгоритм разделяй и властвуй) то, будет проще, чем представлять всю ситуацию в голове.
Алгоритмы «разделяй и властвуй» разбивают задачу на две или более подзадачи того же типа, но меньшего размера до элементарных задач и объединяют их решения для получения ответа к исходной задаче.
Составьте вопросы для декомпозиции. Какие бы вы предложили?
1) Какая ситуация самая элементарная? Что можем сделать за одно взвешивание?
За одно взвешивание можем определить, какая монета тяжелее, равен ли вес монет.
2) Если у нас 2 монеты, и, известно, фальшивая тяжелее или легче. Как за одно взвешивание определить фальшивую?
Необходимо взвесить монеты, и в зависимости от стрелки весов определить фальшивую.
3) Если у нас 2 монеты, и, не известно, фальшивая тяжелее или легче, как за одно взвешивание определить фальшивую?
Взвесив одну из 2-х представленных монет с третьей монетой, про которую известно, что она подлинная.
4) Если у нас 3 монеты, и, известно, фальшивая тяжелее или легче. Как за одно взвешивание определить фальшивую?
Необходимо сравнить любые две из этих монет, если они равны, фальшивой является третья монета.
5) Если у нас 3 монеты, и, неизвестно, фальшивая тяжелее или легче. Можно ли определить фальшивую за одно взвешивание?
К сожалению, нет.
6) Если у нас 4 монеты, и, неизвестно фальшивая тяжелее или легче, можно определить фальшивую за одно взвешивание?
К сожалению, нет.
7) Если у нас 4 монеты, и, неизвестно, фальшивая тяжелее или легче, за сколько взвешиваний можно определить фальшивую?
За два взвешивания.
Далее из элементарных случаев соберем ситуации из 8, 9, 10, 11 и 12 монет. Как вы видите решение?
Ниже полное решение.
Сравним первые две группы. Возможны три варианта:
- первая группа тяжелее;
- вторая группа тяжелее;
- равны.
1) Если группы равны, то фальшивая монета находится в третьей группе. Необходимо найти фальшивую монету из 4 монет за два взвешивания.
Делим третью группу на две: 9 10 11 12
Сравниваем 9 и 10:
- если они равны, то фальшивая монета во второй группе – сравниваем 9 и 11. Если 9 и 11 равны — то фальшивая – 12, если нет -11
- если они не равны, то фальшивая в первой группе – сравниваем 10 и 12. Если 10 и 12 равны – фальшивая – 9, если нет – 10.
Таким образом мы нашли фальшивую монету.
2) Рассмотрим второй случай. Если первая группа тяжелее второй, то присваиваем первой группе знак «>», второй группе знак «<», третьей группе – «0».
Делим монеты на группы 1 9 10 11 и 5 2 3 4, взвешиваем. Возможны три варианта:
- Равны. Фальшивая монета находится среди чисел: 6 7 8. Сравниваем 6 и 7, если равны – фальшивая — 8, если 6 больше, то фальшивая – 7, если 7 больше, то фальшивая – 6, так как в данном случае фальшивая монета легче.
- Первая группа тяжелее, то фальшивая монета либо 1, либо 5. Сравниваем 1 и 9, если они равны – фальшивая монета — 5, если нет — 1.
- Первая группа легче, то фальшивая среди монет 2 3 4, так как известно, что 9, 10 и 11 настоящие, и перевесить вторая группа может только за счет монет 2, 3 и 4. Сравниваем 2 и 3, если равны – фальшивая 4, если 2 тяжелее, то фальшивая – 2, иначе 3-я является фальшивой.
3) Случай когда вторая группа тяжелее первой, аналогичен второму.
Общая диаграмма «Дерева решений» представлена ниже.
- Определиться, что дано?
- На какие элементарные случаи\задачи можно разложить?
- Что неизвестно для решения задачи? Какие эксперименты нужно провести, чтобы снизить энтропию?
- Выполнить.
- Задача решена? Нет? Вернуться к шагу 1.
Успешных решений.
Комментарии (46)
FGV
09.04.2019 14:19За 3 взвешивания необходимо найти фальшивую монетку и определить легче она или тяжелее.
Решение не до конца.
basilio
09.04.2019 16:10Хм, я уверен, что я тоже это видел, но похоже автор уже изменил условия чтобы они соответствовали его решению…
В любом случае, оригинальная задача показалась мне интереснее и я ее, кажется, решил:
РешениеКак найти фальшивую монетку и определить легче она или тяжелее.
монеты пронумерованы от 1 до 12, подчеркнутые номера — заведомо настоящие монеты по результатам предыдущих взвешиваний, CF — counterfeit, L — is lighter, H — is heavier. На линиях результат взвешивания и известная на данный момент информация.
image uploadCrzyDocTI
10.04.2019 09:02В любом случае из условий
Неизвестно легче или тяжелее
— соответственно и относительный вес монеты будет найден.basilio
10.04.2019 12:00К сожалению, нет. Я не буду проверять все варианты, но очевидно, что алгоритм не работает на примере 12 монеты. В посте решение о том, что она фальшивая принимается в результате цепочки, в которой 12 монета вообще ни разу не оказывается на весах — 1234 = 5678, 9 = 10, 10 = 11. В данном случае она может быть легче, тяжелее, и даже точно такого же веса.
JC_IIB
09.04.2019 14:20Тут было неправильное решение, я его, пожалуй, сотру. Спасибо людям из комментов ниже за указание на ошибку.
Vantela
09.04.2019 14:23А если фальшивая монета легче чем оригинал?
UPD: О! Исправились:) Но не до конца.
И я тогда дополню.
Не известно же легче фальшивка или тяжелее)
Sirion
09.04.2019 14:24+1Стоило потратить ещё минуту на внимательное чтение условия) вы решили не ту задачу.
boxvk257
09.04.2019 15:32Раньше думал, эта задача имеет единственное решение. Теперь появилась новая задача — сколько решений имеет эта задача?
basilio
09.04.2019 16:50На самом деле выше я пропустил две ветви в самом конце решения. Вот тут полное дерево:
РешениеКак найти фальшивую монетку и определить легче она или тяжелее.
монеты пронумерованы от 1 до 12, подчеркнутые номера — заведомо настоящие монеты по результатам предыдущих взвешиваний, CF — counterfeit, L — is lighter, H — is heavier. На линиях результат взвешивания и известная на данный момент информация.
image upload
ksbes
09.04.2019 17:04Ну допустим я злоумышленник и подложил «облегчённую» монету №7 где для неё вариант?
И тут вообще только 16 вариантов из 24 (12* L-H) возможных.
Или я что-то упустил?basilio
09.04.2019 17:07Похоже что упустили. Если 7 (или 5, 6 или 8) монета легче сработает блок "… swap 1234 with 5678". Алгоритм то один и тот же на самом деле, я решил сэкономить место и не расписывать оба варианта. Просто поменяйте кучки 1234 и 5678 местами и продолжайте, теперь легкая монета будет иметь индекс 3. Прошу прощения за неочевидность.
ksbes
09.04.2019 17:18Ок да, разобрался. Странноватый алгоритм, кажется что можно проще. Интересно, сколько вообще существует алгоритмов решения данной задачи?
basilio
09.04.2019 17:21-1Я пока знаю только одно решение, мое. Решение автора я не считаю решением первоначальной задачи, так как оно не отвечает на вопрос легче или тяжелее?
Вы знаете другие решения? Поделитесь?p_fox
10.04.2019 11:07Решение автора отвечает на вопрос "легче или тяжелее" на втором-третьем взвешивании, в зависимости от результатов взвешивания. Единственное исключение — когда после первого взвешивания, фальшивая монета оказывается в третьей группе, и в последующие 2 взвешивания она не попадает. Тогда да, ее вес неизвестен.
Habra_nik
09.04.2019 21:45Три, как минимум -> mathforum.org/library/drmath/view/55618.html. Мне второе больше всех нравится, хотя (во всех) коряво то, что монеты по условию выглядят одинаково, а если их пронумеровать, то выглядеть одинаково они перестанут.
AmartelRU
09.04.2019 17:28Вместо сравнения 1 2 5 6 vs 4 8 11 12 достаточно сравнить 5 6 12 vs 4 7 8. И «тройки» сравнивать чуть легче, чем «четвёрки», и «лёгкость» фальшивой монеты более однородно по случаям распределится. У Вас в каждом из трёх случаев она может быть как легче, так и тяжелее нормальной. А в данном варианте в случае "=" монета всегда H, при сохранении неравенства ">" монета всегда L, и только при смене неравенства на "<" будут смешанные варианты.
side2k
09.04.2019 17:35+2Если не ошибаюсь, где-то во второй половине девяностых, целое семейство задач про монеты, с их подробным разбором было опубликовано в журнале Компьютерра. Я, тогда ещё школьник, здорово помучился, пока не сообразил, что, взвешивая две из трёх частей, мы не только сужаем количество монет, среди которых фальшивая, но и получаем гарантированно «настоящие» эталоны, которые можно использовать в последующих взвешиваниях.
kvaks
09.04.2019 19:45А почему нельзя так?
1 взвешивание 6vs6
2 взвешивание 3vs3
3 взвешивание 1vs1 и если равны то оставшаяся?AmartelRU
09.04.2019 20:11Потому что неизвестно, является ли фальшивая монета легче или тяжелее настоящей. Вы взвешиваете 6 vs 6 и одна группа монет тяжелее другой. Но что это значит? В тяжёлой группе есть тяжёлая фальшивая монета или же в лёгкой группе — лёгкая фальшивая монета? Ноль полезной информации.
Xander_Vi
09.04.2019 20:23В первом же взвешивании уже неизвестно, какую из шестерок брать для второго взвешивания, так как фальшивая монета может быть как легче, так и тяжелее нормальной.
mikeus
10.04.2019 01:122) Рассмотрим второй случай. Если первая группа тяжелее второй, то присваиваем первой группе знак «>», второй группе знак «<», третьей группе – «0».
Делим монеты на группы 1 9 10 11 и 5 2 3 4, взвешиваем. Возможны три варианта:
- Равны. Фальшивая монета находится среди чисел: 6 7 8.
А двенадцатая монета куда подевалась?herodream Автор
10.04.2019 12:22Посмотрите внимательно 1-ый случай
1) Если группы равны, то фальшивая монета находится в третьей группе. Необходимо найти фальшивую монету из 4 монет за два взвешивания.
KonkovVladimir
10.04.2019 11:14Дано:
1214 монет, одна из них фальшивая, отличается только весом. Неизвестно легче или тяжелее. Даны рычажные весы, которые показывают, что груз с одной из сторон тяжелее. За 3 взвешивания необходимо найти фальшивую монетку, в распоряжении имеется одна настоящая монета.
Предполагаю, что можно решить задачу в общем случае для:
(3N+1)/2 монет + настоящая монета за N взвешиваний.
N = 1, монет = 2 + настоящая монета
N = 2, монет = 5 + настоящая монета
N = 3, монет = 14 + настоящая монета
и.т.д
Поскольку N взвешиваний дают log2(3N) бит информации — информация о местоположении фальшивой монете среди (3N+1)/2 монет и ее весе равна log2(3N+1) бит, однако в одном из вариантов взвешиваний, когда весы всегда были в равновесии, фальшивая монета никогда не попадает на весы и мы не знаем ее вес, т.е. количество информации сокращается до log2(3N) бит.
Лемма: (3N+1)/2 + 1 — всегда делится на 3 т.к (3N+1)/2 + 1 = 3*(3N-1 + 1)/2
Случай N=1, монет = 2 неизвестных + настоящая:
Делим монеты на 3 кучки, так чтобы настоящая была на одной из чашек весов.
С вероятностью 50% определяем вес фальшивой.
Случай N=2, монет = 5 неизвестных + настоящая:
Делим монеты на 3 кучки по 2, так чтобы настоящая была на одной из чашек весов.
Результат:
весы в равновесии => переход к случаю N=1
весы не в равновесии => (фальшивая монета на весах) => снимаем с весов одну неизвестную монеты, переставляем на ее место другую неизвестную монету с соседней чашки, возмещаем освободившееся место настоящей монетой.
Результат:
весы пришли в равновесие — фальшивую монету сняли
весы сменили показания — фальшивую монету переместили на другую чашку
весы не изменили показания — фальшивую монету не трогали.
Случай N=3, монет = 14 неизвестных + настоящая:
Делим монеты на 3 кучки по 5, так чтобы настоящая была на одной из чашек весов.
Результат
весы в равновесии => переход к случаю N=2
весы не в равновесии => (фальшивая монета на весах) => снимаем с весов 3 неизвестных монеты, переставляем на их место другие три неизвестных монеты с соседней чашки, возмещаем освободившееся место 3-мя настоящими монетами.
Результат
весы пришли в равновесие — фальшивую монету сняли
весы сменили показания — фальшивую монету переместили на другую чашку
весы не изменили показания — фальшивую монету не трогали.
+ стал известен вес фальшивой монеты
Третье взвешивание — определить фальшивую монету из трех монет при известном весе за одно взвешивание — тривиально.
P.S. Поскольку заведомо настоящая монета появляется только после первого взвешивания, в случае когда ее нет в самом начале, приходится стартовать с 13 неизвестных монет (разбить их на группы по 5+4+4), но этот способ вы можете сами найти.
P.P.S для просто 14 неизвестных монет, тоже хватает информации чтобы найти фальшивую монету, однако невозможно уравновесить весы в самом первом взвешивании.
Sirion
О, универсальная методика решения задач, ну наконец-то. Решите, пожалуйста, P = NP.
ksbes
Хотя я согласен с вашим общим настроем, но отмечу, что конкретно для этой задачки зависли на 2-й стадии (декомпозиции). Пока доказывают что-то для частных случаев, но «глобальной декомпозиции» пока провести не удалось.
P.S. не знаю, что там автор час думал, я в своё время решил минут за 5 — и был одним из последних в нашей группе ребят-олимпиадников, кто это сделал (выше городских не поднимался, да)
Sirion
Ну, я просто не люблю неоправданно громкие заголовки. «Полезная эвристика» звучало бы гораздо лучше.
А задачу я, кстати, в своё время решал довольно долго, чуть ли не полчаса. При том, что я был регулярный участник всероса.
herodream Автор
Спасибо за название.
MaxVetrov
Sirion
Вы упустили случай P=0, N — любое)
MaxVetrov
Да упустил,) я вам оставил пространство для маневра :)
Vantela
Мне учительница математики помню рассказывала.
Она подрядилась быть репетитором для старшекласника. Подготовка к поступлению в ВУЗ.
И вот на первом занятии она дает задает ему вопрос:
как можно преобразовать
six^2 x/cos^2 x
Получает ответ:
six
^2x/cos^2x =six
x/cosx=sin/cosin/co
На этом месте она поняла, что работы… предстоит много.
MaxVetrov
a как еще «шесть» сокращать? ) Шучу, видимо опячатка.
Не так много — только объяснить человеку, что такое тригонометрические функции, а сокращать дроби он умеет.)
Vantela
Блин. Действительно опечатался.
Но к концу сумел исправиться))
Настолько не знать, что такое тригонометрические функции — это надо было постараться.:)
Сокращать дроби тоже не умеет, кстати. «Квадраты» так не сокращают.
MaxVetrov
Кстати да, еще и степени объяснять надо… многочлены, квадратные уравнения, и т.д. Все друг за друга цепляется. В общем, много получается.)