Меню

Из трех монет одна фальшивая она легче остальных за сколько взвешиваний



Универсальная методика к решению задач на примере головоломки «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. первая группа тяжелее;
  2. вторая группа тяжелее;
  3. равны.

1) Если группы равны, то фальшивая монета находится в третьей группе. Необходимо найти фальшивую монету из 4 монет за два взвешивания.

Делим третью группу на две: 9 10 11 12

Сравниваем 9 и 10:

  • если они равны, то фальшивая монета во второй группе – сравниваем 9 и 11. Если 9 и 11 равны — то фальшивая – 12, если нет -11
  • если они не равны, то фальшивая в первой группе – сравниваем 10 и 12. Если 10 и 12 равны – фальшивая – 9, если нет – 10.
Читайте также:  Монета 20 senti 1935

Таким образом мы нашли фальшивую монету.

2) Рассмотрим второй случай. Если первая группа тяжелее второй, то присваиваем первой группе знак «>», второй группе знак « Заключение

При поступлении задачи на доработку или отладку хорошо применить рассмотренный выше подход:

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

Успешных решений.

Источник

Простая задача о взвешивании монет

Задача

Хорошо известна задача о взвешивании монет на простых рычажных весах, с целью найти одну фальшивую монету за минимальное число взвешиваний.

Например, у Вас имеется 100 одинаковых по виду монет. Все они одинакового веса, кроме одной фальшивой монеты, которая легче остальных монет. Спрашивается, за какое минимальное число взвешиваний на рычажных весах можно найти фальшивую монету.

Алгоритм

Алгоритм решения этой задачи довольно простой. Берем ближайшее большее число к 100, которое делится на 3. Это число 102. Делим 102 на 3, получаем 34. На обе чаши весов кладем по 34 монеты, а 32 монеты оставляем лежать на столе.

Если чаши весов уравновешены, значит, на нах находятся только настоящие монеты, а фальшивая монета среди 32 монеты, которые остались на столе. В этом случае работаем только с этими 32 монетами. А если какая-то из чаш весов с 34 монетами оказалась легче другой чаши, то работаем далее с теми 34 монетами, где находится более легкая монета.

И далее повторяем весь алгоритм заново. То есть, если число монет не делится на 3, то находим ближайшее целое число, которое превышает число монет и которое делится без остатка на три. Делим это число на 3, чтобы получить, сколько монет нужно положить на обе чаши весов. А оставшиеся монеты оставляем лежать на столе. Это число монет всегда меньше или равно числу монет на одной из чаш весов. Проводим взвешивание, чтобы определить, с какой из этих трех групп монет работать дальше.

Допустим, у нас обе чаши весов с 34 монетами уравновешены. Значит, работаем с оставшимися на столе 32 монетами. Ближайшее большее число, которое делится на 3, будет 33. Делим 33 на 3 и получаем, что на обе чаши весов надо положить по 11 монет, а 10 монет оставить на столе.

А если легче оказалась чаша весов с 34 монетами, то ближайшее большее целое, которое делится на 3, будет 36. Поэтому берем из этой легкой кучи из 34 монет по 12 монет на каждую чашу весов, а 10 монет оставляем лежать на столе.

Разное число минимальных взвешиваний

Перебирая таким алгоритмом все возможные варианты, мы получаем, что надо сделать или 4 или 5 взвешиваний. Какое именно число взвешиваний надо будет сделать, 4 или 5, это уж как повезет.

Например, как получается 4 взвешивания. Если после второго взвешивания нам придется работать с 10 монетами, которые при втором взвешивании оставались на столе, то в третьем взвешивании кладем на обе чаши весов по 4 монеты. Две монеты оставляем на столе. Если в третьем взвешивании чаши весов уравновешены, то остается сделать только одно четвертое взвешивание, поместив на каждую чашу весов по одной монете из двух оставшихся на столе монет.

А если на третьем взвешивании нам не повезет, и, допустим, дальше надо будет работать не с 2 монетами, а с 4 монетами, то 4 взвешиваний уже не хватит. На 4-м взвешивании мы кладем на обе чаши весов по 2 монеты, а на столе ничего не остается. И затем делаем 5-е взвешивание с чашами весов по одной монете.

Можете сами проверить другие разветвления после второго взвешивания, когда придется работать не с 10 монетами, а с 11 или с 12 монетами, что данный алгоритм дает максимум 5 взвешиваний, но если повезёт, то и 4 взвешивания.

Одно число минимальных взвешиваний

А бывает ли так, чтобы число взвешиваний по данному алгоритму было бы строго определенным числом и не зависело бы от везения?

Читайте также:  Сколько стоят монеты 10 рублей желтые

Да, такое бывает, когда каждый раз на столе остается столько же монет, сколько и на каждой чаши весов. Это бывает тогда, когда на каждом взвешивании число монет всё время делится на 3 без остатка. То есть, начальное число монет должно быть равным степени числа 3. Это числа

Степень тройки показывает, сколько взвешиваний нужно сделать.

Например, число 27, это 3 в 3-й степени (3 3 =27). Значит, найти фальшивую монету среди 27 монет можно за 3 взвешивания. На первом взвешивании кладем на обе чаши весов по 9 монет и еще 9 монет оставляем на столе. На втором взвешивании 9 монет делим на три кучки по 3 монеты, и кладем на обе чаши весов по 3 монеты и еще 3 монеты оставляем на столе. И, наконец, на последнем третьем взвешивании по одной монете кладем на обе чаши весов и одну монету оставляем на столе.

Нетрудно проверить, что для 27 монет взвешиваний всегда будет 3, где бы случайно не оказалась фальшивая монета на каждом взвешивании, на одной из чаш весов или на столе.

Общее правило

Общее правило определения числа минимальных взвешиваний следующее. Если дано N монет, среди которых одна монета отличается по весу, и это число N не является степенью числа 3, то надо найти ближайшие к N два числа, которые являются степенями числа 3. Показатели степеней числа 3 для этих двух чисел и будут равны числу минимальных взвешиваний. Если N точно является степенью числа 3, то показатель степени числа 3, будет одним минимальным числом взвешиваний.

В нашем примере N=100. Данное число не является степенью числа 3. Значит, ищем ближайшие к 100 степени числа 3. Это числа 81 и 243. При этом 3 4 =81 и 3 5 =243. Значит, числа 4 и 5 являются минимальным числом взвешиваний для поиска фальшивой монеты среди 100 монет.

Если число монет 59’049, то это число является точной степенью числа 3, а именно: 3 10 =59049. Значит, для поиска фальшивой монеты среди 59’049 монет нужно будет сделать точно 10 взвешиваний.

Понятно, что это правило и этот же алгоритм будут работать, если фальшивая монета не легче настоящей, а тяжелее её. Но в общем случае нужно обязательно заранее знать, какая из монет тяжелее, настоящая или фальшивая, чтобы правильно определять, с какой группой монет работать на следующем взвешивании.

Сложная задача о взвешивании монет

Это была очень простая задача о взвешивании монет. А как Вам теперь такая задача.

Имеется N мешков с монетами. Все монеты на вид не отличаются друг от друга. В каждом мешке находятся монеты только одного какого-нибудь вида, или настоящие монеты или какой-нибудь один сорт фальшивых монет. Известно, сколько весит каждый сорт монет, то есть известен вес настоящей монеты и веса всех сортов фальшивых монет. Неизвестно в каких именно мешках находятся настоящие монеты, а в каких мешках находятся фальшивые монеты.

Вопрос: Как ОДНИМ взвешиванием определить, в каких мешках находятся настоящие монеты, а в каких мешках находятся какие сорта фальшивых монет? Весы обычные, которые показывают вес, например, в граммах.

Считается, что в мешках достаточное количество монет, чтобы брать оттуда любое количество монет.

Обратите внимание, что фальшивые монеты не обязательно должны быть легче, чем настоящие. Например, может быть, что всего 7 сортов монет со следующими весами в граммах: 4, 5, 8, 9, 10, 13 и 16. Настоящая монета имеет вес 10 грамм, а все остальные фальшивые. Кроме того, у нас не обязаны все 7 сортов этих монет присутствовать. Может быть такая ситуация, что во всех N мешках находятся только одни настоящие монеты, или во всех N мешках находятся только фальшивые монеты с весом 9 грамм. Или могут быть любые более сложные ситуации, когда часть мешков занята одним сортом монет, часть мешков другим сортом монет и т.д. И нам неизвестно в каком порядке чередуются в этих мешках эти монеты.

Читайте также:  Сколько стоят золотые монеты в сбере

На первый взгляд, эта задача кажется не имеющая решения. И, тем не менее, за одно взвешивание можно определить всё распределение всех сортов монет по всем мешкам.

Решение этой красивой задачи смотрите здесь.

Источник

«Бородатая» задачка, которая до сих пор ставит многих в тупик. 12 монет и 3 взвешивания

Задача абсолютно стандартная. Разобрана в миллиарде книг. Мне кажется, даже каждый школьный учитель её рассказывает в какой-то момент своим ученикам. Тем не менее задача встречается на олимпиадах в разных классах едва ли не чаще остальных. И все равно находятся люди, которые не понимают что к чему. Даже среди взрослых.

Давайте разберем одну из таких задач. Имеется 12 монет. Одна из которых фальшивая. Она отличается от подлинных только по весу (но заранее не известно в меньшую или в большую сторону). Как на чашечных весах определить фальшивку за 3 взвешивания и понять легче она или тяжелее, чем остальные? Как вы понимаете количество монет и взвешиваний может быть разным. От этого суть не изменится.

В любом случае нам надо будет разбить монеты на кучки, чтобы взвешивать их группами. В данной задаче удобно разбить монеты на 3 кучки по 4 монеты в каждой.

В какой-то момент в одном из случаев вам может показаться, что для некоторых случаев трех взвешиваний мало и надо бы четвертое. Ну или не получится определить легче или тяжелее фальшивка. Если так, то вы ошибаетесь, надо думать снова. Трех взвешиваний достаточно в любом случае. И в любом случае получится узнать легче фальшивка или тяжелее.

Для наглядности пронумеруем монеты: <1,2, 3, 4>; <5, 6,7, 8>; <9,10, 11, 12>и приступим к решению.

Первое взвешивание

Сравниваем первые две кучки монет <1,2, 3, 4>и <5, 6,7, 8>. Если весы находятся в равновесии, значит фальшивка в третьей кучке. Переходим к пункту а) во втором взвешивании.

Если весы не в равновесии, то фальшивка в одной из этих двух кучек, а в третьей все монеты настоящие. Запоминаем, какая кучка перевесила [я для примера буду считать, что перевесила кучка <1,2,3,4>, но если нет, то решение будет симметричным] и переходим к пункту б) во втором взвешивании.

Второе и третье взвешивания

а) Фальшивка среди монет <9,10, 11, 12>. Взвешиваем <1, 2, 3>и <9,10, 11>. Если весы в равновесии, значит фальшивая монета под номером 12. третьим взвешиванием узнаем, легче она или тяжелее.

Если не равны, значит, фальшивка среди монет 9, 10, 11. При этом уже после второго взвешивания мы будем точно знать легче фальшивка или тяжелее. Третьим взвешиванием однозначно находим фальшивку: взвешиваем монеты 9 и 10. Если они равны, то фальшивка — 11. Если не равны, то фальшивка либо 9, либо 10 в зависимости от того, какая монета легче (оригинал или фальшивка), ведь эту информацию мы узнали после второго взвешивания.

б) Фальшивка в одной из первых двух кучек. Для того, чтобы понять в какой, взвесим <1, 2, 5>и <3, 4, 9>[опечатки нет, монета 9 заведомо настоящая]. Если весы в равновесии, значит, фальшивка среди 6, 7, 8, причем одна из них легче остальных [это потому что мы для ясности рассматриваем случай, когда первое взвешивание показало, что первая кучка тяжелее]. Третьим взвешиванием сравниваем монеты 6 и 7. Если они равны, то фальшивка — 8. Если нет, то фальшивка та, которая весит меньше.

Если весы после второго взвешивания оказались не в равновесии, возникает два случая

б.1) Если перевесила кучка <1, 2, 5>, то фальшивка среди монет 1 и 2. Третьим взвешиванием мы узнаем, какая из них тяжелее и это и есть фальшивка.

б.2) Если перевесила кучка <3, 4, 9>, то фальшивка среди монет 3, 4 и 5. Если фальшивка — 5, то она будет легче других. А если 3 или 4, то фальшивка тяжелее настоящих. Третьим взвешиванием сравниваем монеты 3 и 4. Если одна из них тяжелее, то это фальшивка. Если они равны, то фальшивка — 5 и она легче.

Всё. Как вам задачка? Как видите, рассмотрены все случаи и трех взвешиваний достаточно даже для того, чтобы определить не только фальшивку, но и её относительный вес.

Источник