Среди 12 монет имеется одна фальшивая

Среди 12 монет имеется одна фальшивая

Головоломки и задачи на сообразительность

воскресенье, 6 ноября 2011 г.

12 монет, 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 взвешивания» несколько раз возникала в моей жизни. Первый раз ее задал мне мой товарищ-олимпиадник, решил я ее после олимпиады и пришлось пару часиков поломать голову. И через несколько лет она далось мне не сразу. Если желаете решить самим — делайте на листочке.

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

Предлагаю вам, прежде чем читать предложить решение. У вас есть ответ? Проверенный?

Читайте также:  D sub power saving mode

Если бы это было программного обеспечения вопросы были бы следующие: «Вы запрограммировали, протестировали алгоритм? Рассмотрели тестовые случаи и проверили их?».

Как показывает опыт, чтобы решить требуется нарисовать дерево решений и проверить все 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.
Читайте также:  Как прописать принтер на компьютер windows 10

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

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

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

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

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

Ой, у вас баннер убежал!

Читают сейчас

Похожие публикации

  • 20 сентября 2019 в 15:31

Алгоритмы обнаружения контуров изображения

Гуляем по городу с умом — 2: ходим по городу кругами с помощью генетического алгоритма

Генетические алгоритмы (или Клиент всегда король — и часто дурак)

Заказы

AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Комментарии 46

Хотя я согласен с вашим общим настроем, но отмечу, что конкретно для этой задачки зависли на 2-й стадии (декомпозиции). Пока доказывают что-то для частных случаев, но «глобальной декомпозиции» пока провести не удалось.

P.S. не знаю, что там автор час думал, я в своё время решил минут за 5 — и был одним из последних в нашей группе ребят-олимпиадников, кто это сделал (выше городских не поднимался, да)

Ну, я просто не люблю неоправданно громкие заголовки. «Полезная эвристика» звучало бы гораздо лучше.

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

Мне учительница математики помню рассказывала.
Она подрядилась быть репетитором для старшекласника. Подготовка к поступлению в ВУЗ.
И вот на первом занятии она дает задает ему вопрос:
как можно преобразовать
six^2 x/cos^2 x

На этом месте она поняла, что работы… предстоит много.

a как еще «шесть» сокращать? ) Шучу, видимо опячатка.

Не так много — только объяснить человеку, что такое тригонометрические функции, а сокращать дроби он умеет.)

Блин. Действительно опечатался.
Но к концу сумел исправиться))

Настолько не знать, что такое тригонометрические функции — это надо было постараться.:)

Сокращать дроби тоже не умеет, кстати. «Квадраты» так не сокращают.

За 3 взвешивания необходимо найти фальшивую монетку и определить легче она или тяжелее.

Решение не до конца.

Ну допустим я злоумышленник и подложил «облегчённую» монету №7 где для неё вариант?
И тут вообще только 16 вариантов из 24 (12* L-H) возможных.

Или я что-то упустил?

Решение автора отвечает на вопрос "легче или тяжелее" на втором-третьем взвешивании, в зависимости от результатов взвешивания. Единственное исключение — когда после первого взвешивания, фальшивая монета оказывается в третьей группе, и в последующие 2 взвешивания она не попадает. Тогда да, ее вес неизвестен.

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

Лежит в кармане. Она не фальшивая, в решении не участвует.

Читайте также:  Схема соединения наушников с микрофоном

Посмотрите внимательно 1-ый случай

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

Дано: 12 14 монет, одна из них фальшивая, отличается только весом. Неизвестно легче или тяжелее. Даны рычажные весы, которые показывают, что груз с одной из сторон тяжелее. За 3 взвешивания необходимо найти фальшивую монетку, в распоряжении имеется одна настоящая монета.

Предполагаю, что можно решить задачу в общем случае для:
(3 N +1)/2 монет + настоящая монета за N взвешиваний.
N = 1, монет = 2 + настоящая монета
N = 2, монет = 5 + настоящая монета
N = 3, монет = 14 + настоящая монета
и.т.д
Поскольку N взвешиваний дают log2(3 N ) бит информации — информация о местоположении фальшивой монете среди (3 N +1)/2 монет и ее весе равна log2(3 N +1) бит, однако в одном из вариантов взвешиваний, когда весы всегда были в равновесии, фальшивая монета никогда не попадает на весы и мы не знаем ее вес, т.е. количество информации сокращается до log2(3 N ) бит.

Лемма: (3 N +1)/2 + 1 — всегда делится на 3 т.к (3 N +1)/2 + 1 = 3*(3 N-1 + 1)/2
Случай N=1, монет = 2 неизвестных + настоящая:
Делим монеты на 3 кучки, так чтобы настоящая была на одной из чашек весов.
С вероятностью 50% определяем вес фальшивой.
Случай N=2, монет = 5 неизвестных + настоящая:
Делим монеты на 3 кучки по 2, так чтобы настоящая была на одной из чашек весов.
Результат:
весы в равновесии => переход к случаю N=1
весы не в равновесии => (фальшивая монета на весах) => снимаем с весов одну неизвестную монеты, переставляем на ее место другую неизвестную монету с соседней чашки, возмещаем освободившееся место настоящей монетой.
Результат:
весы пришли в равновесие — фальшивую монету сняли
весы сменили показания — фальшивую монету переместили на другую чашку
весы не изменили показания — фальшивую монету не трогали.
Случай N=3, монет = 14 неизвестных + настоящая:
Делим монеты на 3 кучки по 5, так чтобы настоящая была на одной из чашек весов.
Результат
весы в равновесии => переход к случаю N=2
весы не в равновесии => (фальшивая монета на весах) => снимаем с весов 3 неизвестных монеты, переставляем на их место другие три неизвестных монеты с соседней чашки, возмещаем освободившееся место 3-мя настоящими монетами.
Результат
весы пришли в равновесие — фальшивую монету сняли
весы сменили показания — фальшивую монету переместили на другую чашку
весы не изменили показания — фальшивую монету не трогали.
+ стал известен вес фальшивой монеты
Третье взвешивание — определить фальшивую монету из трех монет при известном весе за одно взвешивание — тривиально.

Рассмотрим первый вариант:
Второе взвешивание:
Взвешиваем 3 кучку с 1ой (где все настоящие) , определяем легче фальшивая монета или тяжелее.
Третье взвешивание:
Взвешиваем монеты из третьей кучки: две на одну чашу весов и две на другую, определяем в какой паре фальшивая.
Четвертое взвешивание:
Взвешиваем пару в которой была фальшивая — находим фальшивую.

Ссылка на основную публикацию
Adblock detector