В одной стране было очень много бюрократов. Ну очень много.
Мудрый правитель этой страны решил от них избавиться хитрым способом: построить в колонну по одному, надеть каждому на голову колпак, белого или чёрного цвета и с хвоста колонны спрашивать у каждого - какого цвета колпак у него на голове. Угадал - живи, не угадал - в расход.
Каждый стоящий в колонне видит цвета колпаков всех стоящих впереди, но не видит свой цвет и цвета стоящих сзади. Последний в колонне - видит цвета вообще всех колпаков, кроме своего. Ответ каждого бюрократа слышат все в колонне.

Так как правитель был действительно мудрый, он дал возможность бюрократам договориться между собой накануне.
Бюрократы были не такие мудрые, поэтому в итоге казнили половину: кому как повезло.

Как бюрократы должны были действовать, чтобы минимизировать свои потери? Сколько бы из них гарантированно выжило?


demiurg
2010.03.14 12:44:55
#cid182

Ответить

Поскольку их было 50% на 50%, то достаточно узнать общее количество белых и черных последнему, то есть:
если в цепочке будет 100 белых колпаков и 99 черных, то у последнего оставшийся черный.
Таким образом, просто каждый бюракрат должен спросить у взади стоящего свой цвет. Передавая по цепочке видящие цвет соседа, можно посчитать сколько белых и сколько черных.
Вообщем задача не интересная.

2010.03.14 14:12:06
#cid183

Ответить

Колпаков - не 50/50, просто - белые и чёрные, их соотношение неизвестно, произвольное количество.

Бюрократ не может спросить стоящего сзади о цвете своего колпака, он видит только цвета впередистоящих, а рот открыть сможет только тогда, когда его спросят о его цвете.

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

Ещё раз условия задачи, без лирики:

1. Стоит колонна бюрократов, колонна по одному, спина к спине.
2. На них одеты колпаки двух цветов: чёрного или белого, одеты абсолютно произвольно.
3. Так как бюрократы стоят друг за дружкой, то каждый из них видит только колпаки впередистоящих.
4. Опрос ведётся с конца колонны, сзади.
5. Ответ каждого слышат все бюрократы в колонне.

Какая стратегия должна быть у бюрократов, чтобы минимизировать потери?
Сколько в этом случае выживет гарантированно?

Именно гарантированно, потому что теория вероятностей - злая штука, по ней они могут и все погибнуть.

2010.03.14 14:13:18
#cid184

Ответить

Задача компании ABBYY при приёме на работу. Одна из многих.

Reisende
2010.03.25 02:03:39
#cid191

Ответить

Возможно, они договорились, что каждый называет цвет впереди стоящего. Вероятность последнего погибнуть 50/50, а вот человек стоящий впереди будет знать свой цвет. Однако при таком раскладе когда перед чёрным стоит белый, и чёрный знает что он чёрный,
сказав белый он подписывает себе приговор (тут зависит от бюрократа, но я бы сказал свой цвет).

P.S. проснусь и подумаю нормально, заодно прочту приговор этой версии. (скорее всего не верной)

Reisende
2010.03.25 03:45:13
#cid192

Ответить

Решение:
по условию у бюрократов было время договориться. и если они хотели жить то должны были действовать так:
Последний называет цвет колпака впереди стоящего. Теперь впереди стоящий знает свой цвет, и если перед ним тот же цвет он его просто называет, если передним другой он говорит: - у меня не...
Пример:
Цепочка такая Б5-Ч4-Ч3-Б2-?1
?1 (первый с конца его шансы 50/50, пожелаем ему удачи)- белый
Б2 (тут если сказать черный убьют, если сказать белый нарушается система) он должен сказать- у меня не чёрный
Ч3 - чёрный
Ч4- у меня не белый
и тд

В итоге максимальная потеря 1 человек, хотя я верю что ему повезло...

2010.03.25 10:18:09
#cid193

Ответить

> он говорит: - у меня не...

Они могут сказать только цвет. Только одно слово - «Черный» или «Белый».
Иначе ответ действительно можно обвесить дополнительными сигналами, типа «У меня светлый», «У меня не ч0рный» и т.д.

Смысл задачи теряется.
Поэтому - неправильно, условие не соблюдено.

По первому варианту ответа: 50% гарантированно выживших - маловато.

Сергей.
2011.10.31 21:42:20
#cid7238

Ответить

все бы выжили кроме одного(последнего) если бы задние друг другу говорили

Никита
2018.05.16 21:01:55
#cid92042

Ответить

Решение:

Бюрократы договариваются о нескольких правилах:

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

Слышат ли бюрократы того, кто спрашивает?

Второй вариант: Такой же как и первый, только отсчет времени начинается не с момента, когда спрашивающий замолчит (его не слышно), а с того момента, когда последовал ответ предыдущего бюрократа. Если на впередистоящем бюрократе колпак черный, то бюрократ должен назвать ответ через 40 (80, 120, 160 итд) секунд после ответа предыдущего бюрократа, если колпак белый, то через 20 (60, 100, 140 итд) секунд.

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