Форум умных людей

Задачи и головоломки => Логические задачи и головоломки => Тема начата: Илья от Апрель 17, 2010, 11:59:41



Название: Задачка от Генерала
Отправлено: Илья от Апрель 17, 2010, 11:59:41
Имеется 14 шаров. Среди них 2 радиоактивных. Имеется счётчик Гейгера. Его можно поднести к группе шаров и узнать, есть ли в ней радиоактивные (но неизвестно - сколько их).

За сколько замеров можно найти оба радиоактивных шара в группе из 14 шаров? А из 15 шаров?


Название: Re: Задачка от Генерала
Отправлено: Dippy от Апрель 17, 2010, 13:48:06
7(при самом плохом раскладе)


Название: Re: Задачка от Генерала
Отправлено: Илья от Апрель 17, 2010, 13:55:50
Да, 7 из 14. А из 15?


Название: Re: Задачка от Генерала
Отправлено: Dippy от Апрель 17, 2010, 14:04:43
при 15-ти тоже 7(да и при 16-ти).А вот для 17-ти шаров с 2-мя радиоактивными понадобится уже 8.


Название: Re: Задачка от Генерала
Отправлено: Илья от Апрель 17, 2010, 14:10:03
Цитировать
при 15-ти тоже 7
Хм, сомнительно. Стратегию можете показать при самом "худшем" случае?
Цитировать
(да и при 16-ти).
А вот это уже очень маловероятно. Тоже стратегию, если конечно это вообще осуществимо.


Название: Re: Задачка от Генерала
Отправлено: Dippy от Апрель 17, 2010, 14:35:15
делим на 2 кучи(7 и 8)-проводим измерение
в наихудшем случае в каждой куче по 1 Р-шару
для 7-ной: делим на 3 и 4-в одной из них желанный радиоактивный.проводим измерение (для одной рандомной кучи):
Допустим искомый шар в 4х,тогда делим на 2 и 2(в одной из них искомый).Еще одно измерение(находим радиоактивную кучу):
остается 2 шара(один радиоактивный)-еще 1 измерение и желанный шар найден.
8-ную же кучу делим на 4 и 4 и ситуация повторяется.
В итоге имеем 1 измерение в начале +3 для 7-ной горки+3 для восьмерной.
Для 16-ти шаров just the same:1  измерение в начале+3 для восьмерной горки+3 для восьмерной горки,и шары у нас в руках!


Название: Re: Задачка от Генерала
Отправлено: Илья от Апрель 17, 2010, 14:41:14
Вот здесь ошибка:
Цитировать
В итоге имеем 1 измерение в начале

В начале мы имеем два измерения:
1)7+
2)8+
А дальше по вашему алгоритму и получается 8 операций.


Название: Re: Задачка от Генерала
Отправлено: Dippy от Апрель 17, 2010, 14:48:06
Да,извиняюсь,вы правы.уже побился апстену.таки получается 8 и для 15 и для 16 шт.


Название: Re: Задачка от Генерала
Отправлено: Илья от Апрель 17, 2010, 14:50:30
Цитировать
таки получается 8 и для 15
Вы в этом уверены? :)


Название: Re: Задачка от Генерала
Отправлено: Dippy от Апрель 17, 2010, 21:41:56
  15                       
  l    \
(7-) (8+)                 -2 изм.
       /     \
   (4+)  (4+)            -2 изм.
    / \        / \
(2+)(2-)  (2+)(2-)    -2 изм.
  / \             /\
(1+)(1-)   (1+)(1-)   -2 изм.

  15                       
  l    \
(7+)   (8+)                -2 изм.
 / \          /  \
(3-)(4+) (4-) (4+)     -2 изм.
      /   \        / \
(2+)(2-)  (2+)(2-)    -2 изм.
  / \             /\
(1+)(1-)   (1+)(1-)   -2 изм.

в обоих случаях - 8 измерений.Хуже расклада пока не придумал,если таковой есть ???


Название: Re: Задачка от Генерала
Отправлено: General от Апрель 17, 2010, 21:57:51
А можно ли в 7 уложиться?


Название: Re: Задачка от Генерала
Отправлено: Илья от Апрель 17, 2010, 22:09:24
А почему Вы именно на две кучки изначально делите? Ведь можно попробовать какие-то другие варианты? ;)


Название: Re: Задачка от Генерала
Отправлено: Илья от Апрель 17, 2010, 22:39:35
Признаюсь честно: до сегодняшнего утра я тоже думал, что меньше чем за 8 операций из 15 невозможно, но мне открыли глаза. :pinkgirl: Правда с одним подвариантом еще не все ясно, но решение точно есть.


Название: Re: Задачка от Генерала
Отправлено: Тиана от Апрель 17, 2010, 22:40:59
найдем подвариант, делов-то  :laugh: Показать скрытый текст


Название: Re: Задачка от Генерала
Отправлено: Илья от Апрель 17, 2010, 22:41:48
найдем подвариант, делов-то  :laugh: Показать скрытый текст
Его не надо искать - он уже найден. С ним надо разобраться.


Название: Re: Задачка от Генерала
Отправлено: Тиана от Апрель 17, 2010, 22:43:27
Показать скрытый текст


Название: Re: Задачка от Генерала
Отправлено: buka от Апрель 18, 2010, 01:26:59
Робяты, вы что-то заспешили.  :bad2:
Вариант 2-х из 14 за 7 измерений ещё никто не нашёл.  :bad:
Сразу скажу - деление на две кучки по 7 - дохлый номер:  :skull:
1-е измерение, 7 первых - радиоактивны.
2-е измерение, 7 вторых - радиоактивны.
Итак, у нас осталось 5 измерений чтобы в каждой кучке из 7 найти радиоактивный шар.
Но это - невозможно: для нахождения 1 из 7 требуется 3 измерения, т.е. для 2-х кучек - 6. Итого - 8.  :wall:
--------------------------------------------------
Можно выделить 2 шара из 14 за 7 измерений, но стратегия куда более изощрённая.
Для разминки - выделите 2 шара из 7 за 5 измерений.  :crazy:


Название: Re: Задачка от Генерала
Отправлено: Илья от Апрель 18, 2010, 15:26:34
buka, ни кто не куда не спешил, два шара из 14 за 7 операций находятся элементарно:
Показать скрытый текст


Название: Re: Задачка от Генерала
Отправлено: Илья от Апрель 18, 2010, 15:38:14
А вот как определить 2 из 15 за 7 операций тут уже надо подумать.


Название: Re: Задачка от Генерала
Отправлено: buka от Апрель 18, 2010, 21:33:54
buka, ни кто не куда не спешил, два шара из 14 за 7 операций находятся элементарно:
Показать скрытый текст
Да, так можно. Но этого варианта никто не представил.
Вариант 2 из 15 за 7 существует.


Название: Re: Задачка от Генерала
Отправлено: Илья от Апрель 18, 2010, 21:51:25
Цитировать
Вариант 2 из 15 за 7 существует.
Я знаю, что он существует. Вот как раз он и будет "изощренным".


Название: Re: Задачка от Генерала
Отправлено: buka от Апрель 18, 2010, 22:14:00
Да :)
Но 2 из 22 за 8 - тоже возможно, но я ещё не нашёл.


Название: Re: Задачка от Генерала
Отправлено: Тиана от Апрель 18, 2010, 23:24:12
22 шарика
Показать скрытый текст
вариантов много, так что загадывай два числа, вдруг повезет  :laugh:


Название: Re: Задачка от Генерала
Отправлено: buka от Апрель 19, 2010, 01:26:31
Tiana, не балуйтесь...


Название: Re: Задачка от Генерала
Отправлено: Тиана от Апрель 19, 2010, 08:21:34
Tiana, не балуйтесь...
??? вы это о чем?


Название: Re: Задачка от Генерала
Отправлено: Илья от Апрель 19, 2010, 08:23:14
А если 1-8 +?


Название: Re: Задачка от Генерала
Отправлено: Тиана от Апрель 19, 2010, 08:34:27
Показать скрытый текст


Название: Re: Задачка от Генерала
Отправлено: Илья от Апрель 19, 2010, 08:38:02
А если 9 10 11 12 +?


Название: Re: Задачка от Генерала
Отправлено: Тиана от Апрель 19, 2010, 08:42:40
Показать скрытый текст


Название: Re: Задачка от Генерала
Отправлено: Илья от Апрель 19, 2010, 08:50:50
Да, вроде все каверзные случаи рассмотрены. :bravo2:
P.S. buka, Тиана не балуется. :)


Название: Re: Задачка от Генерала
Отправлено: Тиана от Апрель 19, 2010, 08:59:29
 8)


Название: Re: Задачка от Генерала
Отправлено: buka от Апрель 19, 2010, 10:58:21
Да, вроде все каверзные случаи рассмотрены. :bravo2:
P.S. buka, Тиана не балуется. :)
1-8 +
9-15  -
Илья, 8 измерений предполагает ~ 250 комбинаций...
Если так просто бросать одну-две из них - это баловаться.
Я нашел способ за 2 из 22 за 8, он изощрённее, чем 2 из 15 за 7.
А 2 из 15 за 7 тоже изощрённый...


Название: Re: Задачка от Генерала
Отправлено: Тиана от Апрель 19, 2010, 11:00:57
Цитировать
Если так просто бросать одну-две из них - это баловаться.
это не одна-две. это от 1 до 8 и от 9 до 15


Название: Re: Задачка от Генерала
Отправлено: Илья от Апрель 19, 2010, 11:07:54
Цитировать
Если так просто бросать одну-две из них - это баловаться.
это не одна-две. это от 1 до 8 и от 9 до 15
Тиана, buka предлагает тебе ситуацию, когда:
1)1-8+
2)9-15 -
Твои дальнейшие действия.


Название: Re: Задачка от Генерала
Отправлено: Тиана от Апрель 19, 2010, 11:13:01
1. 1 2 3 4 5 6 7 8 +
2. 9 10 11 12 13 14 15 -
3. 1 2 3 4 -
4. 16 17 18 19 -
5. 5 6 +
6. 5+
7. 20 21 +
8. 20+


Название: Re: Задачка от Генерала
Отправлено: Илья от Апрель 19, 2010, 11:17:09
По-моему где-то ошибка закралась: в первом изм +, а во втором -


Название: Re: Задачка от Генерала
Отправлено: Тиана от Апрель 19, 2010, 11:18:11
ага. не туда посмотрела  :-[
щас исправлю
готово :) знаки в 1х двух строчках перепутала   :-\


Название: Re: Задачка от Генерала
Отправлено: Илья от Апрель 19, 2010, 14:01:57
Да, все верно.
P.S. buka, Тиана не балуется, она справилась с предложенным вами вариантом развития событий. :)


Название: Re: Задачка от Генерала
Отправлено: buka от Апрель 19, 2010, 14:45:10
1. 1 2 3 4 5 6 7 8 +
2. 9 10 11 12 13 14 15 -
3. 1 2 3 4 -
4. 16 17 18 19 -
5. 5 6 +
6. 5+
7. 20 21 +
8. 20+
1. 1 2 3 4 5 6 7 8 +
2. 9 10 11 12 13 14 15 -
3. 1 2 3 4 -
4. 16 17 18 19 -
5. 5 6 +
6. 5+
7. 20 21 -
дальше?   :question: 
Осталось 6,7,8,22 и одно измерение. .. :wall:


Название: Re: Задачка от Генерала
Отправлено: buka от Апрель 19, 2010, 14:52:24
Да, все верно.
P.S. buka, Тиана не балуется, она справилась с предложенным вами вариантом развития событий. :)
Она ещё не справилась... Илья, у нее ещё 200 попыток если она и дальше будет так справляться...... :)
1. 1 2 3 4 5 6 7 8 +
2. 9 10 11 12 13 14 15 -
3. 1 2 3 4 -
4. 16 17 18 19 -
5. 5 6 +
6. 5+
7. 20 21 -
дальше?   
Осталось 6,7,8,22 и одно измерение. .


Название: Re: Задачка от Генерала
Отправлено: Тиана от Апрель 19, 2010, 20:45:23
если долго мучиться - что-нибудь получится  :tianchik:
я буду думать :wall: и не сдамся так просто  :yesgirl:


Название: Re: Задачка от Генерала
Отправлено: Илья от Апрель 19, 2010, 20:46:47
Видимо нужно найти общий алгоритм. :read:


Название: Re: Задачка от Генерала
Отправлено: buka от Апрель 20, 2010, 00:54:01
Есть нечто вроде общего подхода...
Но назвать это общим алгоритмом я бы не стал...


Название: Re: Задачка от Генерала
Отправлено: buka от Апрель 21, 2010, 02:21:00
Ну так как определить 2 из 15 за 7 измерений?


Название: Re: Задачка от Генерала
Отправлено: Murat от Апрель 21, 2010, 05:46:34
8-14, 9-15


Название: Re: Задачка от Генерала
Отправлено: Илья от Апрель 21, 2010, 07:31:35
Ну так как определить 2 из 15 за 7 измерений?
Вот  и я спрашиваю: как? :)


Название: Re: Задачка от Генерала
Отправлено: buka от Апрель 21, 2010, 11:54:10
Я могу показать решение. Дайте мне знать, если это Вас интересует.
Можно также обсудить общий подход.


Название: Re: Задачка от Генерала
Отправлено: Илья от Апрель 21, 2010, 12:46:09
Конечно интересует. Ведь не зря же я тему создал и вопросы задал. :)


Название: Re: Задачка от Генерала
Отправлено: buka от Апрель 21, 2010, 13:19:30
Показать скрытый текст
Я полагаю, могут возникнуть вопросы. Задавайте. А затем можно перейти к "философии" :)


Название: Re: Задачка от Генерала
Отправлено: Илья от Апрель 21, 2010, 14:41:20
Цитировать
3.2 И(5) = Р. Итак, один шар мы определили и намостаётся определить ещё один из 14-ти за оставшиеся 4 измерения, а это - раз плюнуть (14 < 16 = 2^4)
А вот с этого места поподробнее.
Я так понимаю у нас остаются:
1-4
6-9
10-15
Проверяем первые две группы, если запиликило, то легко, а вот если запиликало на 3-ей проверке: 10-15, то что дальше? Или допустим начинаем с группы, где 6 шариков 10-15, а запиликало на 3-ей проверке, например 6-9 и у нас осталось одно измерение в запасе. Как быть? Если делить на две по 7 шариков, тоже не выйдет.


Название: Re: Задачка от Генерала
Отправлено: buka от Апрель 21, 2010, 16:05:04
Цитировать
3.2 И(5) = Р. Итак, один шар мы определили и намостаётся определить ещё один из 14-ти за оставшиеся 4 измерения, а это - раз плюнуть (14 < 16 = 2^4)
А вот с этого места поподробнее.
Я так понимаю у нас остаются:
1-4
6-9
10-15
Проверяем первые две группы, если запиликило, то легко, а вот если запиликало на 3-ей проверке: 10-15, то что дальше? Или допустим начинаем с группы, где 6 шариков 10-15, а запиликало на 3-ей проверке, например 6-9 и у нас осталось одно измерение в запасе. Как быть? Если делить на две по 7 шариков, тоже не выйдет.
Нет, в этом случае:
4. И(1...4,6...9) -> если Р -> ещё 3 измерения, если Н, то:
5. И(10...13) -> если Р -> ещё 2 измерения, если Н -> ещё одно.
------------------------------
Илья, ведь после того, как мы выделили 1 шар, убив 3 измерения, у нас осталось 14 шаров и мы знаем, что 1 и только 1 из них радиоактивный.
"Забудем" о том, что мы делили на 1..4,6..9, 10..15
Если у нас есть М шаров и 1 из них радиоактивный, то:
если 2К-1 < М <=2К, нам требуется для этого К измерений. И это - железно. :)
14<24=16, значит за 4 измерения мы определяем.


Название: Re: Задачка от Генерала
Отправлено: Илья от Апрель 21, 2010, 16:15:16
Цитировать
5. И(10...13) -> если Р -> ещё 2 измерения, если Н -> ещё одно
А куда делись шары с номерами 14 и 15?


Название: Re: Задачка от Генерала
Отправлено: buka от Апрель 21, 2010, 16:21:50
Цитировать
5. И(10...13) -> если Р -> ещё 2 измерения, если Н -> ещё одно
А куда делись шары с номерами 14 и 15?
Если И(10...13) = Н, то за одно измерение определяем:
И(14) = Р -> значит 14-й, иначе -> 15.
Если же И(10...13) = Р -> 2 измерения для 4-х...


Название: Re: Задачка от Генерала
Отправлено: Илья от Апрель 21, 2010, 16:25:00
Да, все так. Вопросов больше нет. Задача решена.


Название: Re: Задачка от Генерала
Отправлено: Илья от Апрель 21, 2010, 19:22:01
Ну что ж, самое вкусное оставим Тиане.  :nyam:


Название: Re: Задачка от Генерала
Отправлено: sek140675 от Апрель 21, 2010, 19:56:33
Ну что ж, самое вкусное оставим Тиане.  :nyam:
Да, все так. Вопросов больше нет. Задача решена.


так теперь можно поискать 3 радиактивных шара :bomb: :bomb: :bomb:


Название: Re: Задачка от Генерала
Отправлено: House Fox от Апрель 21, 2010, 19:57:42
Ну что ж, самое вкусное оставим Тиане.  :nyam:

:D Да, мне понравился коммент, сразу вспомнил задачу про тень, линейку и гравитацию :D


Название: Re: Задачка от Генерала
Отправлено: Тиана от Апрель 21, 2010, 20:18:38
Ну что ж, самое вкусное оставим Тиане.  :nyam:

:D Да, мне понравился коммент, сразу вспомнил задачу про тень, линейку и гравитацию :D
напомнишь?  :-\


Название: Re: Задачка от Генерала
Отправлено: House Fox от Апрель 21, 2010, 20:19:34
Ну что ж, самое вкусное оставим Тиане.  :nyam:

:D Да, мне понравился коммент, сразу вспомнил задачу про тень, линейку и гравитацию :D
напомнишь?  :-\

К кому конкретно вопросик? :)


Название: Re: Задачка от Генерала
Отправлено: Тиана от Апрель 21, 2010, 20:21:42
К кому конкретно вопросик? :)
кого цитирую, к тому и вопросик  :tianchik:


Название: Re: Задачка от Генерала
Отправлено: House Fox от Апрель 21, 2010, 20:26:17
К кому конкретно вопросик? :)
кого цитирую, к тому и вопросик  :tianchik:

Ясно. Ну тема, где я дал правильный ответ, человек, который загадал загадку его немного подправил и... ты дальше начала что-то "новое" решать, докапываться и др., пока не вывела из себя загадчика :D


Название: Re: Задачка от Генерала
Отправлено: Тиана от Апрель 21, 2010, 20:32:14
не помню такого  :no2:


Название: Re: Задачка от Генерала
Отправлено: House Fox от Апрель 21, 2010, 20:39:45
Почитай эту страницу, точно вспомнишь :D
Показать скрытый текст
 :tianchik:


Название: Re: Задачка от Генерала
Отправлено: Тиана от Апрель 21, 2010, 22:15:36
buka, молодец  :peace: красиво получилось

Ну что ж, самое вкусное оставим Тиане.  :nyam:
и что же мне оставили?  :pinkgirl:


Название: Re: Задачка от Генерала
Отправлено: Илья от Апрель 21, 2010, 22:19:47
Как обычно самое легкое, 2 из 22 за 8. ;)


Название: Re: Задачка от Генерала
Отправлено: buka от Апрель 22, 2010, 02:25:22
А как оценить: из какого максимального числа шаров можно выделить 2 шара за К измерений:
М: 3 4 5 7 10 15 22 ?  ?
К: 2 3 4  5   6  7   8 9 10


Название: Re: Задачка от Генерала
Отправлено: Тиана от Апрель 30, 2010, 22:48:54
я похоже совсем запуталась  :roll: попыталась начать все с самого начала - как найти 2 Р шарика из 3, из 4 и т.д.
и на 6 шариках  :wall: не получается у меня за 4 измерения найти 2Р шарика  :'(
buka, подскажите плиз


Название: Re: Задачка от Генерала
Отправлено: General от Апрель 30, 2010, 23:38:24
Сколько может быть вариантов расположения 2Р шариков из 6?
6*5/2=15
15<16, так что пока противоречия с тем, что 2 из 6 можно найти на 4 нет.

НО

Если разобрать все возможные варианты первого измерения увидим, что ни в одном из случаев эти 15 вариантов не разделятся на 7+8. Так что в 4 измерения не уложиться, только 5.


Название: Re: Задачка от Генерала
Отправлено: buka от Май 01, 2010, 00:09:40
я похоже совсем запуталась  :roll: попыталась начать все с самого начала - как найти 2 Р шарика из 3, из 4 и т.д.
и на 6 шариках  :wall: не получается у меня за 4 измерения найти 2Р шарика  :'(
buka, подскажите плиз
Это невозможо, как верно заметил Генерал.
Несмотря на то, что кол-во сочетаний по 2 из 6 = 15 < 16, невозможно разделить эти 6 шаров на две группы, чтобы ни в одной из них не было больше 8 сочетаний (т.е. на 7 и 8 ).
Нельзя определить 2Р шара из 8 за 5 взвешиваний, несмотря на то, что кол-во сочетаний по 2 из 8 = 28 и можно разделить  на две группы так, что в каждой из групп будет < 16 сочетаний (можно на 6 и 2, т.е 15 и 13).
Надеюсь, Вы догадаетесь почему :)


Название: Re: Задачка от Генерала
Отправлено: General от Май 14, 2010, 06:44:49
Вот, написал, наконец, об общем методе решения схожих задач (http://intelmath.narod.ru/radiation.html)


Название: Re: Задачка от Генерала
Отправлено: Илья от Май 14, 2010, 07:01:23
Генерал, нашел пару орфографических ошибок:
Цитировать
При 2-3+ замеряем шар №1 и далее находим свтрой  радиоактивный из 8 или из 7 за 3 измерения.

Цитировать
За сколько измерений можно найти полодительный и отрицательный шары в группе?
Я нашел за три измерения.


Название: Re: Задачка от Генерала
Отправлено: General от Май 14, 2010, 12:30:39
Спасибо, поправил :)

Да, за три


Название: Re: Задачка от Генерала
Отправлено: Валерий от Май 17, 2010, 10:50:45
 ...


Название: Re: Задачка от Генерала
Отправлено: Валерий от Май 17, 2010, 11:18:10
У меня на радиакт. шары 2 из 22 за 8 измерений ушло сегодня по меньшей мере 5 листов. Решение так и не нашел. :wall:
Нужно разбить на группы 7  10  5, и задача решаема. Интересно - пиши.




 Не проходит.
 Не заметил "дыру"   :tormoz: 


Название: Re: Задачка от Генерала
Отправлено: Илья от Май 17, 2010, 11:57:43
Интересно - не то слово.
Знаю только одно - за первое измерение, надо мерить не менее 7 шаров, чтобы если будет отриц показание нам оставалось не более 15 шаров на 7 измерений. Ну вот, а если полож, то как дальше я не знаю. Пробовал и так и этак, все время не хватает одного измерения. :wall:
P.S. Бука либо колдун, либо лукавит. :)


Название: Re: Задачка от Генерала
Отправлено: General от Май 17, 2010, 13:31:32
Вот я как-то решал её табличным методом (http://dxdy.ru/post124977.html#p124977)