Помогите наити радиоактивные мячи- все 15, 2 плохие, 7 опита

[LyuboHr]

Помогите наити радиоактивные мячи:
У вас есть все15 мячи, среди которых есть 2 радиоактивные (плохие), Имеете тоже апарат в котором можна поставит и попробават для радиоактивности любои набор мячи. Он дает ответ ДА/НЕТ имеет или нет радиоактивности для набор в целом. Имеете толко 7 опита, что бы наити плохие ??

[Capella]

Все шарики надо разбивать на половину их количества. В данном случае я приведу Вам один из возможных раскладов (самый тяжёлый), а остальные Вы сделаете сами.
1) Выбираем 8 шариков, измеряем радиактивность и получаем, что есть радиация (Если её нет, то переходим к друим 7)
2) из этих восьми выбираем 4, если есть радиация то делим ЭТИ 4 на 2, если нет переходим к другим 4 шарикам из группы "8"
Здесь может быть прикольно! Определяет ли машина точноеколичество шариков в группе испытаний? Если нет, то лучше сначала
3) перейти к группе с 7 шариками, которую мы оставили после первого дележа. проверяя всю груупу на радиоактивность, мы сразу сможем вычислить оба радиоактивных шарика, если ответ будет "нет". Но допустим мы и там получили "да" (наличие радиации у одного из шариков)
4) Пробуем два шарика после шага 2). Если один нам дан ответ "да", то не стоит даже проверять второй шарик, т.к. второй радиоактивный шарик находиться точно в группе "7". (Терперь понятно, почему мы сначала измерили группы "7" на радиоактивность - мы сэкономили этим важный шаг по проверке группу из одного шарика!!)
5) Делаем замер из подгруупы в 4 шарика из группы "7", если "нет", переходим к группу из 3 шариков, а если да..
6).. то делаем замер из подгруппы 2 и если снова "да", то
7) Делаем последний замер одного шарика из подгруппы опыта 6) и если "нет", то второй радиоактивный шарик тот, который остался незамеренным.
Уфффф, в 7 шагов уложились вроде

[Capella]

Сорри, как раз не заметила, что набор в целом

[General]

Если в первых 8 шариках будет радиация, то мы будем иметь $C \limits_{8}^{2}+8*7=84$ вариантов, что больше, чем $2^6$ (мы ведь одно измерение потратили.)

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

Как, говорить решение?

Кстати, интересна также задача поиска 2 радиоактивных из 21 за 8 попыток.

[V.V.]

Задача разобрана на problems.ru

[General]

Там по слову "радиоактивный" вот что нашёл:

1) Из 11 шаров 2 радиоактивны. Про любой набор шаров за одну проверку можно узнать, имеется ли в нем хотя бы один радиоактивный шар (но нельзя узнать, сколько их). Можно ли за 7 проверок найти оба радиоактивных шара?

Но за 7 можно найти и из 15-ти

2) Из 19 шаров 2 радиоактивны. Про любую кучку шаров за одну проверку можно узнать, имеется ли в ней хотя бы один радиоактивный шар (но нельзя узнать, сколько их). Доказать, что за 8 проверок всегда можно выделить оба радиоактивных шара.

Но за 8 можно найти и из 21

[General]

Кстати, интересно, что на problems.ru при решении второй задачи строится таблица, в которой утверждается, что из 22 шаров можно найти 2 радиоактивных за 8 измерений, хотя на самом деле это не так, здесь менее, чем девятью замерами не обойтись.

[maxal]

General писал(а):

Кстати, интересно, что на problems.ru при решении второй задачи строится таблица, в которой утверждается, что из 22 шаров можно найти 2 радиоактивных за 8 измерений, хотя на самом деле это не так, здесь менее, чем девятью замерами не обойтись.

У вас есть контрпример к представленному там решению?

// переношу тему в Олимпиадные задачи

[General]

Maxal, спасибо, вы раскрыли мне глаза! Начал писать большой пост о том, почему нельзя найти 2 шара из 22 за 8 измерений, как оказалось, что осталась незамеченной ещё одна лазейка, позволяющая это осуществить.

Выложу уже тогда решение. Если для первого измерения брать 6 или меньше шаров, то в случае отрицательного ответа мы получим задачу нахождения за 7 попыток двух радиоактивных шаров как минимум из 16 шаров, которая решения не имеет.

Если для первого измерения взять 8 шаров, то в случае положительного ответа у нас останется $C\limits_8^2=28$ (если оба шара среди измеренных) $+8*14=112$ (если один шар среди измеренных, а второй – сред неизмеренных). Всего будет 140 вариантов, $140>2^7$, значит, за оставшиеся 7 измерений мы не управимся.

Значит, первым измерением нужно брать только 7 шаров. Ели прибор не запищит, то получается задача 2 из 15 за 7 измерений, которая решается. Рассмотри вариант, когда прибор запищал.
Перенумеруем шары от 1 до 22. и составим следующую таблицу:


В ней каждая ячейка обозначает одну из возможных пар радиоактивных шаров. Всего 126 ячеек, что меньше $2^7$. Выбрав для измерения определённые шары, мы разбиваем ячейки таблицы на 2 группы: в одну группу идёт строки и столбцы, содержащие номера выбранных шатров, а в другую – все остальные. Чтобы управиться за 7 измерений, следующее должно разбивать ячейки на 62+64 или на 63+63. Возможно всего 3 варианта для второго измерения:
9 шаров из неизмеренной группы

7 шаров неизмеренных и 1 измеренный

1 неизмеренный шар и 3 измеренных


Отрицательный ответ в первом и втором вариантах не позволяет в дальнейшем делить группы ровно надвое. А вот третий вариант достаточно перспективен. Далее можно просто построить дерево решений.

Будем записывать так:
(Исходы предыдущих измерений) Номера измеряемых шаров, + (количество вариантов при положительном ответе), - (количество вариантов при отрицательном ответе)

Измерение 1.
1,2,3,4,5,6,7 -(105), +(126)
Измерение 2.
(1-) Получаем задачу 2 из 15 за 7 измерений, которая решается.
(1+) 1,2,3,22 –(62), +(64)
Для лучшей читаемости сначала разберём все варианты, где измерение 2 дало -:
Измерение 3.
(1+2-) 14,15,16,17,18,19,20,21 –(14), +(16)
(1+2+) 1,7,8,9,10,11 –(30), +(32)
Измерение 4.
(1+2-3-) 10,11,12,13 –(14), +(16)
(1+2-3+) Имеем 1 шар среди 8, другой среди 4, за оставшиеся 5 измерений решается дихотомией
Измерение 5.
(1+2-3-4-) 8,9 –(6), +(8)
(1+2-3-4+) Дихотомия: 1 из 4 и ещё 1 из 4
Измерение 6.
(1+2-3-4-5-) 4 –(3), +(3)
(1+2-3-4-5+) Дихотомия, 1 из 2, 1 из 4
Измерение 7.
(1+2-3-4-5-6-) 7 –(1) +(2)
(1+2-3-4-5-6+) 1 шар найден, на подозрении №№5,6,7, за 2 измерения находится
Измерение 8.
(1+2-3-4-5-6-7-) И мерить ничего не надо, это пара 5,6
(1+2-3-4-5-6-7+) 1 шар найден, другой – это или 5, или 6, одним измерением находим.

А теперь, когда Измерение 2 дало + (тут нужно быть особенно аккуратными, т.к. каждый раз нужно делить точно поровну)
Измерение 3.
(1+2+) 1,7,8,9,10,11 -(32), +(32)
Измерение 4.
(1+2+3-) 2,12 –(16), +(16)
(1+2+3+) 7,8,9,10,11 –(16), +(16)
Измерение 5.
(1+2+3-4-) 18,19,20,21,22 –(16), +(16)
(1+2+3-4+) 15,16,17,18,19,20,21,22 –(16), +(16)
(1+2+3+4-) 1 шар найден, ещё 16 на подозрении, 4 измерений хватит
(1+2+3+4+) 1,7 –(16), +(16)
Измерение 6.
(1+2+3-4-5-) 1 шар найден, это №3, ещё 8 на подозрении, за 3 измерения справимся
(1+2+3-4-5+) 22 –(4), +(4)
(1+2+3-4+5-) 3,4,5,6 –(4), +(4)
(1+2+3-4+5+) 1 шар найден, 1 из 8 найдём за 3 измерения
(1+2+3+4+5-) 1 шар найден, 1 из 8 найдём за 3 измерения
(1+2+3+4+5+) 7- (4),+(4)
Измерение 7.
(1+2+3-4-5+6-) Найден 1 шар, это №3, нужно ещё найти 1 из 4 за 2 измерения
(1+2+3-4-5+6+) Найден 1 шар, это №22, нужно ещё найти 1 из 4 за 2 измерения
(1+2+3-4+5+6-) 12 -(2), +(2)
(1+2+3-4+5+6+) 1 шар найден, 1 из 4 найдём за 2 измерения
(1+2+3+4+5+6-) 1 шар найден, 1 из 4 найдём за 2 измерения
(1+2+3+4+5+6+) 1 шар найден, 1 из 4 найдём за 2 измерения
Измерение 8.
(1+2+3-4+5+6-7-) 1 шар найден, 1 из 2 найдём за 1 измерение
(1+2+3-4+5+6-7+) 1 шар найден, 1 из 2 найдём за 1 измерение

Теперь буду думать над вашей задачей с весами

[Makaron11]

Мне кажется, что всё немного проще. Можно использовать прибор 5 раз. 15 шаров делим на три кучи по 5 и используя прибор максимум три раза, одну пятёрку отбрасываем. Затем одну группу из 5 шаров помещаем в прибор и просто вынимаем из него по одному шару пока прибор не перестанет показывать радиацию,таким образом находим радиоактивный шар, тоже и с другой группой шаров, всего 5 раз.

[VAL]

Makaron11 в сообщении #261197 писал(а):

Мне кажется, что всё немного проще. Можно использовать прибор 5 раз. 15 шаров делим на три кучи по 5 и используя прибор максимум три раза, одну пятёрку отбрасываем. Затем одну группу из 5 шаров помещаем в прибор и просто вынимаем из него по одному шару пока прибор не перестанет показывать радиацию,таким образом находим радиоактивный шар, тоже и с другой группой шаров, всего 5 раз.

Итого три использования вначале и по четыре для каждой пятерки (если их оказалось две): 3+4+4... как-то больше пяти получается.

-- 13 ноя 2009, 00:09 --

Вот, раскопал у себя в архивах:

C(15,2) = 105  <  128 = 2^7

Будем выбиpать гpуппы шаpиков для испытания, чтобы деpжаться как можно ближе к
половинному делению.
Hе знаю только, как пpедставить тут все деpево пеpебоpа, гpомоздковато
получается.
Ввведем обозначения:
4е  - гpуппа из четыpех шаpиков, сpеди котоpых есть pадиоактивный;
5мб - гpуппа из пяти шаpиков, сpеди котоpых может быть pадиоактивный;
+(-)   - в испытуемой гpуппе есть(отсутствует) pадиоактивный шаpик;


1)                                     4
                                     /   \
                                   +       -
                                 /           \
                            4е+11мб           11е
                                │               \
2)                            7мб                8
                             /   \               │ \
                            +     -              +  -
                          /       │              │    \
                      7е+4е     4е+4мб         3е+8мб   8е
                     /             │               │       \
3)                 4(из 7)        3мб              5мб       2
                  /    \           /  \           /  │       │  \
                 +      -        +     -         +   -       +    -
                 │      │        │     │        /    │       │      \
              4e+4e   4е+3е    4е+3е  4е+мб  3е+5е  3е+3мб  2е+6мб  6е
                 │      │        │      │      │      │        │     │
число ваpиантов: 16    12       12     10     15     12       13    15

Дальше деpево получается слишком шиpоким. Однако, в каждом из случаев число
ваpиантов меньше 16-и и легко выявить нужные шаpики за 4 пpовеpки.

Рассмотpим, напpимеp, случай 3е+5е (он наиболее тонкий).
                                │
4)                       1(из 3)+1(из 5)
                              /      \
                             -         +
                           /            \
                         4е+2е        (1+1)е+2мб+4мб
                         /                 \
5)                   здесь пpосто        1(тот из 1+1, где 4мб)
                                        /     \
                                      -         +
                                    /             \
                                1е+4е              1мб+2мб
                                  │                 │
                           здесь пpосто        здесь тоже пpосто