Призрачная нога

Закрывая середину линий, игрок выбирает начальную точку (А). Затем линии раскрываются, и выбранная начальная точка прослеживается до ее конца (3).

Призрачная нога — это метод лотереи, предназначенный для создания случайных пар между двумя наборами любого количества вещей, при условии, что количество элементов в каждом наборе одинаково. Это часто используется для распределения вещей между людьми, когда количество распределяемых вещей равно количеству людей. Например, таким образом можно распределять обязанности по дому или призы справедливо и случайным образом.

На японском языке она известна как Амидакудзи ( лотерея Амида , « Амида лотерея ») , ^{[ номер 1 ]} на корейском языке как Садаритаги (사다리타기, буквально «восхождение по лестнице») и на китайском как Гуйцзяоту ( китайский : 鬼腳圖 , буквально «диаграмма ног призрака»).

Он состоит из вертикальных линий с горизонтальными линиями, соединяющими две соседние вертикальные линии, хаотично разбросанные по их длине; горизонтальные линии называются «ногами». Количество вертикальных линий равно количеству играющих людей, а внизу каждой линии находится предмет — вещь, которая будет находиться в паре с игроком. Общее правило этой игры: выберите линию вверху и следуйте по ней вниз. Когда встретите горизонтальную линию, следуйте по ней, чтобы добраться до другой вертикальной линии и продолжить движение вниз. Повторяйте эту процедуру, пока не дойдете до конца вертикальной линии. Затем игроку дается вещь, написанная внизу строки.

Если элементы, записанные над фантомной ветвью, рассматриваются как последовательность , и после использования фантомной ветви те же элементы записываются внизу, то стартовая последовательность преобразуется в другую перестановку . Следовательно, призрачную ногу можно рассматривать как своего рода оператор перестановки.

Процесс

В качестве примера рассмотрим распределение ролей в пьесе между актерами.

Начнем с того, что два набора нумеруются горизонтально по доске. Имена актеров будут вверху, а роли внизу. Затем рисуются вертикальные линии, соединяющие каждого актера с ролью, находящейся непосредственно под ним.
Имена актеров или ролей затем скрываются, так что люди не знают, какой актер на какой линии или какая роль на какой линии.
Затем каждый актер добавляет ногу на доску. Каждая нога должна соединять две соседние вертикальные линии и не должна касаться какой-либо другой горизонтальной линии.
Как только это будет сделано, прорисовывается путь от верха каждой вертикальной линии до низа. Поскольку линия следует вниз, если встречается участок слева или справа, этот участок необходимо проследить до соседней вертикальной линии, с которой он соединяется, затем движение вниз возобновляется, продолжая до тех пор, пока не будет достигнута нижняя часть вертикальной линии. Верхний элемент, с которого начинался путь, теперь связан с нижним элементом, на котором он закончился.

Другой процесс предполагает предварительное создание лестницы, а затем ее скрытие. Затем люди по очереди выбирают путь, начиная с самого верха. Если ни одна часть амидакудзи не скрыта, то можно исправить систему так, чтобы гарантировать определенное спаривание, тем самым побеждая идею случайности.

Математика

Частично привлекательность этой игры заключается в том, что, в отличие от случайных игр, таких как камень, ножницы, бумага , амидакудзи всегда создает соответствие 1:1 и может обрабатывать произвольное количество пар. Гарантируется, что два элемента вверху никогда не будут иметь один и тот же соответствующий элемент внизу, а ни у одного элемента внизу никогда не будет соответствующего элемента вверху.

Это также работает независимо от того, сколько добавлено горизонтальных линий. Каждый человек мог добавить одну, две, три или любое количество строк, и соответствие 1:1 сохранялось.

Один из способов понять, как это работает, — рассмотреть аналогию с монетами в чашках. чашках находится n монет В n , обозначающих предметы, находящиеся на дне амидакудзи . Затем каждая добавляемая ножка представляет собой замену местами двух соседних чашек. Таким образом, в итоге стаканчиков все равно останется n , и в каждом стакане будет одна монета, независимо от того, сколько обменов будет выполнено.

Характеристики

перестановка

Призрачная ветвь преобразует входную последовательность в выходную последовательность с тем же количеством элементов и (возможно) другим порядком. Таким образом, это можно рассматривать как перестановку n символов, где n — количество вертикальных линий в призрачной ветви. ^{[ 2 ]} следовательно, оно может быть представлено соответствующей матрицей перестановок .

Периодичность

Применение ложной ветви конечное число раз к входной последовательности в конечном итоге генерирует выходную последовательность, идентичную исходной входной последовательности.

То есть, если M — матрица, представляющая конкретную призрачную ногу, то M ^н = I для некоторого конечного n .

обратимость

Для любой призрачной ветви с матричным представлением M существует призрачная нога с представлением M. ⁻¹, такой, что M M ⁻¹ = Я

Нечетно-четное свойство перестановки

Поскольку каждая ветвь меняет местами два соседних элемента на своих концах, количество ветвей указывает на свойство перестановки нечетного/четного фантомного участка. Нечетное количество ветвей представляет собой нечетную перестановку, а четное количество ветвей дает четную перестановку.

Бесконечные призрачные ноги с одинаковой перестановкой.

Можно выразить каждую перестановку как призрачную ветвь, но это выражение не является однозначно однозначным, т. е. конкретная перестановка не соответствует уникальной призрачной ветви. Бесконечное количество призрачных ног представляет собой одну и ту же перестановку.

Основной

Поскольку существует бесконечное количество призрачных ветвей, представляющих определенную перестановку, эти призрачные ветки имеют своего рода эквивалентность. Среди эквивалентных призрачных ног те, которые имеют наименьшее количество ног, называются «простыми».

Пузырьковая сортировка и максимальная простота

Призрачная ножка может быть построена произвольно, но такая призрачная ножка не обязательно будет простой. Можно доказать, что только призрачные ноги, построенные с помощью пузырьковой сортировки, содержат наименьшее количество ног и, следовательно, являются простыми. Это эквивалентно утверждению, что пузырьковая сортировка выполняет минимальное количество соседних обменов для сортировки последовательности.

Максимальное количество ног простого числа

Для перестановки с n элементами максимальное количество обменов соседями = ${\frac {n(n-1)}{2}}$

Точно так же максимальное количество ветвей в простом числе с n дорожками = ${\frac {n(n-1)}{2}}$

пузырение

Произвольную призрачную ногу можно преобразовать в простое с помощью процедуры, называемой «пузырением». Когда работает «пузырьковость», следующие два тождества применяются повторно, чтобы переместить и устранить «бесполезные» ветки.

⇒
⇒

Когда два тождества больше не могут быть применены, оказывается, что призрачный участок точно такой же, как и призрачный участок, построенный с помощью пузырьковой сортировки , таким образом, пузырьковая обработка может свести призрачные этапы к простым числам.

Случайность

Поскольку, как упоминалось выше, нечетное количество ветвей дает нечетную перестановку , а четное количество ветвей дает четную перестановку, заданное количество ветвей может дать максимум половину всех возможных перестановок (меньше половины, если количество ветвей мала по отношению к числу дорожек и достигает половины по мере увеличения количества ветвей сверх определенного критического числа).

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

В популярной культуре

Аркадная игра Amidar 1981 года , запрограммированная Konami и изданная Stern , использует ту же решетку, что и лабиринт. Игра получила свое название от амидакудзи . и большая часть движений противника соответствовала правилам игры.

Ранняя Master System игра под названием Psycho Fox использует механику доски амидакудзи как средство поставить мешок монет на шанс получить приз в верхней части экрана. Более поздние игры Sega Genesis основаны на той же игровой концепции DecapAttack и ее японском предшественнике Magical Hat no Buttobi Tabo! Дайбокен использует ту же игровую механику, включая бонусные уровни амидакудзи .

Super Mario Land 2: 6 Golden Coins представляет собой бонусную игру в стиле амидакудзи , которая награждает игрока усилением. В новых Super Mario Bros. , Super Mario 64 DS и Wario: Master of Disguise есть мини-игра в стиле амикудзи , в которой игрок использует стилус для добавления новых линий, которые должны вести персонажа игрока по победному пути, когда он скользит по доске.

В Mega Man X Боспаук спускается по рельсам в форме паутины, похожим на амидакудзи для атаки на первом этапе крепости Сигмы.

Тренажерный зал Азалии в Pokémon HeartGold и SoulSilver был переработан с использованием амидакудзи системы передвижных тележек на основе . Правильный выбор приведет к руководителю спортзала; неправильные заставляют других тренеров драться.

Phantasy Star Online 2 использует принцип амидакудзи для случайно появляющейся мини-игры по обезвреживанию бомбы. Нужно проследить путь амидакудзи вокруг каждой бомбы, чтобы определить, какая кнопка ее обезвреживает; неправильный выбор отбрасывает игроков на несколько секунд, теряя время.

В японской драме « Дон Кихот» (эпизод 10) персонаж Широта ( Шота Мацуда ) использует амидакудзи , чтобы помочь выбрать между семьями-кандидатами на усыновление.

В Raging Loop «лотерея ног призраков» описывается как аналогия выбора ролей в деревне для церемонии, которая занимает центральное место в сюжете игры.

Примечания

^ Названа так потому, что в период Муромати печатные изображения системы рисовались радиально (с начальными точками снаружи и конечными точками внутри), что напоминало дизайн «круг, излучающий лучи», широко используемый для изображения нимба Амиды. ^{[ 1 ]}

Ссылки

^ Фредерик, Луи (2002). Японская энциклопедия . ISBN 9780674017535 .
^ I 2012, стр.31

Внешние ссылки

https://web.archive.org/web/20091023070628/http://geocities.com/Athens/Acropolis/7247/amidakuji.html
Лестницы: исследовательская статья Дэвида Сенфта (PDF)
Ман-Кит Хо, Хой-Кван Лау, Тинг-Фай Ман, Шек Юнг (2012). «Нога-призрак», Сборник победителей конкурса Hang Lung Mathematics Awards, 2004 г. Международная пресса. ISBN 978-1-57146-254-1 .

[2] Названа так потому, что в период Муромати печатные изображения системы рисовались радиально (с начальными точками снаружи и конечными точками внутри), что напоминало дизайн «круг, излучающий лучи», широко используемый для изображения нимба Амиды. ^{[ 1 ]}

[1] Фредерик, Луи (2002). Японская энциклопедия . ISBN 9780674017535 .

[3] I 2012, стр.31

[ номер 1 ]

[ 2 ]

[ 1 ]