На столе 12 монет одна из которых фальшивая
Есть 12 монет, среди них одна поддельная. Помогите математику обнаружить её всего за три взвешивания.
За критику налоговой системы император заточил в темницу величайшего математика страны. Но однажды пленнику представился шанс вновь обрести свободу. Один из 12 наместников императора уплатил налог фальшивой монетой, которая уже попала в казну. Император пообещал освободить математика, если тот сумеет найти подделку.
Перед пленником поставили стол, на котором были чашечные весы, карандаш и 12 одинаковых на вид монет. А потом сказали, что фальшивка отличается от остальных денег по весу в большую или меньшую сторону. Взвесить монеты разрешили лишь трижды. Как математику вычислить подделку?
У математика всего три попытки, поэтому взвешивать каждую монету по отдельности нельзя. Нужно разделить их на кучки и класть на весы по несколько штук за раз, постепенно подбираясь к фальшивой.
Допустим, математик решил разделить 12 монет на три кучки по четыре монеты в каждой. Потом он положил на каждую чашу весов по четыре монеты. Такое взвешивание может дать два результата. Рассмотрим каждый из них.
1. Вес двух кучек с монетами оказался одинаковым. Следовательно, все деньги в них настоящие, а подделка лежит где‑то среди четырёх невзвешенных монет.
Чтобы отслеживать результат, математик помечает ноликом все подлинники. Потом берёт три из них и сравнивает с тремя невзвешенными монетами. Если их вес равен, то оставшаяся (четвёртая) невзвешенная монета фальшивая. Если вес отличается, то математик ставит на трёх непомеченных монетах плюс, если они тяжелее тех, что с ноликами, или минус, если они легче.
Потом он берёт две монеты, помеченные плюсом или минусом, и сравнивает их вес. Если он одинаковый, то оставшийся экземпляр — подделка. Если нет, математик смотрит на знаки: среди монет с плюсом фальшивой будет та, что тяжелее, среди монет с минусом — та, что легче.
2. Вес двух кучек с монетами оказался неодинаковым.
В этом случае математику нужно действовать так: пометить деньги в тяжёлой кучке плюсом, в лёгкой — минусом, в невзвешенной — ноликом, так как известно, что фальшивый экземпляр был на весах.
Теперь нужно перегруппировать монеты, чтобы уложиться в два оставшихся взвешивания. Один из способов — взять вместо трёх монет с плюсом три монеты с минусом, а на их место положить три штуки с ноликом.
Кадр: TED‑Ed/YouTube
Далее следует три возможных варианта. Если та чаша весов, которая была тяжелее, всё ещё перевешивает, значит, либо старая монета со знаком плюс на ней тяжелее остальных, либо оставшаяся на другой чаше весов монета со знаком минус — легче. Математику нужно выбрать любую из них и сравнить с обычным образцом, чтобы найти фальшивку.
Если же та чаша весов, которая была тяжелее, стала легче, значит, одна из трёх перемещённых математиком монет со знаком минус и есть самая лёгкая. Теперь ему нужно сравнить на весах две из них. При равенстве результатов третья монета будет поддельной. При неравенстве — фальшивая та, что легче.
Если после замены чаши уравновесились, одна из трёх снятых с весов монет со знаком плюс тяжелее остальных. Математику нужно сравнить две из них. При их равенстве третья — поддельная. При неравенстве ненастоящая та, что тяжелее.
Император одобрительно кивает, выслушивая рассуждения математика, а нечестный наместник отправляется в темницу.
"Бородатая" задачка, которая до сих пор ставит многих в тупик. 12 монет и 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 и она легче.
Всё. Как вам задачка? Как видите, рассмотрены все случаи и трех взвешиваний достаточно даже для того, чтобы определить не только фальшивку, но и её относительный вес.
Нерешаемая задача про 12 монет или я решила её правильно?
После публикации с головоломкой наш читатель задал нам встречную задачку. Решаем её в картинках.
А так как в следующем комментарии Руслан сказал, что в интернете верного решения нет, то пришлось решать её.
Нерешаемая задача
Имеется 12 монет. 11 одного веса. А одна - фальшивка, весит либо больше, либо меньше. Нужно узнать какая, если монеты можно сравнивать только друг с другом на чашечных рычажных весах. Всего разрешено только три взвешивания.
Давайте попробуем представить решение схематично.
Вот наши 12 монет.
Шаг 1
Делим все монеты на 3 кучки
ВАРИАНТ 1
Взвешивание 1
Взвешиваем любые две кучки.
Допустим, мы взяли для взвешивания кучку 1 и кучку 2 .
Если весы будут уравновешены, то фальшивая монета останется в третьей кучке.
Среди монет 1,2,3,4,5,6,7,8 фальшивых нет.
Взвешивание 2
На одну чашу весов кладем три монеты из 1,2,3,4,5,6,7,8 и три монеты из кучки 3.
Пусть это будут монеты
ПЕРВЫЙ возможный вариант ВТОРОГО взвешивания
Так после второго взвешивания можно найти фальшивую монету. В нашем случае фальшивая монета — №12.
Теперь можем применить третье взвешивание, чтобы узнать легче или тяжелее фальшивая монета, сравнив на весах её с настоящей.
ВТОРОЙ возможный вариант ВТОРОГО взвешивания
После этого взвешивания мы узнаем, тяжелее или легче фальшивая монета.
Мы видим, что три монеты 9, 10, 11 оказались легче или тяжелее. Значит, среди них находится фальшивая монета.
Для дальнейшего расчета примем один вариант — фальшивая монета ТЯЖЕЛЕЕ . Если выбрать вариант «легче», то дальнейшее решение будет идентичным.
ТРЕТЬЕ взвешивание для второго варианта
Сравним вес монет №9 и № 10
Если монета под №10 тяжелее, то она и есть фальшивая.
Если же весы с монетами № 9 и № 10 будут уравновешены, то фальшивая — это монета № 11
ВАРИАНТ 2
Взвешивание 1
Допустим, что взвешивание монет
мы видим неравенство (любое из вариантов на картинке)
Но пока мы не знаем, тяжелее или легче фальшивая монета.
Взвешивание 2 (случай первый)
Допустим весы установились так, как показано на рисунке справа . То есть монеты 1, 2, 3, 4 — ТЯЖЕЛЕЕ
Займемся чашей весов с монетами 1, 2, 3, 4 и добавим к ним еще две.
Кладем на весы так:
Если весы уравновешены, то среди монет 6, 7, и 8 есть одна фальшивая и она ЛЕГЧЕ.
Взвешивание 3
Сравниваем монеты 6, 7, 8.
Первое возможное сравнение
Если весы уравновешены, то фальшивая монета № 8. И она легче
Хотя в этом случае нам не важно легче или тяжелее фальшивая монета.
Но ответ получен, так как о «тяжелее/легче» нас не спрашивают.
Весы ведь могут установиться по-другому.
Второе возможное сравнение
Если весы установились так?
Тогда нам станет ясно, что раз монета №6 оказалась легче, то она и есть фальшивая.
Взвешивание 2 (случай второй)
А если картина будет такая
Но весы не уравновесились.
Вывод : монеты 1, 2, 5 оказались тяжелее, чем 3, 4, 9. Это означает, что фальшивая монета находится среди монет 1 и 2, причём, она тяжелее остальных.
Взвешивание 3
Сравниваем монеты №1 и №2
Какая будет тяжелее, та и фальшивая.
Взвешивание 2 (случай третий)
Если во втором взвешивании окажется , что монеты 1, 2, 5 окажутся легче, чем 3, 4, 9, это будет означать один из вариантов:
- Монета № 5 легче остальных
- Одна из монет №3 или №4 тяжелее остальных
Взвешивание 3 (случай третий)
Сравниваем вес монет №3 и №4.
Ответ: Какая монета тяжелее, та и фальшивая.
Декомпозиция и понижение энтропии для программиста на примере головоломки «12 монет, 3 взвешивания найти фальшивую»
Дано: 12 монет, одна из них фальшивая, отличается только весом. Неизвестно легче или тяжелее. Даны рычажные весы, которые показывают, что груз с одной из сторон тяжелее. За 3 взвешивания необходимо найти фальшивую монетку.
Из опыта советую не спешить, решать письменно. Головоломка «12 монет, 3 взвешивания» несколько раз возникала в моей жизни. Первый раз ее задал мне мой товарищ-олимпиадник, решил я ее после олимпиады и пришлось пару часиков поломать голову. И через несколько лет она далось мне не сразу. Если желаете решить самим — делайте на листочке.
Ниже будет разбор и этапы решения. Этапы проведут по универсальной методике решения задач, которая применима как к программированию, так и к жизни. Благодаря подходу решение головоломки станет простым.
Предлагаю вам, прежде чем читать предложить решение. У вас есть ответ? Проверенный?
Если бы это было программного обеспечения вопросы были бы следующие: «Вы запрограммировали, протестировали алгоритм? Рассмотрели тестовые случаи и проверили их?».
Как показывает опыт, чтобы решить требуется нарисовать дерево решений и проверить все 12 случаев.
В процессе решения поможет:
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) Рассмотрим второй случай. Если первая группа тяжелее второй, то присваиваем первой группе знак «>», второй группе знак «
Делим монеты на группы 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-я является фальшивой.
Общая диаграмма «Дерева решений» представлена ниже.
При поступлении задачи на доработку или отладку хорошо применить рассмотренный выше подход:
Дюжина логических задач с собеседований
Не знаю, как у вас, но у меня любимая часть интервью — логические задачи.
Довелось пройти немало собеседований на вакансию разработчика, поэтому набралась небольшая коллекция.
Спешу поделиться с вами!
Некоторые задачи проще и широкоизвестные, другие заставляют хорошенько задуматься.
Ответы пока что публиковать не буду, надеюсь, вы сами сможете всё решить.
Предлагаю размять свой мозг.
1) Человек построил дом, все стены которого смотрят на юг. К нему в дом забрался медведь. Какого цвета медведь?
2) На столе 12 монет, одна из которых фальшивая. Она отличается от остальных лишь по массе. За какое минимальное число взвешиваний на чашечных весах можно обнаружить фальшивую монету?
3) В первой изолированной комнате — три лампочки, во второй — три переключателя от каждой из них. Разрешается произвольно дёргать переключатели, но перейти из второй комнаты в первую можно лишь один раз. Как узнать, от какой лампочки каждый переключатель, если до потолка можно достать рукой?
4) Даны две веревки и спички. Каждая из верёвок сгорает за 1 час, но горят они неравномерно, поэтому нельзя точно узнать, какая часть веревки за какое время сгорит. Как отмерить при помощи этих веревок интервал в 45 минут?
5) В офис привезли три автомата с напитками. Первый выдаёт чай, второй кофе, а третий случайным образом чай или кофе. Стакан любого напитка стоит одну монету. На каждом автомате есть наклейка с названием продукта, который он выдаёт. Так получилось, что на заводе перепутали местами наклейки и на каждом автомате оказалась неправильная. Сколько нужно потратить монет, чтобы выяснить, где какой автомат?
6) Есть два абонента A и B, почтальон C и открытый сейф с двумя замками. У каждого абонента есть ключ от одного из замков. Если передавать ключ через почтальона, то он может сделать дубликат. Как передать письмо от одного абонента к другому через почтальона, чтобы тот не смог его прочитать? Как изменится алгоритм, если в сейфе сделать небольшое отверстие для вложения письма?
7) Путник находится в лесу в какой-то случайной точке. Известно, что площадь леса равна S, а форма может быть совершенно произвольная, однако в лесу нет полян. По какой траектории нужно двигаться путнику, чтобы гарантировано выйти из леса затратив минимальный по длине маршрут?
8) Путешественник прошёл один километр на юг, затем один километр на запад, а после один километр на север и вернулся в исходную точку. Сколько существует таких мест на земле? Подсказка: больше одного…
9) Есть огромный файл в несколько гигабайт, в котором записаны целые числа. Нужно записать в другой файл все эти числа в отсортированном порядке. Как это эффективно сделать?
10) Есть огромный файл в несколько гигабайт, в котором записаны целые числа. Известно, что каждое число встречается два раза, но есть единственное число, которое встречается один раз. Предложите эффективный алгоритм для поиска этого числа. Как изменится алгоритм, если каждое число будет встречаться в файле чётное число раз, а единственное из них нечётное число раз?
11) Есть огромный файл, в котором записаны все целые числа из диапазона от 1 до 10^9 в произвольном порядке. То есть в файле есть абсолютно все числа из этого диапазона, и встречаются они лишь по одному разу. Однако одно число встречается два раза. Как найти это число эффективным образом?
Читайте также: