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

Тема в разделе "Университет", создана пользователем Grigoriy, 10 дек 2006.

  1. TopicStarter Overlay

    Grigoriy Заблокирован

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

    • Участник
    Рег.:
    08.09.2006
    Сообщения:
    1.282
    Симпатии:
    1
    Репутация:
    0
    Адрес:
    Toronto, Canada
    Оффлайн
    В каком порядке они пишут свои guess-ы и видят ли они что другие написали ? ;)
  3. TopicStarter Overlay

    Grigoriy Заблокирован

    • Заблокирован
    Рег.:
    11.02.2006
    Сообщения:
    4.117
    Симпатии:
    87
    Репутация:
    5
    Нарушения:
    31
    Оффлайн
    Пишут они по - отдельности, что написали другие - тоже не видят. Но ведь о чём-то они могли договориться :)
    Подсказка - ... Нет, не буду. :)
  4. drowsy Учаcтник

    • Участник
    Рег.:
    08.09.2006
    Сообщения:
    1.282
    Симпатии:
    1
    Репутация:
    0
    Адрес:
    Toronto, Canada
    Оффлайн
    Кстати, вот такая задачка :

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

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

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

    Grigoriy Заблокирован

    • Заблокирован
    Рег.:
    11.02.2006
    Сообщения:
    4.117
    Симпатии:
    87
    Репутация:
    5
    Нарушения:
    31
    Оффлайн
    Ну, эта задача простая :) Что интересно, что все неопределённости раскрываются однозначно. :)
  6. MS Михаил Семионенков

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    6.542
    Симпатии:
    3.361
    Репутация:
    175
    Оффлайн
    drowsy, не совсем понял, на что ловля. (Сейчас Саша придет и все раз'яснит :)
    Есть р>1/2 на конечную величину, то ставим на 2/3...

    Нет, не угадал. :mad:

    А Григорий - совсем жулик :). Намекает, что обмен информации возможен. Ну, если возможен, так я просто покажу визави образец из своего набора. Границы бы определить, когда обмен информацией возможен: как предварительный договор, во время показа или после.
  7. drowsy Учаcтник

    • Участник
    Рег.:
    08.09.2006
    Сообщения:
    1.282
    Симпатии:
    1
    Репутация:
    0
    Адрес:
    Toronto, Canada
    Оффлайн
    А что такое p ?
  8. MS Михаил Семионенков

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    6.542
    Симпатии:
    3.361
    Репутация:
    175
    Оффлайн
    drowsy, я пас - двое могут иметь по 0.5 при любом варинте.
    "Честного" решения, вроде, быть не может.

    Р - постериорная вероятность горения лампочки в камере
  9. drowsy Учаcтник

    • Участник
    Рег.:
    08.09.2006
    Сообщения:
    1.282
    Симпатии:
    1
    Репутация:
    0
    Адрес:
    Toronto, Canada
    Оффлайн
    Р - постериорная вероятность горения лампочки в камере — а что это такое ? :)

    дайте чёткое определение. будте муж ... математиком. :)
  10. TopicStarter Overlay

    Grigoriy Заблокирован

    • Заблокирован
    Рег.:
    11.02.2006
    Сообщения:
    4.117
    Симпатии:
    87
    Репутация:
    5
    Нарушения:
    31
    Оффлайн
    Это гдей-то я и на что намекал? Нет, никакой обмен информацией не нужен. Совершенно чистая задача. Но мне решить не удалось :( Попробуйте для начала решить для N = 2, а не 100 - это совсем просто. Впрочем, и в общем случае решение занимает 2 строчки - 1- на ответ, 1- на доказательство его правильности. :)
    И какие трудности с задачей drowsy? Там же всё ясно, Только надо предел не 2/3, а, скажем, 2/5. Или 1/2
  11. TopicStarter Overlay

    Grigoriy Заблокирован

    • Заблокирован
    Рег.:
    11.02.2006
    Сообщения:
    4.117
    Симпатии:
    87
    Репутация:
    5
    Нарушения:
    31
    Оффлайн
    Наврал конечно :( Надо подумать ещё. drowsy, не придирайтесь, совершенно ясно, что имеет ввиду МС
    Подумал. Да, видимо МС прав.
  12. drowsy Учаcтник

    • Участник
    Рег.:
    08.09.2006
    Сообщения:
    1.282
    Симпатии:
    1
    Репутация:
    0
    Адрес:
    Toronto, Canada
    Оффлайн
    предел ? какой ещё предел ? а он существует ?
  13. TopicStarter Overlay

    Grigoriy Заблокирован

    • Заблокирован
    Рег.:
    11.02.2006
    Сообщения:
    4.117
    Симпатии:
    87
    Репутация:
    5
    Нарушения:
    31
    Оффлайн
    Имелся в виду не lim, а число, начиная выше которого надо говорить 2, а ниже - 1
  14. drowsy Учаcтник

    • Участник
    Рег.:
    08.09.2006
    Сообщения:
    1.282
    Симпатии:
    1
    Репутация:
    0
    Адрес:
    Toronto, Canada
    Оффлайн
    вообще ничего не понял. Напишите чётко решение :)
  15. MS Михаил Семионенков

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    6.542
    Симпатии:
    3.361
    Репутация:
    175
    Оффлайн
    drowsy, Вы, вижу, пацан реальный: Ваши кореша пожизненный срок честно отсидели и на волю вышли.
    Нам, фраерам, нужно Вам в рот смотреть. Начните, что такое бесконечное число дней, статья какая, что такое случайно, а я постараюсь базар подхватить.

    Григорий, спасибо за подсказку. Похоже, для 2 я решил. Обобщение сходу не осилил. "Честной" задача все-таки не считаю. Мои выводы пока такие (поправьте, если заблудился):

    1. нет одной стратегии, которой следуют все. Мудрецы должны быть пронумерованы, и и-тый следует и-той стратегии. Задача может быть поправлена: мудрецы представляются друг другу по очереди: первый - всем остальным, второй - всем остальным и т.д.
    2. Пока гипотеза. Цвета тоже должны быть упорядочены (пронумерованы) единообразно для всех.
  16. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Начнем с двух мудрецов.
    Если мудреца 2, то первый называет цвет который видит на втором, а второй цвет которого нет на первом.
    Один из них всегда угадает (всего четыре случая, так что легко проверить)
    ...
  17. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Всё, решил :)
    Вообще можно давать как олимпиадную третьеклассникам :)
    решение отправил в "личку".
  18. TopicStarter Overlay

    Grigoriy Заблокирован

    • Заблокирован
    Рег.:
    11.02.2006
    Сообщения:
    4.117
    Симпатии:
    87
    Репутация:
    5
    Нарушения:
    31
    Оффлайн
    Да, конечно. Я Вам ответил - как я это записываю :)
    Ну Вы как всегда - третьеклассникам :) Матёрный олимпиадник(участвовал, был отв серетарём Московской олимпиады, составил сборник задач оной)(и, кстати, один из авторов Каиссы) на вопрос, как он рассуждал при решении, ответил - "Повезло" :):
    http://zavalinka.org/read.php?id=176991
  19. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Я не помню, но эта тема вроде проходится в третьем классе (правда у нас вроде олимпиады начинались с четвертого)
    Могу дать сравнение - в девятом классе на последнем туре городской я влетел на задачу о семи мостах.
    Может ли её решить человек за четыре часа, заранее не зная решения? :)
  20. TopicStarter Overlay

    Grigoriy Заблокирован

    • Заблокирован
    Рег.:
    11.02.2006
    Сообщения:
    4.117
    Симпатии:
    87
    Репутация:
    5
    Нарушения:
    31
    Оффлайн
    И ещё насчёт третьеклассников. В своё время я - с величайшим удивлением, нашёл "автоматическое" д-во теоремы Кантора-Бернштейна ( (A~B' & B~A') —> A~B) - т е автоматически получающееся как только спросим: "А как?" Не такое красивое, как у Келли, но по существу тоже)то, что у Келли получается после разглядывания этого)
  21. drowsy Учаcтник

    • Участник
    Рег.:
    08.09.2006
    Сообщения:
    1.282
    Симпатии:
    1
    Репутация:
    0
    Адрес:
    Toronto, Canada
    Оффлайн
    2 Grigoriy — Это что за док-во теоремы Кантора-Бернштейна такое ? Расскажите.

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

    Grigoriy Заблокирован

    • Заблокирован
    Рег.:
    11.02.2006
    Сообщения:
    4.117
    Симпатии:
    87
    Репутация:
    5
    Нарушения:
    31
    Оффлайн
    Да док-во само по себе стандартное. Оно же видимо приведено и у Дьёдонне("Основы") и у Шилова("Анализ-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
    Вот и всё.
  23. MS Михаил Семионенков

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    6.542
    Симпатии:
    3.361
    Репутация:
    175
    Оффлайн
    Стратегия: если отношение времени, когда лампочка горела, к общему времени заключения превышает 0.5 на конечную величину, голосовать за 2 лампочки.
    Если если отношение времени, когда лампочка горела, к общему времени заключения меньше 0.5 на конечную величину, голосовать за 1 лампочку.
    Если если отношение времени, когда лампочка горела, к общему времени заключения равно 0.5 (+- б.м. величина) голосовать за 2 лампочки, если в последний день заключения лампочка горела, и за 1 - если не горела.
  24. drowsy Учаcтник

    • Участник
    Рег.:
    08.09.2006
    Сообщения:
    1.282
    Симпатии:
    1
    Репутация:
    0
    Адрес:
    Toronto, Canada
    Оффлайн
    Блин, MS, общее время заключения бесконечно. Общее время,когда горела лампочка может быть конечно, а может быть и бесконечно. Последнего дня заключения нет, как и нет наибольшего натурального числа !!!!(иначе просто те, у кого она в посл. день горела говорят за, остальные против)

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


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

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


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

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Если горит лампочка, то говорит что горит две, если не горит, то говорит что одна.
  26. drowsy Учаcтник

    • Участник
    Рег.:
    08.09.2006
    Сообщения:
    1.282
    Симпатии:
    1
    Репутация:
    0
    Адрес:
    Toronto, Canada
    Оффлайн
    хм, для n=4 в задачке Grigoriy-a получилось не меньше 1536 вариантов. Забавно, что самый очевидный вариант дааааалеко не единственный. Даже с учётом того, что можно хвостик переставлять.
  27. MS Михаил Семионенков

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    6.542
    Симпатии:
    3.361
    Репутация:
    175
    Оффлайн
    drowsy, какой нафиг последовательностью Вы меня хотите запугать? И о какой строгости Вы говорите "По истечении бесконечного числа дней". Умерла - значит умерла. На момент истечения, раз он был, у меня есть указанное отношение. Если двое имеют по 0.5 (плюс-минус бесконечно малое), а последнего дня не было, ничего мудрецам не сделать. 1-ый, 3-ий, 5-ый день лампочка горит у первого, 2-ой, 4-ый и т.д. - у второго. Все прекрасно сойдется к 0.5, и что заставит этих двоих проголосовать по-разному, если обмена информацией и предварительного сговора не было?
  28. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    В задачке Григория - решение действительно подвласно третьеклассникам.
    Если дать на городской олимпиаде - то кто-нибудь решит. :)
  29. drowsy Учаcтник

    • Участник
    Рег.:
    08.09.2006
    Сообщения:
    1.282
    Симпатии:
    1
    Репутация:
    0
    Адрес:
    Toronto, Canada
    Оффлайн
    Кстати, NS, расскажите какое там у вас решение в одну строчку ? С переходом к числам по модулю n или нет ? Просто своё решение я бы не взялся 3-е классникам объяснять. :)

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

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    6.542
    Симпатии:
    3.361
    Репутация:
    175
    Оффлайн
    NS, Грирорий - Только не публикуйте пока: я еще обобщение не схватил, не теряю надежды.

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

    • Участник
    Рег.:
    08.09.2006
    Сообщения:
    1.282
    Симпатии:
    1
    Репутация:
    0
    Адрес:
    Toronto, Canada
    Оффлайн
    Вы, кажется, не понимаете условие задачи совершенно. Чем вам не нравится бесконечное число дней ?
    Это мат. абстракция такая. Замените это тем, что мудрецы сидят в особых камерах, в которых течение времени ускоряется в два раза каждую секунду(а сами они не старятся). Или что интервалы времени, называемые днями, уменьшаются в два раза каждый раз.
    То есть первый день проходит за день. Второй за половину нормального дня. И так далее.
    Понятно, что все эти включения-выключения промелькнут у них перед глазами за два дня. При этом считается, что мудрецы умные и могут всё заметить и запомнить, когда горело, а когда нет, хоть и очень быстро всё происходит.

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

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    6.542
    Симпатии:
    3.361
    Репутация:
    175
    Оффлайн
    Спасибо за совет. Повторяю просьбу: укажите строгое решение для указанного случая:
    В камере 1 лампочка горит все нечетные дни, в камере 2 - все четные.
  33. drowsy Учаcтник

    • Участник
    Рег.:
    08.09.2006
    Сообщения:
    1.282
    Симпатии:
    1
    Репутация:
    0
    Адрес:
    Toronto, Canada
    Оффлайн
    MS, стратегия мудрецами выбирается до того, как их сажают в камеры.
    И какие бы посл. вы не приводили, решение будет одно и тоже.

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

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    6.542
    Симпатии:
    3.361
    Репутация:
    175
    Оффлайн
    Низачот. Честно говоря, не вижу даже, как предварительный сговор может облегчить ситуцию.
    Ситуация в камерах 1 и 2 абсолютно эквивалентна. Поскольку априори не известно, какая пара может оказаться в такой ситуации, не ясно, о чем можно договориться. Надобности в аппарате не вижу, поскольку он может пригодиться для доказательства общего случая, я же опровергаю, для этого один конкретный пример вполне достаточен.
  35. MS Михаил Семионенков

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    6.542
    Симпатии:
    3.361
    Репутация:
    175
    Оффлайн
    И это говорит математик? Если у Вас есть решение, работающее вообще, то оно сработает и на моей конкретной последовательности. А если в задаче дыра - так и скажите: тут все свои, Ваши студенты сюда, наверное, не заглядывают.

Поделиться этой страницей