И я попробую задачку задать

← →
Kaban (2002-08-19 11:43) [0]

Стоит очередь из ста человек. Над каждым висит веревка черного или белого цвета (рспределение произвольное). Т.о. последний человек видит перед собой 99 веревок (кроме той, которая над ним), второй 98 и т.д. По очереди, начиная с последнего, они начинают угадывать цвет веревки. При этом они могут произнести только одно из двух слов "черная" или "белая". Если человек угадывает, он остается в живых, в противном случае его убивают. Перед тем как выстроится в очередь они могут обговорить стратегию.

Сколько человек можно гарантированно спасти?

← →
Kaban (2002-08-19 11:48) [1]

Как же это она зараза в общие вопросы то попала

← →
France (2002-08-19 11:48) [2]

Вспомним теорию вероятности, наверное. И исходя из этого, получаем то что нам нужно, количество спасенных человек. :-)))

← →
RV (2002-08-19 11:49) [3]

в потрепаться надо бы..
кол-во черных и белых одинаково?

← →
lenin (2002-08-19 11:50) [4]

А черных и белых веревок одинаковое количество?

← →
Kaban (2002-08-19 11:51) [5]

2 France (19.08.02 11:48)
Теория вероятностей здесь нипричем - ключевое слово гарантировано

RV © (19.08.02 11:49)
внимательно читай - распределение произвольное

← →
France (2002-08-19 11:51) [6]

А вообще, если честно, раньше была такая программа "Fuzzy Calculator" называлась. Работа с приближенными числами. Найди, может поможет составить алгоритм решения данной задачи.

← →
France (2002-08-19 11:53) [7]

>Kaban
Ты хочешь сказать, что он эти веревки Randomize"ом "развешивает"?

← →
Kaban (2002-08-19 11:55) [8]

еще раз, распределение произвольное, это означает, что может быть даже 100 белых или 100 черных веревок

← →
Ekaterina (2002-08-19 12:11) [9]

50 человек

← →
RV (2002-08-19 12:11) [10]

почти всех можно спасти
каждый говорит цвет веревки впереди стоящего

← →
Ekaterina (2002-08-19 12:14) [11]

>RV
Тогда только одного, т.к. когда он говорит цвет верёвки впереди стоящего, то сам-то может умереть, если его цвет не совпадёт с цветом следующей.

← →
McSimm (2002-08-19 12:17) [12]

99 человек можно гарантированно спасти.

> Перед тем как выстроится в очередь они могут обговорить
> стратегию.

Долго же они будут выбирать добровольца на последнее место

← →
RV (2002-08-19 12:19) [13]

вообщем да, тормознул :)
по инерции по мысле написал
но можно договориться об интонации произношения
о временной задержке перед ответом

← →
Ekaterina (2002-08-19 12:22) [14]

Тоже верно ;)

← →
Kaban (2002-08-19 12:34) [15]

McSimm © (19.08.02 12:17)
99 человек можно гарантированно спасти.

Молодец.

← →
Kaban (2002-08-19 12:36) [16]

RV © (19.08.02 12:19)
Действительно существует способ гарантированно спасти 99 человек, интонация и прочее здесь ни при чем

← →
RV (2002-08-19 12:39) [17]

Kaban © (19.08.02 12:34)

ирония?
правильный ответ Ekaterina © (19.08.02 12:11)
плюс те, крые угадают

← →
RV (2002-08-19 12:39) [18]

пока писал
ты еще раз написал

← →
RV (2002-08-19 12:42) [19]

блин, как!?
сдаюсь

← →
Kaban (2002-08-19 12:43) [20]

2 RV
Без всякой иронии. Теперь можно переформулировать вопрос:
Требуется найти способ, при котором гарантировано спасется 99 человек.

Ответ Ekaterina © (19.08.02 12:11) неверный

Если бы задачка так просто решалась, стал бы я ее задавать.

← →
Kaban (2002-08-19 12:43) [21]

может еще кто захочет голову поломать

← →
France (2002-08-19 12:50) [22]

Интересно, а к программированию это относится или нет? Пойди в "потрепаться" спроси. Я серьезно, не обижайся, кроме шуток.

← →
McSimm (2002-08-19 12:51) [23]

Принцип четности.
Договориться можно, например, так:

Последний (который согласился рискнуть жизнью ради спасения всех остальных) своим ответом сообщает четное или нечетное число черных веревок он видит. Тогда используя эту информацию и учитывая ответы стоящих позади те кто умеют считать легко определят цвет своей веревки

← →
Kaban (2002-08-19 12:51) [24]

см. Kaban © (19.08.02 11:48)

← →
Kaban (2002-08-19 12:52) [25]

McSimm © (19.08.02 12:51)
не ну так неинтересно

← →
Squ (2002-08-19 12:55) [26]

В формулировкее вопроса есть "гарантированно":
гарантированно нельзя спасти ни одного, ведь все 100 веревок могут быть черными.

← →
Kaban (2002-08-19 13:00) [27]

2 Squ (19.08.02 12:55)

Прочитай внимательно McSimm © (19.08.02 12:51)

← →
McSimm (2002-08-19 13:01) [28]

>Kaban © (19.08.02 12:52)
Извини, действительно поспешил.

>Squ (19.08.02 12:55)
Именно гарантированно. Если только никто не протормозит и не ошибется в подсчетах(но это его личная проблема). А также при условии что всем слышны ответы всех сзади стоящих

← →
RV (2002-08-19 13:02) [29]

← →
Andrey007 (2002-08-19 13:22) [30]

А я так и не понял как вы 99 спасённых человек насчитали. Ведь первый угадывающий не видит никакой верёвки - следовательно в наихудшем случае он погибает. Второй видит верёвку, которая была над первым, но это нисколько не спасет остальных. i-ый угадывающий видит верёвку, которая висит над i-1-ым, который либо остался жив, либо нет, и знание этого факта нисколько на влияет на то, угадает ли он или нет. Так что в наихудшем случае погибают все. Если угадывать начинает тот, кто видит 99 верёвок, то можно спасти 50 человек - этот человек говорит цвет верёвки, которая висит над 98-м. В наихудшем случае н гибнет. И т.д. - i-ый угадывающий говорит цвет верёвки на i+1-ым угадывающим, спасая его жизнь, но при этом жертвуя своей. Возьмём для примера 98-го человека, который из слов 99-го знает цвет верёвки висящий над ним и над следующим. Если брать наихудший случай, то цвета верёвок различаются, и у него есть выбор - повторить цвет, который сказал 99-й, и, таким образом, спасти свою жизнь, или сказать цвет верёвки, висящей над 97-м, жертвуя своей жизнью ради жизни 97-го. Очевидно, что эгоистическая стратегия оказывается выгоднее альтруистской, поскольку в альтруистской стратегии в наихудшем случае погибают все альтруисты, а эгоистическая стратегия гарантирует 50 спасённых - гарантировано выживание только тех, чей номер нечётный.

← →
Kaban (2002-08-19 13:24) [31]

внимательно читай условия задачи

Т.о. последний человек видит перед собой 99 веревок (кроме той, которая над ним), второй 98 и т.д. По очереди, начиная с последнего, они начинают угадывать цвет веревки.

← →
Andrey007 (2002-08-19 13:25) [32]

Кстати, а откуда взялась такая задача? Помнится мне один знакомый, вернувшийся из Чечни, где он служил, рассказывал, что разведка расстреливает около 80% раненых боевиков, и только около 20% отдает куда следует.

← →
Kaban (2002-08-19 13:26) [33]

Да мне одна знакомая загадала, давно правда. мне все лень было на форум отправить

← →
Andrey007 (2002-08-19 13:26) [34]

> Т.о. последний человек видит перед собой 99 веревок (кроме той, которая над ним), второй 98 и т.д. По очереди, начиная с последнего, они начинают угадывать цвет веревки.

Ну в таком случае гарантировано спасение 50 человек, объяснение чему я и привёл выше - Andrey007 (19.08.02 13:22)

← →
Andrey007 (2002-08-19 13:28) [35]

> Да мне одна знакомая загадала

А ей зачем? Боевиков расстреливать?

← →
Kaban (2002-08-19 13:28) [36]

← →
Turalyon (2002-08-19 13:30) [37]

По таким условиям выживут 99 человек.. если полседний будет не угадывать а говорить цвет веревки впередистоящего. Рискует только он с вероятностью 1/2 вот.

← →
Andrey007 (2002-08-19 13:34) [38]

2 Turalyon: Выше я показал, что такая стратегия обеспечивает выживание только 50 человек - Возьмём для примера 98-го человека, который из слов 99-го знает цвет верёвки висящий над ним и над следующим. Если брать наихудший случай, то цвета верёвок различаются, и у него есть выбор - повторить цвет, который сказал 99-й, и, таким образом, спасти свою жизнь, или сказать цвет верёвки, висящей над 97-м, жертвуя своей жизнью ради жизни 97-го. Очевидно, что эгоистическая стратегия оказывается выгоднее альтруистской, поскольку в альтруистской стратегии в наихудшем случае погибают все альтруисты, а эгоистическая стратегия гарантирует 50 спасённых - гарантировано выживание только тех, чей номер нечётный.

А вероятность вычислить невозможно, поскольку по условиям задачи неизвестно распределение.

← →
Andrey007 (2002-08-19 13:37) [39]

2 Kaban:
>Ознакомься с McSimm © (19.08.02 12:51)

McSimm © (19.08.02 12:51):

Принцип четности.
Договориться можно, например, так:

Последний (который согласился рискнуть жизнью ради спасения всех остальных) своим ответом сообщает четное или нечетное число черных веревок он видит. Тогда используя эту информацию и учитывая ответы стоящих позади те кто умеют считать легко определят цвет своей веревки.

Ну а где здесь оценка снизу количества выживших, если допустить, что считать умеют все?

← →
Kaban (2002-08-19 13:38) [40]

И я попробую задачку задать Найти похожие ветки