Задачка о шапках

Дима · Сообщение **Дима** » 05 окт 2006, 09:32

Вроде, эта задачка на форуме еще не предлагалась, но если была, то извините

Итак, 10 человек выстраиваются в затылок друг другу. На голове у каждого - черная или белая шапка. Каждый видит шапки, надетые на впередистоящих(и, соответственно, не видит ни своей, ни тех, которые сзади). Стоящий последним говорит "черная" или "белая"(и все слышат, что он сказал). После этого предпоследний говорит "черная" или "белая". И так далее, до 1-го. При этом если говорящий называет цвет СВОЕЙ шапки, команда получает очко. Вопрос. О какой стратегии должны договориться эти 10 человек, чтобы количество очков было максимальным ? И каким будет это количество ?
Пример одной из стратегий: говорящий первым называет цвет шапки соседа спереди, а тот потом просто повторяет это слово. Стоящий 3-им с конца называет цвет шапки 4-го с конца. И так далее. При этом мы ТОЧНО угадаем цвет 5 шапок, а остальные 5 - с вероятностью 50%. Итого , в среднем, 7.5 очков. Кто больше ?

anton2 · Сообщение **anton2** » 05 окт 2006, 16:34

9 гарантировано + 1 с вероятностью 0.5 (в среднем 9.5)

Ключевое слово - четность.

Yury · Сообщение **Yury** » 05 окт 2006, 19:41

зависит от того сразу они узнают результат ответа, или только когда все назвали цвет

Дима · Сообщение **Дима** » 05 окт 2006, 21:27

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

При этом получается 8.5. Ключевое слово "четность" помогает увеличить результат до 9.5

anton2 · Сообщение **anton2** » 06 окт 2006, 09:00

Yury писал(а):зависит от того сразу они узнают результат ответа, или только когда все назвали цвет

Привет

Не зависит на самом деле, после того как 10-ый сказал, все остальные могут догадаться (учитывая цвета шапок впередистоящих и то что сказали те кто сзади).

Yury · Сообщение **Yury** » 06 окт 2006, 09:49

anton2 писал(а):
Yury писал(а):зависит от того сразу они узнают результат ответа, или только когда все назвали цвет
Привет
Не зависит на самом деле, после того как 10-ый сказал, все остальные могут догадаться (учитывая цвета шапок впередистоящих и то что сказали те кто сзади).

и точно...

трудно нормальному человеку думать в двоичной системе

Earl Grey · Сообщение **Earl Grey** » 06 окт 2006, 13:50

Вот другая "шапочная задача":

В одной очень престижной фирме открылась вакансия на очень престижную позицию. Заявлений было подано видимо-невидимо, но по результатам очень тщательного отбора и собеседований осталось пять претендентов, которые продемонстрировали абсолютно одинаковые профессиональные качества. Отборочная комиссия оказалась в затруднении, и чтобы выбрать единственного победителя, решила провести соревнование на сообразительность.
Для этого испытуемым было объявлено, что им предстоит пройти тест, и чтобы тест был справедливым, все они будут поставлены в одинаковые условия.
Суть теста заключается в следующем:
комиссия располагает шестью шапками, пять из которых чёрные, а одна - белая. Испытуемых сажают за круглый стол (таким образом, чтобы каждый мог видеть остальных и, тем самым, шапки, которые будут на них одеты), им (испытуемым, а не шапкам, конечно же) завязывают глаза, и каждому на голову одевают одну из шапок. Затем им всем (т.е. опять таки испытуемым, а не шапкам) одновременно развязывают глаза, и тот, кто первый правильно назовёт цвет своей шапки, получит вакансию...

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

Yury · Сообщение **Yury** » 06 окт 2006, 14:00

Уникурсал Уникурсалыч писал(а):Вопрос - мог ли он это знать ?

да

(равные условия)

Earl Grey · Сообщение **Earl Grey** » 06 окт 2006, 14:46

Yury писал(а):
Уникурсал Уникурсалыч писал(а):Вопрос - мог ли он это знать ?
да

(равные условия)

ты знал!

Yury · Сообщение **Yury** » 06 окт 2006, 15:00

Уникурсал Уникурсалыч писал(а):
Yury писал(а):
Уникурсал Уникурсалыч писал(а):Вопрос - мог ли он это знать ?
да

(равные условия)
ты знал!

не, просто умный

ajkj3em · Сообщение **ajkj3em** » 07 окт 2006, 22:15

Уникурсал Уникурсалыч писал(а): комиссия располагает шестью шапками, пять из которых чёрные, а одна - белая.

есть другой вариант задачи, менее тривиальный.

человеков - три.
шапок - пять, две черных и три белых.
всем троим надевают белые.

самый умный догадывается, что у него белая. вопрос - как ?

anton2 · Сообщение **anton2** » 08 окт 2006, 16:16

ajkj2em писал(а): есть другой вариант задачи, менее тривиальный.

человеков - три.
шапок - пять, две черных и три белых.
всем троим надевают белые.

самый умный догадывается, что у него белая. вопрос - как ?

Примерно так: "допустим, у меня черная шапка. Тогда каждый из оставшихся двух подумал бы: "я вижу черную и белую шапку. Если бы на мне была черная, то тот на ком белая увидел бы две черных шапки и сразу же сказал бы что он знает какая у него шапка. Так как он ничего не сказал, на мне белая шапка". Но так как никто не догадался какая у него шапка, на мне не может быть черной шапки; следовательно - она белая"

Earl Grey · Сообщение **Earl Grey** » 08 окт 2006, 16:56

anton2 писал(а):
ajkj2em писал(а): есть другой вариант задачи, менее тривиальный.

человеков - три.
шапок - пять, две черных и три белых.
всем троим надевают белые.

самый умный догадывается, что у него белая. вопрос - как ?
Примерно так: "допустим, у меня черная шапка. Тогда каждый из оставшихся двух подумал бы: "я вижу черную и белую шапку. Если бы на мне была черная, то тот на ком белая увидел бы две черных шапки и сразу же сказал бы что он знает какая у него шапка. Так как он ничего не сказал, на мне белая шапка". Но так как никто не догадался какая у него шапка, на мне не может быть черной шапки; следовательно - она белая"

Дык, еще проще: условия для всех ОДИНАКОВЫЕ. Это значит, что все трое должны решать задачи с ОДИНАКОВЫМ условием! Если кто-то видит белую и черную, а кто-то две белые, то условия разные.

anton2 · Сообщение **anton2** » 08 окт 2006, 17:08

ajkj2em писал(а): есть другой вариант задачи, менее тривиальный.

человеков - три.
шапок - пять, две черных и три белых.
всем троим надевают белые.

самый умный догадывается, что у него белая. вопрос - как ?

Раз на то пошло, вот тогда еще менее тривиальный вариант (хотя и ближе к программированию чем к логике):

Дано: сколько человек (до 75), сколько разных цветов (от 2 до 5), сколько шапок каждого цвета (от 1 до 15), сколько шапок каждого цвета надето. Например предыдущую задачу можно описать как (3 человека, 2 шапки, всего: {2 черных, 3 белых}, надето: {0 черных, 3 белых}).

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

Задача: написать программу которая овечает на вопрос, "сколько раз потребуется спросить, пока все не догадаются какого цвета их шапка" для любого допустимого ввода?

Пример с той же задачей - после первого вопроса получаем ответы {"нет", "нет", "нет"}. После второго тоже самое. После третьего, каждый может догадаться что на нем белая шапка (то же самое рассуждение) и ответы будут {"да", "да", "да"}. Значит, овет - 3.

anton2 · Сообщение **anton2** » 08 окт 2006, 17:09

Уникурсал Уникурсалыч писал(а): Дык, еще проще: условия для всех ОДИНАКОВЫЕ. Это значит, что все трое должны решать задачи с ОДИНАКОВЫМ условием! Если кто-то видит белую и черную, а кто-то две белые, то условия разные.

Так в его варианте ничего не было сказано об одинаковых условиях.