2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Помогите наити радиоактивные мячи- все 15, 2 плохие, 7 опита
Сообщение27.11.2005, 14:32 


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

 Профиль  
                  
 
 
Сообщение27.11.2005, 16:12 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение27.11.2005, 16:15 
Заслуженный участник
Аватара пользователя


09/10/05
1142
Сорри, как раз не заметила, что набор в целом

 Профиль  
                  
 
 
Сообщение01.06.2008, 23:26 
Аватара пользователя


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

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

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

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

 Профиль  
                  
 
 
Сообщение01.06.2008, 23:34 
Заслуженный участник


09/01/06
800
Задача разобрана на problems.ru

 Профиль  
                  
 
 
Сообщение01.06.2008, 23:42 
Аватара пользователя


17/05/08
358
Анк-Морпорк
Там по слову "радиоактивный" вот что нашёл:

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

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

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

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

 Профиль  
                  
 
 
Сообщение02.06.2008, 17:32 
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение06.06.2008, 08:27 
Модератор
Аватара пользователя


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

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

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

 Профиль  
                  
 
 
Сообщение06.06.2008, 18:09 
Аватара пользователя


17/05/08
358
Анк-Морпорк
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 измерение

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

 Профиль  
                  
 
 Re: Помогите наити радиоактивные мячи- все 15, 2 плохие, 7 опита
Сообщение12.11.2009, 14:22 


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

 Профиль  
                  
 
 Re: Помогите наити радиоактивные мячи- все 15, 2 плохие, 7 опита
Сообщение12.11.2009, 22:05 
Заслуженный участник


27/06/08
4058
Волгоград
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осто

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 11 ] 

Модераторы: Модераторы Математики, Супермодераторы



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

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


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group