Задача на сообразительность.

ole-ole-ole · 03/06/12 209

Имеется 7 с виду одинаковых шаров, из которых два радиоактивные. Дозиметром можно проверить на радиоактивность любую
группу шаров. За какое наименьшее число проверок можно выявить оба радиоактивных шара?

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

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

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

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

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

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

levtsn · 08/08/14 ∞ 991 Москва

Достаточно проверит 5 шаров из 7 так как число радиошаров задано.

ole-ole-ole · 03/06/12 209

levtsn в сообщении #1036234 писал(а):

Достаточно проверит 5 шаров из 7 так как число радиошаров задано.

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

levtsn · 08/08/14 ∞ 991 Москва

Всего возможно 21 исход. Это более 4 бит информации. Следовательно 4 проверками узнать исход невозможно.

ole-ole-ole · 03/06/12 209

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)

Nemiroff · 20/07/09 4026 МФТИ ФУПМ

levtsn в сообщении #1036234 писал(а):

Достаточно проверит 5 шаров из 7 так как число радиошаров задано.

Проверили 5, один раз детектор щелкнул. Ну и чего дальше?

Red_Herring · 31/01/14 11304 Hogtown

Nemiroff в сообщении #1036259 писал(а):

Проверили 5, один раз детектор щелкнул. Ну и чего дальше?

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

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

Nemiroff · 20/07/09 4026 МФТИ ФУПМ

Red_Herring в сообщении #1036294 писал(а):

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

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

Red_Herring · 31/01/14 11304 Hogtown

Nemiroff
Ваше замечание совершенно справедливо о том, что его подход (через теорию информации) дает только оценку снизу. И что тупо перебирать по шарику не работает.

ole-ole-ole · 03/06/12 209

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 испытаний. Что-то много.

Nemiroff · 20/07/09 4026 МФТИ ФУПМ