Прерванная установка игры на комп или как найти молекулу

логическая задача на взвешивание молекул

Фомуви устанавливал новенькие логические игры на свой компьютер, как вдруг его занятие прервал звук программы, извещающей о получении электронного письма. Он открыл ящик и увидел сообщение следующего содержания:

«Уважаемый господин инопланетянин! Мне известно, что Вы умеете решать логические задачи, и в связи с этим у меня к Вам просьба. Наш институт столкнулся с некоторыми трудностями в исследованиях, и я очень рассчитываю на Вашу помощь. Так как работа НИИ связана с повышенной секретностью, подробности Вы получите при личной встрече. С глубоким почтением, директор Научно-исследовательского института Экспериментальной химии А.С. Пробиркин».

«Еще одна интересная головоломка!» – радостно подумал Фомуви, отложил установку игры на комп и, отправив сообщение, что уже вылетает, спешно отправился в НИИ. На проходной его ожидал сам директор, высокий худощавый мужчина 40 или 45 лет.
Обменявшись с инопланетянином крепким рукопожатием, он сразу перешел к делу:
– Наш институт изучает свойства новых веществ. Недавно нам посчастливилось открыть сразу два вида неизвестных ранее науке молекул. Мы получили сразу 12 образцов. Путем долгих исследований мы смогли определить, что одна из двенадцати молекул отличается молекулярной массой от одиннадцати других, но мы не знаем, какая именно. Нам нужно отделить ее, чтобы провести дополнительные опыты. Вы можете значительно помочь не только институту, но и всей земной науке.
– С удовольствием помогу, — ответил инопланетянин.
– Тогда давайте пройдем к Большому Химическому Анализатору, – поспешно сказал директор Пробиркин.

Они перешли в просторный зал, посередине которого поблескивал светящимися индикаторами гигантский прибор, на котором висела табличка: «БХА»

–Это наш Анализатор. Он умеет сравнивать вещества и показывать, одинаковы ли они по молекулярной массе в сравниваемых образцах или различаются. И он может показать, у какой молекулы или группы молекул молекулярная масса больше, чем у сравниваемой молекулы или группы. К сожалению, в его устройстве есть ряд недостатков. БХА расходует прорву энергии, а она у нас лимитирована. Поэтому мы можем провести только три сравнения, иначе энергии не хватит на другие важные исследования в этом году. Во время одного действия можно сравнивать две любые молекулы или две равные по числу группы молекул. Для удобства мы поместили каждую из них в отдельный контейнер, пронумеровав от 1 до 12. Наши программисты могут написать программу сравнения содержимого контейнеров, но не знают алгоритма. Вы специалист по этой части, возможно, вы подскажете порядок действий?

Это была сложная головоломка, инопланетянину пришлось потрудиться над ней минут 15, но он нашел, как именно следует сравнивать молекулы, в результате чего удалось их правильно разделить. Благодарные работники института устроили банкет в честь Фомуви, после которого он, довольный собой, отправился домой, где его ждали диски с играми. Что именно подсказал Фомуви ученым? Первый, кто решит эту головоломку, получит 30 фомувиков.

Оставить комментарий

Для отправки комментария вам необходимо авторизоваться.

  1. absurd_logik

    В общем так. Делим молекулы на 2 кучки по 6. Одну из них делим пополам и ложим обе части на весы. Если весы уравновешены, то берем другую кучку, если нет, то продолжаем работать с этой. Из 6 выбираем 4, делим на 2 и взвешиваем. Если они уравновешены, то берем одну из этих четырех и одну из других двух и сравниваем. Тогда молекула найдена. Если не уравновешены, то отбрасываем 2, которые точно нормальные. Остается 4. Мы знаем, что 2 из них тяжелее/легче двух других, пронумеруем их как 1, 2, 3, 4. Пусть 1+2>3+4. Взвесим их другим способом. Возьмем 2 из молекул, которые мы отбросили ранее. Пусть назовем их 5 и 6. Например 1+3>5+6, тогда искомая молекула 1, или 1+3=5+6, тогда искомая молекула 2. Ну и там аналогично.

  2. Art

    Создадим 2 группы: в первую молекулы 1, 2, 3, 4 во вторую 5, 6, 7, 8.
    Проанализируем.
    1) Если массы равны, значит, молекулы одинаковы и другая молекула среди молекул с номерами 9-12.
    Взвесим 1, 2, 3 и 9, 10, 11.
    1.1) Если массы равны, то 12.
    1.2) Если нет (например 1, 2, 3>9, 10, 11), то мы будем знать, что другая среди 9, 10, 11 и она легче. Взвесим 9 и10 если равны, то 11 если нет, то та которая легче.

    2) Если массы не равны (например, 1, 2, 3, 4>5, 6, 7, 8).
    Создадим 2 группы: в первую 4, 5, 6, 7 во вторую 8, 9, 10, 11.
    2.1) Если равны, то другая среди 1, 2, 3 и тяжелее. Взвесим 1 и 2 если равны, то 3 если нет, то та которая тяжелее.
    2.2) Если не равны и 4, 5, 6, 78, 9, 10, 11, то другая или 4 или 8. Взвесим 8 и 9 если равны, то 4 если нет, то 8.

  3. Art

    2.2) Если не равны и 4, 5, 6, 7>8, 9, 10, 11, то другая или 4 или 8. Взвесим 8 и 9 если равны, то 4 если нет, то 8.
    2.3) Если не равны и 4, 5, 6, 7<8, 9, 10, 11, то другая среди 5, 6, 7 и легче. Взвесим 5 и 6 если равны, то 7 если нет, то та которая легче.

  4. LoadRunner

    К этому ответу добавлю:
    2.2) Если молекула 4, то она тяжелее остальных, если будет 8 — то она легче.
    А вообще, довольно интересный ход решения. Я бы вряд ли додумался, но был близко :) Точнее, искал способы определить однозначно, легче или тяжелее искомая молекула.

  5. Irma

    1. Делим все молекулы на три парные группы:
    І. №№ 1, 2, 3 и №№ 4, 5, 6
    ІІ. №№ 7, 8 и №№ 9, 10
    ІІІ. № 11 и № 12

    2. Сравниваем первую парную группу (№№ 1, 2, 3 и №№ 4, 5, 6). ПЕРВОЕ взвешивание. Допустим, равновесие нарушилось. Допустим №№ 1, 2, 3 тяжелее. Значит, в одной из этих групп искомая молекула. Но мы не знаем, легче ли она чем остальные, или тяжелее. Значит, нужно произвести ещё одно взвешивание.

    3. Берём любые три молекулы из остальных (например, №№ 7, 8, 9). Сравниваем их массу с №№ 1, 2, 3. ВТОРОЕ взвешивание. Если равновесие не нарушилось, искомая молекула в №№ 4, 5, 6.

    4. Мы знаем, что группа №№ 4, 5, 6 легче, чем группа №№ 1, 2, 3. (По условию задачи анализатор может показывать, у какой группы молекулярная масса больше!) Значит, нужно искать самую лёгкую молекулу. Сравниваем массы №4 и №5. Если одна из них легче, то это и есть искомая молекула, если равновесие не нарушилось, искомая молекула — №6. Это и будет ТРЕТЬЕ взвешивание. Если в третьем пункте равновесие нарушилось, ищем соответственно самую массивную молекулу.

    5. Допустим в первой группе (№№ 1, 2, 3 и №№ 4, 5, 6) искомой молекулы нет, и равновесие во время ПЕРВОГО взвешивания не нарушилось.

    6. Разбираемся с молекулами групп №№ 7, 8 и №№ 9, 10. Для этого берём любые две из уже взвешенных (например, №№ 1, 2). Во время ВТОРОГО взвешивания сравниваем №№ 1, 2 и №№ 7, 8. Если равновесие не нарушилось, значит, искомая молекула среди №№ 9, 10. (Если нарушилось, то среди №№ 7, 8 – это не принципиально для последнего взвешивания, я это расписывать не буду).

    7. Во время ТРЕТЬЕГО взвешивания сравниваем №1 (или любой из уже взвешенных) с №9. Если равновесие нарушилось, то искомая молекула — №9. Если не нарушилось, то № 10.

    8. Если равновесие не нарушилось во время сравнения первой и второй групп, то у нас остаётся только две молекулы и одно взвешивание. Для ТРЕТЬЕГО взвешивания достаточно взять любую из уже взвешенных молекул и сравнить с №11. Если равновесие нарушилось, то искомая молекула №11. Если не нарушилось, то искомая молекула №12.

  6. admin

    Уважаемая Irma, прошу помочь. Вот ответ есть, но у меня так и не получилось понять, правильно вы решили или нет. Возможно, нужно каждый ответ проверять практически, на что пока, к сожалению, времени нет. Может есть какие-то мысли по этому поводу?

    Разделим контейнеры с молекулами на три группы. В группе «А» будут контейнеры 1, 2, 3 и 4. В группе «Б» – 5, 6, 7 и 8, в группе «В» – 9, 10, 11 и 12.
    Сравниваем группы «А» и «Б». Они могут быть одинаковыми или различающимися. Если они одинаковы, то искомая молекула находится в группе «В», а молекулы из групп «А» и «Б» эталонные. Сравниваем между собой молекулы с номерами 9 и 10. Если они разные, то третьим действием сравниваем 9 молекулу с любой эталонной. Если они одинаковы, тоискомая 10, а если различаются, то искомая 9. В случае если 9 и 10 были одинаковыми, то искомая либо 11, либо 12. Сравниваем 11 с любой эталонной. Если они различаются, то искомая 11, если одинаковы, то искомая 12.
    Однако если группы «А» и «Б» были разными, то могут быть два варианта:
    1. Совокупность молекул «А» имеет большую молекулярную массу, чем «Б», а группа «В» эталонная.
    2. Молекулы «А» имеют меньшую молекулярную массу, чем молекулы «Б», а «В» – эталонная группа.
    Второй вариант абсолютно симметричен первому (с переменой знаков «больше» и «меньше» местами), поэтому рассмотрим первый вариант.
    Во время второго действия сравним молекулы 1, 2 и 5 с молекулами 3, 4 и 9, зная, что 9-я молекула эталонная.
    Если 1,2 и 5 одинаковы с 3, 4 и 9, то искомая молекула находится среди 6, 7 и 8, причем, одна из них имеет меньшую молекулярную массу, чем прочие. Тогда третьим действием сравниваем между собой молекулы 6 и 7. Если они равны, то искомая 8, если не равны, то искомая та, что окажется легче.
    Если же во время второго сравнения молекулы 1, 2 и 5 оказались с большей молекулярной массой, чем у 3, 4 и 9, то искомая находится среди 1 и 2, к тому же, она должна иметь большую молекулярную массу, чем у любой другой. Третьим взвешиванием сравниваем 1 и 2. Та, что имеет большую молекулярную массу, есть исходная.
    Если же при втором взвешивании у молекул 1, 2 и 5 совокупная молекулярная масса оказалась меньше, чем у 3, 4 и 9, это значит, что либо молекула 5 имеет меньшую молекулярную массу, чем все прочие, либо молекула 3 или 4 имеет большую молекулярную массу. Третьим действием сравниваем 3 и 4. Если они равны, то искомая 5. Иначе же искомой является та, что имеет большую массу.

  7. Irma

    Всё-таки я ошиблась. В шестом пункте я пытаюсь выяснить, какая из четырёх молекул отличается по массе, совершенно забывая, что у меня есть ещё и молекулы №11 и №12. (Вот она — нехватка оперативной памяти :( ) Если при втором взвешивании равновесие нарушается, то мой вариант ещё возможен. Но, если не нарушается, то с четырьмя оставшимися молекулами за одно оставшееся взвешивание никак не разобраться.
    Задачка, конечно, зубодробительная. Даже для того, чтобы понять уже готовый ответ, нужно поднапрячься.
    Кстати, как это вы собрались «ответ проверять практически»? У вас есть прибор для измерения молекулярной массы? =)

  8. Irma

    И набор молекул… :-D

  9. LoadRunner

    Можно на монетках проверять, если не хватит воображения и бумаги с ручкой :)

  10. Irma

    Почему админы обходят молчанием ответы на эту задачу?

  11. admin

    Потому что я не семилапый пятиног. На данный момент я ищу правильный ответ, чтобы проверить ваши ответы. Ко мне ещё вопросы есть?

  12. Irma

    Не надо так бурно реагировать. Это всего лишь вопрос.

  13. admin

    Я совершенно спокоен :-) задача запутанная. Ответ нашёл. Теперь бы сравнить всё и найти ошибки (или сказать, что всё верно).

  14. LoadRunner

    Стандартная задача про фальшивую монету и аптекарские весы :) Меняется количество и фон задачи, а шаблон и алгоритм одинаковые :) Только для тех случаев, когда МЫ ЗНАЕМ, больше или меньше (строго определённо) искомый предмет.
    В общем виде он примерно следующий (решается по этому алгоритму в обратном порядке):
    1. К последнему взвешиванию должно остаться 2-3 предмета.
    Два предмета сравниваются между собой. Если один из них легче (как правило, именно легче, а не тяжелее, но это не имеет значения), то искомый предмет найден. Если оба одинаковы, то третий — искомый (если к концу осталось три предмета).
    2. К предпоследнему взвешиванию должны остаться 2-3 группы предметов (по 2-3 предмета в каждой, одинаковое количество в каждой группе).
    Взвешивание двух групп приводит к выявлению той, где искомый предмет.
    3. То же самое, что и 2, если общее количество предметов больше 9.
    4. То же самое, что и 2, если общее количество предметов больше 27.

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

    Взвешивание N (последнее): 2-3 предмета (задача на одно взвешивание).
    Взвешивание N-1 (предпоследнее): 2-3 предмета, умноженное на 2-3 группы, итого: 4-9 предметов (задача на два взвешивания).
    Взвешивание N-2: 4-9 предметов умножить на 2-3 группы. Итого 8-27 предметов. На самом деле 10-27, поскольку до 9 — это два взвешивания.

    Принцип понятен, я думаю. Теперь приступим к решению задачи, у которой три способа её решить :) I. Искомая молекула больше остальных.

    Первое решение:
    1. Делим 12 молекул на две группы по 6 контейнеров в каждой. Сравниваем. Оставляем ту, где молекулярная масса больше.
    2. Делим на две группы по три молекулы. Сравниваем. Оставляем большую.
    3. Берём два любые контейнера и сравниваем. Где молекулярная масса больше — там и искомая молекула. Если она равна, то искомая молекула в третьем контейнере.

    Второе решение:
    1. Делим 12 молекул на три группы по 4 контейнера. Сравниваем, оставляем группу с большей молярной массой (если равны — третью группу).
    2. Делим на две группы по 2 контейнера и сравниваем. Оставляем большую группу.
    3. Сравниваем оставшиеся два контейнера между собой и искомая молекула сами знаете где :)
    Третье решение:
    1. Делим на четыре группы по 3 контейнера. Сравниваем любые две группы. Если они равны, то:
    2а) Взвешиваем оставшиеся две группы, оставляем ту, где молекулярная масса больше.
    3а) У нас три контейнера и мы знаем, что с ними делать :) Если не равны, то оставляем ту группу, где молекулярная масса больше:
    2б) Сэкономили энергию, так как у нас осталось три контейнера — а это одно взвешивание :)
    II. Искомая молекула меньше остальных.
    Алгоритм тот же, но со словом «меньше» :)
    III. Мы НЕ ЗНАЕМ, больше или меньше молекулярная масса у искомой молекулы.
    А в условиях задачи не сказано, больше или меньше. Там как раз неопределённость :( У каждого участника довольно интересные способы нахождения, но в каждом может возникнуть ситуация, где тремя взвешиваниями не обойтись. Это если я правильно все варианты просчитал :) Но в любом случае, проверяющие ответы тоже рассмотрят эти варианты, поэтому не вижу смысла расписывать те ситуации, где потребуется четвёртое взвешивание.
    На мой взгляд, задача не решаема гарантировано за три взвешивания (есть вероятность выпадения того самого варианта на четвёртое взвешивание), но я ещё подумаю над задачкой, зацепило :)

Подпишись на обновления