Загадка про 12 монет и 3 взвешивания
Обновлено: 22.11.2024
Дано: 12 монет, одна из них фальшивая, отличается только весом. Неизвестно легче или тяжелее. Даны рычажные весы, которые показывают, что груз с одной из сторон тяжелее. За 3 взвешивания необходимо найти фальшивую монетку.
Из опыта советую не спешить, решать письменно. Головоломка «12 монет, 3 взвешивания» несколько раз возникала в моей жизни. Первый раз ее задал мне мой товарищ-олимпиадник, решил я ее после олимпиады и пришлось пару часиков поломать голову. И через несколько лет она далось мне не сразу. Если желаете решить самим — делайте на листочке.
Ниже будет разбор и этапы решения. Этапы проведут по универсальной методике решения задач, которая применима как к программированию, так и к жизни. Благодаря подходу решение головоломки станет простым.
Предлагаю вам, прежде чем читать предложить решение. У вас есть ответ? Проверенный?
Если бы это было программного обеспечения вопросы были бы следующие: «Вы запрограммировали, протестировали алгоритм? Рассмотрели тестовые случаи и проверили их?».
Как показывает опыт, чтобы решить требуется нарисовать дерево решений и проверить все 12 случаев.
1. Подсказки
В процессе решения поможет:
1) Понижение энтропии (меры неопределенности) и ответы на вопросы:
- Что узнали на предыдущем шаге?
- Что снижает неопределённость?
- Какой информацией располагаем?
- Что еще нужно узнать?
2) Декомпозиция. Подход от простого к сложному. Если подготовить решение простейших случаев, затем использовать их для решения задачи (алгоритм разделяй и властвуй) то, будет проще, чем представлять всю ситуацию в голове.
Алгоритмы «разделяй и властвуй» разбивают задачу на две или более подзадачи того же типа, но меньшего размера до элементарных задач и объединяют их решения для получения ответа к исходной задаче.
Составьте вопросы для декомпозиции. Какие бы вы предложили?
Какие вопросы вы сформулировали для декомпозиции? Есть совпадения?
1) Какая ситуация самая элементарная? Что можем сделать за одно взвешивание?
За одно взвешивание можем определить, какая монета тяжелее, равен ли вес монет.
2) Если у нас 2 монеты, и, известно, фальшивая тяжелее или легче. Как за одно взвешивание определить фальшивую?
Необходимо взвесить монеты, и в зависимости от стрелки весов определить фальшивую.
3) Если у нас 2 монеты, и, не известно, фальшивая тяжелее или легче, как за одно взвешивание определить фальшивую?
Взвесив одну из 2-х представленных монет с третьей монетой, про которую известно, что она подлинная.
4) Если у нас 3 монеты, и, известно, фальшивая тяжелее или легче. Как за одно взвешивание определить фальшивую?
Необходимо сравнить любые две из этих монет, если они равны, фальшивой является третья монета.
5) Если у нас 3 монеты, и, неизвестно, фальшивая тяжелее или легче. Можно ли определить фальшивую за одно взвешивание?
К сожалению, нет.
6) Если у нас 4 монеты, и, неизвестно фальшивая тяжелее или легче, можно определить фальшивую за одно взвешивание?
К сожалению, нет.
7) Если у нас 4 монеты, и, неизвестно, фальшивая тяжелее или легче, за сколько взвешиваний можно определить фальшивую?
За два взвешивания.
Далее из элементарных случаев соберем ситуации из 8, 9, 10, 11 и 12 монет. Как вы видите решение?
Ниже полное решение.
Первый шаг: разделим монеты на 3 группы по 4: 1 2 3 4, 5 6 7 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-я является фальшивой.
Общая диаграмма «Дерева решений» представлена ниже.
Заключение
При поступлении задачи на доработку или отладку хорошо применить рассмотренный выше подход:
Следующая загадка
Задача абсолютно стандартная. Разобрана в миллиарде книг. Мне кажется, даже каждый школьный учитель её рассказывает в какой-то момент своим ученикам. Тем не менее задача встречается на олимпиадах в разных классах едва ли не чаще остальных. И все равно находятся люди, которые не понимают что к чему. Даже среди взрослых.
Давайте разберем одну из таких задач. Имеется 12 монет. Одна из которых фальшивая. Она отличается от подлинных только по весу (но заранее не известно в меньшую или в большую сторону). Как на чашечных весах определить фальшивку за 3 взвешивания и понять легче она или тяжелее, чем остальные? Как вы понимаете количество монет и взвешиваний может быть разным. От этого суть не изменится.
В любом случае нам надо будет разбить монеты на кучки, чтобы взвешивать их группами. В данной задаче удобно разбить монеты на 3 кучки по 4 монеты в каждой.
В какой-то момент в одном из случаев вам может показаться, что для некоторых случаев трех взвешиваний мало и надо бы четвертое. Ну или не получится определить легче или тяжелее фальшивка. Если так, то вы ошибаетесь, надо думать снова. Трех взвешиваний достаточно в любом случае. И в любом случае получится узнать легче фальшивка или тяжелее.
Для наглядности пронумеруем монеты: ; ; и приступим к решению.
Первое взвешивание
Сравниваем первые две кучки монет и . Если весы находятся в равновесии, значит фальшивка в третьей кучке. Переходим к пункту а) во втором взвешивании.
Если весы не в равновесии, то фальшивка в одной из этих двух кучек, а в третьей все монеты настоящие. Запоминаем, какая кучка перевесила [я для примера буду считать, что перевесила кучка , но если нет, то решение будет симметричным] и переходим к пункту б) во втором взвешивании.
Второе и третье взвешивания
а) Фальшивка среди монет . Взвешиваем и . Если весы в равновесии, значит фальшивая монета под номером 12. третьим взвешиванием узнаем, легче она или тяжелее.
Если не равны, значит, фальшивка среди монет 9, 10, 11. При этом уже после второго взвешивания мы будем точно знать легче фальшивка или тяжелее. Третьим взвешиванием однозначно находим фальшивку: взвешиваем монеты 9 и 10. Если они равны, то фальшивка - 11. Если не равны, то фальшивка либо 9, либо 10 в зависимости от того, какая монета легче (оригинал или фальшивка), ведь эту информацию мы узнали после второго взвешивания.
б) Фальшивка в одной из первых двух кучек. Для того, чтобы понять в какой, взвесим и [опечатки нет, монета 9 заведомо настоящая]. Если весы в равновесии, значит, фальшивка среди 6, 7, 8, причем одна из них легче остальных [это потому что мы для ясности рассматриваем случай, когда первое взвешивание показало, что первая кучка тяжелее]. Третьим взвешиванием сравниваем монеты 6 и 7. Если они равны, то фальшивка - 8. Если нет, то фальшивка та, которая весит меньше.
Если весы после второго взвешивания оказались не в равновесии, возникает два случая
б.1) Если перевесила кучка , то фальшивка среди монет 1 и 2. Третьим взвешиванием мы узнаем, какая из них тяжелее и это и есть фальшивка.
б.2) Если перевесила кучка , то фальшивка среди монет 3, 4 и 5. Если фальшивка - 5, то она будет легче других. А если 3 или 4, то фальшивка тяжелее настоящих. Третьим взвешиванием сравниваем монеты 3 и 4. Если одна из них тяжелее, то это фальшивка. Если они равны, то фальшивка - 5 и она легче.
Всё. Как вам задачка? Как видите, рассмотрены все случаи и трех взвешиваний достаточно даже для того, чтобы определить не только фальшивку, но и её относительный вес.
Следующая загадка
Задача не нова и хорошо пережевана во многих книгах ещё с советских времен. Кто-то наверняка вспомнит, что решал её ещё в 60-70-ых годах. Но от этого она не становится хуже или проще. Наоборот, раз она так долго рассказывается ученикам учителями, значит, хорошая, заставляет подумать.
Эту задачу любили раньше давать на собеседованиях в МГУ. Когда не было ЕГЭ, были внутренние экзамены, олимпиады, а потом собеседование. Там могли спросить что угодно: просто поболтать, проверить эрудицию в других областях, а не по специальности, спросить про родителей или дать какую-то несложную задачку на логику. Как правило, строго решения никто не требовал, достаточно было сказать идею и все всё и так понимали. Так что не думайте, что это сложная задача.
Имеется 10 мешков с большим количеством монет в каждом. В 9 мешках все монеты настоящие, а в одном — все фальшивые. Настоящая монета весит 10 граммов, а фальшивая — 9 граммов. В вашем распоряжении есть электронные весы с точностью до граммов, но воспользоваться ими можно всего один раз. Как определить мешок с фальшивками?
Как я уже сказал, ничего сложного в задаче нет. Но сначала лирическое отступление.
ЛитРес дарит мне, а я дарю вам промокод YELLOWDZEN. В течение двух дней после активации на весь каталог у вас будет действовать 25% скидка. А вообще промокод работает до 4 марта 2021 года. Пользуйтесь, покупайте в подарок книги на 23 февраля и 8 марта.
Ну а теперь решение. Пронумеруем мешки от одного до 10. Берем из первого мешка одну монету, из второго — две, из третьего — три и так далее. Всего у нас получится 55 монет. Если бы они все были настоящими, они бы весили 550 граммов. Но так как среди них есть фальшивые, общей вес будет меньше. Так вот на сколько граммов будет меньше вес, в том мешке и есть фальшивые монеты.
Обычно на словах "пронумеруем мешки и возьмем из каждого столько монет, какой у него порядковый номер. " абитуриента останавливали, всем становилось понятно, что он понял, как решать. А вы решили? Этим способом или нашли какой-то другой?
Следующая загадка
Дано: 12 монет, одна из них фальшивая, отличается только весом. Неизвестно легче или тяжелее. Даны рычажные весы, которые показывают, что груз с одной из сторон тяжелее. За 3 взвешивания необходимо найти фальшивую монетку.
Из опыта советую не спешить, решать письменно. Головоломка «12 монет, 3 взвешивания» несколько раз возникала в моей жизни. Первый раз ее задал мне мой товарищ-олимпиадник, решил я ее после олимпиады и пришлось пару часиков поломать голову. И через несколько лет она далось мне не сразу. Если желаете решить самим — делайте на листочке.
Ниже будет разбор и этапы решения. Этапы проведут по универсальной методике решения задач, которая применима как к программированию, так и к жизни. Благодаря подходу решение головоломки станет простым.
Предлагаю вам, прежде чем читать предложить решение. У вас есть ответ? Проверенный?
Если бы это было программного обеспечения вопросы были бы следующие: «Вы запрограммировали, протестировали алгоритм? Рассмотрели тестовые случаи и проверили их?».
Как показывает опыт, чтобы решить требуется нарисовать дерево решений и проверить все 12 случаев.
Читайте также: