пятница, 5 июля 2013 г.

Радиоактивность

Знак
В лабораторию для анализа поступило 18 одинаковых предметов. Доподлинно известно, что 2 из них радиоактивны. Тестировать на радиоактивность можно любое количество предметов одновременно, но если во время теста их будет несколько, то нельзя определить какой именно из них радиоактивен. Как за 8 тестов найти оба радиоактивных предмета?

update
Первый - Andrew Antonets.
Ответ
Разделим всю задачу на несколько отдельных.
Задача №1.
Находим два радиоактивных предмета из 18 за восемь тестов.
Проверяем пять любых предметов. Если радиоактивности нет, то переходим к задаче №2. В противном случае проверяем два из этих пяти предметов. Это второй тест. Если нет радиоактивности, то за два теста находим один радиоактивный из трёх оставшихся. Затем из 13 предметов находим один радиоактивный за четыре теста. Аналогично поступаем, если при второй проверке радиоактивность есть.
Задача №2.
Находим два радиоактивных предмета из 13 за семь тестов.
Проверяем четыре любых предмета. Если радиоактивности нет, то остаются девять предметов и шесть тестов и переходим к задаче №3. Если радиоактивность есть, проверяем два из этих четырёх предмета, а затем находим хотя бы один радиоактивный из четырёх. Объединив все оставшиеся предметы, за четыре теста находим из 12 один радиоактивный.
Задача №3.
Находим два радиоактивных предмета из девяти за шесть тестов.
Проверяем три любых предмета. Если радиоактивности нет, то найти из шести предметов два радиоактивных за пять тестов проблем не составит. Если же эти три показывают радиоактивность, то проверяем на радиоактивность последовательно по отдельности два из них. Если хотя бы один из них радиоактивен, то задача становится очевидной - находим из оставшихся восьми один радиоактивный с помощью метода деления пополам.

Как найти монету, которая отличается по весу от остальных?

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

  1. тест на радиоактивность показывает сколько именно предметов из проверяемых радиоактивны?

    ОтветитьУдалить
  2. Разобьем все предметы на 5 групп: 4 по 4 предмета, и ещё одну группа из 2.
    Последовательно проверяем группы из 4х предметов. Возможны варианты:

    Случай 1: все 4 проверки групп из 4х предметов не показывают радиоактивности. Значит радиоактивные предметы - оставшиеся два

    Случай 2. Только одна из первых четырёх проверок показывает радиоактивность. Обозначим предметы из группы с обнаруженной радиоактивностью буквами abcd, плюс у нас есть еще группа из двух предметов - ef.
    Проверяем предметы ef (5я проверка)
    Случай 2-1. В ef есть радиоактивность. Тогда искомые предметы - один из abcd и один из ef. Шестой проверкой (например, предмета f) определяем искомый из ef. Седьмой проверяем ab, если есть радиоактивность, то восьмая проверка (например, предмета b) выделит искомый из ab, если нет - то восьмая проверка (например, предмета d) выделит искомый из cd.
    Случай 2-2. В ef - нет радиоактивности. Тогда искомые предметы - какие-то два из abcd. Проверяем последовательно предметы a, b и c, тем самым мы или обнаружим два радиоактивных, или только один, тогда второй искомый - d.

    Случай 3. Две из первых четырех проверок показали радиоактивность. Опять обозначим буквами предметы в группах, искомые предметы - один из abcd, и один из efgh. Действуем по алгоритму из 2-1: пятым замером проверяем ab. Если есть радиоактивность - значит один из ab, шестым выделяем искомый, а если нет, то один из cd, шестым определяем нужный. Точно так же поступаем с группой efgh, проверка группы ef, если есть радиоактивность, восьмым замером определяем один из них, если нет, то восьмым опеределяем один из gh.

    ОтветитьУдалить