Радиоактивные шары
Модераторы: Азарапетыч, Администрация
- Dendr
- Акула пера
- Сообщения: 5717
- Зарегистрирован: 06 май 2005, 15:11
- Пол: Мужской
- Откуда: Раменское, Мос.обл.
- Контактная информация:
Радиоактивные шары
Имеется 100 неотличимых по виду шаров, про которые известно, что среди них ровно 51 радиоактивный.
У вас есть детектор радиоактивности, в который умещается не более двух шаров. Однако его чувствительность невысока, поэтому он срабатывает только если оба шара активны.
За какое количество тестов вы можете гарантированно найти все радиоактивные шары?
У вас есть детектор радиоактивности, в который умещается не более двух шаров. Однако его чувствительность невысока, поэтому он срабатывает только если оба шара активны.
За какое количество тестов вы можете гарантированно найти все радиоактивные шары?
Re: Радиоактивные шары
Пока, по-простому, получается 146 тестов. Можно меньше?
- Инна
- Популярный автор
- Сообщения: 1434
- Зарегистрирован: 18 июл 2006, 18:44
- Пол: Женский
- Откуда: Калифорния
Re: Радиоактивные шары
Да, 146.
Не очень понятно, куда можно меньше.
Не очень понятно, куда можно меньше.
Вы только что начали читать фразу, чтение которой Вы уже заканчиваете...
- Dendr
- Акула пера
- Сообщения: 5717
- Зарегистрирован: 06 май 2005, 15:11
- Пол: Мужской
- Откуда: Раменское, Мос.обл.
- Контактная информация:
Re: Радиоактивные шары
Ну, во-первых, 145. Последний шар проверять необязательно, ведь состав определен однозначно.
А вторых, сократить есть куда. Начните со случая двух положительных тестов в первой серии.
А вторых, сократить есть куда. Начните со случая двух положительных тестов в первой серии.
Re: Радиоактивные шары
Ну здесь всё просто. только одна активная пара в первой серии однозначно свидетельствует, что в остальных 49-ти парах расклад смешанный, активный плюс неактивный.Dendr писал(а):Начните со случая двух положительных тестов в первой серии.
Таким образом вставляем в датчик шар из активной пары и последовательно докидываем к нему по одному из оставшихся пар.
Зазвенело — значит пошёл в активные, а парный к нему без всякой проверки в неактивные. Ну а если не зазвенело значит соответственно наоборот.
Всего получается 99 замеров.
В случае если активных пар после первого замера будет больше одной всё несколько сложнее, т.к. среди оставшихся пар будут как смешанные, так и неактивные.
Чтобы понять что такое рекурсия, нужно сначала понять что такое рекурсия.
- Шшок
- Акула пера
- Сообщения: 9094
- Зарегистрирован: 28 ноя 2003, 14:05
- Пол: Мужской
- Откуда: С большой дороги.
Re: Радиоактивные шары
В худшем случае у меня не получается меньше 145.Dendr писал(а):Ну, во-первых, 145. Последний шар проверять необязательно, ведь состав определен однозначно.
А вторых, сократить есть куда. Начните со случая двух положительных тестов в первой серии.
В борьбе бобра с козлом побеждает бобро. Или козло.
Re: Радиоактивные шары
Есть гарантированный алгоритм на не более чем 125 испытаний.
--- скрыто
Шары образуют пул.
Берем пару шаров из пула и испытываем. Если результат отрицательный - откладываем пару в сторону. Продолжаем до первого положительного результата (он нам гарантирован, так как R-шаров больше половины).
После положительного результата проверяем один из шаров из каждой отложенной пары вместе с известным R-шаром. Отрицательный результат - откладываем шар как обычный, второй возвращаем в пул. Положительный - оба шара из пары идентифицированы.
После того как все шары возвращены в пул - повторяем процедуру.
Обычный шар требует не более двух испытаний - 50*2=100.
R-шары определяются либо по ходу дела, либо парами за одно испытание. 50/2=25.
Последний шар отдельно идентифицировать не надо.
--- конец
Наверняка можно дополнительно сэкономить, зная, сколько каких шаров еще не идентифицировано, но процесс в этом случае трудно формализовать.
--- скрыто
Шары образуют пул.
Берем пару шаров из пула и испытываем. Если результат отрицательный - откладываем пару в сторону. Продолжаем до первого положительного результата (он нам гарантирован, так как R-шаров больше половины).
После положительного результата проверяем один из шаров из каждой отложенной пары вместе с известным R-шаром. Отрицательный результат - откладываем шар как обычный, второй возвращаем в пул. Положительный - оба шара из пары идентифицированы.
После того как все шары возвращены в пул - повторяем процедуру.
Обычный шар требует не более двух испытаний - 50*2=100.
R-шары определяются либо по ходу дела, либо парами за одно испытание. 50/2=25.
Последний шар отдельно идентифицировать не надо.
--- конец
Наверняка можно дополнительно сэкономить, зная, сколько каких шаров еще не идентифицировано, но процесс в этом случае трудно формализовать.
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
- Инна
- Популярный автор
- Сообщения: 1434
- Зарегистрирован: 18 июл 2006, 18:44
- Пол: Женский
- Откуда: Калифорния
Re: Радиоактивные шары
Обычный шар требует не более двух испытаний - Юля, а почему? Если он был проверен с обычным и отправлен в пул, и так может много раз происходить.
Вы только что начали читать фразу, чтение которой Вы уже заканчиваете...
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: Радиоактивные шары
В источнике (школьная олимпиада) ответ был 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 шара). Трех тестов хватит.
Для прочих случаев убеждаемся, что все тоже получается...
У меня вышло 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: Радиоактивные шары
Вообще, если мы пронумеруем шары, то число комбинаций равно C(100,51)~=2^100/sqrt(50pi)<2^97, то есть теоретически должно получиться за 97 тестов.
Но почему-то не выходит даже при везении: 49 отрицательных в первой серии подряд, затем проверка одного из каждой пары с помощью двух нетронутых (они точно активны). Видимо, дело в том, что дихотомия неравномерная.
Но почему-то не выходит даже при везении: 49 отрицательных в первой серии подряд, затем проверка одного из каждой пары с помощью двух нетронутых (они точно активны). Видимо, дело в том, что дихотомия неравномерная.
Re: Радиоактивные шары
А как получить 122 при двух положительных результатах?
--- отбой вопросу, моя ошибка при подсчете
--- отбой вопросу, моя ошибка при подсчете
Последний раз редактировалось Юляша 01 фев 2017, 22:09, всего редактировалось 1 раз.
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
- Инна
- Популярный автор
- Сообщения: 1434
- Зарегистрирован: 18 июл 2006, 18:44
- Пол: Женский
- Откуда: Калифорния
Re: Радиоактивные шары
Дендр, а что за олимпиада и когда, если не секрет.
Вы только что начали читать фразу, чтение которой Вы уже заканчиваете...
- Dendr
- Акула пера
- Сообщения: 5717
- Зарегистрирован: 06 май 2005, 15:11
- Пол: Мужской
- Откуда: Раменское, Мос.обл.
- Контактная информация:
Re: Радиоактивные шары
Не помню, скорее всего, эйлеровская от 2016 года. Я даты не отслеживаю, просто задачи интересные подмечаю и запоминаю.