Радиоактивные шары

Логические задачи

Модераторы: Азарапетыч, Администрация

Ответить
Аватара пользователя
Dendr
Акула пера
Акула пера
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Пол: Мужской
Откуда: Раменское, Мос.обл.
Контактная информация:

Радиоактивные шары

Сообщение Dendr »

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

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

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

Тоня
Популярный автор
Популярный автор
Сообщения: 2526
Зарегистрирован: 29 июн 2005, 21:45
Пол: Женский

Re: Радиоактивные шары

Сообщение Тоня »

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

Аватара пользователя
Инна
Популярный автор
Популярный автор
Сообщения: 1434
Зарегистрирован: 18 июл 2006, 18:44
Пол: Женский
Откуда: Калифорния

Re: Радиоактивные шары

Сообщение Инна »

Да, 146.
Не очень понятно, куда можно меньше.
Вы только что начали читать фразу, чтение которой Вы уже заканчиваете...

Аватара пользователя
Dendr
Акула пера
Акула пера
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Пол: Мужской
Откуда: Раменское, Мос.обл.
Контактная информация:

Re: Радиоактивные шары

Сообщение Dendr »

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

Аватара пользователя
Valentin
Акула пера
Акула пера
Сообщения: 6885
Зарегистрирован: 15 дек 2005, 10:51
Пол: Мужской
Откуда: С. Пб

Re: Радиоактивные шары

Сообщение Valentin »

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

Аватара пользователя
Шшок
Акула пера
Акула пера
Сообщения: 9061
Зарегистрирован: 28 ноя 2003, 14:05
Пол: Мужской
Откуда: С большой дороги.

Re: Радиоактивные шары

Сообщение Шшок »

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

Юляша
Популярный автор
Популярный автор
Сообщения: 3352
Зарегистрирован: 15 янв 2009, 12:32
Пол: Женский

Re: Радиоактивные шары

Сообщение Юляша »

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

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

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

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

--- конец

Наверняка можно дополнительно сэкономить, зная, сколько каких шаров еще не идентифицировано, но процесс в этом случае трудно формализовать.
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.

Аватара пользователя
Инна
Популярный автор
Популярный автор
Сообщения: 1434
Зарегистрирован: 18 июл 2006, 18:44
Пол: Женский
Откуда: Калифорния

Re: Радиоактивные шары

Сообщение Инна »

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

Юляша
Популярный автор
Популярный автор
Сообщения: 3352
Зарегистрирован: 15 янв 2009, 12:32
Пол: Женский

Re: Радиоактивные шары

Сообщение Юляша »

Инна писал(а):Обычный шар требует не более двух испытаний - Юля, а почему? Если он был проверен с обычным и отправлен в пул, и так может много раз происходить.
Нечетко у меня получилось.
Правильнее было бы написать, что пул уменьшается либо на один обычный шар после пары испытаний, либо на два 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 положительными замерами на первом этапе.
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.

Аватара пользователя
Dendr
Акула пера
Акула пера
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Пол: Мужской
Откуда: Раменское, Мос.обл.
Контактная информация:

Re: Радиоактивные шары

Сообщение Dendr »

В источнике (школьная олимпиада) ответ был 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 шара). Трех тестов хватит.

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

Аватара пользователя
Dendr
Акула пера
Акула пера
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Пол: Мужской
Откуда: Раменское, Мос.обл.
Контактная информация:

Re: Радиоактивные шары

Сообщение Dendr »

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

Юляша
Популярный автор
Популярный автор
Сообщения: 3352
Зарегистрирован: 15 янв 2009, 12:32
Пол: Женский

Re: Радиоактивные шары

Сообщение Юляша »

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

--- отбой вопросу, моя ошибка при подсчете
Последний раз редактировалось Юляша 01 фев 2017, 22:09, всего редактировалось 1 раз.
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.

Аватара пользователя
Инна
Популярный автор
Популярный автор
Сообщения: 1434
Зарегистрирован: 18 июл 2006, 18:44
Пол: Женский
Откуда: Калифорния

Re: Радиоактивные шары

Сообщение Инна »

Дендр, а что за олимпиада и когда, если не секрет.
Вы только что начали читать фразу, чтение которой Вы уже заканчиваете...

Аватара пользователя
Dendr
Акула пера
Акула пера
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Пол: Мужской
Откуда: Раменское, Мос.обл.
Контактная информация:

Re: Радиоактивные шары

Сообщение Dendr »

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

Ответить

Вернуться в «Задачки»