По типу взвешиваний (2)

coder · Post by **coder** » 25 Feb 2002 15:49

Решите задачу про шарики, при условии, что общее количество шариков - 16! [img:e3b9230c10]images/smiles/icon_eek.gif[/img:e3b9230c10]
(это просто восклицательный знак, не факториал)

решение есть [img:e3b9230c10]images/smiles/icon_razz.gif[/img:e3b9230c10]

zels · Post by **zels** » 26 Feb 2002 04:27

Это невозможно.
Хотя вариантов 120 < 128, но при первом измерении 5 шариков получается при наличии радиации 65 вариантов, что за 6 попыток даже теоритически нельзя.

Drom · Post by **Drom** » 26 Feb 2002 17:01

yep. при оптимальной стратегии, но плохом раскладе, первое измерение оставляет не меньше 65 возможных комбинаций. так что для 16 эта задача решается только если знать прикуп.

coder · Post by **coder** » 26 Feb 2002 17:23

<empty>

[ 26-02-2002, 08:24: Message edited by: Дима ]

coder · Post by **coder** » 26 Feb 2002 17:25

<blockquote>quote:<hr />Originally posted by Drom:
yep. при оптимальной стратегии, но плохом раскладе, первое измерение оставляет не меньше 65 возможных комбинаций. так что для 16 эта задача решается только если знать прикуп.<hr /></blockquote>Пhавильно, но только где в условии задачи написано, что в первом измерении должно быть 5 шариков? <img border="0" title="" alt="[Big Grin]" src="biggrin.gif" />
(можете воспринимать это как подсказку)
Поверьте на слово - но я свое решение раза 3 проверял - работает <img border="0" title="" alt="[Smile]" src="smile.gif" />

zels · Post by **zels** » 27 Feb 2002 14:13

Наверное, 3 раза - недостаточно
5 шариков - это лучший вариант.
Если в первой попытке меньше 5, рассмотри случай "нет"
Если 5 или больше - случай "есть"
Шесть оставшихся измений не хватит.

Drom · Post by **Drom** » 27 Feb 2002 14:53

<blockquote>quote:<hr />Originally posted by Дима:
 <blockquote>quote:<hr />Originally posted by Drom:
yep. при оптимальной стратегии, но плохом раскладе, первое измерение оставляет не меньше 65 возможных комбинаций. так что для 16 эта задача решается только если знать прикуп.<hr /></blockquote>Пhавильно, но только где в условии задачи написано, что в первом измерении должно быть 5 шариков? <img border="0" title="" alt="[Big Grin]" src="biggrin.gif" />
(можете воспринимать это как подсказку)
Поверьте на слово - но я свое решение раза 3 проверял - работает <img border="0" title="" alt="[Smile]" src="smile.gif" /> <hr /></blockquote>не верю! <img border="0" title="" alt="[Razz]" src="tongue.gif" />
я специально поправил zero - сказал "при оптимальной", а не "при 5 шариках в первом измерении", хотя это одно и то же.

можно расписать (количество шариков в измерении) => (остается комбинаций при отрицательном результате)/(при положительном):

3 => 78/42
4 => 66/54
5 => 55/65
6 => 45/75

к сожалению такая логика годится только для доказательства невозможности - по ней в первом измерении при 15 шариках должно быть 4 шара (хотя может быть и 5)...

хммм, что и после этого все равно ваше решение работает?

coder · Post by **coder** » 27 Feb 2002 16:55

эээ...

Еще раз проверил - действительно НЕ работает <img border="0" title="" alt="[Frown]" src="frown.gif" /> . стыдно... <img border="0" title="" alt="[Eek!]" src="eek.gif" />

принощу глубочайшие извинения <img border="0" title="" alt="[Smile]" src="smile.gif" />

coder · Post by **coder** » 27 Feb 2002 16:58

Я начинал измерять по 6 (2+4) по похожей схеме с 5-ю (4+1)

Но вот только в случае, когда первые 2 измерения дали "Да" - решение "рассыпается" <img border="0" title="" alt="[Frown]" src="frown.gif" /> . не заметил-с.

Во всех остальных - ОК, но, как говорится, "почти" не считается <img border="0" title="" alt="[Smile]" src="smile.gif" />