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

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

  1. Guest

    Рег.:
    Сообщения:
    0
    Симпатии:
    0
    Репутация:
    0
    Онлайн
    Ну вот, а я-то голову ломал, пытаясь понять, каково-же условие задачи на самом деле :)
  2. Kir Старожил

    • Участник
    • Старожил
    Рег.:
    08.02.2007
    Сообщения:
    1.207
    Симпатии:
    223
    Репутация:
    22
    Оффлайн
    Ув. drowsy еще здесь? Очень меня заинтересовала эта задачка. Доказать, что нужной стратегии нет не получается, найти ее тоже пока не могу. Я еще подумаю, просто хочу убедиться, что есть возможность узнать ответ.
  3. drowsy Учаcтник

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

    Короче, нужно всё свести к последовательнастям чисел и функану, что, мол, нужно найти функционал(назовём его "обобщенный предел", с хорошими свойствами). Обобщённые пределы с хорошими свойствами(типа более-менее все свойства пределов + функционал должен быть определён для абсолютно всех последовательностей) существуют. Первым их научился строить Банах. Прочитать можно, вроде, в талмуде Иосида "функциональный анализ", но там доказано в слабом виде, только основные свойства доказаны(но для этой задачки хватит, полстранички, вроде, всё построение). Можно конструировать покруче функционалы. В принципе, во многих достаточно толстых книгах это должно быть. В разных книгах способы построения могут быть разными :lol:(ой как не хочется в золотою книгу...)

    Есть ещё какое-то симпатичное построение обобщенного предела через теорему о компактификации Стоуна-Чеха(о том, что можно компактифицировать пространство так, что все непрерывные функции однозначно продолжаться), но где можно прочитать я не помню. Зато, вроде, при таком способе все свойства функционала получаются почти бесплатно.
  4. TopicStarter Overlay

    Grigoriy Старожил

    • Участник
    • Старожил
    Рег.:
    10.02.2006
    Сообщения:
    4.100
    Симпатии:
    26
    Репутация:
    2
    Оффлайн
    drowsy, нехорошо так издеваться над человеком :) Но должен сказать, Вы так хорошо замаскировали задачу, что решение не приходит в голову :)
    Не ответил на ПМ, ибо не знаю, что ответить. Я мехматчик, но к математике и её преподаванию много лет не имею отношения - только решаю задачки, чтобы мозги не деревенели. Последний раз ( и единственный, кроме диплома) сделал самостоятельно в математике - доказал(по работе понадобилось) - что тело на подставке, колеблющейся гармонически с трением (покоя и скольжения) само начинает колебаться почти гармонически. Математики обычно говорят, что будет уход(по аналогии со случайным блужданием) - и я так думал. Но наверняка это было известно раньше :)
  5. drowsy Учаcтник

    • Участник
    Рег.:
    07.09.2006
    Сообщения:
    1.282
    Симпатии:
    1
    Репутация:
    0
    Адрес:
    Toronto, Canada
    Оффлайн
    Grigoriy, там и отвечать нечего. Аспирант-препод, который рисует x^3 пот трём точкам как прямую линию и элементарные пределы не может сделать, да и вообще за весь семинар ничего не может решить, это нечто.
    Ну там мне предположили, что, может, андерградуата тот чел не в математике делал, а в рисовании. Но это не по теме задачки.
  6. Kir Старожил

    • Участник
    • Старожил
    Рег.:
    08.02.2007
    Сообщения:
    1.207
    Симпатии:
    223
    Репутация:
    22
    Оффлайн
    А, хорошо что вы здесь. Один уточняющий вопрос - мудрецы отвечают независимо друг от друга или слышат ответы предшественников?
  7. drowsy Учаcтник

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

    • Участник
    • Старожил
    Рег.:
    08.02.2007
    Сообщения:
    1.207
    Симпатии:
    223
    Репутация:
    22
    Оффлайн
    Ясно, тогда придется подумать :)
  9. TopicStarter Overlay

    Grigoriy Старожил

    • Участник
    • Старожил
    Рег.:
    10.02.2006
    Сообщения:
    4.100
    Симпатии:
    26
    Репутация:
    2
    Оффлайн
    Кстати, drowsy, насчёт Вашей дымовой завесы. Как-то мне дали задачку: найти сечение 4-мерного куба 3-мерной гиперплоскостью перпендикулярной главной диагонали в центре. Я завёлся, день продумал, применил теорему Крейна-Мильмана, посчитал, представил. Сказал задачу Гене Архипову(вероятно знаете; мы вместе работали) - он призадумался секунд на 20 и выдал ответ :)
  10. drowsy Учаcтник

    • Участник
    Рег.:
    07.09.2006
    Сообщения:
    1.282
    Симпатии:
    1
    Репутация:
    0
    Адрес:
    Toronto, Canada
    Оффлайн
    Честно говоря, мне тоже ничего лучшего в голову не приходит. Хотя с моими скиллами в геометрии для меня такая задачка и в случае трёхмерного куба тяжела :lol: Я ж действ. анализом и эргодической теорией занимаюсь.
  11. jenya Ветеран

    • Ветеран
    Рег.:
    11.02.2006
    Сообщения:
    2.937
    Симпатии:
    4
    Репутация:
    0
    Оффлайн
    Правильно ли я понимаю, что утром лампочки включают (случайным образом, одну или две), а ночью - свет у всех выключен. Или мудрецам еще и спать не дают?
    Второй вопрос - как включаются лампочки до выбора стратегии? Случайное количество, случайным образом?
  12. drowsy Учаcтник

    • Участник
    Рег.:
    07.09.2006
    Сообщения:
    1.282
    Симпатии:
    1
    Репутация:
    0
    Адрес:
    Toronto, Canada
    Оффлайн
    Cчитайте что в той задачке день=сутки. Какая разница, спят они или нет ? Вы ещё спросите, чем их кормят :lol:
    Им же за бесконечное число дней любая баланда надоест.

    Говоря мат. языком, им каждый день дают нулик или единичку информации. Получается посл. из нулей и единиц.
  13. jenya Ветеран

    • Ветеран
    Рег.:
    11.02.2006
    Сообщения:
    2.937
    Симпатии:
    4
    Репутация:
    0
    Оффлайн
    То есть Вы имеете в виду, что "включить" - это не обязательно перевести лампочку из состояния "выключена" в состояние "включена", а просто щелкнуть выключателем?
    Вы не ответили на второй вопрос.
  14. drowsy Учаcтник

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

    Да как тюремщику в голову взбредёт, так и включают. Но только конечное число дней, а потом выбирают одну из стратегий. И тюремщик по ней, опять же, как ему в голову взбредёт, врубает либо всегда одну лампочку в день, либо всегда две.
  15. TopicStarter Overlay

    Grigoriy Старожил

    • Участник
    • Старожил
    Рег.:
    10.02.2006
    Сообщения:
    4.100
    Симпатии:
    26
    Репутация:
    2
    Оффлайн
    Ну, Гена вообще числовик :) Просто он классный математик и блестящий олимпиадник
  16. jenya Ветеран

    • Ветеран
    Рег.:
    11.02.2006
    Сообщения:
    2.937
    Симпатии:
    4
    Репутация:
    0
    Оффлайн
    Каждый день тюремщик производит некую операцию с тремя нулями?
    В результате которой (после выбора стратегии) получается комбинация с одной единчкой и двумя нулями, или с двумя единичками и одним нулем?
    И каждый мудрец получает временную последовательность из нулей и единичек?
    Если так, то я не очень понимаю в чем сложность.
  17. drowsy Учаcтник

    • Участник
    Рег.:
    07.09.2006
    Сообщения:
    1.282
    Симпатии:
    1
    Репутация:
    0
    Адрес:
    Toronto, Canada
    Оффлайн
    Сложность в том, что свет зажигают в случайных камерах, постоянно только кол-во горящих лампочек.
  18. jenya Ветеран

    • Ветеран
    Рег.:
    11.02.2006
    Сообщения:
    2.937
    Симпатии:
    4
    Репутация:
    0
    Оффлайн
    В чем проблема каждому мудрецу произвести усреднение по большому числу дней? Каждый считает сколько было светлых дней за три месяца и делит это число на 90, заменяя последовательность нулей и единичек последовательностью таких чисел. А дальше смотрит, вокруг чего колеблется последовательность (0.33 или 0.66). А вот что будет до выбора стратегии - надо прикинуть. Прикинул - колебания вокруг 4/7 или 1/2, если тюремщик может оставить свет выключенным.
  19. drowsy Учаcтник

    • Участник
    Рег.:
    07.09.2006
    Сообщения:
    1.282
    Симпатии:
    1
    Репутация:
    0
    Адрес:
    Toronto, Canada
    Оффлайн
    Не пойму решение. Вроде я пример выше приводил ? Допустим у мудреца посл. такая :
    10 нулей, 100 единиц, 1000 нулей, 10000 единиц, 1000000 нулей, 100000000000 единиц,
    100000000000000000000000000000 нулей, 1000000000000000000000000000000000000000000000000000000000000000000000000000 единиц, ну и так далее, идея понятна. Вокруг чего колеблется эта последовательность ?

    Она ж по синусу гуляет туда-обратно между 0 и 1 и к каждому числу из [0,1] подходит сколь угодно близко.
  20. jenya Ветеран

    • Ветеран
    Рег.:
    11.02.2006
    Сообщения:
    2.937
    Симпатии:
    4
    Репутация:
    0
    Оффлайн
    Ваша последовательность - нетипична. Я же предположил, что тюремщик действует случайным образом (в рамках выбранной стратегии - включать каждое утро одну или две лампочки), а значит получает типичные последовательности. Появление 1000000000000000000000000000000000000000000000000000000000000000000000000000 единиц подряд у одного мудреца аналогично сбору всех частиц в левом верхнем углу ящика. Таким образом, с вероятностью близкой к единице обычный физический метод, который я привел, сработает. Согласен, что можно придумать специальные случаи, когда это не так, но общее число этих специальных случаев пренебрежимо мало по сравнению с общим числом вариантов.

    P.S.
    Посмотрел обсуждение и увидел, что Вас интересует строгое математическое доказательство, учитывающее и специальные случаи.
  21. Kir Старожил

    • Участник
    • Старожил
    Рег.:
    08.02.2007
    Сообщения:
    1.207
    Симпатии:
    223
    Репутация:
    22
    Оффлайн
    Интересная задачка. Мой первый ответ оказался неверным.
  22. jenya Ветеран

    • Ветеран
    Рег.:
    11.02.2006
    Сообщения:
    2.937
    Симпатии:
    4
    Репутация:
    0
    Оффлайн
    Ответ: каждый мудрец считает сумму своей последовательности и делит ее на число членов последовательности. Если ответ меньше, чем 0.5 - выбирает единичную стратегию, если больше - двоечную.
  23. jenya Ветеран

    • Ветеран
    Рег.:
    11.02.2006
    Сообщения:
    2.937
    Симпатии:
    4
    Репутация:
    0
    Оффлайн
    drowsy, прокомментируете?
  24. drowsy Учаcтник

    • Участник
    Рег.:
    07.09.2006
    Сообщения:
    1.282
    Симпатии:
    1
    Репутация:
    0
    Адрес:
    Toronto, Canada
    Оффлайн
    я ж написал пример последовательности, для которой не работает. Ваше новое предложение с суммированием методом средних арифметических тоже падает на этом примере. А вообще решение я уже написал. Надо доказывать, что существуут функционал "обобщенный предел" с определёнными свойствами, расширяющий понятие предела на _все_ последовательности. Или просто воспользоваться теоремой о его существовании. Хотя студентам-математиком, конечно, надо про него знать

    PS функционал = линейный функционал
  25. jenya Ветеран

    • Ветеран
    Рег.:
    11.02.2006
    Сообщения:
    2.937
    Симпатии:
    4
    Репутация:
    0
    Оффлайн
    Честно говоря, не понял. Прежде чем объяснять свое решение, я хочу понять, какой ответ у задачи. Вопрос был: что надо делать мудрецам, чтобы два из трех угадали бы избранную стратегию. Каждый мудрец видит перед собой последовательность нулей и единичек. Что он с ней делает, чтобы сделать выбор? Считает некий обобщенный предел?
  26. drowsy Учаcтник

    • Участник
    Рег.:
    07.09.2006
    Сообщения:
    1.282
    Симпатии:
    1
    Репутация:
    0
    Адрес:
    Toronto, Canada
    Оффлайн
    >> Считать некий обобщенный предел?
    да. Вроде можно выписать формулу для него(у меня в конспектах есть нечто, но я не могу дать ссылку, в какой книге это есть), Банах так строил, но там довольно нетривиально, то ли инфимум от супремума неких сумм, то ли наоборот.
  27. jenya Ветеран

    • Ветеран
    Рег.:
    11.02.2006
    Сообщения:
    2.937
    Симпатии:
    4
    Репутация:
    0
    Оффлайн
    Понимаю. Интересно, в чем ошибочность моего решения. Пусть a_i, b_i, c_i - это три последовательности для трех мудрецов. Предлагаю рассмотреть для каждого мудреца такой объект: (сумма всех a_i при i от 1 до n)/n. Пусть n очень велико (гораздо больше индекса N, при котором произошел выбор стратегии), но я не устремляю n к бесконечности, так как предел может не существовать. В такой ситуации роль первых N членов незначительна, и можно сказать, что выбор стратегии происходит сразу. Итак, выберем это гигантское (но конечное) n и вычислим эти средние - получим числа A, B, C. Каждое из них - на интервале [0 1]. A+B+C равно 1 или 2, в зависимости от внешней стратегии. Мне кажется, что первый мудрец может сделать выбор: если A>0.5 - выбираем двойку, если A<0.5 - выбираем единичку, остальные - аналогично. В такой ситуации мне кажется невозможным исход, при котором ошибутся двое: скажем A<0.5, В<0.5, но A+B+C = 2 невозможно, как и A>0.5, В>0.5, но A+B+C = 1.
  28. drowsy Учаcтник

    • Участник
    Рег.:
    07.09.2006
    Сообщения:
    1.282
    Симпатии:
    1
    Репутация:
    0
    Адрес:
    Toronto, Canada
    Оффлайн
    в этом рассуждении такое кол-во ошибок, что комментировать я не буду, полезнее самому хотя бы в этом разобраться :p
  29. jenya Ветеран

    • Ветеран
    Рег.:
    11.02.2006
    Сообщения:
    2.937
    Симпатии:
    4
    Репутация:
    0
    Оффлайн
    Так нечестно! Я же не могу только задачи решать :)
    Скажите, в чем тут дело, а?
  30. drowsy Учаcтник

    • Участник
    Рег.:
    07.09.2006
    Сообщения:
    1.282
    Симпатии:
    1
    Репутация:
    0
    Адрес:
    Toronto, Canada
    Оффлайн
    1. момент когда выбирается стратегия не известен. Так что вы можете выбирать какое угодно большое число, но всё равно промазать. Метод, который учитывает только конечное число первых дней не может работать!

    2. средние не сходяться никуда — смотрите на пример. Так как конечное число первых членов ни на что не влияет, то посторяя единички миллиарды раз, мы забиваем всё,что было до этого, и предел идёт к 1. Потом идёт ещё больше нулей, они забивают всё, что было до этого, так что средние идут к нулю. А на самом деле для любого числа из [0,1] они к нему в какой-то момент подходят на любое наперёд заданное эпсилон, так что когда вы выбираете N случайное большое число, никаких 1/2 не будет, будет какая-то случайная хрень из [0,1].
  31. TopicStarter Overlay

    Grigoriy Старожил

    • Участник
    • Старожил
    Рег.:
    10.02.2006
    Сообщения:
    4.100
    Симпатии:
    26
    Репутация:
    2
    Оффлайн
    drowsy просто редиска, туман напускает. :)
    Решение же просто:
    если лампочка в последний день горит - мудрец называет 2-ую стратегию, не горит - 1-ую. Т. обр, имеем 2 верных ответа. :)
  32. drowsy Учаcтник

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

    • Ветеран
    Рег.:
    11.02.2006
    Сообщения:
    2.937
    Симпатии:
    4
    Репутация:
    0
    Оффлайн
    Я и не утверждал, что они сходятся. Из Вашего примера хорошо видно обратное - мне казалось, я четко сформулировал. Я только предположил, что возможно остановить игру на гигантском, но конечном n>>N, где N - индекс, при котором выбрана стратегия.
  34. jenya Ветеран

    • Ветеран
    Рег.:
    11.02.2006
    Сообщения:
    2.937
    Симпатии:
    4
    Репутация:
    0
    Оффлайн
    Ах черт, Grigoriy, - Ваше гораздо проще!
    Но я был близок :)
  35. drowsy Учаcтник

    • Участник
    Рег.:
    07.09.2006
    Сообщения:
    1.282
    Симпатии:
    1
    Репутация:
    0
    Адрес:
    Toronto, Canada
    Оффлайн
    Grigoriy, киньте сюда и теоремы Ферма тогда док-во :lol: может тоже кто поверит

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