Универсальная методика к решению задач на примере головоломки «12 монет, 3 взвешивания»

home.png  ГлавнаяЗагадкиВзвешиванияЗагадки №: 1..9 9 монет —>

Раздел: Загадки

     Есть 9 монет. Есть одни весы. Весы обычные, лабораторные (чашечные). Одна из 9 монет является легче, чем все другие. Как определить какая монета является легче? Монеты на весах можно взвесить лишь 2 раза. [ Ответ ]      Разделим 9 монет по 3 монеты в кучке. Две из 3-х кучек положим на разные стороны весов. Если весы не перевесили в одну из сторон, то выходит, что вес монеток является ровным, следовательно, легкая монета осталась в невзвешенной 3-ей кучке. С 3-мя монетами, которые остались, совершаем так же. Взвешиваем две монеты. Если их вес оказался ровным, то легкой будет невзвешенная монета. Есть 12 монет, одна из которых фальшивая. При этом неизвестно, в какую сторону она отличается от настоящих, т.е. она может быть как легче, так и тяжелее. В вашем распоряжении чашечные весы без гирь, как в аптеке. Нужно за три взвешивания найти фальшивую монету, а также выяснить, тяжелее она или легче.Решение Для удобства пронумеруем монеты от 1 до 12. Первым взвешиванием сравним две группы по четыре монеты: 1, 2, 3, 4 и 5, 6, 7, 8.Случай I: первое взвешивание показало равенство Если весы покажут равенство, то фальшивая монета находится среди оставшихся четырёх монет. Тогда вторым взвешиванием мы сравним три монеты 9, 10, 11 с заведомо настоящими 1, 2, 3. Если и в этот раз весы покажут равенство, то фальшивка — монета номер 12, и третьим взвешиванием мы сравним её с настоящей и узнаем, легче она или тяжелее. Если же три монеты 9, 10, 11 оказались легче (тяжелее), то третьим взвешиванием сравним друг с другом монеты 9 и 10. Если они равны, то монета 11 — фальшивая, и она легче (тяжелее) настоящей. Иначе заключаем, что из монет 9 и 10 фальшивая та, которая легче (тяжелее) другой.Случай II: первое взвешивание показало неравенство Теперь предположим, что первое взвешивание показало, что монеты 1, 2, 3, 4 тяжелее, чем 5, 6, 7, 8. Случай, когда первые монеты оказались легче, симметричен. Во втором взвешивании на одну чашу поместим монеты 1, 2, 5, а на другую — монеты 3, 4, 9 (монета 9 — заведомо настоящая). Если второе взвешивание показало равенство, то у нас остаются три монеты 6, 7, 8, одна и которых легче остальных. Третьим взвешиванием сравниваем монеты 6 и 7. Если они равны, то монета 8 легче остальных. Иначе фальшивой является та, которая легче другой. Теперь предположим, что во втором взвешивании монеты 1, 2, 5 оказались тяжелее, чем 3, 4, 9. Это означает, что фальшивка находится среди монет 1 и 2, причём она тяжелее остальных. Сравнив в третьем взвешивании эти две монеты друг с другом, мы определим фальшивую. Предположим, что во втором взвешивании монеты 1, 2, 5 оказались легче, чем 3, 4, 9. Это означает, что либо монета 5 легче остальных, либо одна из монет 3 и 4 тяжелее остальных. Третьим взвешиванием мы сравним друг с другом монеты 3 и 4 и найдём ответ.Дано: 12 монет, одна из них фальшивая, отличается только весом. Неизвестно легче или тяжелее. Даны рычажные весы, которые показывают, что груз с одной из сторон тяжелее. За 3 взвешивания необходимо найти фальшивую монетку. Из опыта советую не спешить, решать письменно. Головоломка «12 монет, 3 взвешивания» несколько раз возникала в моей жизни. Первый раз ее задал мне мой товарищ-олимпиадник, решил я ее после олимпиады и пришлось пару часиков поломать голову. И через несколько лет она далось мне не сразу. Если желаете решить самим — делайте на листочке. Ниже будет разбор и этапы решения. Этапы проведут по универсальной методике решения задач, которая применима как к программированию, так и к жизни. Благодаря подходу решение головоломки станет простым. Предлагаю вам, прежде чем читать предложить решение. У вас есть ответ? Проверенный? Если бы это было программного обеспечения вопросы были бы следующие: «Вы запрограммировали, протестировали алгоритм? Рассмотрели тестовые случаи и проверили их?». Как показывает опыт, чтобы решить требуется нарисовать дерево решений и проверить все 12 случаев.ea6b20h3z2v8we64yxscyvzfls4.png1. ПодсказкиВ процессе решения поможет: 1) Понижение энтропии (меры неопределенности) и ответы на вопросы:

  • Что узнали на предыдущем шаге?
  • Что снижает неопределённость?
  • Какой информацией располагаем?
  • Что еще нужно узнать?

Вопросы подходят для любой задачи, проектов. Ответы на них помогают в снижении рисков срыва сроков, перерасхода бюджета и получения нагоняя от начальства. 2) Декомпозиция. Подход от простого к сложному. Если подготовить решение простейших случаев, затем использовать их для решения задачи (алгоритм разделяй и властвуй) то, будет проще, чем представлять всю ситуацию в голове.Алгоритмы «разделяй и властвуй» разбивают задачу на две или более подзадачи того же типа, но меньшего размера до элементарных задач и объединяют их решения для получения ответа к исходной задаче. Составьте вопросы для декомпозиции. Какие бы вы предложили?2. ДекомпозицияКакие вопросы вы сформулировали для декомпозиции? Есть совпадения? 1) Какая ситуация самая элементарная? Что можем сделать за одно взвешивание? За одно взвешивание можем определить, какая монета тяжелее, равен ли вес монет. 2) Если у нас 2 монеты, и, известно, фальшивая тяжелее или легче. Как за одно взвешивание определить фальшивую? Необходимо взвесить монеты, и в зависимости от стрелки весов определить фальшивую. 3) Если у нас 2 монеты, и, не известно, фальшивая тяжелее или легче, как за одно взвешивание определить фальшивую? Взвесив одну из 2-х представленных монет с третьей монетой, про которую известно, что она подлинная. 4) Если у нас 3 монеты, и, известно, фальшивая тяжелее или легче. Как за одно взвешивание определить фальшивую? Необходимо сравнить любые две из этих монет, если они равны, фальшивой является третья монета. 5) Если у нас 3 монеты, и, неизвестно, фальшивая тяжелее или легче. Можно ли определить фальшивую за одно взвешивание? К сожалению, нет. 6) Если у нас 4 монеты, и, неизвестно фальшивая тяжелее или легче, можно определить фальшивую за одно взвешивание? К сожалению, нет. 7) Если у нас 4 монеты, и, неизвестно, фальшивая тяжелее или легче, за сколько взвешиваний можно определить фальшивую? За два взвешивания. Далее из элементарных случаев соберем ситуации из 8, 9, 10, 11 и 12 монет. Как вы видите решение? Ниже полное решение.3. РешениеПервый шаг: разделим монеты на 3 группы по 4: 1 2 3 4, 5 6 7 8, 9 10 11 12. Сравним первые две группы. Возможны три варианта:

  1. первая группа тяжелее;
  2. вторая группа тяжелее;
  3. равны.

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. Определиться, что дано?
  2. На какие элементарные случаизадачи можно разложить?
  3. Что неизвестно для решения задачи? Какие эксперименты нужно провести, чтобы снизить энтропию?
  4. Выполнить.
  5. Задача решена? Нет? Вернуться к шагу 1.

Успешных решений.Как не берегутся, а растрясутся.Ответ(Деньги) Это — средство обращения, Это — средство накопления. Средство стоимости также, Также средство платежа. Штучка невеличка, А всякому нужна.Ответ(деньги) Для всех мы в обилии рождаемся на свет. У одних нас много, а у других нас нет.Ответ(деньги) В кошелек мы их кладем, С ними в магазин идем. За них взамен хоть что бери, Кроме чести и любви. ВОтвет(деньги) Я кладу их не в платок, Я кладу их в кошелек. Без рук, без ног Всё делают в срок Был ведь момент — нет ни гроша. Вдруг он появится — жизнь хороша! Кто меня сделал — не сказывает, Кто меня не знает — принимает, А кто знает — на двор не пускает.Ответ(фальшивая деньга) Маленька, Кругленька, Из кармана в карман скачет, Весь мир обскачет, Ни с чему сама не годна, А всем нужна.Ответ(монета) У каждой из них достоинство есть, И по нему воздают каждой честь — По щепотке одной, другой же — по пуду. Но сравнивать их я, конечно, не буду: Без маленькой самой не будет большой. И вам приходилось встречаться с такой.Ответ(деньги) Дядя Коля — нумизмат. Значит, каждый экспонат, Я скажу вам по секрету, Называется … Кругло, Мало, Всякому мило.Ответ(монета) Мала, кругла, покатна, Как убежит, не догонишь.Ответ(монета)В кошелек мы их кладем, С ними в магазин идем.Ответ(деньги)Здесь деньги принимают И чек нам отбивают.Ответ(касса)Если хочешь в зоопарке Посмотреть зверюшек массу. Для начала за билетом Отправляйся, друг мой, в…Ответ(кассу) Чтобы купить в магазине Игрушечную автотрассу, Нужно сначала деньги Отдать продавцу на…Ответ(кассу)Она рубль бережёт.Ответ(копейка)Если хочешь в магазине, Ты купить, к примеру, сок. Отправляясь за покупкой, Возьми с деньгами…Ответ(кошелек)Обычно из кожи Шьют этот предмет. То есть в нем монеты, То их уже нет.Ответ(кошелек)В этой сумочке живет Звонкая монета. Как для денег домик звать? Жду от вас ответа!Ответ(кошелек)Чтоб в магазине расплатиться смог, Возьми с собой с деньгами…Ответ(кошелек) Маленька, Кругленька, Из кармана в карман скачет, Весь мир обскачет, Ни с чему сама не годна, А всем нужна.Ответ(монета) Книга — раздвига, Два листа, а середка пуста.Ответ(бумажник)Маленькая, кругленькая Из кармана в карман скачет.Ответ(монета)Мала, кругла, покатна, как убежит, не догонишь.Ответ(монета)Как не берегутся, а растрясутся.Ответ(деньги)Штучка невеличка, а всякому нужна.Ответ(деньги)Для всех мы в обилии рождаемся на свет. У одних нас много, а у других нас нет.Ответ(деньги)Маленько, кругленько из тюрьмы в тюрьму скачет, весь мир обскачет, ни к чему сама не годна, а всем нужна.Ответ(монета)На что поп покупает шляпу с широкими полями?Ответ(на деньги)Без ног ходятОтвет(деньги)Кругло, мало, всякому мило.Ответ(монета)Молотком побьют и нам дают.Ответ(деньги)Что горит без пламени? Круглый, малый, всякому милыйОтвет(золотой)Тоненька, беленька, маленька, кругленька, всему свету миленька.Ответ(серебряная монета)Одно брюхо, четыре уха.Ответ(кошелек)Используемые источники:

  • http://allriddles.ru/ru/riddles/weighing/p1/5/
  • http://master-flomaster.blogspot.com/2011/11/12-3.html
  • https://habr.com/ru/post/447354/
  • https://kykyryzo.ru/загадки-про-деньги-34-штук/

Оцените статью
Рейтинг автора
5
Материал подготовил
Илья Коршунов
Наш эксперт
Написано статей
134
Добавить комментарий