Дискретная математика в «бытовом» применении

    Во вчерашней серии футурамы поставили довольно интересную задачку — не мог не удержаться и не разобрать ее тут.
    image

    Итак, фабула такова: Профессор изобрел машину для обмена телами, которая, как оказалось, работает только в одну сторону. После нескольких перестановок герои оказались в тяжелой ситуации, в которой им предстояло придумать способ вернуться обратно в свои тела. Вот тут-то нам и поможет «чистая математика».

    Итак, приступим. Пусть — это цикл длины k на множестве [n] = {1… n}. Без потери общности запишем:


    Пусть теперь (a, b) представляет собой транспозицию, которая меняет местами содержимое a и b.
    По предположению, получена с помощью определенных подстановок над [n].

    Введем два «новых тела» {x, y} и запишем


    Для любых i = 1,… k запишем как ряд перестановок:


    Заметим, что транспозиции меняют элемент из [n] с каким-либо элементом из {x, y}, поэтому все транспозиции отличаются от оных, образовавших исходную подстановку , а также от транспозиции (x, y). Простой проверкой получаем:

    Таким образом, инвертирует цикл длины k, оставляя x и y переставленными без использования транспозиции (x, y).

    Теперь пусть — случайная подстановка; она распадается на композицию независимых циклов, каждый из которых может быть инвертирован с использованием полученного выше алгоритма, после чего при необходимости можно поменять местами x и y, используя транспозицию (x, y).

    Так-то. А вы говорите, что у дискретки нет применений IRL.

    Комментарии 65

    • НЛО прилетело и опубликовало эту надпись здесь
        +83
        Взятие интеграла по методу Гомера:
        1. Подойти
        2. Взять.
          +8
          Тогда уж лучше метод Симпсона ;)
            0
            Дык я потому и написал по методу Гомера, чтобы не путали.
          +67
          Поясню: пирог там потому, что и «пи» и «пирог» по-английски произносятся одинаково — как «пай».
            –33
            даже как-то неудобно вас К.О. после этого называть. вы выше его!
              +21
              Ну не знаю…
              Я например этого не знал и думал, что шутка в том, что Гомер в принципе думает о пирогах постоянно…
              Нежнее надо быть. Ещё нежнее)
                0
                считаем количество человек, которые не поняли картинку по количеству минусов предыдущего поста
                  –3
                  а я поставил ему плюс, потому что, как мне показалось, он отреагировал нормально
                  я засрал статистику (:
                    +1
                    По количеству плюсов к пояснению, мб?
                    +10
                    очень даже не очивидно, я думал что пи греческая буква и должна читаться по гречески, а не по-английский
                      +4
                      Я тоже не знал что в английском Пи как «Пай» читается. Тот же «Игрек» американцы наоборот не понимают.
                        –1
                        А «Игрек» наоборот это «кергИ»?! :)
                        +2
                        я тоже не знал что пи читается как «пай», но «пи» и «пай» все равно созвучны
                          +1
                          и интуитивно понятно что они в ином языке могут быть созвучны.
                        –5
                        Факт остаётся фактом, увы (как я уже замечал) даже среди читателей хабра есть люди не понимающие английского… (обидно, но факт)
                        0
                        Нет, это не так.
                          0
                          Ой, не туда ответил :(
                    • НЛО прилетело и опубликовало эту надпись здесь
                        +2
                        Оно первым было в гугле по запросу онлайн LaTeX-редактора, а там хтмл-код дают, ссылки из которого влом выкорчевывать. Да почему бы и не порекламить — удобный сервис.
                        • НЛО прилетело и опубликовало эту надпись здесь
                        +1
                        как будто пару лет назад на семинаре по дискретной математике =)
                          –4
                          А вы говорите, что у дискретки нет применений IRL.
                          У нас уже изобретена такая машина? :)
                            +2
                            Ну ирония же.
                            +7
                            Из всей серии, где даже профессор с зойдбергом целовались на столе в ресторане, выловить математику — это крайне круто :)
                              +2
                              В оправдание профессора и зойдберга скажу, что в их телах были фрай и лила(фрай-зойдберг, лила — профессор).
                                +2
                                Спойлер!
                                  +6
                                  Хуже! Он расспойлил мой спойлер!
                                    0
                                    Тогда уж заспойлил :)
                                  –1
                                  спасибо блин обоим :( не все же ведь ещё успели посмотреть.
                                +2
                                Эх, пару моих знакомых, посмотрев Футураму сказали: «Вот это бред!» :) Отличный пример сериала, кстати, когда поверхностное мышление можно выкинуть на свалку, в силу его бесполезности ;)
                                  +6
                                  «Профессор изобрел машину для обмена телами, которая, как оказалось, работает только в одну сторону. „

                                  Так и не понял, что вы решаете. Есть случайная перестановка, ее нужно упорядочить. Но какие операции с ней допустимы — уже непонятно. Как решаете — понимал до введения сигмы, тут откуда-то появилась любое i, и все стало непонятно. Сигма — это какая-то одна перестановка, или их множество. Если множество — то как мы его используем?

                                  Может стоит немного детальнее расписать, поставить задачу на языке той же дискретки, а потом решать?
                                  Ну и если где не тот термин использую — не судите строго, дискретную математику учил лет восемь назад, старый уже, позабыл :)
                                    +2
                                    Вопрос в том, что для исходного цикла необходимо найти такую подстановку, композиция с которой даст тождественную подстановку. Очевидный ответ с обратной подстановкой отпадает, ибо машина не умеет менять тела назад.
                                    Сигма позволяет поочередно поменять всех местами без использования обратной подстановки. (Честно говоря, я не особо понял, как они сигму записали).

                                    Пример: Зойдберга поменяли телами с Фраем, обозначим их F(Z) и Z(F), в скобочках указав «разум», вне скобок — тело. Добавим еще двоих: X(X) и Y(Y).
                                    1 перестановка:
                                    F(Z) <-> X(X) => F(X),X(F)
                                    Z(F) <-> Y(Y) => Z(Y),Y(Z)
                                    2 перестановка:
                                    X(F) <-> F(Y) => F(F),X(Y)
                                    Y(Z) <-> Y(X) => Z(Z),Y(X)
                                    Получили то, что надо, теперь используем оставшуюся перестановку и меняем Х и Y.

                                    Теорема же делает адское обобщение на произвольную перестановку.
                                      +2
                                      Но почему считается разрешенной перестановка X(Y) <-> Y(X)? Ведь это и есть обратная подстановка.
                                        0
                                        футы… неправильно сказал) нельзя транспозиции дважды использовать.
                                          0
                                          Вот теперь более менее понятно. Спасибо.
                                            +1
                                            Если я что упустил — буду благодарен если укажите на это. Но я понял все выкладки так: любая перестановка телами среди n субъектов может быть успешно возвращена в исходное состояние за счет перестановки между X и Y.

                                            Насколько я вижу нет способа вернуть всех в свои тела. Почему? Предположим тогда такой способ есть — очевидно что на последнем шаге для возврата на нужно обменять местами X(Y) и Y(Z), что по условию невозможно. Значит полный возврат к исходному состоянию невозможен.
                                              0
                                              Перестановку (x,y) мы не используем во время работы алгоритма ни разу, x и y оказываются поменяны местами в результате всех остальных перестановок (см. частный случай, на нем легче всего доехать). Поэтому в конце мы и можем использовать нужную перестановку (думаю, это понадобится, если n четно).
                                                0
                                                Смотрите у нас есть некий алгоритм благодаря которому мы собираемся поменять всех назад. Всё идет отлично последний шаг — какой он? A(?) <-> B(?), очевидно что это обмен вида A(B) <-> B(A) (иначе получиться не последний шаг). То есть обмен который запрещен. Получается что последний шаг невозможен — следовательно невозможно полное возвращение всех назад.
                                                Путем привлечения субъектов X Y мы можем получить перестановку в которой всех вернулись в свои тела, но при этом X и Y поменялись местами.

                                                Я не вижу ошибки в рассуждении о том что последний шаг алгоритма невозможен в рамках заданных условий. Если вы мне укажите на неё буду благодарен.
                                                  +1
                                                  Обмен запрещен только тогда, когда мы его уже делали одновременно над A и B. А они у нас получаются переставлены за счет работы алгоритма, как побочный эффект. Во время работы конкретно над A и B перестановок не производится.
                                                    0
                                                    Понял какое какое именно ограничение наложено на обмен. Спасибо.
                                      +2
                                      Новая серия?
                                      +5
                                      в бытность студентом, подрабатывал на базаре — торговали коврами. неожиданно пригодилась «вышка»: длинну свернутого в рулон ковра считал без разворачивания и «линейного» измерения с точностью до 20 сантиметров.
                                      к сожалению, 20 сантиметров ковра — это оказалось серьезными деньгами для других реализаторов и все равно все перемерялось в ручную.
                                        +2
                                        Надо было курвиметр брать
                                          +2
                                          погрешность всегда будет, поскольку распечатанные ковры никогда не бывают идеально скатанными…

                                          это из серии «Если вы уже открыли банку с червями, то единственный способ их снова запечатать — это воспользоваться банкой большего размера.»
                                          +2
                                          А точно ли тут вышка?
                                            0
                                            учась в экстремально-гуманитарной школе, интегралы и пределы я открыл для себя только в университете…
                                            объективно, скорее всего это старшие классы школы. субъективно — вышка :)
                                        • НЛО прилетело и опубликовало эту надпись здесь
                                            0
                                            Блин так и захотелось снова пройти дискретку ибо первый раз почти ничего не понял.
                                              0
                                              Кто там говорил, что хабр уже не тот?
                                                –1
                                                Он говорил что не торт.
                                                –2
                                                ФПМК ВМК МЕХМАТ МАТМЕХ
                                                  +2
                                                  Что интересно, решение уже было видно по иллюстрации из начала серии:
                                                    0
                                                    и где все +++?)
                                                      0
                                                      где вы тут увидели решение?
                                                        +1
                                                        Ну после обмена Эми-Профессор уже произошли обмены Лила-Профессор и Эми-Бендер (обозная контейнерами), оставалось только по зелёным стрелочкам доменяться (Лила-Бендер последними). Что не так?
                                                        А причём здесь все эти странные формулы — понятия не имею.
                                                      –1
                                                      Оффтоп: где скачать с сабами?
                                                        –5
                                                        думал, если оффтоп напишешь минусовать не будут?)
                                                          0
                                                          Бебебе
                                                          +1
                                                          Ответ: на рутрекере
                                                            –2
                                                            Сам спросил, сам ответил. Молодец.
                                                          +1
                                                          А мне кажется, автор перевел то, что было написано на доске в сериале… Меня даже разочаровало… Было бы интереснее, если была бы решена частная задачка… Подбор слов в переводе очень корявый…
                                                            0
                                                            Задача напоминает игру пятнашки и решается целевым перебором
                                                              0
                                                              Вот вы все пишете, пишете, но в исходной задаче имелись Эмми, Профессор, Бендер, Лила, Бухгалтер, Фрай, Зойдберг, Ведерко, Царь Николай, Баскетболист1, Баскетболист2. Кто-нибудь может адекватно представить как работает теория в «real-world applications»?

                                                              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                              Самое читаемое