Математические задачки. Морковкин, скучаем :-)

Фараон решил проверить, стоит ли ему кормить своих 100 мудрецов, или пришло время заменить. Он заказал шапки ста цветов - по 200 каждого, собрал мудрецов и сказал:
У Вас 3 часа на раздумье и договор. Вот Вам каждому по одной шапке каждого цвета, бумага, карандаши (фараон, естественно, был новохронологический, продвинутый). Завтра каждому наденут на голову шапку - какого цвета - Вы знать каждый про себя не будете. И покажут каждому всех других. И каждый должен написать - какого цвета шапка на нём. Если хоть один напишет правильно - будете жить и продолжать служить. Нет - всем отрубят головы.
Вопрос - могут ли мудрецы гарантированно сохранить свои головы и содержание?
Пояснение. Образцы даны мудрецам только как образцы - чтобы не напрягать их память запоминанием цветов.

В каком порядке они пишут свои guess-ы и видят ли они что другие написали ?

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

Кстати, вот такая задачка :

Сажают 3 мудрецов в 3 изолированные клетки, навечно. Идут дни, каждый день у каждого мудреца в комнате лампочка либо горит, либо нет(ей управляют снаружи). Так же после некоего неизвестного числа дней будет выбрана одна из двух стратегий(навечно) —
1) каждый день зажигать одну случайную лампочку
2) зажигать две случайных лампы.

По истечении бесконечного числа дней у каждого спрашивают какая стратегия была выбрана(а что было всё это время с другими мудрецами они понятия не имеют !). Если угадают хотя бы 2, то зашибись. Если только один или нуль, то капут. Что делать ?

в решении просьба учесть, что непонятно, когда же выбирают стратегию(а до этого лампочки просто рандомом зажигают), и то, что когда стратегия выбрана, то опять же зажигают в рандомных камерах лампочки. Хотя может это уже было тут ? Я решил эту задачку, но я математик...

Ну, эта задача простая Что интересно, что все неопределённости раскрываются однозначно.

А что такое p ?

Р - постериорная вероятность горения лампочки в камере — а что это такое ?

дайте чёткое определение. будте муж ... математиком.

Это гдей-то я и на что намекал? Нет, никакой обмен информацией не нужен. Совершенно чистая задача. Но мне решить не удалось Попробуйте для начала решить для N = 2, а не 100 - это совсем просто. Впрочем, и в общем случае решение занимает 2 строчки - 1- на ответ, 1- на доказательство его правильности.
И какие трудности с задачей drowsy? Там же всё ясно, Только надо предел не 2/3, а, скажем, 2/5. Или 1/2

Наврал конечно Надо подумать ещё. drowsy, не придирайтесь, совершенно ясно, что имеет ввиду МС
Подумал. Да, видимо МС прав.

предел ? какой ещё предел ? а он существует ?

Имелся в виду не lim, а число, начиная выше которого надо говорить 2, а ниже - 1

вообще ничего не понял. Напишите чётко решение

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

Всё, решил
Вообще можно давать как олимпиадную третьеклассникам
решение отправил в "личку".

Да, конечно. Я Вам ответил - как я это записываю
Ну Вы как всегда - третьеклассникам Матёрный олимпиадник(участвовал, был отв серетарём Московской олимпиады, составил сборник задач оной)(и, кстати, один из авторов Каиссы) на вопрос, как он рассуждал при решении, ответил - "Повезло" :
http://zavalinka.org/read.php?id=176991

Я не помню, но эта тема вроде проходится в третьем классе (правда у нас вроде олимпиады начинались с четвертого)
Могу дать сравнение - в девятом классе на последнем туре городской я влетел на задачу о семи мостах.
Может ли её решить человек за четыре часа, заранее не зная решения?

И ещё насчёт третьеклассников. В своё время я - с величайшим удивлением, нашёл "автоматическое" д-во теоремы Кантора-Бернштейна ( (A~B' & B~A') —> A~B) - т е автоматически получающееся как только спросим: "А как?" Не такое красивое, как у Келли, но по существу тоже)то, что у Келли получается после разглядывания этого)

2 Grigoriy — Это что за док-во теоремы Кантора-Бернштейна такое ? Расскажите.

2 NS — хорош решать задачки для 3-е классников, мою решите-ка.
Рандомно означает, что все возможные комбинации горения возможны и ваше решение должно работать на абсолютно любых комбинациях. Бесконечное число дней означает счётное, то есть бесконечная последовательность дней, занумерованных натуральными числами. Можете представить себе, что дни для мудрецов сокращаются вдвое, тогда всё пролетит за конечное время(помните, про Ахиллеса и черепаху ? ).

Да док-во само по себе стандартное. Оно же видимо приведено и у Дьёдонне("Основы") и у Шилова("Анализ-3") - "видимо" потому, что я их не разбирал, а на взгляд видимо тоже, и я их видел до. Интерес именно в "автоматичности". Итак:
f: A-->B
g: B-->A
f, g - иньекции
Надо построить изоморфизм А—>В Как? А что имеем? - только f и g.
Ну и начннём с f. Но ведь оно может не накрывать всё В! Не беда. На ненакрытой части есть g, и её накрываем g**(-1). Но тут мы теряем то, что накрывалось f с области в А, которую мы теперь отобразили посредством g**(-1). Так повторяем тот же трюк - накроем её той же самой g**(-1). И т д до бесконечности.
Т е меня поразило, что решение сложной задаци получилось автоматически, просто ничего другого не оставалось делать - нет выбора.
А вот как тоже по сути д-во изложено у Келли :

Можно считать, что А и В не пересекаются. Точку х назовём предшественником точки у, если у получается из х в результате последовательног применения f и g (или g и f). Разложим А в 3 множества:
А1- точки с чётным числом предшественников, А2 - с нечётным, А3 - с бесконечным. Аналогично В
Заметим, что f отображает А1 на В2, А3 на В3, а g**(-1) A2 на В1
Вот и всё.

Блин, MS, общее время заключения бесконечно. Общее время,когда горела лампочка может быть конечно, а может быть и бесконечно. Последнего дня заключения нет, как и нет наибольшего натурального числа !!!!(иначе просто те, у кого она в посл. день горела говорят за, остальные против)

Если вы хотите брать пределы, то сначала порадуйтесь такой последовательности :
0 111 0000000 1111111111111111111111111111111111111 00000000000000000000000000000000000000000000000000000000000000000000000000000
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111


и так далее, то есть 1 и 0 чередуются, причём интервалы когда посл. константа увеличиваются очень быстро, и среднее отношение всё время болтается между 0 и 1, приближаясь к ним как угодно близко(можно сделать такую посл., что у неё средние будут вообще к любому числу из [0,1] подходить сколь угодно близко бесконечно много раз, я студентам на экзаменах гораздо более тяжёлые задачи давал на посл.).

Я уже и не знаю, как объяснить, что решение должно быть строгим.


Grigoriy, я тут на коленке посчитал, что в вашей задачке, кроме простого решения есть много других, для n=3 получилось не меньше 24 разных стратегий, для больших n утром посчитаю, а сейчас спааааать.

Если горит лампочка, то говорит что горит две, если не горит, то говорит что одна.

хм, для n=4 в задачке Grigoriy-a получилось не меньше 1536 вариантов. Забавно, что самый очевидный вариант дааааалеко не единственный. Даже с учётом того, что можно хвостик переставлять.

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

Кстати, NS, расскажите какое там у вас решение в одну строчку ? С переходом к числам по модулю n или нет ? Просто своё решение я бы не взялся 3-е классникам объяснять.

ЗЫ Мою задачку даже студентам мехмата МГУ не всем дано решить.

Вы, кажется, не понимаете условие задачи совершенно. Чем вам не нравится бесконечное число дней ?
Это мат. абстракция такая. Замените это тем, что мудрецы сидят в особых камерах, в которых течение времени ускоряется в два раза каждую секунду(а сами они не старятся). Или что интервалы времени, называемые днями, уменьшаются в два раза каждый раз.
То есть первый день проходит за день. Второй за половину нормального дня. И так далее.
Понятно, что все эти включения-выключения промелькнут у них перед глазами за два дня. При этом считается, что мудрецы умные и могут всё заметить и запомнить, когда горело, а когда нет, хоть и очень быстро всё происходит.

Чтобы облегчить понимание, сначала разбератесь в парадоксе с Ахиллесом и черепахой, которая всегда впереди него. Потом поймите, почему у той посл., которую я привёл нет никакого предела, и вообще её средние скачут куда хотят. То есть аппарат пределов тут ну никак не применим(даже пределов в среднем!). Ну а тогда останется только понять, а какой, собственно, мат. аппарат тут можно применить. Для этого аппарата копайте на слово Банах. Ну или Стоун-Чех. Но это задачка для математиков, если хотя бы поймёте, что пределы тут не применимы, то это уже большой успех.

MS, стратегия мудрецами выбирается до того, как их сажают в камеры.
И какие бы посл. вы не приводили, решение будет одно и тоже.

Соответственно никакого решения для конкретного набора из посл. быть не может. Так как оно будет работать только на этом наборе. Это как с шапками. Указать решение для конкретного набора шапок — если есть в наборе шапка какого-то цвета, а вот пусть все 100 этот цвет и говорят. Один да угадает