Им всего-то и нужно было договориться называть цвет колпака впереди стоящего... :-/

Первый мрёт с 50% гарантией давая 100% шанс выжить остальным..

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

Нет, так не получится. Например:
БКБКБКБК

Тогда по этому алгоритму все умрут.

Это очень интересное решение, но работает оно только в случае, если каждый чиновник действительно может видеть всю очередь впереди себя, а не только непосредственно того, кто перед ним.
Так как если задача на классическую логику, и чиновники смотрят в затылок впередистоящего - они наверное не должны выглядывать сбоку на всю очередь, как и поворачиваться назад, как и говорить лишние слова.
Лучший вариат - дать два варианта ответа

хм, признаю я жестоко сглупил, посчитав задачу тривиальной.. :/

2Ravlyk:
В условии задачи сказано: "... Первым отвечал тот кто видит всех ...", т.е. чиновники видят всех впереди стоящих.
А на собеседовании нужно задавать наводящие вопросы, если что-то непонятно и рассуждать вслух. Тогда можно получить подсказки.

2jonny3D: со всеми бывает

"более правильное решение" просто неверно

2Stranger:
А почему это оно неверно? Какие аргументы?

Чтобы дать точный ответ, сначала нужно получить точный алгоритм решения. Здесь вместо алгоритма сказано:
"...И так по цепочке..."
Вопрос:"Каким правилом,называя цвет, руководствуются те, кто относится к этой цепочке?".

2Stranger:

Давайте рассмотрим на примере:
0 - красный, 1 - белый
Возьмем такую последовательность:
[1]101000110
Начинать будем слева, т.е. чиновник в белом колпаке (самая левая единица в квадратных скобках) видит всех впереди и подсчитывает сумму по модулю 2, которая равна в данном примере 0. Он называет соответствующий цвет и будет убит, т.к. названный цвет не совпадает с его собственным.

Остается такая цепочка:
[1]01000110
Причем, все знают ответ первого чиновника и алгоритм.
Следующий чиновник подсчитывает сумму по модулю 2 всех, которые перед ним, получается 1. Т.к. у предыдущего чиновника получилось 0, следовательно его цвет должен быть 1. Что он и называет.

Остается такая цепочка:
[0]1000110
Сумма по модулю 2 = 1
предыдущий цвет = 1
в сумме имеем 0, чтобы общая сумма была равно 0, цвет текущего колпака должен быть 0.

[1]000110
(+) = 0
(+) предыдущих ответов = 0(+)1(+)0 = 1
ответ = 1

[0]00110
(+) = 0
(+) предыдущих ответов = 0(+)1(+)0(+)1 = 0
ответ = 0

[0]0110
(+) = 0
(+) предыдущих ответов = 0
ответ = 0

[0]110
(+) = 0
(+) предыдущих ответов = 0
ответ = 0

[1]10
(+) = 1
(+) предыдущих ответов = 0
ответ = 1

[1]0
(+) = 0
(+) предыдущих ответов = 1
ответ = 1

[0]
(+) = 0
(+) предыдущих ответов = 0
ответ = 0

Хм. Не знаю с чего и начать...
Предыдущее пояснение было весьма подробным, поэтому не буду экономить буквы, но заранее извиняюсь за многословие. Начну издалека. Предлагается такая игра:
Пусть имеется группа участников, каждый из которых имеет 100 руб. и согласился участвовать в следующей игре-лотерее. Ведущий говорит: "Вас 1000 человек. Для удобства я вас пронумерую числами от 1 до 1000. Правила игры. Выбирается случайным образом один из вас (пусть его номер будет М>1) и я бросаю монету. Если выпадет герб, то участнику с предыдущим номером я выплачиваю 500 рублей, а если герб не выпадает, то его 100 руб. переходят ко мне. Играем один раз". Толпа гудит: "Не тяни время, начинай!!!"
Начинается игра. Первому же из участников под довольно большим номером М "не повезло" - герб не выпал. Ведущий говорит:" Прошу всех предыдущих участников с номерами от 1 до М-1 отдать мне свои 100 руб. Все свободны до следующей игры!"...
Некоторые из этих М-1 участников немного недовольны: "Как же так? Ведь речь шла только об участнике с предыдущим номером?"
Ведущий, собирая денежки в большой мешок, объясняет: "Нет, дорогие! Я имел в виду всех участников с предыдущими номерами! Не надо придираться по мелочам!!!"... Толпа снова гудит...
А теперь по существу. Вспомним, что обсуждалось следующее решение: (цитата)
>"...чиновник, который отвечает первым и видит цвета всех остальных, подсчитывает сумму по модулю 2 и называет получившийся цвет. С вероятностью 50% результат совпадет с его цветом. Далее, следующий чиновник, подсчитав сумму по модулю 2 всех, кто стоит перед ним, и ЗНАЯ ОТВЕТ ПРЕДЫДУЩЕГО (выделено мною, Stranger), стопроцентно правильно называет свой цвет. И так по цепочке..."
Здесь вроде бы всё верно. Но очередной следующий чиновник не сможет "стопроцентно правильно назвать свой цвет" , используя информацию: "сумму по модулю 2 всех, кто стоит перед ним, и ЗНАЯ ОТВЕТ ПРЕДЫДУЩЕГО".
В подробно разобранном примере приводится решение на основе совершенно другого алгоритма (вот цитата):
> " (+) предыдущих ответов = 0 (+) 1 (+) 0 (+) 1 . .."
Здесь, как видим, уже используются ВСЕ предыдущие ответы, т.е. совершается плавный переход от использования одного предыдущего ответа (что прозвучало в алгоритме решения) к использованию всех предыдущих ответов. НО это СОВЕРШЕННО ДРУГОЕ РЕШЕНИЕ. Те, кто с этим не согласен, наверное, уже пошли участвовать в повторной игре с упомянутым выше ведущим, который уже ждёт их со своим большим мешком .
Принципиально важный момент: сколько прозвучавших ответов может использовать чиновник с номером М (нумерация с хвоста):
- один ответ (стоящего непосредственно за ним) => задача А;
- все прозвучавшие ответы => задача В.
Согласитесь, что это всё-таки разные задачи, различны и алгоритмы их решения.
Какую же задачу решаем мы?
1. В УСЛОВИИ задачи сказано, что чиновник, дающий ответ, видит цвета всех колпаков впереди, но не сказано, что он слышит все прозвучавшие ответы. А ведь если "ОЧЕРЕДЬ ДОСТАТОЧНО ДЛИННАЯ", то вряд ли БЕЗ ОСОБЫХ НА ТО ОСНОВАНИЙ можно предполагать, что чиновники, стоящие в начале колонны, могут слышать ВСЕ ответы. Например, если сказано, что вы сможете, оглянувшись, увидеть цвет колпаков идущих за вами достаточно далеко прохожих, то вряд ли ОТСЮДА СЛЕДУЕТ, что вы сможете услышать их беседу! Вот если наоборот...
Можно изготовить колпаки и пригласить прохожих для участия в таком эксперименте.
Итак, мы имеем, что в условии задачи оговорена возможность видеть все колпаки впереди, но не оговорена аналогичная (и не менее существенная!) возможность слышать все ответы, прозвучавшие за спиной чиновника.
2. В РЕШЕНИИ сказано: " следующий чиновник, ... ЗНАЯ ОТВЕТ ПРЕДЫДУЩЕГО...".
Отсюда делаем вывод, что решается задача А. К этому случаю и относится мой комментарий. Для этого случая я назвал решение, которое привёл Sergiy Oliynyk, оптимальным.
Если же решается задача В, то, на мой взгляд, обсуждаемый алгоритм решения лучше сформулировать несколько иначе - в виде одного правила:
- каждый чиновник подсчитывает и называет сумму по модулю 2 цветов всех колпаков впереди и всех прозвучавших ответов.
Конец алгоритма.
В этом случае:
- формулировка алгоритма более компактна.
- сразу ясно, о какой задаче идёт речь и т.д.
Из этого алгоритма вытекает следующее решение задачи.
ВОПРОС :о чём нужно договориться чиновникам?
ОТВЕТ: каждый чиновник подсчитывает сумму по модулю два цветов колпаков впереди и получает исходное число S (которое может принять только одно из двух значений: 0 или 1). Теперь он слушает ответы. Если слышит 1 - меняет число S , а если 0 - то не меняет. Это число S он и называет, когда придёт его очередь.

ЗЫ 1. Возможно, что либо условие задачи, либо её решение, либо и то и другое были пересказаны неточно (или неполно). Если условие пересказано точно, то, наверное, количество слышимых ответов нужно было уточнить. Здесь я согласен с рекомендацией: "А на собеседовании нужно задавать наводящие (уточняющие - Stranger) вопросы, если что-то непонятно..."

ЗЫ 2. По ходу записи этого ответа возникло предложение рассмотреть вот такой (возможно, неинтересный) вариант обсуждаемой задачи:
будем считать, что
1. в колонне N чиновников
2. в зону слышимости попадают К соседей сзади. Т.е. если номер очередного чиновника больше, чем К, то он слышит только К последних прозвучавших ответов. Если номер чиновника меньше, чем К+1, то он слышит все прозвучавшие ответы.
Какой оптимальной стратегии должны придерживаться чиновники? Для достаточно большой очереди: чему равно в этом случае математическое ожидание количества уцелевших чиновников?
Случаи К=0, К=1 и К=N -1, кажется, разобраны?

2Stranger:

ОК, признаю, что сформулировал ответ не совсем точно, хотя имелось в виду именно то, что разобрано в примере, замечания принимаю.

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

В общем, спасибо за конструктивную дискуссию, надеюсь, теперь, мы пришли к согласию.

2Sergiy Oliynyk. Спасибо за взаимоинтересный диалог. А о каком форуме речь?
>" Это решение было высказано на форуме..."

На rsdn.ru:

http://rsdn.ru/forum/?group=job

2Sergiy Oliynyk. Спасибо.

Если решаем задача А:
Когда чиновник знает только один ответ (стоящего непосредственно за ним) => ;
Решение можно модифицировать так:
Просто уходим от двоичной системы исчесления.
Кажадый чиновник называет следующим Разницу между колпаками одного цвета.
Напрмиер, Красных больше чем синих на три.
Соответсвенно зная предудущую озвученую разницу и разницу чиновников перед ним. Он одназночно может определить какой у него цвет.

2shma
И что это даст?

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