У царя есть 1000 людей. Он выстраивает их в колонну и надевает на каждого шляпу либо черного, либо красного цвета. При этом каждый человек в колонне видит только шляпы впереди стоящих. Царь спрашивает у последнего человека (который видит шляпы всех остальных), какого цвета у него шляпа. Если человек отвечает неправильно, царь казнит его, а если правильно, то оставляет в живых. Затем он задает такой же вопрос 999-ому человеку, и т. д. Перед этим люди могут договориться между собой. Для уважаемого nikolaykruzh...: каждый человек в ответ на вопрос говорит одно из двух слов:"черная" или "красная". Другие варианты ответа адекватный человек не даст, так как это сведет его шанс выжить к нулю. Все остальные каналы информации между людьми перекрыты.
Какое наибольшее количество человек можно гарантированно спасти?

Чтобы закончить все разногласия по поводу условия, заменю естественную и простую формулировку на формальную: Пусть $%M$% множество функций $%f:\{0;1\}^{999}\rightarrow\{0;1\}$%. Для набора $%(f_1,f_2,..,f_{1000},a_1,a_2,..,a_{1000})$% определим набор $%(h_1,..,h_{1000})$%, такой что $%h_{1000}=f_{1000}(a_1,..,a_{999}) ,h_{i-1}=f_{i-1}(a_1,..,a_{i-2},h_i,..,h_{1000})$%Пусть $%g:M^{1000}\times\{0;1\}^{1000}\rightarrow\mathbb{N}$%, такая, что $%g(f_1,f_2,..,f_{1000},a_1,a_2,..,a_{1000})$% равно числу таких $%i:1\leq i\leq 1000$%, что $%h_i=a_i.$% Найти $%\max_{f_1,f_2,..,f_{1000}\in M}\min_{a_1,a_2,..,a_{1000}\in\{0;1\}} g(f_1,f_2,..,f_{1000},a_1,a_2,..,a_{1000})$%

задан 30 Сен '12 20:17

изменен 3 Окт '12 19:27

Знают ли люди, казнили ли тех, кто был перед ними?

(30 Сен '12 21:11) chameleon

Да, они знают.

(30 Сен '12 21:27) dmg3

Да, иначе у них не будет информации

В моем алгоритме этого знать не нужно, но нужно слышать все, что ответили предыдущие. Это тоже информация. А это возможно?

(30 Сен '12 21:46) DocentI

Да, вы правы

(30 Сен '12 22:03) dmg3

По моему мнению, такие задачки адресованы DocentI и аналогичным "математикам до мозга костей".

(1 Окт '12 16:49) Галактион

Точно! Есть в них что-то эзотерическое...

(1 Окт '12 19:16) DocentI
1

@nikolaykruzh..., Вы неправильно поняли @aapetrov (кстати, автора вопроса). Он пишет, что по методу ASailyan могут погибнуть все.
Возможность "шептать друг другу на ухо" никак в задаче не предусмотрена. Тогда давайте уж сразу поставим где-нибудь рядом зеркало. Или дадим в руки "наложнице".

Но вообще-то, конечно, такие задачи - некая игра, "правила" которой, даже и неписанные, понятны посвященным. По-моему, все, кроме Вас (и Галактиона?) в результате поняли задачу одинаково.

(2 Окт '12 21:20) DocentI

Мне приятно быть в компании с Галактионом, но боюсь, что он предпочтёт быть в компании с Вами, нежели со мною... Автор, каковы способы договора ДО ТОГО? К примеру, 1000-я отвечает царю (999-й): "Ч-чёрная", и та понимает, что шляпа на ней красная, и наоборот. Или она царю говорит на ухо, чтобы 999-я не слыхала? Царь за два "ч" отрубит голову? Вообще, ДО ТОГО они знают, что царь на них будет надевать шляпы, а не, извините, рейтузы? Если хоть как-то не сопроводить свой ответ предварительным договором, то задача вероятностная, т. е. не имеет точного, гарантированного решения.

(2 Окт '12 22:46) nikolaykruzh...

@aapetrov задал вопрос, я ответила, он согласился. Мы друг другом довольны! А третий, извините, лишний...

(2 Окт '12 23:10) DocentI

И всегда-то и везде-то я лишний. Стоя вместе с наложницами в строю, я не сумел бы посчитать количество шляп впереди меня даже одного цвета, а тем более двухцветных - с тем, чтобы определить, делится число на два или нет? Мне наверняка отсекли бы голову, потому что даже я, мужчина, дальше 10 считать в то время не умел бы. А уж женщина-а-а...! Автор и ответчица - только двое спаслись бы, потому что у них высшее специальное образование (хотя и за них у меня опасения есть!). Поэтому они друг другом довольны, а что касается всех остальных - да плевать на них!

(3 Окт '12 0:27) nikolaykruzh...
показано 5 из 10 показать еще 5
10|600 символов нужно символов осталось
2

Можно модифицировать решение @Asailyan. Договориться, что последний человек, скажем, говорит "черная", если перед ним нечетное число черных шляп и "красная", если четное. Тогда предпоследний получает информацию, достаточную для того, чтобы узнать, какая у него шляпа. И все остальные тоже, так как они будут отслеживать, какие шляпы назвали и четное или нечетное число черных шляп в ряду с ним включительно.

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

Спасти гарантированно последнего человека не удастся, так как у него нет никакой информации.

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

ссылка

отвечен 30 Сен '12 21:41

изменен 2 Окт '12 22:24

1

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

(30 Сен '12 21:46) dmg3

Ну, это в теории! Избыточность кода всегда желательна в каналах с шумом. ;-)))

(1 Окт '12 16:44) DocentI
10|600 символов нужно символов осталось
0

"....-и т. д. Перед этим люди могут договориться между собой." Если перед этим каждый скажет впереди стоящего какого цвета у него шляпа,то можно спасти 998 человек.

ссылка

отвечен 30 Сен '12 21:33

@Docenti , да, они договариваются об алгоритме до того, как им надели шляпы, но что мешает договориться им отвечать на вопрос царя цвет шляпы впереди стоящего. @ASailyan, вы не доказали что это число наибольшее.

(30 Сен '12 21:43) dmg3

Отвечать цвет впереди стоящего - значит, жертвовать собой. Он-то узнает, а я-то погибну, если у меня шляпа другого цвета!
Конечно, одним человеком пожертвовать придется, тут уж ничего не поделаешь!

(30 Сен '12 21:54) DocentI

Если действовать по способу @ASailyan, то цвет своей шляпы может знать каждый, кроме последнего. А последний - повезёт или нет? 999.

(30 Сен '12 22:03) nikolaykruzh...
1

Может быть я неправильно понял, но если цвета шляп чередуются, то погибнут все

(30 Сен '12 22:13) dmg3

@nikolaykruzh.., главное не знать, главное - выжить!

(30 Сен '12 23:35) DocentI

Царь оставляет в живых тех, кто правильно называет цвет своей шляпы. 999 человек знают это, кроме последнего, 1000-го. А почему стоит проблема выжить? Или, как всегда в обществе, находятся те, кто не хочет добра людям? Таковым может оказаться последний, и он, из мстительного чувства, что может погибнуть, назовёт соседу ложный цвет? Но тогда - права @ASailyan: 998. А вообще задача не чётко поставлена: о чём и когда могут договориться несчастные? Что имели в виду авторы - "моему уму непостижимо" (Петька из "Чапаева")

(1 Окт '12 12:17) nikolaykruzh...

Да нет.Я просто подумала,что люди понимали намерение царья и стали договориваться после того как был кознен 1000-й человек. А тогда 999-й не может гарантированно спасен.

(1 Окт '12 15:29) ASailyan

@nikolaykruzh.., проблема "выжить" стоит по условию задачи. Если бы в вопросе утверждалось, что все 1000 человек - самоубийцы, решение было бы другим. Вы пишете, что 999 человек "знают это" (цвет шляпы) Откуда?
Если Вам непонятна задача - боюсь, это не вина авторов. Конечно, в математической текстовой задаче всегда есть элемент условности (нет такого царя, нет таких ситуаций, и 1000 человек просто физически не услышат, что говорится на другом конце "очереди").
Просто привычный к таким задачам математик понимает, где проходит граница между жизнью и задачей.

(1 Окт '12 16:41) DocentI

Жаль,кто то минусовал мой ответ. Я бы удалила его, но это было бы не честно,с ним удалятся 9 умных комметарии моих однофорумцев.

(1 Окт '12 20:15) ASailyan

@ASailyan, давайте я поставлю плюс. В конце концов, это первая попытка к решению, из которой выросло правильное решение. Это очень ценно!

(1 Окт '12 23:18) DocentI

Господа-товарищи! Речь идёт не о царе и его гареме(я так понимаю, что 1000 человек - это женщины, потому что мужчины для него - это воины, народ очень ценный!). Речь идёт об авторах, которые сотворили задачу, которую можно понимать, как угодно. Вот двое товарищей, мнение которых почему-то удалили, предположили, что погибнут все (напишу их по-русски: Галактион и Петров). И эту точку зрения нетрудно обосновать. Если задача понятна всем одинаково, почему такой разнобой в мнениях? Не бойтесь, уважаемая @DocentI: это не Ваша вина, а именно авторов, которых Вы берёте под своё крылышко.

(2 Окт '12 20:38) nikolaykruzh...

Прошу прощения: я не ответил на вопрос: откуда? Если в очереди стоят не шахидки, а нормальные женщины, 1000-я шепнёт 999-ой: "У тебя, подружка, чёрная шляпа", 999-я оповестит 998-ю: ".... красная..." и т. д. И только 1000-й никто ничего не скажет. Я именно так понял методу @ASailyan и счёл её разумной. Но в условии задачи об этом - ни слова, и, естественно, я не понял, "где проходит граница между жизнью и задачей". Но я себе это, с Вашего позволения, простил, как непривычный к таким задачам нематематик. "Элемент условности" не должен выпирать за пределы разумности - это теорема, не треб. док.!

(2 Окт '12 21:06) nikolaykruzh...
показано 5 из 12 показать еще 7
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×958
×29

задан
30 Сен '12 20:17

показан
703 раза

обновлен
3 Окт '12 19:27

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru