danetka.ru

Имеется 100 неотличимых по виду шаров, про которые известно, что среди них ровно 51 радиоактивный.

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

За какое количество тестов вы можете гарантированно найти все радиоактивные шары?

Пока, по-простому, получается 146 тестов. Можно меньше?

Да, 146.
Не очень понятно, куда можно меньше.

Ну, во-первых, 145. Последний шар проверять необязательно, ведь состав определен однозначно.
А вторых, сократить есть куда. Начните со случая двух положительных тестов в первой серии.

Dendr писал(а):Начните со случая двух положительных тестов в первой серии.

Ну здесь всё просто. только одна активная пара в первой серии однозначно свидетельствует, что в остальных 49-ти парах расклад смешанный, активный плюс неактивный.
Таким образом вставляем в датчик шар из активной пары и последовательно докидываем к нему по одному из оставшихся пар.
Зазвенело — значит пошёл в активные, а парный к нему без всякой проверки в неактивные. Ну а если не зазвенело значит соответственно наоборот.
Всего получается 99 замеров.
В случае если активных пар после первого замера будет больше одной всё несколько сложнее, т.к. среди оставшихся пар будут как смешанные, так и неактивные.

Dendr писал(а):Ну, во-первых, 145. Последний шар проверять необязательно, ведь состав определен однозначно.
А вторых, сократить есть куда. Начните со случая двух положительных тестов в первой серии.

В худшем случае у меня не получается меньше 145.

Есть гарантированный алгоритм на не более чем 125 испытаний.

--- скрыто
Шары образуют пул.
Берем пару шаров из пула и испытываем. Если результат отрицательный - откладываем пару в сторону. Продолжаем до первого положительного результата (он нам гарантирован, так как R-шаров больше половины).

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

После того как все шары возвращены в пул - повторяем процедуру.
Обычный шар требует не более двух испытаний - 50*2=100.
R-шары определяются либо по ходу дела, либо парами за одно испытание. 50/2=25.
Последний шар отдельно идентифицировать не надо.
--- конец

Наверняка можно дополнительно сэкономить, зная, сколько каких шаров еще не идентифицировано, но процесс в этом случае трудно формализовать.

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

Инна писал(а):Обычный шар требует не более двух испытаний - Юля, а почему? Если он был проверен с обычным и отправлен в пул, и так может много раз происходить.

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

--- добавление
Тут, видимо, можно еще сэкономить.

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

Пусть у нас К положительных результатов.
После этого проведем этап чистки по всем парам. Будем считать, что пул пополнен по максимуму.

Получится следующее.
Мы провели 50 замеров по пулу и 50-К по отрицательным парам, всего 100-К замеров.

У нас идентифицировано 50-К обычных шаров и 2К R-шаров. Осталось 50-К шаров в пуле, из которых 51-2К R-шаров и К-1 обычный шар.
Мы можем пойти двумя путями:

I. Испытаем все оставшиеся шары вместе с R-шаром. Потребуется еще 49-К попыток, всего 149-2К.
2. Сработаем описанным методом пула. Понадобится, напрямую, не больше чем 2( К-1)+(51-2К)/2 попыток. Округлим вниз вместо вычитания попытки на последний шар, получим 23+К, всего 123.

Это видимо уже близко к реальному пределу. Может быть, где-то еще 1-2 попытки можно сэкономить, если повторить итерацию. На данный момент наименее перспективным)) для нас выглядит вариант с 13 положительными замерами на первом этапе.

В источнике (школьная олимпиада) ответ был 145, но с комментарием, что можно уменьшить.
У меня вышло 122. По потому, что для двух положительных тестов улучшить не удается, а все прочие нет смысла сокращать, достигнув этого числа.
Таким образом, случай 14 положительных (все про первую серию) берется "в лоб", остальные нуждаются в персональной стратегии, хотя шаблон общий.

Случай 13 действительно критический, но и он проходится:
50 замеров в первой серии: "положительные" откладываем, "отрицательные" маркируем jA-jB, где j - номер теста от 1 до 37.
37 замеров во второй серии: все шары "A" с активным шаром. Таким образом, мы находим 37 чистых шаров и некое (возможно ноль) активных.
Остается вычислить 12 чистых из не более чем 37 подозрительных.

Разбиваем их на пары - 18 пар и проверяем.
К этому моменту мы сделаем 105 замеров и у нас найдется от 6 до 12 "отрицательных" пар плюс один подозрительный.

Поскольку минимизация излишня, вспомним, что у нас 17 тестов в запасе, следовательно, при 8 или менее отрицательных проверяем в лоб.
При 12 - проводим 12 тестов с одним из шаров каждой пары и находим 12 чистых.

Совсем особые случаи: 9, 10 или 11 отрицательных. Не забудем про "37-й" шар.
Проверяем как на втором этапе, находим чистые, и получаем табличку
9 - 8 тестов в запасе - 3 чистых из 10
10 - 9 - 2 из 11
11 - 10 - 1 из 12
последний проще всего, 6 пар, одна отрицательная. За 7 тестов справляемся.
Второй. 5 пар, либо 2 отрицательных пары (плюс два теста), либо одна, то есть два чистых из трех (эта пара и нечетный шар). 7 тестов хватило.

Теперь 9...
Проводим 5 тестов, остается 3 в запасе.
У нас будет либо три пары (в каждой чистый и активный), либо две (всего 4 шара). Трех тестов хватит.

Для прочих случаев убеждаемся, что все тоже получается...

Вообще, если мы пронумеруем шары, то число комбинаций равно C(100,51)~=2^100/sqrt(50pi)<2^97, то есть теоретически должно получиться за 97 тестов.
Но почему-то не выходит даже при везении: 49 отрицательных в первой серии подряд, затем проверка одного из каждой пары с помощью двух нетронутых (они точно активны). Видимо, дело в том, что дихотомия неравномерная.

А как получить 122 при двух положительных результатах?

--- отбой вопросу, моя ошибка при подсчете

Дендр, а что за олимпиада и когда, если не секрет.

Не помню, скорее всего, эйлеровская от 2016 года. Я даты не отслеживаю, просто задачи интересные подмечаю и запоминаю.