- 28,538
- 46
- 8 Ноя 2022
Шутка для мультфильма зашла так далеко, что математики позже писали к ней научные статьи.
<div class="articl-text-cover" style="position:relative;width:100%;max-width:800px;margin-left:auto;margin-right:auto;aspect-ratio:1200/676;margin-bottom:2rem;overflow:hidden">
<div itemprop="articleBody">Обычная комедийная серия Футурамы однажды упёрлась в математическую задачу, для которой не нашлось готового решения. Сценаристу пришлось самостоятельно доказать, сколько новых персонажей потребуется, чтобы вернуть разменянные тела и сознания владельцам. Ответ оказался неожиданно простым: двух дополнительных участников хватает при любом количестве обменов.
Задача возникла во время работы над эпизодом «Узник Бенды». Профессор Фарнсворт изобретает машину, способную менять местами сознания двух существ. Профессор хочет снова почувствовать себя молодым и переселяется в тело Эми. Эми соглашается, поскольку рассчитывает есть без ограничений в теле пожилого мужчины и не беспокоиться о фигуре.
После первого обмена герои обнаруживают важное ограничение. Машина может сработать для каждой пары тел только один раз. Фарнсворт и Эми уже использовали взаимный обмен, поэтому просто повторить операцию и вернуться назад нельзя.
В дальнейшем к эксперименту присоединяются другие персонажи. Машину запускают семь раз, а сознания девяти героев распределяются по чужим телам. Следить за происходящим становится всё сложнее: внешность больше не подсказывает, кто именно говорит или действует в кадре.
Причины для новых обменов постоянно меняются. Робот Бендер собирается украсть яхту императора Николая и занимает тело Эми, чтобы соблазнить охранников. Лила переселяется в профессора Фарнсворта, поскольку хочет понять, почему Фрай её любит. Фрай пытается отомстить и намеренно выбирает непривлекательную внешность, поэтому меняется с похожим на омара доктором Зойдбергом. Каждый новый переход усложняет схему и сокращает число доступных пар.
К финалу всем требуется вернуть собственные тела, но прежние комбинации использовать уже нельзя. Сценарист Кен Килер столкнулся не просто с сюжетной трудностью. Перед ним возникла отдельная математическая задача: сколько дополнительных участников нужно добавить, чтобы распутать произвольную цепочку обменов между n персонажами, если ни одна пара тел не может пройти через машину дважды?
Число помощников могло расти вместе с количеством запутавшихся героев или оставаться постоянным. Готового решения в математической литературе Килер не нашёл, поэтому разработал собственное доказательство. Расчёты показали, что при любом числе участников достаточно двух новых персонажей.
В серии роль помощников получают баскетболисты и учёные глобтроттеры. Свит Клайд Диксон и Итан Бабблгам Тейт записывают решение на доске и по очереди участвуют в обменах. Показанные формулы повторяют настоящее доказательство , которое Килер подготовил для сценария.
Чтобы отделить математику от тел и сознаний, Килер заменил персонажей числами. Представим n объектов, расположенных в неправильном порядке:
(2, 3, 4, 5, ..., i, i + 1, ..., n, 1).
Задача состоит в том, чтобы вернуть последовательность к исходному виду:
(1, 2, 3, ..., n).
Для исправления порядка добавляются два новых элемента, x и y. Каждый обмен меняет местами только два элемента. Запись (i, x) означает, что i и x переставляются.
Килер разделил исходную последовательность на две части. В первую входят элементы от 1 до i, во вторую — от i + 1 до n. Затем каждый неправильно расположенный элемент первой группы по очереди меняется с x, а каждый элемент второй группы — с y.
Последовательность обменов можно записать так:
(1, x), (2, x), (3, x), ..., (i, x),
затем
(i + 1, y), (i + 2, y), ..., (n, y),
после чего выполняются ещё две операции:
(i + 1, x) и (1, y).
После завершения перестановок основные элементы возвращаются в порядок:
(1, 2, 3, ..., i, i + 1, ..., n).
Положение вспомогательных элементов x и y не имеет значения, поскольку два новых участника нужны лишь для временного хранения перемещаемых объектов. Выбор границы i тоже не влияет на результат. Метод работает при любой исходной перестановке.
Логику доказательства проще проследить на небольшой паре. Фрай и Зойдберг обменялись только друг с другом, поэтому образуют отдельную группу. Их неправильное расположение можно записать как (2, 1). После добавления Клайда и Тейта получается последовательность:
(2, 1, x, y).
В группе всего два основных элемента, поэтому i равняется 1. По правилу Килера требуются четыре обмена:
(1, x), (2, y), (2, x), (1, y).
После первой операции последовательность принимает вид:
(2, x, 1, y).
Затем второй элемент меняется с y:
(y, x, 1, 2).
Третий обмен ставит второй основной элемент на нужное место:
(y, 2, 1, x).
Последняя операция возвращает первый элемент в начало:
(1, 2, y, x).
Фрай и Зойдберг снова оказываются в собственных телах, но сознания Клайда и Тейта меняются местами. Немедленно обменяться друг с другом помощники не могут, поскольку их пара ещё нужна для исправления оставшейся части схемы. Сначала Клайд и Тейт участвуют в возвращении семи других персонажей.
В эпизоде полное восстановление занимает 13 операций. Математически задачу можно решить и за девять обменов, однако сценаристы выбрали более длинную последовательность, подходящую для сюжета. К концу серии каждое сознание возвращается в родное тело, а ограничение машины ни разу не нарушается.
Килер имел докторскую степень по математике, но не посчитал доказательство достаточно важным для отдельной научной статьи. Позже работу продолжили математики Рон Эванс, Лихуа Хуан и Туан Нгуен. В 2014 году они опубликовали в журнале American Mathematical Monthly улучшенное девятистраничное доказательство.
Сюжетная проблема из мультсериала превратилась в полноценную задачу о перестановках. Футурама не ограничилась шуткой для зрителей, знакомых с математикой: формулы на экране действительно решают поставленную в серии проблему, а два новых участника гарантированно распутывают любое число обменов.
<div class="articl-text-cover" style="position:relative;width:100%;max-width:800px;margin-left:auto;margin-right:auto;aspect-ratio:1200/676;margin-bottom:2rem;overflow:hidden">
<div itemprop="articleBody">Обычная комедийная серия Футурамы однажды упёрлась в математическую задачу, для которой не нашлось готового решения. Сценаристу пришлось самостоятельно доказать, сколько новых персонажей потребуется, чтобы вернуть разменянные тела и сознания владельцам. Ответ оказался неожиданно простым: двух дополнительных участников хватает при любом количестве обменов.
Задача возникла во время работы над эпизодом «Узник Бенды». Профессор Фарнсворт изобретает машину, способную менять местами сознания двух существ. Профессор хочет снова почувствовать себя молодым и переселяется в тело Эми. Эми соглашается, поскольку рассчитывает есть без ограничений в теле пожилого мужчины и не беспокоиться о фигуре.
После первого обмена герои обнаруживают важное ограничение. Машина может сработать для каждой пары тел только один раз. Фарнсворт и Эми уже использовали взаимный обмен, поэтому просто повторить операцию и вернуться назад нельзя.
В дальнейшем к эксперименту присоединяются другие персонажи. Машину запускают семь раз, а сознания девяти героев распределяются по чужим телам. Следить за происходящим становится всё сложнее: внешность больше не подсказывает, кто именно говорит или действует в кадре.
Причины для новых обменов постоянно меняются. Робот Бендер собирается украсть яхту императора Николая и занимает тело Эми, чтобы соблазнить охранников. Лила переселяется в профессора Фарнсворта, поскольку хочет понять, почему Фрай её любит. Фрай пытается отомстить и намеренно выбирает непривлекательную внешность, поэтому меняется с похожим на омара доктором Зойдбергом. Каждый новый переход усложняет схему и сокращает число доступных пар.
К финалу всем требуется вернуть собственные тела, но прежние комбинации использовать уже нельзя. Сценарист Кен Килер столкнулся не просто с сюжетной трудностью. Перед ним возникла отдельная математическая задача: сколько дополнительных участников нужно добавить, чтобы распутать произвольную цепочку обменов между n персонажами, если ни одна пара тел не может пройти через машину дважды?
Число помощников могло расти вместе с количеством запутавшихся героев или оставаться постоянным. Готового решения в математической литературе Килер не нашёл, поэтому разработал собственное доказательство. Расчёты показали, что при любом числе участников достаточно двух новых персонажей.
В серии роль помощников получают баскетболисты и учёные глобтроттеры. Свит Клайд Диксон и Итан Бабблгам Тейт записывают решение на доске и по очереди участвуют в обменах. Показанные формулы повторяют настоящее доказательство , которое Килер подготовил для сценария.
Чтобы отделить математику от тел и сознаний, Килер заменил персонажей числами. Представим n объектов, расположенных в неправильном порядке:
(2, 3, 4, 5, ..., i, i + 1, ..., n, 1).
Задача состоит в том, чтобы вернуть последовательность к исходному виду:
(1, 2, 3, ..., n).
Для исправления порядка добавляются два новых элемента, x и y. Каждый обмен меняет местами только два элемента. Запись (i, x) означает, что i и x переставляются.
Килер разделил исходную последовательность на две части. В первую входят элементы от 1 до i, во вторую — от i + 1 до n. Затем каждый неправильно расположенный элемент первой группы по очереди меняется с x, а каждый элемент второй группы — с y.
Последовательность обменов можно записать так:
(1, x), (2, x), (3, x), ..., (i, x),
затем
(i + 1, y), (i + 2, y), ..., (n, y),
после чего выполняются ещё две операции:
(i + 1, x) и (1, y).
После завершения перестановок основные элементы возвращаются в порядок:
(1, 2, 3, ..., i, i + 1, ..., n).
Положение вспомогательных элементов x и y не имеет значения, поскольку два новых участника нужны лишь для временного хранения перемещаемых объектов. Выбор границы i тоже не влияет на результат. Метод работает при любой исходной перестановке.
Логику доказательства проще проследить на небольшой паре. Фрай и Зойдберг обменялись только друг с другом, поэтому образуют отдельную группу. Их неправильное расположение можно записать как (2, 1). После добавления Клайда и Тейта получается последовательность:
(2, 1, x, y).
В группе всего два основных элемента, поэтому i равняется 1. По правилу Килера требуются четыре обмена:
(1, x), (2, y), (2, x), (1, y).
После первой операции последовательность принимает вид:
(2, x, 1, y).
Затем второй элемент меняется с y:
(y, x, 1, 2).
Третий обмен ставит второй основной элемент на нужное место:
(y, 2, 1, x).
Последняя операция возвращает первый элемент в начало:
(1, 2, y, x).
Фрай и Зойдберг снова оказываются в собственных телах, но сознания Клайда и Тейта меняются местами. Немедленно обменяться друг с другом помощники не могут, поскольку их пара ещё нужна для исправления оставшейся части схемы. Сначала Клайд и Тейт участвуют в возвращении семи других персонажей.
В эпизоде полное восстановление занимает 13 операций. Математически задачу можно решить и за девять обменов, однако сценаристы выбрали более длинную последовательность, подходящую для сюжета. К концу серии каждое сознание возвращается в родное тело, а ограничение машины ни разу не нарушается.
Килер имел докторскую степень по математике, но не посчитал доказательство достаточно важным для отдельной научной статьи. Позже работу продолжили математики Рон Эванс, Лихуа Хуан и Туан Нгуен. В 2014 году они опубликовали в журнале American Mathematical Monthly улучшенное девятистраничное доказательство.
Сюжетная проблема из мультсериала превратилась в полноценную задачу о перестановках. Футурама не ограничилась шуткой для зрителей, знакомых с математикой: формулы на экране действительно решают поставленную в серии проблему, а два новых участника гарантированно распутывают любое число обменов.
- Источник новости
- www.securitylab.ru
