В одной стране было очень много бюрократов. Ну очень много.
Мудрый правитель этой страны решил от них избавиться хитрым способом: построить в колонну по одному, надеть каждому на голову колпак, белого или чёрного цвета и с хвоста колонны спрашивать у каждого - какого цвета колпак у него на голове. Угадал - живи, не угадал - в расход.
Каждый стоящий в колонне видит цвета колпаков всех стоящих впереди, но не видит свой цвет и цвета стоящих сзади. Последний в колонне - видит цвета вообще всех колпаков, кроме своего. Ответ каждого бюрократа слышат все в колонне.
Так как правитель был действительно мудрый, он дал возможность бюрократам договориться между собой накануне.
Бюрократы были не такие мудрые, поэтому в итоге казнили половину: кому как повезло.
Как бюрократы должны были действовать, чтобы минимизировать свои потери? Сколько бы из них гарантированно выжило?
Комментарии
demiurg
#cid182
Ответить
Поскольку их было 50% на 50%, то достаточно узнать общее количество белых и черных последнему, то есть:
если в цепочке будет 100 белых колпаков и 99 черных, то у последнего оставшийся черный.
Таким образом, просто каждый бюракрат должен спросить у взади стоящего свой цвет. Передавая по цепочке видящие цвет соседа, можно посчитать сколько белых и сколько черных.
Вообщем задача не интересная.
#cid183
Ответить
Колпаков - не 50/50, просто - белые и чёрные, их соотношение неизвестно, произвольное количество.
Бюрократ не может спросить стоящего сзади о цвете своего колпака, он видит только цвета впередистоящих, а рот открыть сможет только тогда, когда его спросят о его цвете.
То, что половина была казнена - это лирика, к условию задачи не имеет отношения. Ну, просто по теории вероятностей получается так, что если они не договорятся и будут называть произвольные цвета - погибнет примерно половина.
Ещё раз условия задачи, без лирики:
1. Стоит колонна бюрократов, колонна по одному, спина к спине.
2. На них одеты колпаки двух цветов: чёрного или белого, одеты абсолютно произвольно.
3. Так как бюрократы стоят друг за дружкой, то каждый из них видит только колпаки впередистоящих.
4. Опрос ведётся с конца колонны, сзади.
5. Ответ каждого слышат все бюрократы в колонне.
Какая стратегия должна быть у бюрократов, чтобы минимизировать потери?
Сколько в этом случае выживет гарантированно?
Именно гарантированно, потому что теория вероятностей - злая штука, по ней они могут и все погибнуть.
#cid184
Ответить
Задача компании ABBYY при приёме на работу. Одна из многих.
Reisende
#cid191
Ответить
Возможно, они договорились, что каждый называет цвет впереди стоящего. Вероятность последнего погибнуть 50/50, а вот человек стоящий впереди будет знать свой цвет. Однако при таком раскладе когда перед чёрным стоит белый, и чёрный знает что он чёрный,
сказав белый он подписывает себе приговор (тут зависит от бюрократа, но я бы сказал свой цвет).
P.S. проснусь и подумаю нормально, заодно прочту приговор этой версии. (скорее всего не верной)
Reisende
#cid192
Ответить
Решение:
по условию у бюрократов было время договориться. и если они хотели жить то должны были действовать так:
Последний называет цвет колпака впереди стоящего. Теперь впереди стоящий знает свой цвет, и если перед ним тот же цвет он его просто называет, если передним другой он говорит: - у меня не...
Пример:
Цепочка такая Б5-Ч4-Ч3-Б2-?1
?1 (первый с конца его шансы 50/50, пожелаем ему удачи)- белый
Б2 (тут если сказать черный убьют, если сказать белый нарушается система) он должен сказать- у меня не чёрный
Ч3 - чёрный
Ч4- у меня не белый
и тд
В итоге максимальная потеря 1 человек, хотя я верю что ему повезло...
#cid193
Ответить
> он говорит: - у меня не...
Они могут сказать только цвет. Только одно слово - «Черный» или «Белый».
Иначе ответ действительно можно обвесить дополнительными сигналами, типа «У меня светлый», «У меня не ч0рный» и т.д.
Смысл задачи теряется.
Поэтому - неправильно, условие не соблюдено.
По первому варианту ответа: 50% гарантированно выживших - маловато.
Сергей.
#cid7238
Ответить
все бы выжили кроме одного(последнего) если бы задние друг другу говорили
Никита
#cid92042
Ответить
Решение:
Бюрократы договариваются о нескольких правилах:
Если на впередистоящем бюрократе колпак черный, то бюрократ, которого спрашивают, должен после того, как спрашивающий замолчит, выждать таймаут не менее 20 секунд (а куда торопиться?) а затем сказать свой цвет (при этом следующий бюрократ должен слышать того, кто спрашивает). Если колпак белый, то ответ нужно назвать сразу (но не спеша). Таким образом он дает понять следующему о его цвете.
Слышат ли бюрократы того, кто спрашивает?
Второй вариант: Такой же как и первый, только отсчет времени начинается не с момента, когда спрашивающий замолчит (его не слышно), а с того момента, когда последовал ответ предыдущего бюрократа. Если на впередистоящем бюрократе колпак черный, то бюрократ должен назвать ответ через 40 (80, 120, 160 итд) секунд после ответа предыдущего бюрократа, если колпак белый, то через 20 (60, 100, 140 итд) секунд.
Во втором варианте гарантированно выживают все бюрократы кроме последних двух (ведь чтобы бюрократу узнать свой цвет, нужно замерить время между двумя предыдущими ответами).
#cid92056
Ответить
#cid92042, Никита
Кстати, отличный вариант!