23 авг. 2012 г.

Задача о двух милиционерах

Добрый день.

Многие помнят из детского сада школы теорему о двух милиционерах (название которой, видимо, объясняется тем, что если два милиционера идут в отделение, держа между собой преступника, то совершенно точно известно, куда идёт арестованный). Теорема важная и полезная, позволяет много хорошего понять про последовательности и функции, но сегодня мы поговорим не о ней (впрочем, желающие найдут подробности в википедии), а о задачке про 10 монет и весы. Раньше мы уже решали несколько простых задач о взвешиваниях. А сейчас будет более интересная.

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

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

Вам повезло, так как у торговца есть рычажные весы (т.е. весы с двумя чашами), а милиционеры согласны позволить вам сэкономить время, прямо на месте воспользовавшись этими весами, чтобы доказать свою честность (показать, что все монеты настоящие). Но есть одна проблема: весы очень ветхие, поэтому вы можете воспользоваться ими всего три раза (на четвёртый раз они сломаются, а вот три раза отработают правильно). Вам повезло ещё больше, ведь у милиционеров есть образец фальшивой монеты, который они любезно позволили использовать для доказательства (чтобы не перепутать с остальными монетами, на нём фломастером написали букву «Ф»).

Итак, вопрос: как выяснить за три взвешивания, есть ли среди ваших девяти монет фальшивая, пользуясь ещё одной заведомо фальшивой монетой?

Автор этой задачи А. В. Шаповалов, а сама она достаточно свежая (засвечена, насколько я помню, всего около двух лет назад).

Дополнение: в таких задачах предполагается, что весы умеют показывать, какая чаша тяжелее, но не показывают разницу масс объектов, находящихся в чашах. Другими словами, весы выдают знак (один из трёх ответов: «левая чаша тяжелее», «правая чаша тяжелее» или «чаши имеют одинаковый вес»), но не абсолютное значение.

Приглашаю обсудить задачу в комментариях. И покажите, пожалуйста, ссылку на эту задачку (http://my-tribune.blogspot.com/2012/08/9-monet.html) своим знакомым, любящим поломать голову :)

Хорошего дня!

63 комментария:

  1. Ответы
    1. Если вы знали эту задачу или уже успели всё в ней продумать, то лучше пока не надо (напишите через пару дней, пожалуйста). Полное и аккуратное решение может помешать остальным получить удовольствие от процесса самостоятельного решения задачки.

      Удалить
    2. А отдельной ссылкой можно?

      Удалить
    3. Да, отдельной ссылкой лучше. Желающие по ней пройдут, а остальные сами решат :)

      Удалить
  2. >> Нам повезло, так как враг хоть и коварен, но аккуратен — все фальшивые монеты заведомо имеют одинаковый вес.

    По-моему нам не повезло. Имели бы все фальшивые монеты заведомо разный вес, проблем бы не было.

    ОтветитьУдалить
  3. Спасибо! - красивое решение.

    ОтветитьУдалить
  4. Анонимный23.08.2012, 11:46

    Фальшивых монет может быть больше 1? Нам надо только установить факт наличия фальшивки, или ещё и найти её?

    ОтветитьУдалить
    Ответы
    1. Да, теоретически фальшивыми могли быть как все наши 9 монет, так и ни одна из них. Надо надёжно установить, есть ли среди наших девяти монет хоть одна фальшивая. Т.е. попытаться доказать свою честность (что все монеты настоящие). Находить все фальшивые не требуется.

      Удалить
  5. Анонимный23.08.2012, 11:54

    "выяснить за три взвешивания, есть ли среди ваших девяти монет фальшивая"
    вот если фальшивая заведомо только одна, то быстро решается.
    А если фальшивых может быть произвольное количество, то решения пока не нашел

    ОтветитьУдалить
  6. Мне показалось простым, извините:
    1. Н1Н2Н3 == Н3Н5Н6
    2. Н1Н2Н3 == Н7Н8Н9
    -> (Н3Н5Н6 == Н7Н8Н9) -> (Hx == Hx)
    3) НxНxНx < HxHxФ1

    ОтветитьУдалить
    Ответы
    1. Анонимный23.08.2012, 12:10

      не таким простым.
      1. Н1Н2Н3 == Н3Н5Н6 (тут Н4 наверное потеряли?)
      Допустим Н1, Н4, Н7 у Вас фальшивые. Тогда первые два взвешивания будут показывать равенство несмотря на то, что часть монет разные.
      А на третьем возможно такое:
      НхНхНх < НфНхФ1 но справа две фальшивых монеты, а не одна.

      Удалить
    2. Я не понимаю это решение. Можете пояснить?

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

      Вторым взвешиванием вы сравнили те же три монеты с оставшимися тремя (и опять логично считать, что веса совпали, т.к. в противном случае фальшивая точно есть).

      А что в третьем взвешивании?

      Удалить
    3. Анонимный23.08.2012, 13:03

      Предпологаю что 3ье взвешивание должно определять не было ли фальшивых в наших наборах по 3 монеты.
      H1H2H3<H7H8Ф. Но если H7H8 и H1H2 фальшивые, то это нам ничего не даст.

      Удалить
  7. Ответы
    1. Анонимный23.08.2012, 12:09

      1. Взвешиваем по 4 наших монеты, если вес не одинаков, то нашли фальшку. Если вес одинаков, то либо все фальшивые либо все настоящие.
      2. Взвешиваем одну из этих монет с фальшивкой, если вес разный то при первом взвешивании у нас были все настоящие, если вес одинаков то нашли фальшивку.
      3. Взвешиваем оставшуюся монету с фальшивкой, делаем выводы :)

      Удалить
    2. > Если вес одинаков, то либо все фальшивые либо все настоящие.
      Не совсем так. Если вес одинаков, то справа и слева одинаковое количество фальшивых.

      Удалить
    3. А если одинаков и в двух кучках оказалось по две фальшивки? Задача не такая простая, как кажется. :)

      Удалить
    4. Анонимный23.08.2012, 12:21

      опять неверно (если не предполагать, что только одна фальшивка есть)
      1. Ф1 Н2 Ф3 Н4 = Ф5 Н6 Ф7 Н8
      2. Н2 < Ф
      3. Н9 < Ф

      Удалить
  8. если не надо _находить_ фальшивую монету, а только доказать _факт_ её присутствия, то решение я нашёл; максимум за 3 (в большинстве комбинаций -- быстрее) взвешивания. Суть в толковании результатов взвешивания.

    ОтветитьУдалить
    Ответы
    1. По условию на фальшифой написано, что она такая, так что в этой задаче находит её не надо.

      Удалить
    2. Есть эталонная фальшивая монета (на ней "ф" написано). А есть сомнение, найдутся ли ещё фальшивые среди девяти одинаково выглядящих монет. Нам не надо найти среди них фальшивые, а надо установить, есть они там или нет.

      Удалить
  9. Задача точно имеет решение? Для восьми монет все просто, а для девяти все время не хватает взвешивания. Остается 1 монета с неизвестным статусом. :)

    ОтветитьУдалить
    Ответы
    1. Анонимный23.08.2012, 14:33

      Выложите решение для 8ми. Я могу только для 7ми :)

      Удалить
    2. > Задача точно имеет решение?
      У меня в своё время был такой же вопрос. Казалось, что где-то в условии опечатка или неточность... В этом прелесть этой задачки.

      Удалить
    3. Аноним, я ошибся в формулировках. Для восьми монет все приводится к той же одной монете. :) Для девяти я могу подтвердить все, кроме одной, последней.

      Удалить
  10. Анонимный23.08.2012, 14:41

    Илья, ну что ты наделал? У нас работа встала! :)

    ОтветитьУдалить
  11. Наст - н1, н2, н3...
    Фальш - ф1

    н1+н2+н3+н4 = н5+н6+н7+н8 (вывод, монеты с н1 по н8, либо все фальшивие, либо все настоящие)
    ф1>н9 (вывод, н9 - настоящая)
    ф1>"любой от н1 до н8" (вывод, монеты с н1 по н8 - настоящие)

    ОтветитьУдалить
    Ответы
    1. н1+н2+н3+н4 = н5+н6+н7+н8 (вывод, монеты с н1 по н8, либо все фальшивие, либо все настоящие)

      Либо н2 и н3 фальшивые, а также н6 и н7 фальшивые.

      Удалить
    2. Анонимный23.08.2012, 15:49

      Spelendora

      "вывод, монеты с н1 по н8, либо все фальшивие, либо все настоящие" - либо на каждой чаше весов одинаковое количество фальшивых монет

      Удалить
  12. Анонимный23.08.2012, 16:19

    решил. за 3 часа =(

    ОтветитьУдалить
    Ответы
    1. Анонимный23.08.2012, 16:25

      Блин, комментарий уехал.

      "Выложи куда-нибудь решение (pastebin, к примеру), я отказываюсь что-либо понимать)"

      Удалить
    2. Анонимный23.08.2012, 16:33

      Ок. Кажется, Илья не возражал.
      http://pastebin.com/aADeMYi7

      Удалить
    3. Анонимный23.08.2012, 16:52

      Вы спасли мой день

      Удалить
    4. Анонимный23.08.2012, 17:13

      Очень круто, вроде правильно, вы молодец

      Удалить
    5. Уважаемый аноним, спасибо за чёткое изложение! Думаю, оно многим поможет.
      И здорово, что Вы не стали расписывать последние полтора шага.

      Удалить
    6. Я шел тем же путем, но не дошел последние полшага!
      И правда, отличное изложение.

      Удалить
    7. Я, наверно, чего-то не сообразил, но вроде двух полученных неравенств достаточно, чтобы доказать отсутствие фальшивок во всех трех группах. То есть, достаточно двух взвешиваний?

      Удалить
    8. Ну, то что этот метод не позволит доказать подлинность 10 монет, это как бы очевидно, но смешно то, что этот способ не позволит доказать подлинность меньшего количества монет. Например, восьми монет. :)))
      В этой задаче скорее условие (количество монет) подогнано под решение, чем решение получено из условия :)))

      Удалить
    9. > То есть, достаточно двух взвешиваний?
      Я не понимаю, как за два взвешивания решить эту задачу.
      Скорее всего, Вы сделали неверный вывод из двух получившихся неравенств.

      Удалить
    10. Да, обманулся, извиняюсь. Можно сделать вывод только о том, что фальшивых монет не больше шести.

      Рассуждения были такие:
      В терминах обсуждаемого решения получается система неравенств:
      {
      x+y <= z
      z <= y

      Сложим неравенства:
      x+y+z <= y+z
      x <= 0

      Поскольку количество фальшивых монет неотрицательно:
      x = 0

      Подставим в исходную систему:
      {
      0+y <= z
      z <= y

      {
      y <= z
      z <= y

      Откуда:
      y = z

      Ну и поскольку y <= 3, ясно, что:
      x+y+z = y+z = 2y <= 6

      Удалить
  13. Анонимный23.08.2012, 17:42

    Делаем так:

    1) Делим свои монеты на 3 кучки по 3 монеты в каждой.
    2) Взвешиваем 2 кучки. Если веса одинаковые, продолжаем. Если нет, идем в тюрьму.
    3) Снимаем с весов любую из кучек, кладем туда еще не взвешенную. Взвешиваем. Если веса одинаковые, продолжаем. Если нет, идем в тюрьму.
    4) Снимаем с весов любую из кучек, из оставшейся кучки берем одну монету и кладем на пустую чашку. Туда же добавляем фальшивую. Взвешиваем. Если чашка с фальшивой монетой перевесила - у нас все монеты настоящие.

    Как это работает: На шагах (2) и (3) мы доказали, что кучки имеют одинаковый вес. Может в них и есть фальшаки, но их равное количество в каждой из кучек. Т.к. у всех кучек вес одинаковый, для дальнейших тестов мы можем использовать только одну из них.
    На шаге (4) определяем есть ли среди наших монет фальшак. Т.к. фальшак тяжелее, то вес (Н)+(Ф) > (Н)+(Н). То есть, чашка с известным фальшаком должна перевесить.
    Если перевесила наша чашка, то мы имеем (F)+(F) > (Н)+(Ф). Если веса равные, то это или (F)+(F) == (F)+(Ф) или (F)+(Н) == (Н)+(Ф), то есть среди наших монет есть как минимум один фальшак.

    О терминологии (Н) - настоящая монета, (F) - "неизвестный", наш фальшак (Ф) - "известный", ментовский фальшак. Разумеется, вес известного и неизвестного фальшака одинаковый

    ОтветитьУдалить
    Ответы
    1. Анонимный23.08.2012, 17:44

      а если все ваши монеты фальшивые?

      Удалить
    2. Вы не рассмотрели случай на последнем шаге: (Н)+(Н) < (F)+(Ф)
      Это вариант: в каждой кучке по одной фальшивке и в последнем шаге вы именно фальшивку переложили к ментовской фальшивке.

      Удалить
  14. Анонимный23.08.2012, 17:51

    Тогда сыграет случай (F)+(F) == (F)+(Ф)
    И весы уравновесятся.

    Нас оправдывает только случай (H)+(H) < (H)+(Ф), когда чашка с известным фальшаком перевешивает

    ОтветитьУдалить
    Ответы
    1. Анонимный23.08.2012, 18:10

      Но ведь (H)+(F) < (F)+(Ф) не оправдывает, хотя весы покажут такой же результат.

      Удалить
  15. Анонимный23.08.2012, 22:01

    Пусть ф - фальшивая монета (выданная полицейскими), И1-И9 - тестируемые монеты.

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

    Путь П() - количество фальшивых монет в выборке

    Взвешивание 1: (фИ1И2) <-> (И3И4И5)
    Если (фИ1И2) равно или меньше (И3И4И5) - значит тюрьма
    Если (фИ1И2) больше(И3И4И5), значит П(И1И2) => П(И3И4И5)

    Взвешивание 2: (фИ3И4И5) <-> (И6И7И8И9)
    Опять же, если (фИ3И4И5) равно или меньше(И6И7И8И9) - значит тюрьма
    Иначе П(И3И4И5) => П(И6И7И8И9)

    Взвешивание 3: (фИ6И7И8И9) <-> (И1И2И3И4И5)
    П(И1И2) => П(И3И4И5)=> П(И6И7И8И9)
    Обязательным условием отсутствия среди И1-И9 фальшивых монет является условие П(И6И7И8И9) = П(И1И2) = П(И3И4И5) = 0 при этом результат взвешивания будет равен (фИ6И7И8И9) > (И1И2И3И4И5).

    В остальных случаях при П(И6И7И8И9) != 0 результат взвешивания не будет (фИ6И7И8И9) > (И1И2И3И4И5).

    cj.

    ОтветитьУдалить
  16. Анонимный24.08.2012, 1:44

    добавил своё решение
    http://pastebin.com/PH7fbWMv

    ОтветитьУдалить
  17. Хм. А зачем торговец вообще звал полицейских? У него же наверняка есть хотя бы одна заведомо настоящая монета? С помощью этой монеты и трёх взвешиваний он бы спокойно мог и сам определить, что все монеты - настоящие.

    ОтветитьУдалить
    Ответы
    1. Возможно, это было раннее утро, а решающий задачу - первый клиент. Поэтому у никто из продавцов не мог предложить даже одну эталонную настоящую монету.

      Удалить
  18. Анонимный25.08.2012, 17:01

    Первое взвешивание:
    м1м2м3м4м5 -- м6м7м8м9ф
    может быть три случая: первая чаша перевесит - есть фальшивки
    равенство весов - есть фальшивки
    вторая чаша перевесит - либо м6м7м8м9 настоящие,либо среди них есть фальшивки надо это проверить

    Второе взвешивание:
    м6м7 -- м8ф
    может быть три случая: первая чаша перевесит - есть фальшивки
    равенство весов - есть фальшивки
    вторая чаша перевесит - либо м6м7м8 настоящие,либо м8 фальшивая

    Третье взвешивание:
    вместо ф ставим м9
    м6м7 -- м8м9
    может быть три случая: первая чаша перевесит - есть фальшивки
    равенство весов - нет фальшивок
    вторая чаша перевесит - есть фальшивки

    ОтветитьУдалить
    Ответы
    1. Анонимный26.08.2012, 3:21

      если в третьем будет равенство, то возможен вариант, что М7 и М8 фальшивые.

      Удалить
  19. Все монеты по условию задачи настоящие, надо только это доказать. То есть всегда должен случаться тот вариант, при котором нельзя точно сказат, есть ли фальшивая монета.
    взвешиваем х1+х2-ф+х3, где х - неизвестные, ф - фальшивые.
    здесь рабочие варианты- н1+н2-ф+н3, либо н1+н2- ф +ф3, то есть когда перевешивает правая чаша, часть. В ЛЮБЫХ других случаях фальшивая монета точно есть.
    таким образом мы уверены в трех монетах: ф, н1, н2.
    Взвешиваем н1+н2+ф-х4+х5+х6. Здесь случится перевес левой части, остальные варианты говорИ о наличии фальшивки.
    и финальнвя проверка: н1+н4+н5+н6-х7+х8+х9+х3. Здесь случится равновесие, то есть все монеты настоящие.
    как-то так...

    ОтветитьУдалить
    Ответы
    1. Вы ошибаетесь, возможен вариант н1+ф2 - ф+ф3

      Удалить
  20. В задаче не определено правило ВЗВЕШИВАНИЯ.
    Вернее отсутствует четкое определение КОНЦА ВЗВЕШИВАНИЯ, то есть МОМЕНТА когда счетчик оставшихся взвешиваний становится на единицу меньше.

    Свойство рычажныж весов в том, что в зависимости от складывающейся ситуации на чаши можно докладывать вес, причем на разные стороны.

    ОтветитьУдалить
    Ответы
    1. Верно, уточняю:
      Взвешивание - это считывание данных (т.е. взгляд на стрелку весов). Посмотреть можно ровно три раза.

      Удалить
  21. Анонимный15.09.2012, 11:11

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

    ОтветитьУдалить
    Ответы
    1. Решения выше уже предложены. Но Вы правы - гораздо интереснее и полезнее решить самому, чем понять чужой ход мыслей.
      Вопрос про "правильный путь" я не понял.

      Удалить
  22. Анонимный07.10.2012, 22:56

    Моя мысль:
    1.Взвешиваем 2 монетки (Ф)милицейская и (Х)ваша. Имеем:
    (Ф)=(Х)*тюрьма* или (Ф)>(Х) значит (Х)=(Н) настоящая.
    2.Взвещиваем по 4 монетки(Х) и по 1 извесной (Ф) или (Н)
    Имеем:
    Либо 4*(х)+(Ф)<4*(Х)+(Н)*тюрьма*
    Либо 4*(х)+(Ф)=4*(Х)+(Н)*тюрьма*
    Либо 4*(х)+(Ф)>4*(Х)+(Н)
    3.Взвешиваем, меняя (Н) и (Ф) местами. Получаем
    Либо 4*(х)+(Н)>4*(Х)+(Ф)*тюрьма*
    Либо 4*(х)+(Н)=4*(Х)+(Ф)*тюрьма*
    Либо 4*(х)+(Н)<4*(Х)+(Ф)*вы свободны*

    ОтветитьУдалить
    Ответы
    1. Анонимный08.10.2012, 7:35

      А если в составе 4*(х)и 4*(Х)одинаковое количество фальшивых монет, например все фальшивые кроме(Н)?

      Удалить
  23. Анонимный28.11.2012, 23:26

    Не могу найти ошибку в рассуждениях. Допустим, монеты (м1, м2...м9) и фальшивую монету (ф) взвесить таким образом:
    1. м1м2м3м4м5 - фм6м7м8м9
    При перевешивании левой части и при уравнивании - спектакль окончен, при перевесе правой продолжаем.
    2. м1м6м7м8м9 - фм2м3м4м5
    Опустим плачевные варианты, правая перевесила, значит,
    3. м1 - ф, при перевесе правой части мы совершенно свободны и вправе наслаждаться арбузом.

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

    Любовь

    ОтветитьУдалить
    Ответы
    1. Если м2 и м6 фальшивые, то переход к третьему пункту будет некорректным.

      Удалить

Понравилась заметка? Подпишитесь на RSS-feed или email-рассылку.

Хотите поделиться ссылкой с другими? Добавьте в закладки:



Есть вопросы или предложения? Пишите письма на адрес mytribune АТ yandex.ru.

С уважением,
      Илья Весенний