Алгоритм

[wpoms.]

Есть `100` металлических, неотличимых друг от друга, шаров, среди которых `50` шаров радиоактивны. Также имеются три детектора. Для каждой группы шаров детектор определяет наличие в группе радиоактивных шаров. Известно, что один детектор всегда дает правильный ответ, другой всегда дает неправильный ответ, а третий иногда реагирует должным образом, а иногда и неправильно, но не известно, какой из детекторов что делает. Предложите процедуру, позволяющую с уверенностью найти `50` радиоактивных шаров. Детекторы могут быть использованы как угодно часто и для групп из любого количества шаров.

@темы: Головоломки и занимательные задачи, Олимпиадные задачи

Comments

[Adjirranirr]

Для определенности, пусть детектор A всегда дает правильный ответ, детектор B — неправильный, C — произвольный.
Просканируем всеми детекторами кучу из 100 шаров. Возможны 2 исхода — 2 положительных, один отрицательный результат, или 2 отрицательных, 1 положительный результат (все три одновременно результата не могут быть равными, т.к. всегда A = ¬B).
В первом случае, детектор, давший отрицательный результат — это B, во втором случае, детектор, давший положительный результат, это A. Дальше сканируем каждый шар и, в зависимости от типа детектора, определяем, радиоактивен шар или нет.

[Слушатель]

Adjirranirr,
Я не понял вашего решения.

Возможны 2 исхода — 2 положительных, один отрицательный результат, или 2 отрицательных, 1 положительный результат

Для каждого шара? Если нет - то получается для каждого детектора - вектор из 100 значений с которым непонятно что делать. Предполагаю, что вы имели в виду исход трёх детекторов для каждого шара. Тогда:

В первом случае, детектор, давший отрицательный результат — это B

Неверно. Контрпример: возьмём нерадиоактивный шар и проверим его с помощью трёх детекторов X1, X2, X3. Допустим что:
X1: 1 X2: 0 X3: 1

Тогда X2 дал отрицательный результат, но не ошибся. Следовательно X2 не B.

во втором случае, детектор, давший положительный результат, это A

Неверно. Контрпример выстраивается похожим образом.

wpoms.,
Задача имеет решение? Потому что у меня получается, что нет. Для простоты я предположил, что кол-во шаров 2 и один из них радиоактивен (думаю, что 100 - здесь несущественный фактор).
Мы можем с уверенностью выделить детектор, который неслучаен. Но знать прав он или всегда врёт - по-моему мы не можем. То есть:

Допустим, что исход для взятого шара - X1: 0, X2: 0, X3: 1. Поскольку у правого и неправого детектора одинаковых результатов быть не может - следовательно либо X1 либо X2 - случайный, X3 - неслучайный.
Итак мы знаем, что X3 - неслучайный детектор. Однако знать прав он или нет - по-моему возможным не представляется. То есть:

Очевидно, что вектор результатов X3 для двух шаров будет 1 0.

Тогда для какого-то детектора из X1, X2 вектор будет: 0 1
И что? Откуда мы знаем какой детектор прав, а какой нет?

Детекторы могут быть использованы как угодно часто и для групп из любого количества шаров.

Этот момент для меня немного непонятен. Как определяется результат детектора для группы из k шаров? Я предположил, что в виде вектора. Но тогда это тоже самое, что k раз использовать детектор для одного шара, который каждый раз другой. И значит из "как угодно часто" и "групп из любого кол-ва шаров" - одно условие избыточно.

Буду рад услышать где я ошибаюсь.

[All_ex]

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

[Гость]

Как определяется результат детектора для группы из k шаров?

Как для одного, большого, шара, состоящего из всех шаров группы. Т.е. это не вектор, не некая величина, зависящая от количества радиоактивных шаров, но датчик типа Да-Нет.

Но знать прав он или всегда врёт - по-моему мы не можем. То есть:

Наша первая тестовая группа - ваши два шара, среди которых есть, гарантированно, один радиоактивный.
Процитирую Adjirranirr

Возможны 2 исхода — 2 положительных, один отрицательный результат, или 2 отрицательных, 1 положительный результат (все три одновременно результата не могут быть равными, т.к. всегда A = ¬B).
В первом случае, детектор, давший отрицательный результат — это B, во втором случае, детектор, давший положительный результат, это A. Дальше сканируем каждый шар и, в зависимости от типа детектора, определяем, радиоактивен шар или нет.

wpoms

[Слушатель]

Гость,
Понял, спасибо.