2014 dxdy logo

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

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




На страницу 1, 2, 3  След.
 
 Задача на сообразительность.
Сообщение12.07.2015, 17:32 
Имеется 7 с виду одинаковых шаров, из которых два радиоактивные. Дозиметром можно проверить на радиоактивность любую
группу шаров. За какое наименьшее число проверок можно выявить оба радиоактивных шара?

1 - радиоактивен, 0 -- не радиоактивен.

Сразу ясно, что осмысленных попыток -- не более 7. Семь можно получить, просто все шары проверив на радиоактивность. Давайте попробуем уменьшить число 7.

1. Если возьмем группу из 2 шаров. Будем проверять ее на радиоактивность.
а) Если дозиметр покажет, что эта группа радиоактивна, то радиоактивен один или два шара.

Проверяем оба шара по отдельности.

1.1. Если первый радиоактивен, то нужно будет проверить второй. Если оба радиоактивны, значит нам потребовалось три проверки всего.
1.1. Если первый радиоактивен, то нужно будет проверить второй. Если второй не радиоактивен, значит нам потребовалось три проверки. Значит один радиоактивный среди пяти оставшихся.
Возьмем группу еще из двух шаров из пяти оставшихся
1.1.2. Эта группа не радиоактивна еще одна проверка. Тогда радиоактивен один из трех оставшихся. Если мы возьмем два из них.
1.1.2.1 Если эта группа из двух не радиоактивна, то радиоактивен третий. Мы уже определили все радиоактивные.
1.2. Если первый не радиоактивен, то нам второй проверять не нужно. Пока что две проверки и мы выявили один радиоактивный...

Что-то это как-то слишком сложно получается, кажется, что есть способ проще. Можете подсказать -- возможно ли упростить описание, если да, то как?

 
 
 
 Re: Задача на сообразительность.
Сообщение12.07.2015, 17:37 
Аватара пользователя
Достаточно проверит 5 шаров из 7 так как число радиошаров задано.

 
 
 
 Re: Задача на сообразительность.
Сообщение12.07.2015, 17:43 
levtsn в сообщении #1036234 писал(а):
Достаточно проверит 5 шаров из 7 так как число радиошаров задано.

Спасибо! Ну хорошо, согласен, 5 проверок хватит (что-то я затупил). Но как доказать, что число 5 нельзя уменьшить?

 
 
 
 Re: Задача на сообразительность.
Сообщение12.07.2015, 17:45 
Аватара пользователя
Всего возможно 21 исход. Это более 4 бит информации. Следовательно 4 проверками узнать исход невозможно.

 
 
 
 Re: Задача на сообразительность.
Сообщение12.07.2015, 17:55 
levtsn в сообщении #1036238 писал(а):
Всего возможно 21 исход. Это более 4 бит информации. Следовательно 4 проверками узнать исход невозможно.

А почему всего 21 исход? У меня пока что 23 исхода. А почему, если 21 исход, то за 4 проверки не узнать, как это доказать?
1100000 (1)
0110000 (2)
0011000 (3)
0001100 (4)
0000110 (5)
0000011 (6)
1000001 (7)
1000010 (8)
1000100 (9)
1001000 (10)
1001000 (11)
1010000 (12)
0100001 (13)
0100010 (14)
0100100 (15)
0101000 (16)
0100001 (17)
0010001 (18)
0010010 (19)
0010100 (20)
0001001 (21)
0001010 (22)
0000101 (23)

-- 12.07.2015, 18:19 --

Заметил два дубля
levtsn в сообщении #1036238 писал(а):
Всего возможно 21 исход. Это более 4 бит информации. Следовательно 4 проверками узнать исход невозможно.

А почему всего 21 исход? У меня пока что 23 исхода. А почему, если 21 исход, то за 4 проверки не узнать, как это доказать?
1100000 (1)
0110000 (2)
0011000 (3)
0001100 (4)
0000110 (5)
0000011 (6)
1000001 (7)
1000010 (8)
1000100 (9)
1001000 (10)
1001000 (11)
1010000 (12)
0100001 (13)
0100010 (14)
0100100 (15)
0101000 (16)
0010001 (17)
0010010 (18)
0010100 (19)
0001001 (20)
0001010 (21)
0000101 (22)

 
 
 
 Re: Задача на сообразительность.
Сообщение12.07.2015, 18:39 
levtsn в сообщении #1036234 писал(а):
Достаточно проверит 5 шаров из 7 так как число радиошаров задано.
Проверили 5, один раз детектор щелкнул. Ну и чего дальше?

 
 
 
 Re: Задача на сообразительность.
Сообщение12.07.2015, 19:52 
Аватара пользователя
Nemiroff в сообщении #1036259 писал(а):
Проверили 5, один раз детектор щелкнул. Ну и чего дальше?

А не так: заметим основополагающее равенство 7=4+3.

Если мы знаем, что из 4х шаров 2 фонят, сколько испытаний надо, чтобы найти их?
Если мы знаем что из 4х шаров 1 фонит, сколько испытаний надо, чтобы найти его?

 
 
 
 Re: Задача на сообразительность.
Сообщение12.07.2015, 19:56 
Red_Herring в сообщении #1036294 писал(а):
А не так: заметим основополагающее равенство 7=4+3.

А я знаю, что 5 хватит. Но подход у levtsn ошибочный. Потому что по такой логике для распознавания 2 из 6 должно хватать четырёх проверок. А не хватит.

 
 
 
 Re: Задача на сообразительность.
Сообщение12.07.2015, 20:04 
Аватара пользователя
Nemiroff
Ваше замечание совершенно справедливо о том, что его подход (через теорию информации) дает только оценку снизу. И что тупо перебирать по шарику не работает.

 
 
 
 Re: Задача на сообразительность.
Сообщение12.07.2015, 20:22 
Red_Herring в сообщении #1036294 писал(а):
Nemiroff в сообщении #1036259 писал(а):
Проверили 5, один раз детектор щелкнул. Ну и чего дальше?

А не так: заметим основополагающее равенство 7=4+3.

Если мы знаем, что из 4х шаров 2 фонят, сколько испытаний надо, чтобы найти их?
Если мы знаем что из 4х шаров 1 фонит, сколько испытаний надо, чтобы найти его?


(а)Если мы знаем, что из 4х шаров 2 фонят, нужно 3 испытания.
(б)Если мы знаем, что из 4х шаров 1 фонит, нужно 3 испытания.
Если мы знаем, что из 4х шаров 0 фонит, нужно 1 испытание.
Потому, мы можем просто взять четверку. Сразу проверить ее. Если фонит, то проводим дальнейшие испытания с этой четверкой.
Сначала берем два шара из четырех:
1. если не фонят, то остальные два проверяем по-отдельности (всего тогда будет 4 испытания)
2. если фонят, то проверяем каждый по отдельности. Если в итоге фонит только 1, то мы провели 4 испытания. А у нас остался еще один шар, который мы не сможем из трех одним испытанием выявить.

Можно пойти по-другому.
Взять просто группу из четырех и группу из трех. Каждую из этих групп сразу проверяем прибором.
1.Если фонит только группа из четырех, то то там еще за 3 испытания найдем нужные шары (всего 5 испытаний).
2.Если фонит только группа из трех, то за два испытания определим их (всего 4 испытания).
3.Если фонит и та, и та группа. То по одному фонящему шару в каждой.
В четверке можно фонящий шар за три испытания найти. Во тройке за два. Итого 7 испытаний. Что-то много.

 
 
 
 Re: Задача на сообразительность.
Сообщение12.07.2015, 20:33 
ole-ole-ole в сообщении #1036308 писал(а):
Если мы знаем, что из 4х шаров 2 фонят, нужно 3 испытания.
:-)
ole-ole-ole в сообщении #1036308 писал(а):
Если мы знаем, что из 4х шаров 1 фонит, нужно 3 испытания.
:-(
ole-ole-ole в сообщении #1036308 писал(а):
Если мы знаем, что из 4х шаров 0 фонит, нужно 1 испытание.
:shock:

-- Вс июл 12, 2015 20:33:50 --

ole-ole-ole в сообщении #1036308 писал(а):
В четверке можно фонящий шар за три испытания найти.

Ну за два. За ДВА. 2. За одно, а потом ещё одно.

 
 
 
 Re: Задача на сообразительность.
Сообщение12.07.2015, 20:35 
Nemiroff в сообщении #1036312 писал(а):
ole-ole-ole в сообщении #1036308 писал(а):
Если мы знаем, что из 4х шаров 0 фонит, нужно 1 испытание.
:shock:

Ну ведь можно поставить 4 шара рядом и прибор покажет, если будет фон. Или имеется ввиду, что нужно каждый по отдельности проверять?

-- 12.07.2015, 20:37 --

ole-ole-ole в сообщении #1036308 писал(а):
В четверке можно фонящий шар за три испытания найти.

Ну за два. За ДВА. 2. За одно, а потом ещё одно.[/quote]
Да вы правы, понял. Нужно просто взять два шара. А не по одному

 
 
 
 Re: Задача на сообразительность.
Сообщение12.07.2015, 20:37 
Если из четырёх шаров нет ни одного, зачем вам вообще шевелиться? Все уже известно. Лежишь и в потолок плюешь — красота же.

 
 
 
 Re: Задача на сообразительность.
Сообщение12.07.2015, 20:56 
Аватара пользователя
Я бы для уровня ТС за основополагающее равенство предлагал $7=2+2+2+1$. Проверять 3 пары, потом действовать по обстоятельствам. Тогда бы количество различных вариантов допустить ошибку уменьшилось бы в несколько раз.

 
 
 
 Re: Задача на сообразительность.
Сообщение12.07.2015, 20:57 
Nemiroff в сообщении #1036317 писал(а):
Если из четырёх шаров нет ни одного, зачем вам вообще шевелиться? Все уже известно. Лежишь и в потолок плюешь — красота же.

Да, это ситуация простая. А как все-таки следует делать изначально? Группу из 4 проверить, а потом оставшиеся?

 
 
 [ Сообщений: 36 ]  На страницу 1, 2, 3  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group