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

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

  1. drowsy Учаcтник

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


    Я же вам привёл решение с шапками, которое работает на любом фикс. наборе, если набор известен :) , но не работает совсем на самом деле.
  2. MS Михаил Семионенков

    • Команда форума
    Рег.:
    10.02.2006
    Сообщения:
    6.500
    Симпатии:
    2.850
    Репутация:
    170
    Оффлайн
    Скажите, скажите :p
  3. TopicStarter Overlay

    Grigoriy Старожил

    • Участник
    • Старожил
    Рег.:
    10.02.2006
    Сообщения:
    4.099
    Симпатии:
    26
    Репутация:
    2
    Оффлайн
    Не понимаю, из-за чего вы спорите. Меня удовлетворяет то решение, которое промелькнуло у МС и которое чётко изложил НС - по последнему дню. Я то просто купился :) - не понял, что даже и с бесконечностями существует последний день :)
    А с шапками решение в одну строчку - конкретный метод. Что их много - интуитивно ясно с самого начала, вот указать хотя бы одно конкретное ... :)
    И с третьекласниками НС загнул - остатки вряд ли проходят раньше 5-ого класса. Хотя я явно и чётко пришёл к пониманию сравнений где-то после 1-ого класса помнится - а я отнюдь не зведа( и тогда не был)
  4. NS Нефёдов Сергей

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

    • Участник
    Рег.:
    07.09.2006
    Сообщения:
    1.282
    Симпатии:
    1
    Репутация:
    0
    Адрес:
    Toronto, Canada
    Оффлайн
    Я не понимаю, в чём проблема, если заранее знать, какая будет последовательность ? Пусть просто все говорят — одна лампочка !!!!!!!!! ;)

    Или так — пусть вычисляют средние, если сходяться, то у кого получилось больше 1/2 говорит второй вариант, остальные первый. Уже будет работать на классе наборов, которые в серднем сходятся. Но не на всех. Можно так же расширить на класс посл., которые сходятся по Абелю и т.д. Но опять же не на все.
  6. drowsy Учаcтник

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


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

    Решать можно в двух случаях —
    1) стратегия для каждого мудреца различная.
    2) им разрешено выработать ОДНУ стратегию на всех, и потом они ей будут следовать, то есть не зависимо от имени-фамилии-днк мудреца они будут делат одно и тоже. Правда в этом случае я решение не помню, а вспоминать лень :rolleyes:
  7. Erge Учаcтник

    • Новичок
    • Участник
    Рег.:
    20.02.2006
    Сообщения:
    22
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Че-то чем дальше в лес тем больше дров...
    Абсолютно очевидно, что в задаче про ламочки, если в стратегиях из зажигают действительно СЛУЧАЙНЫМ образом все перечисенные пределы существуют, причем с вероятностью 1. Это называется закон больших чисел (возможно обобщенный).
    Так что бравирование, тем что математик, и студентами МГУ мне представляется неуместным.
    Хотя скорее всего, просто условие сформулировано неправильно. Например, слово "случайным" - лишнее
    С бесконечностями последнего дня не существует. Этого утверждения я не понял.
  8. drowsy Учаcтник

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

    • Команда форума
    Рег.:
    10.02.2006
    Сообщения:
    6.500
    Симпатии:
    2.850
    Репутация:
    170
    Оффлайн
    Вы утверждаете, что для указанного случая оба скажут 1?
    Вы пролетели, поскольку в камере 3 все время горел свет.

    Вы утверждаете, что для указанного случая оба скажут 2?
    Вы пролетели, поскольку в камере 3 все время было темно.

    Вы утверждаете, что для указанного случая двое находящихся в одинаковых условиях дадут разные ответы?
    А с каких, извините х-в?
  10. MS Михаил Семионенков

    • Команда форума
    Рег.:
    10.02.2006
    Сообщения:
    6.500
    Симпатии:
    2.850
    Репутация:
    170
    Оффлайн
    Я просто вернулся к постам 6 и 8 и констатирую: дыра в задачке, довольно очевидная.
  11. drowsy Учаcтник

    • Участник
    Рег.:
    07.09.2006
    Сообщения:
    1.282
    Симпатии:
    1
    Репутация:
    0
    Адрес:
    Toronto, Canada
    Оффлайн
    нет там никакой дыры ;) решайте пока Григория задачку, она для 3-е классников.
  12. MS Михаил Семионенков

    • Команда форума
    Рег.:
    10.02.2006
    Сообщения:
    6.500
    Симпатии:
    2.850
    Репутация:
    170
    Оффлайн
    А Вы #44 еще не опровергли. :)
    Или "нет там никакой дыры", это пример строго математического доказательства.:lol::lol::lol:

    Григория осилю, не печальтесь
  13. MS Михаил Семионенков

    • Команда форума
    Рег.:
    10.02.2006
    Сообщения:
    6.500
    Симпатии:
    2.850
    Репутация:
    170
    Оффлайн
    Григорий, угробил час, но обобщение даже на 3 упорно натыкается на противоречие.
    Или я что-то неправильно интерпретирую в задаче, или я сильно поглупел после 3-его класса. :lol:
    Короче, прошу поделиться, лично или публично.
  14. TopicStarter Overlay

    Grigoriy Старожил

    • Участник
    • Старожил
    Рег.:
    10.02.2006
    Сообщения:
    4.099
    Симпатии:
    26
    Репутация:
    2
    Оффлайн
    фи(к) = к - Сигма штрих
    Это ответ. Д-во:
    фи(к) - ф(к) = к - Сигма

    :)
  15. PP Учаcтник

    • Участник
    Рег.:
    20.02.2006
    Сообщения:
    799
    Симпатии:
    6
    Репутация:
    0
    Оффлайн
    если у мудреца зажглась лампочка он добавляет 1 если не горит то вычитает 1.
    ответ мудрец дает в зависимости от суммы
    когда сумма < 0 мудрец говорит что лампочка горит только в одной комнате
    когда > 0 мудрец говорит что горит в 2-ух комнатах
    если сумма ноль то
    ответ даётся на основании знака суммы разностей (X[2k]-X[2k-1])
  16. MS Михаил Семионенков

    • Команда форума
    Рег.:
    10.02.2006
    Сообщения:
    6.500
    Симпатии:
    2.850
    Репутация:
    170
    Оффлайн
    Григорий, спасибо. Решение понял, поскольку топтался вокруг.
    А вот идею доказательства пока не уразумел, даже с подсказкой, но подумаю.
    В результате заполнял таблицы руками и, очевидно, провирался.
    Рад, что не ошибся - и мудрецы, и цвета - нумерованые. В этом смысле - задача действительно для 3-его класса - в 7 некоторая некорректность постановки уже глаз режет :) : должно быть ясно из условия, строго говоря, что естественный механизм нумерации существует и понятен мудрецам. А вот полный смысл обобщения случая н=2 осознал только в Вашей записи.
  17. TopicStarter Overlay

    Grigoriy Старожил

    • Участник
    • Старожил
    Рег.:
    10.02.2006
    Сообщения:
    4.099
    Симпатии:
    26
    Репутация:
    2
    Оффлайн
    А доказательство - очевидно. Сигма - константа, а к пробегает все значения от 1 до N , т е где-то будет 0 (по модулю N). А т к фи и ф принимают значения от 1 до N, то из равенства левой чаcти нулю по модулю N следует просто равенство нулю.
    И опять таки Вы не поняли, точнее, невнимательно прочитали. Не нужно никакого естественного способа. У них было время договориться - вот они и установили нумерацию себя и цветов. Т. обр., задача совершенно корректна.
  18. Erge Учаcтник

    • Новичок
    • Участник
    Рег.:
    20.02.2006
    Сообщения:
    22
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    drowsy, Извините, я погорячился. Просто когда задача так формулируется, сразу же возникает ощущение, что она вероятностная. По-моему не у меня одного.
  19. MS Михаил Семионенков

    • Команда форума
    Рег.:
    10.02.2006
    Сообщения:
    6.500
    Симпатии:
    2.850
    Репутация:
    170
    Оффлайн
    "У Вас 3 часа на раздумье и договор"

    Григорий, на "договоре" я и споткнулся, фразу не переварил. Пожал плечами и воспринял как опечатку
    "У Вас 3 часа на раздумье, и договор:..."
    Но, это, конечно, моя проблема - претензии снимаю.

    Возможно, сказались "остаточные образы" от следующей "ясельной" задачи, где нужды в предварительной договоренности нет, все сами естественным образом понимают.
    N мудрецов в подвале у батьки Ангела, шапки красные и белые, у каждого своя фиксированная, которую он не видит. Известно, что есть как минимум одна красная. На утренней поверке все видят всех.
    Если те и только те, кто носит шапки одного цвета выйдут одновременно из строя на утренней поверке - всех отпускают. При ошибочном выходе - всех казнят. Никто не выходит - жизнь в заключении продолжается. Решил мгновенно, но "мне повезло".
  20. MS Михаил Семионенков

    • Команда форума
    Рег.:
    10.02.2006
    Сообщения:
    6.500
    Симпатии:
    2.850
    Репутация:
    170
    Оффлайн
    Да, Григорий - доказательство - очень красивое, мне близко ничего такого в голову не приходило.
    Пытался нащупать решение тыком, но большую часть времени убил на к+сигма штриг. Идея смены знака мелькнула, но показалась непринципиальной. В результате имел принципиальные проблемы. :)

    Спасибо, Григорий - очень красиво!

    PS А вообще подкол классный - с точки зрения обобщения случая н=2 сигма штрих абсолютно естественно выглядит со знаком +. Дальше люди типа меня могут биться до посинения. Хорошо, что догадался сдаться :lol:
  21. drowsy Учаcтник

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

    Просто если заранее договориться можно, то легко, и вроде даже условие, что есть одна красная, не нужно.
  22. MS Михаил Семионенков

    • Команда форума
    Рег.:
    10.02.2006
    Сообщения:
    6.500
    Симпатии:
    2.850
    Репутация:
    170
    Оффлайн
    drowsy, в этом, можно сказать и прелесть: ставка на то, что мудрецы.
    На самом деле, в задаче Григория схожая ситуация, если явно указать, что образцы цветов пронумерованы, а процедуру представления друг другу расписать как строго последовательную, 1-ого - всем, 2-ого - всем и.т.д.
    В предположении, что все мудрецы уровня не ниже Григория, все молча и без сговора ищут самую элегантную стратегию.
  23. PP Учаcтник

    • Участник
    Рег.:
    20.02.2006
    Сообщения:
    799
    Симпатии:
    6
    Репутация:
    0
    Оффлайн
    если на первый день никто не вышел то количество красных шапок больше чем 1
    если на второй никто не вышел то больше чем 2 ...
    и так в какой-то день все обладатели красных шапок смогут выйти предпологая что все они мудрецы

    а вот про лампочки я поторопился так как есть случайный начальный период....
  24. TopicStarter Overlay

    Grigoriy Старожил

    • Участник
    • Старожил
    Рег.:
    10.02.2006
    Сообщения:
    4.099
    Симпатии:
    26
    Репутация:
    2
    Оффлайн
    Вот опять невнимательны :( Я же чётко сказал, что я не решил, и даже дал ссылку на диалог с решившим мудрецом :)(нет, действительно, очень мудрый товарищ, и задачки до сих пор решает здорово, хотя и не без проколов :) )
  25. MS Михаил Семионенков

    • Команда форума
    Рег.:
    10.02.2006
    Сообщения:
    6.500
    Симпатии:
    2.850
    Репутация:
    170
    Оффлайн
    PP - совершенно верно. Мудрецам ничего придумывать не надо - просто отслеживать ситуацию.
  26. Tulean Учаcтник

    • Участник
    Рег.:
    02.07.2006
    Сообщения:
    577
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Господа математики!
    Рискну утверждать, что в этот тред с интересными задачами заглядывают не только профи.
    А нельзя ли вас попросить обнародовать решения?
    Предполагаю, решения весьма красивы и понятны не только специалистам :)

    Предложу вам такую простую задачку:
    Говорят, во время обдумывания задачи об "n офицерах", Эйлеру приснился замечательный латинский квадрат 8х8. В нем каждая пара строк и каждая пара столбцов образовывала цикл (длиной 8, такие квадраты назовем циклическими).
    Проснувшись, Эйлер взял перо и бумагу и за минуту разобрался не только с квадратом 8х8, но и обобщил результат на случай nxn при n четном.
    Вопрос: существуют ли "четные" циклические латинские квадраты, и если да, то как их строить?
  27. MS Михаил Семионенков

    • Команда форума
    Рег.:
    10.02.2006
    Сообщения:
    6.500
    Симпатии:
    2.850
    Репутация:
    170
    Оффлайн
    Tulean, поточнее.
    По памяти, здесь было 4 задачи, по меньшей мере 2 - с решениями, одна - снята с пробега. Что именно пояснить? А у Вас, "пара ... образовала цикл". Не осилил, поясните.
  28. Tulean Учаcтник

    • Участник
    Рег.:
    02.07.2006
    Сообщения:
    577
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Цикл - пара строк/столбцов, образующих циклическую подстановку.
  29. MS Михаил Семионенков

    • Команда форума
    Рег.:
    10.02.2006
    Сообщения:
    6.500
    Симпатии:
    2.850
    Репутация:
    170
    Оффлайн
    Не уверен, что понял правильно.

    12345678
    23456781
    34567812

    и т.д.

    Четность тоже вроде значения не имеет.
  30. Tulean Учаcтник

    • Участник
    Рег.:
    02.07.2006
    Сообщения:
    577
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Цикл должен быть полным, длиной 8.
    12345678
    23456781
    Это правильно.

    12345678
    34567812
    Распадается на два длиной 4:
    1357
    3571
    и
    2468
    4682
  31. Tulean Учаcтник

    • Участник
    Рег.:
    02.07.2006
    Сообщения:
    577
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    На самом деле нечетное составное n - самый трудный случай в вопросе наличия/отсутствия циклических квадратов.
    На сегодняшний день все ясно только для n-четного, n-простого (=р) и немногих других нечетных n: p*2-1, p*p, все нечетные <50.
  32. MS Михаил Семионенков

    • Команда форума
    Рег.:
    10.02.2006
    Сообщения:
    6.500
    Симпатии:
    2.850
    Репутация:
    170
    Оффлайн
    Tulean, я все забыл. На пальцах определения не датите?
  33. Tulean Учаcтник

    • Участник
    Рег.:
    02.07.2006
    Сообщения:
    577
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Попробую.
    Подстановка и цикл - определения здесь
  34. Guest

    Рег.:
    Сообщения:
    0
    Симпатии:
    0
    Репутация:
    0
    Онлайн
    Tulean, я наверное комбинаторику уже забыл, но что меня смущает в Вашей задаче. Циклическая подстановка длины 8 есть нечетная подстановка. Если же мы возьмем первые три столбца матрицы, то подстановка образуемая 1-м и 3-м столбцами является произвидением подстановки образуемых 1-м и 2-м столбцами и подстановки образуемой 2-м и 3-м столбцами. Если это так, то не могут все эти три подстановки быть нечетными. Где я не прав?
  35. Tulean Учаcтник

    • Участник
    Рег.:
    02.07.2006
    Сообщения:
    577
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Так именно это и не дает строить циклические четные латинские квадраты!
    Проснувшись, Эйлер просто понял, что во сне был неправ :D

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