23:42 

Алгоритм

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

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

Комментарии
2013-02-10 в 04:11 

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

2013-02-12 в 23:41 

Слушатель
Don't stop the music.
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 раз использовать детектор для одного шара, который каждый раз другой. И значит из "как угодно часто" и "групп из любого кол-ва шаров" - одно условие избыточно.

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

2013-02-12 в 23:46 

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

2013-02-12 в 23:53 

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

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


wpoms

URL
2013-02-13 в 00:13 

Слушатель
Don't stop the music.
Гость,
Понял, спасибо.

     

Не решается алгебра/высшая математика?.. ПОМОЖЕМ!

главная