|
У царя есть 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 
dmg3
показано 5 из 10
показать еще 5
|
|
Можно модифицировать решение @Asailyan. Договориться, что последний человек, скажем, говорит "черная", если перед ним нечетное число черных шляп и "красная", если четное. Тогда предпоследний получает информацию, достаточную для того, чтобы узнать, какая у него шляпа. И все остальные тоже, так как они будут отслеживать, какие шляпы назвали и четное или нечетное число черных шляп в ряду с ним включительно. Так удастся спасти 999 челвек. Правда, в теории: не запутаться очень трудно, а каждая ошибка повлечет за собой казнь. Правда, следующий человек с учетом этого может исправить ошибку. Спасти гарантированно последнего человека не удастся, так как у него нет никакой информации. Кстати, если не учитывать возможность ошибки, то испытуемым при таком алгоритме не нужно знать, ошибся кто-то до них, или нет. отвечен 30 Сен '12 21:41 
DocentI 1
Верно, и да им правда неважно знать казнили предыдущего, или нет. Но если написать это в условие, будет слишком большая подсказка
(30 Сен '12 21:46)
dmg3
Ну, это в теории! Избыточность кода всегда желательна в каналах с шумом. ;-)))
(1 Окт '12 16:44)
DocentI
|
|
"....-и т. д. Перед этим люди могут договориться между собой." Если перед этим каждый скажет впереди стоящего какого цвета у него шляпа,то можно спасти 998 человек. отвечен 30 Сен '12 21:33 
ASailyan @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 человек "знают это" (цвет шляпы) Откуда?
(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
|
Знают ли люди, казнили ли тех, кто был перед ними?
Да, они знают.
В моем алгоритме этого знать не нужно, но нужно слышать все, что ответили предыдущие. Это тоже информация. А это возможно?
Да, вы правы
По моему мнению, такие задачки адресованы DocentI и аналогичным "математикам до мозга костей".
Точно! Есть в них что-то эзотерическое...
@nikolaykruzh..., Вы неправильно поняли @aapetrov (кстати, автора вопроса). Он пишет, что по методу ASailyan могут погибнуть все.
Возможность "шептать друг другу на ухо" никак в задаче не предусмотрена. Тогда давайте уж сразу поставим где-нибудь рядом зеркало. Или дадим в руки "наложнице".
Но вообще-то, конечно, такие задачи - некая игра, "правила" которой, даже и неписанные, понятны посвященным. По-моему, все, кроме Вас (и Галактиона?) в результате поняли задачу одинаково.
Мне приятно быть в компании с Галактионом, но боюсь, что он предпочтёт быть в компании с Вами, нежели со мною... Автор, каковы способы договора ДО ТОГО? К примеру, 1000-я отвечает царю (999-й): "Ч-чёрная", и та понимает, что шляпа на ней красная, и наоборот. Или она царю говорит на ухо, чтобы 999-я не слыхала? Царь за два "ч" отрубит голову? Вообще, ДО ТОГО они знают, что царь на них будет надевать шляпы, а не, извините, рейтузы? Если хоть как-то не сопроводить свой ответ предварительным договором, то задача вероятностная, т. е. не имеет точного, гарантированного решения.
@aapetrov задал вопрос, я ответила, он согласился. Мы друг другом довольны! А третий, извините, лишний...
И всегда-то и везде-то я лишний. Стоя вместе с наложницами в строю, я не сумел бы посчитать количество шляп впереди меня даже одного цвета, а тем более двухцветных - с тем, чтобы определить, делится число на два или нет? Мне наверняка отсекли бы голову, потому что даже я, мужчина, дальше 10 считать в то время не умел бы. А уж женщина-а-а...! Автор и ответчица - только двое спаслись бы, потому что у них высшее специальное образование (хотя и за них у меня опасения есть!). Поэтому они друг другом довольны, а что касается всех остальных - да плевать на них!