Задачка :) (полный гон)

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

Правда, в этом случае первым спрашивать должны того, кому последним одевали капюшон - он в любом случае дохнет с вероятностью 50%.

не, я в такие условия не поставлен... :)

ты лишь забыл сказать что это задача для шестого класа на четность ..

более интересно решить другую задачу .. M заключенных и N цветов капюшонов .. сколько максимум здохнет при идельной тактике?

и ктстаи сформулировал ты задачу некорректно - в твоей формулировке она не имеет решение

фразу (при этом каждый смертник видит какой капюшон надели на впереди /стоящего/, но не видит какой надели на него). следует читать как (при этом каждый смертник видит какой капюшон надели на впереди *стоящих*, но не видит какой надели на него).

еще одна некорректность ..

палач начинает спрашивать подряд начиная с того кто видит всех ..

иначе если он начнет спрашивать с того кто никого не видит - могут вообще все здохнуть ..

И как они будут действовать? Что-то не догоняю..

>И как они будут действовать? Что-то не догоняю..

каждый предыдущий называет цвет мешка последующего

первый либо дохнет, либо нет, остальные точно отмажутся :)

>более интересно решить другую задачу .. M заключенных и N цветов капюшонов .. сколько максимум здохнет при идельной тактике?

для любого M ответ один и тот же, толькл первый сдохнет с вероятностью 1/M

т.е. 1/N

>каждый предыдущий называет цвет мешка последующего

>первый либо дохнет, либо нет, остальные точно отмажутся :)

Первый называет цвет второго. Второй называет цвет третьего? А не факт, что у второго и третьего они совпадают. Тогда второму хана.

> каждый предыдущий называет цвет мешка последующего

> первый либо дохнет, либо нет, остальные точно отмажутся :)

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

ээээ да вы че народ? это ведь реальная задача для шестого класса, может быть конечно олимпиадного характера но все равно ..

еще раз лишь повторю что задача на четность ..

В голову только одна мысль пришла - передавать информацию о цвете капюшона следующему человеку не явно, а "скрытно". Например порядком слов при ответе на вопрос палача. Но это все гон, естественно. А при чем тут четность?

И вообще - странная задача. Если вдуматься: надо в один ответ втиснуть два - назвать свой цвет и что-то подсказать следующему. Что-то вроде двух бит информации, хранимых в одном. Как это вообще возможно? ИМХО нормального решения тут не должно быть, ответом будет что-нибудь вроде моего.

> еще раз лишь повторю что задача на четность ..

В условии наврали, сейчас точно не помню, но там еще какая-то тонкость была в распределении капюшонов, оно не совсем случайным было или заранее известны количества цветов или еще что-то в этом роде. Смысл, что после ответа первого спрошенного остальные получают сразу информацию о цвете капюшонов двух человек, на которого указан и в любом случае становится ясен цвет отвечавшего. После чего вся цепочка однозначно определена. Но для этого там какое-то другое условие задачи было.

неважно как и какие капюшоны надевали .. ответ первого чела должен содержать информацию о *всех* видимых капюшонах иначе (можно доказать?) существует расклад при котором кто-то сдохнет (кроме первого)

я не помню он в условии упомянул что они(зеки) могут заранее договориться о тактике? по сути он это упомянул - "..зеки придумали метод.."

вобщем оригинально задача звучит типа

есть сто зеков которым придумали интересный вид казни. Им сказали что их выведут в чисто поле - постороят в очередь(так что каждый видит только впереди стоящих) и наденут каждому по колпаку либо синий либо красный, далее палач будет идти по очереди от первого(который видит всех) и задавать вопрос "Какого цвета на тебе колпак?" в случае верного ответа чела отпускают иначе на мясо .. принимаются ответы только "Синий" или "Красный" иначе на мясо. У зеков есть ночь чтобы придумать как им выжить .. сколько зеков максимально выживет если они придумают идеальную тактику?

При таком условии никак не обойдется, что первый спрошенный с вероятностью 50%, а остальные все выживают.

Имеем для остальных кроме первого fact(99)/fact(99-2) == 98*99== 9702 варианта распределения случайным образом и каким образом два варианта ответа сведут их к одному?

в этом то и состоит задача - найти этот метод ..

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

но тут действительно выживут все кроме первого .. а первый выживет только если повезет (50%)

хмм .. я насамом деле в шоке почему подобная задача вызвала сложности у взрослых дядек :-\

А, сообразил! Надо чтобы отвечающий назвал допустим красный цвет, если число видимых ему красных цветов нечетно и синий в противном случае или наоборот. Тогда, поскольку каждый видит всех, находящихся впереди, то свой цвет определяется уже точно. Простая задачка, я просто по ночному времени на сонную голову как то забыл, что впередистоящих видит не только первый, но и все последующие.

Вот при таком условии:

///вобщем оригинально задача звучит типа
есть сто зеков которым придумали интересный вид казни...
...сколько зеков максимально выживет если они придумают идеальную тактику///

задача имеет решения.
1. если отталкиваться от условия:///принимаются ответы только "Синий" или "Красный" иначе на мясо/// то в нем. ничего не сказано про пробелы (задержку перед ответом)
тогда первый говорит цвет колпака впередистоящего (и погибает с вероятностью 50/50) второй, знает какой на нем колпак, и если у вперидистоящего ТАКОЙ ЖЕ, то отвечает сразу. Если у впередистоящего другой цвет, то отвечает досчитав до пяти. Таким образом, впередистоящий понимает, что у него колпак другого цвета. И так далее. (главное, чтоб слыдующий слышал что отвечает предыдущий)

2.если "пробелы" недопустимы (вообщем подразумевается. что нет способов передать дополнительную информацию, только цвет) первый говорит, какого цвета колпак на третьем,если он совпадает с цветом колпака второго./пусть это будет синий/ Если не совпадает, значит цвет колпака второго. (если и на нем тот же цвет, он выживает, если нет - труп 50/50 ))) ) /пусть это будет красный/
второй знает какой колпак на впередистоящем, и если первый назвал другой цвет,/красный/ значит это цвет его колпака. если названый цвет и цвет колпака впередистоящего совпадают, он знает, что на нем тот же цвет /синий/
Таким образом, второй знает какой колпак на нем. Третий тоже знает, какой колпак на втором (про слышимость ничего в условиях нет)
Второй называет свой цвет. Если этот ответ, СОВПАДАЕТ с ответом ПЕРВОГО, значит на третьем, колпак другого цвета /красный/. Если НЕ совпадает, значит на третьем колпак того же цвета, что и на втором /синий/.
Теперь, после ответа второго, третий знает цвет своего колпака.
и четвертый знает цвет колпака третьего.
По существующей предварительной договоренности, каждый третий поставлен перед возможностью оказаться в смертниках.
Он попадает в такие условия, так, как должен назвать цвет колпака так же, как первый.
Если цвет совпадает с его цветом, его не убивают и он радуется.
но принцип остается.

таким образом, погибает каждый третий, с вероятностью 50/50

предыдущий аноним рассказал как сделать так что бы выжили все кроме первого ..

А с точки зрения палача:

1. Беру второго или третьего с конца и задаю ему коварный вопрос.

2. Выбираю ещё одного, через одного или двух (по-настроению), двигаясь к первому, и задаю ему коварный вопрос.

3. Выбираю следующего, через одного или двух (по-настроению) и задаю ему коварный вопрос.

4. и т.д. и т.п.

P.S. ...день удался :D

день удастса больше если он просто пойдет от начала очереди :) - вообще все здохнуть могут ..

ну и как следуя этой рекомендации выжить?
возмем не 100 а 10

с-к-к-к-с-к-с-к-с-с

тогда первому видно (раз уж всех видно) 5 красных и 4 синих.
5 - нечетное, он называет красное.(синее значит четное)
второй начинает считать
и видит 4 красных и 4 синих.
предполагает, что раз предыдущий назвал красный нечетным, значит он является именно тем нечетным красным, которого он не видит.
называет свой цвет /красный/
третий считает и видит 3 красных и 4 синих.
если он будет подразумевать, что он один из невидимых нечетных, он должен назвать синий цвет.

> день удастса больше если он просто пойдет от начала очереди :) - вообще все здохнуть могут ..

А завтра развлекаться? :D

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

2anonymous (*) (03.03.2005 9:31:39)

-- Разговорчики в строю?!

И что? Сначала, все всё обсудили, а потом играем?

Или последнего расстреливают, просто, за болтливость?

2anonymous (*) (03.03.2005 9:31:39)

> возмем не 100 а 10

и, кстати, как на слух определить, какой по счету попал под раздачу, пятнадцатый или шестнадцатый?

с-к-к-к-с-к-с-к-с-с
                  ^
                  | первый

допустим зеки договорились что самый первый(который видит всех) скажет
"Красный" если он видит четное количество красных колпаков и Скажет 
"Синий" если их нечетно

еще заметим, что при каждом продвижении по очереди меняется четность 
количества либо красных либо синих колпаков - причем меняется четность 
колва колпоков цвета который на вновь спрашиваемом

первый говорит "Синий" (видя перед собой нечетное колво красных 
колпаков).  Второй видя перед собой тоже нечетное колво колпаков 
(четность не поменялась) - делает вывод что на нем тоже синий колпак ..
третий видя перед собой четное колво красных колпаков (поменялась 
четность) делает вывод что на нем красный колпак .. четвертый видя 
перед собой четное колво красных колпаков (четность  не поменялась) - 
делает вывод что на нем синий колпак, etc

с-с-к-к-с-с-с-к-с-к
^
| первый

чойто я плохо понял, отчего ваш первый, исходя только из четности, определил свй колпак. в условии нет ничего про то, что колпаков РАВНОЕ кол-во.

во вторых, что значит поменялась четность? Стоящие знают, четными они стоят в ряду или нечетными? И что именно это им дает?

первый видит 4 красных и 5 синих.
он с равным успехом может подразумевать свой колпак что синим, что красным. По предложенному решению, он должен назвать красный цвет если ВИДИТ нечетное кол-во красных. И синий, если синих четное.

Остальные получают информацию о том, четное или нечетное кол-во красных колпаков. (ну и синих)

В данном случае, первого не убьют, так как он назовет синий (нечетный) цвет. (а ежлиб он был красным, то оба цвета были нечетными)
Второй видит все то же четное кол-во красных и синих тоже четное.
Исходя из чего, он определяет себе синий колпак?
прибавля себя к видимым четным синим, на основании выбранного первым цвета?
или на основании того, что он сам четный, и четность не изменилась?
тогда он должен назвать красный.

а с третьим совсем плохо.
с одной стороны. он видит 3 красных -нечетное, с другой 4 синих - четное. Но нечетными определены синие. Прибавляет себя или нет?
или исходит из того, что он третий, значит нечетный, значит четность поменялась, и значит на нем синий колпак???

> По предложенному решению, он должен назвать красный цвет если ВИДИТ нечетное кол-во красных. И синий, если синих четное.

нет - ты не понял, перечитай мой пост предыдущий

спереди стоящие слышат ответы предыдущих, ибо не глухие т/к слышат вопрос палача

> предыдущий аноним рассказал как сделать так что бы выжили все кроме первого ..

Это я был, просто с другого браузера зашел и не залогинился автоматически.

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

> более интересно решить другую задачу .. M заключенных и N цветов капюшонов .. сколько максимум здохнет при идельной тактике?

По-моему, тактика будет похожей.

Решение:

1) присвоим номера цветам, от 0 до N-1

2) первый спрашивающий складывает по модулю N сумму цветов впереди стоящих и называет цвет, соответствующий полученному номеру. Вероятность выжить у него 1/N

3) каждый последующий называет такой свой номер, чтобы с учётом суммы по модулю N уже оглашённых цветов, добавление своего номера давала исходную сумму, названную первым.

Результат: M-1 гарантированно уцелело, а один с вероятностью 1/N.

отлично!