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

← →
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]

← →
McSimm (2002-08-19 13:38) [41]

> Andrey007 (19.08.02 13:37)

Похоже что тебе просто лень думать.

← →
Kaban (2002-08-19 13:39) [42]

Andrey007 (19.08.02 13:37)
При таком способе спасется 99 или 100 человек, в зависимости от того угадает последний свой цвет веревки или нет

← →
Turalyon (2002-08-19 13:41) [43]

>Andrey007 (19.08.02 13:34)
Да согласен... я тут облажался малость... :) (причем дважды :))
Если рассмтривать эгоистичную теорию.... то не гарантировано выживание никому. Объясни откуда взялась цифра 50?

← →
Kaban (2002-08-19 13:42) [44]

Во народ.

Еще раз. Давайте так.
Требуется найти способ, при котором гарантировано спасется 99 человек.

← →
Andrey007 (2002-08-19 13:43) [45]

Kaban>При таком способе спасется 99 или 100 человек, в зависимости от того угадает последний свой цвет веревки или нет

Что-то я не понял как они спасаются. Хотя и подумал.

← →
Kaban (2002-08-19 13:47) [46]

Значит так допустим последний видит перед собой четное количество белых веревок. Он говорит слово "белая", которое при предварительной договоренности означает, что белых веревок четное число.
Теперь если предпоследний видит перед собой нечетное число белых веревок, то он понимает, что над ним веревка белая и наоборот. И т.д. все вычисляют какой цвет веревки над ним

← →
Andrey007 (2002-08-19 13:54) [47]

Kaban> Он говорит слово "белая", которое при предварительной договоренности означает, что белых веревок четное число.

... и, соответственно, он говорит "чёрная" если чёрных верёвок чётное число. Поскольку он видит 99 (нечётное) число верёвок, то либо число чёрных четное, либо число белых чётное. Всё это, конечно, хорошо, но вот если все верёвки будут одного цвета, то его слова всех дезинформируют, и в наихудшем случае погибнут все. Поэтому лучше договориться о том, чтобы словом "белая" или "чёрная" он обозначал те верёвки, которых нечётное количество - это будет работать даже когда все верёвки одного цвета.

← →
Kaban (2002-08-19 14:04) [48]

Да вы не поняли, последний сообщает четность тех веревок, которые он видит, а не все 100. Поэтому какими словами какую четность/нечетность называть не имеет значения

← →
McSimm (2002-08-19 14:04) [49]

>Andrey007 (19.08.02 13:54)

Нет.

Он говорит только очетности одного цвета. Например белого.
Тогда один его ответ означает "белых - четное", второй его ответ означает "белых - нечетное".
Ноль считается четным.

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