Трамвайчик

    Главная : Новости : Связь
Новости киноляповНовости маразмовIMHO Добавить в Избранное Сделать стартовой Назад   

Автор Тема: Задачи на поиск радиоактивных шаров  (Прочитано 404 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн Dendr

  • Ветеран
  • *****
  • Сообщений: 2010
    • Просмотр профиля
Есть такая разновидность задач, похожих на задачи на взвешивание, но с небольшой спецификой.

Классическая задача на эту тему:
1. Имеется 15 внешне неотличимых шаров, среди которых два радиоактивных. У вас есть детектор радиоактивности, в который можно загрузить любое количество шаров, и он покажет, есть ли среди них радиоактивные.
Можете ли вы найти радиоактивные шары а 7 измерений?

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

А эта задача была, в облегченном виде, на одной из прошлогодних олимпиад. Я же жалеть никого не стану, а спрошу иначе.

2. Дано 100 шаров, из них 51 радиоактивный. Детектор, однако, слабенький: вмещает только два шара, да и срабатывает, если только оба они радиоактивны.
За сколько проверок гарантированно найдутся все радиоактивные шары?

3. Кому охота совсем голову сломать: обобщение обеих задач: есть N шаров, из них K радиоактивных. Вторая, кстати, обобщается проще, но при условии на K.

Оффлайн Dendr

  • Ветеран
  • *****
  • Сообщений: 2010
    • Просмотр профиля
Re: Задачи на поиск радиоактивных шаров
« Ответ #1 : 05 Декабрь 2017, 23:24:37 »
Вернулся вот перечитать тему, и понял, что сам не помню ответа. И главное, не помню, где я эти задачи встретил - теперь надо перерешивать заново, а, чтобы в следующий раз не терять, оставляю для истории.

Приходится импровизировать, поэтому ответ будет  сумбурным.
Задача о двух радиоактивных шарах среди 15.


Сначала следует упомянуть, что найти один шар среди N можно простой дихотомией. Все, кто взялся решать такой тип задач, уже должны знать, о чем идет речь, поэтому не буду останавливаться.
В частности, это означает, что за 4 пробы легко найти первый шар, а затем, еще за 4 (среди 14) и второй.
Два из пятнадцати означает 15*14/2=105 комбинаций. Так как результат бинарен, то за 6 попыток мы можем различить 64 вариантов - то есть 6 проб явно не хватит, а вот хватит ли 7?

Начнем издалека - ищем два из пяти. Это 10 комбинаций, и значит, теоретический минимум равен 4. Здесь просто: берем и проверяем подряд по одному шару. За 4 пробы мы либо найдем оба шара, либо только один - тогда пятый, нетронутый, и есть второй искомый.
Итак, 2 из 5 решается за 4 пробы. (также можно показать, что 6 решается таким же образом за 5, а за 4 никак не успеть)

Дальше - 2 из 7. Это 21 вариант, можно попытаться свести к пяти пробам.
Перебрав немного вариантов, можно легко убедиться, что взяв в пробу номер 1 два шара, при отрицательном результате приходим к предыдущему случаю. А при положительном поступим так: проверим (пробой №2) один из уже проверенных шаров. Если детектор скажет, что он чистый, мы сделаем вывод, что его "напарник" радиоактивен, и ищем второй активный среди оставшихся пяти шаров. Если же проба была положительной, мы просто присоединим "напарника" к тем пяти. В любом случае, нам надо обнаружить 1 шар из 5 или 6. Это, очевидно, еще 3 пробы.
Итого - 2 из 7 ищется за 5 измерений.
Можно показать (но я этого делать не буду), что из 8 не хватит 5 проб, но за 6 -легко.

Перейдем сразу к поиску 2 из 10.
Первая проба - три шара, при отрицательном результате придем к поиску 2 из 7 - за 5 ходов, итого 6 хватит.
При положительном - пробы №2 и №3 рассмотрят по одиночке два шара из тех трех. Либо мы находим оба, на чем и закончим, либо один шар, тогда второй радиоактивный может быть как последним в тройке, так и среди семи нетронутых, либо ни одного, что означает, что последний из тройки точно радиоактивен, а другой - среди семи.
В последних двух случаях мы ищем один шар из 7 или 8. На это уйдет три пробы.
Таким образом, 2 из 10 находятся за 6 проб.

Наконец, вишенка на торте: мы ищем 2 из 15.
Сразу берем 5 шаров: при отрицательном результате ищем 2 из 10 - плюс 6 ходов, итого 7.
При положительном начинается свистопляска. Обозначим проверенные шары буквой a, остальные - b. Имеем набор: aaaaa bbbbbbbbbb.
Возьмем для второй пробы один шар из "a" и четыре "b", обозначив их прописными буквами: Aaaaa BBBBbbbbbb
Если проба 2 положительна, проверим шар A (проба 3). Если он радиоактивен, мы просто ищем 1 из 14. Это еще 4 пробы, итого 7. Если же нет, то имеем один среди aaaa, один - среди BBBB. Оба шара ищутся за две пробы, и в итоге те же 7.

Если проба 2 отрицательна, мы ищем два шара в наборе aaaa bbbbbb, держа в уме, что среди "a" как минимум один радиоактивен.
Для пробы 3 берем один "a" и два "b", повторяя обозначения, Aaaa BBbbbb
Если проба 3 положительна, проверим пару BB. Если результат отрицательный, шар A радиоактивен автоматически, и мы ищем второй среди aaa bbbb - на это уйдет еще три пробы, итого 6. При положительном результате мы делаем вывод, что один шар в этой паре (4-я проба найдет его), другой шар - в наборе Aaaa, и две пробы покажут его. Итого снова 6.

Если проба 3 отрицательна, мы снова урезаем количество подопытных шаров: aaa bbbb.
Убедимся, что у нас есть запас. Либо искомая пара a+a (три варианта), либо a+b (12 вариантов) - 15 комбинаций, то есть возможность выбрать за 4 хода еще остается.
Для пробы 4 возьмем по одному шару каждого "типа": Aaa Bbbb.
Положительность пробы 4: проверим пробой №5 шары aa. Если результат отрицательный, шар A - радиоактивен, а другой шар - в группе Bbbb, еще два опыта найдут его, всего 7. Если положительный, то в этой паре один шар, а другой - в паре AB. По одной пробе на каждую пару - и мы закончили поиск за 7 попыток.

Отрицательность пробы 4 означает, что искомые шары в наборе aa bbb.
Теперь проверим два шара "b"(aa BBb) пробой №5.
Если она положительна, то один шар в паре aa, другой - в BB. Шестая и седьмая пробы находят каждый.
Если же пятая проба отрицательна, у нас останется набор из трех шаров, мы даже забываем про их маркировку, потому что проверив два из них пробами №№6 и 7, мы либо обнаружим оба искомых шара, либо найдем один, и другой автоматически кажется тем, который мы отложили.
Таким образом, вот так сумбурно, но доказано, что 2 из 15 вычисляются за 7 проб.

P.S. Помнится, "авторское" решение подразумевало нумерацию шаров с последующим выкладыванием их в детектор в разных комбинациях - причем без оглядки на предыдущие измерения. Но подобрать комбинации заново у меня не получилось. (вероятно, так оно нагляднее было бы, но решение есть решение)

Оффлайн Dendr

  • Ветеран
  • *****
  • Сообщений: 2010
    • Просмотр профиля
Re: Задачи на поиск радиоактивных шаров
« Ответ #2 : 07 Декабрь 2017, 17:05:59 »
Вот писал эту простыню полвечера (а сочинял еще дольше), а потом в метро торкнуло на простейшее решение - его и приведу. Опять же для истории.

Получается разговор сам с собой, но уж что получается...

1. Пронумеруем шары, и в первые три измерения возьмем:
1-2-3-4-5
1-6-7-8-9
1-10-11-12-13

Если все три пробы были положительные, то шар 1 точно радиоактивен и нам надо найти второй среди 14. Это легко сделать за 4 попытки дихотомией. Всего будет 7.
Если ни одна - то радиоактивны шары 14 и 15, и поиск закончен.
Если ровно две (без ограничения общностей положим, что первая и вторая), то ясно, что шар 1 - чистый, иначе бы и третья была положительной. Тогда один шар в четверке 2-3-4-5, второй - 6-7-8-9. Каждый ищется за две пробы, всего будет те же 7.

Если только одна (пусть первая), то имеем две возможности: оба шара в наборе 2-3-4-5, либо в этом наборе один шар, а второй - либо 14, либо 15.
Четвертое измерение: шары 14 и 15. Если проба положительна, пятой вычисляем "грязный" шар, а еще двумя - ищем один шар из четверки 2-3-4-5. Если отрицательна, то оба шара с этой четверке, проверив последовательно шары 2, 3 и 4 мы либо найдем их оба, либо только один, а следовательно, шар 5 должен быть радиоактивным. И опять семи замеров хватает.

2. На самом деле легко, хотя и кажется сложным.
Очевидно, что нам надо исследовать пары, пока не достигнем срабатывания, которое означает, что мы нашли два "грязных" шара, и можем использовать один, как тестовый. Также очевидно, что надо на первом этапе брать новые пары. Сразу будем наклеивать на них ярлычки с номерами (1А и 1Б, 2А и 2Б и т.д.)
Крайний случай: мы проверили 49 пар, и датчик ни разу не сработал. Это значит, что в каждой из этих пар по одному чистому шару, а другой - радиоактивен. Два непроверенных шара тоже радиоактивны, незачем тратить лишний ход. Следующими 49 измерениями мы, используя один из них, разложим шары в парах: зная статус шара 1А, мы автоматически знаем и 1Б. На все-про-все уйдет 98 замеров.

Другой крайний случай: мы сразу нашли два "грязных" шара. Можно, конечно, просто перебрать все, кроме одного, и узнать их - за 98 ходов - но лучше универсализировать. Назовем пулом все шары, которые еще не разделены. Чем меньше шаров в пуле, тем ближе финиш.

Берем новую пару. Допустим, она сработала - значит, оба "грязные". Положим их в ящик с надписью "грязные". За один ход из пула мы убрали два шара - неплохой результат!
Допустим, что не сработала. Либо они оба чистые, либо только один. Берем один из этой пары и измерим совместно с определенно "грязным". Если это проба положительна, значит, нам попалась пара разных шаров, и мы даже знаем, какие они. "Грязный" кладем все в тот же ящик, а чистый - в ящик "чистые". За два хода из пула вышло два шара, или 1 за ход. Но если эта вторая проба отрицательна, то мы наверняка только знаем, что этот шар чист (кладем в ящик), а второй... нетривиально поступим - вернем его в пул (!). За два хода из пула вышел один шар, то есть 0,5 за ход. Медленно, да. Если бы мы измерили и этот шар, было бы 2/3, но мы не сможем тут ускориться. Ведь дальше мы берем новую пару и замыкаем цикл. Лучше, как выясняется, безжалостно возвращать.

Пусть дело у нас продвигается максимально медленно: мы находим только чистые шары. Но когда мы найдем 48 из них (за 96 ходов), в пуле останется один. А это значит, что отрицательная проба новой пары позволяет нам гарантированно выяснить, что мы взяли пару разных и никак иначе, следующим ходом различить их, а все оставшиеся в пуле автоматически "грязные".

Дело продвигается максимально медленно, так? Получается, мы проделали 97 измерений и имеем в пуле 49 "грязных" и 1 чистый. Еще 23 хода тратим на выявление пар "грязных".
Спустя 120 ходов в пуле останется набор ГГГЧ.
121-й ход: либо ГГ (+), либо ГЧ (-). Так мы нашли пару "грязных" (она либо в датчике, либо еще у пуле), положим ее в ящик к собратьям. Остается набор ГЧ
122-м ходом мы выявим статус произвольного из пары, второй автоматически известен.
Итого 122 хода.
Это был крайний вариант, хотя и нетривиально решенный (и не так быстро, как было бы можно)

А промежуточные? Нам на помощь придут те самые ярлычки.
Вот нашли мы два радиоактивных шара на 15-м ходу. Сделаем сначала вид, что мы забыли про 14 предыдущих. Дальше нам надо выбрать пару, измерить ее и далее по алгоритму выше. Но мы только что наизмеряли 14 пар! От перестановки ничего не поменялось - мы можем считать, что сначала выбрали эти два радиоактивных шара, а потом нам 14 раз подряд попались пары с отрицательной пробой. То есть снова решение за 122 хода. Это и есть ответ.

3. Обобщение второй задачи при условии, что радиоактивных шаров больше, чем чистых, совсем несложное. Пусть K радиоактивных и M чистых (K>M).
Тогда та же схема требует 1+2*(M-1)+[(K-4)/2]+2=2M+[K/2]-1 (квадратные скобки - округление до целого в меньшую сторону - сработает при любой четности) ходов максимум. В целом, ответ никогда не превышает 5N/4.
Если K<=M, процесс может затянуться, пока мы ищем "грязную" пару. При K=M, как можно убедиться, всего три дополнительных хода, но при дальнейшей увеличении разницы все сложнее и сложнее.

Оффлайн Почта сайта

  • Moderator
  • Ветеран
  • *****
  • Сообщений: 16583
    • Просмотр профиля
Re: Задачи на поиск радиоактивных шаров
« Ответ #3 : 07 Декабрь 2017, 17:40:11 »
Ну, это что-то уже из разряда олимпиады по математике. Ты про козу и капусту давай :)
Тыгыдымс-тыгыдымс

 

Страница сгенерирована за 0.158 секунд. Запросов: 21.

Назад Наверх
 
Rambler's Top100 © 2017 Генрих Лиговский