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

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

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

Сообщение Dendr » 31 янв 2017, 10:30

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

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

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

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

Сообщение Тоня » 31 янв 2017, 19:04

Пока, по-простому, получается 146 тестов. Можно меньше?
Тоня
Популярный автор
Популярный автор
 
Сообщения: 1543
Зарегистрирован: 29 июн 2005, 21:45

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

Сообщение Инна » 01 фев 2017, 01:37

Да, 146.
Не очень понятно, куда можно меньше.
Вы только что начали читать фразу, чтение которой Вы уже заканчиваете...
Аватара пользователя
Инна
Популярный автор
Популярный автор
 
Сообщения: 1432
Зарегистрирован: 18 июл 2006, 18:44
Откуда: Калифорния

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

Сообщение Dendr » 01 фев 2017, 06:34

Ну, во-первых, 145. Последний шар проверять необязательно, ведь состав определен однозначно.
А вторых, сократить есть куда. Начните со случая двух положительных тестов в первой серии.
Аватара пользователя
Dendr
Акула пера
Акула пера
 
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Откуда: Раменское, Мос.обл.

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

Сообщение Valentin » 01 фев 2017, 10:18

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

Ну здесь всё просто. только одна активная пара в первой серии однозначно свидетельствует, что в остальных 49-ти парах расклад смешанный, активный плюс неактивный.
Таким образом вставляем в датчик шар из активной пары и последовательно докидываем к нему по одному из оставшихся пар.
Зазвенело — значит пошёл в активные, а парный к нему без всякой проверки в неактивные. Ну а если не зазвенело значит соответственно наоборот.
Всего получается 99 замеров.
В случае если активных пар после первого замера будет больше одной всё несколько сложнее, т.к. среди оставшихся пар будут как смешанные, так и неактивные.
Чтобы понять что такое рекурсия, нужно сначала понять что такое рекурсия.
Аватара пользователя
Valentin
Акула пера
Акула пера
 
Сообщения: 6819
Зарегистрирован: 15 дек 2005, 10:51
Откуда: С. Пб

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

Сообщение Шшок » 01 фев 2017, 10:38

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


В худшем случае у меня не получается меньше 145.
В борьбе бобра с козлом побеждает бобро. Или козло.
Аватара пользователя
Шшок
Акула пера
Акула пера
 
Сообщения: 8499
Зарегистрирован: 28 ноя 2003, 14:05
Откуда: С большой дороги.

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

Сообщение Юляша » 01 фев 2017, 11:27

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

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

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

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

--- конец

Наверняка можно дополнительно сэкономить, зная, сколько каких шаров еще не идентифицировано, но процесс в этом случае трудно формализовать.
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
Юляша
Популярный автор
Популярный автор
 
Сообщения: 3115
Зарегистрирован: 15 янв 2009, 12:32

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

Сообщение Инна » 01 фев 2017, 15:18

Обычный шар требует не более двух испытаний - Юля, а почему? Если он был проверен с обычным и отправлен в пул, и так может много раз происходить.
Вы только что начали читать фразу, чтение которой Вы уже заканчиваете...
Аватара пользователя
Инна
Популярный автор
Популярный автор
 
Сообщения: 1432
Зарегистрирован: 18 июл 2006, 18:44
Откуда: Калифорния

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

Сообщение Юляша » 01 фев 2017, 15: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 положительными замерами на первом этапе.
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
Юляша
Популярный автор
Популярный автор
 
Сообщения: 3115
Зарегистрирован: 15 янв 2009, 12:32

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

Сообщение Dendr » 01 фев 2017, 19:17

В источнике (школьная олимпиада) ответ был 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 » 01 фев 2017, 19:26

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

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

Сообщение Юляша » 01 фев 2017, 19:56

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

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

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

Сообщение Инна » 01 фев 2017, 22:03

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

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

Сообщение Dendr » 01 фев 2017, 22:43

Не помню, скорее всего, эйлеровская от 2016 года. Я даты не отслеживаю, просто задачи интересные подмечаю и запоминаю.
Аватара пользователя
Dendr
Акула пера
Акула пера
 
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Откуда: Раменское, Мос.обл.


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

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1