Пятнашки - это простая головоломка-пазл известная любому школьнику прошлого века :) 15 пронумерованных костяшек случайным порядком расставлены на доске 4х4. Одна клетка остается свободной и на это свободное место можно сдвинуть соседнюю костяшку. Задача - перемещая косточки, выставить их по порядку слева направо, сверху вниз, от 1 до 15. Есть большое количество онлайн реализаций этой игры, но все эти реализации, дабы не нервировать игроков, всегда имеют решение. Кроме той, которую я написал специально для этой статьи. В настоящих Пятнашках, когда костяшки высыпались на стол и случайным образом ставились на поле, решение находилось не всегда. Это как в карточном пасьянсе - может сойтись, а может и нет. Я помню, в школе была любимая подколка: когда твой одноклассник первый раз собирал пятнашки, я менял местами последние костяшки 14 и 15, и предлагал собрать заново. И вот твой товарищ, который еще минуту назад сиял от осознания собственной сообразительности, всю перемену двигает костяшками и у него ничего не получается. Почему? Тогда в школе ответ был очевидный, потому что не получается, и все! Можешь попробовать! Они либо собираются, либо нет. Причем если нет, то всегда в самом последнем ряду 15 стоит перед 14.
Конечно, у математиков есть доказательство, почему это невозможно сделать - все дело в четности инверсий, но во-первых в 3 третьем классе такое объяснение не прокатит, а во вторых - оно выглядит, как доказательство следствия, не объясняя причину! Оно звучит так: При определенной нумерации ячеек при нечетном количество инверсий пазл сложить невозможно. Я же хотел найти доказательство без знания того, что такое инверсия, просто "на пальцах" и главное, все же докопаться до причины..
Циклы перестановок на примере задачи о 100 заключенных.
Прежде чем приступить к доказательству сделаем небольшое отступление к другой задаче с перестановками, задаче о 100 заключенных.
Сто заключенных сидят в тюрьме каждому присвоен номер и им предлагают следующее условие освобождения: "В большом зале расставлены 100 коробок, в каждой коробке лежит номер от 1 до 100. Каждый из вас по очереди зайдет в зал, где может открыть ровно 50 коробок и если обнаружит свой номер, то выходит во двор и ждет остальных. Если каждый найдет свой номер - все выйдете на свободу, если хоть кто-то не найдет - вернетесь в свои камеры навечно." В таком виде задача много где опубликована, и на ютубе есть прекрасный видеоролик с ее разбором. Чтобы не повторяться, для разнообразия дополним задачу. "Ха-ха-ха, продолжил коварный надзиратель, вам никогда не выполнить эти условия, но я добр и я разрешаю одно предварительное действие. Один человек-правозащитник может зайти в зал первым и поменять местами любые две коробки. Он может смотреть номера во всех коробках, но поменять разрешается только две и только один раз!"
Красивая задачка и на первый взгляд кажется что шансов у ребят - ноль. 50 попыток из 100 дает вероятность обнаружения 50%. Сто раз подряд угадать "на рулетке" красное невозможно, вероятности умножаются и уже на 10ом заключенном - это 1 шанс на тысячу, а на сотне это меньше чем 1 в -30й степени. Но если найти правильную стратегию, то без правозащитника вероятность освобождения чуть больше 30%, что уже не мало, а с правозащитником - 100%. Выйдут все и всегда! Как же это возможно, при всего одной замене?
Заключенный идет к коробке соответствующей его номеру, открывает ее и видит там другой номер, не свой. Он идет к той коробке, чей номер прочитал и смотрит что в ней и так далее. В конечном счете он находит свой номер, и нам важно, чтобы этот номер был не дальше 50ого шага. Найдя свой номер, он "замыкает" цикл поиска и выходит во двор. Это важно! Любые перестановки образуют циклы разной длины!
![Схема перестановок 15 элементов-цифр, [E] - пустая ячейка](https://habrastorage.org/r/w780/getpro/habr/upload_files/ebf/1e9/d24/ebf1e9d24411e8646acd5fa393e6a3c1.png "Схема перестановок 15 элементов-цифр, [E] - пустая ячейка")
]Для наглядности привожу схему перестановок 16 элементов, расставленных по кругу, позиция 1 на 12 часов, нумерация по часовой. Здесь видно: элемент 9 и элемент [E] остались на своих местах, элементы 4 и 12 поменялись местами, образуя один цикл, и еще три цикла легко различимы на схеме. В случае с нашими заключенными, тот что имел номер 9 подошел бы к 9-й коробке и сразу бы обнаружил в ней свой номер. Заключенный 4 увидел бы номер 12, пошел бы к 12-й коробке и в ней обнаружил бы номер 4, то есть замкнул цикл. На этой схеме нет циклов, длиннее половины элементов, то есть конкретно в этом случае заключенные вышли бы свободу.
И какова же точная вероятность того, что циклов, длиннее чем половина элементов, не встретится? На 100 заключенных количество возможный перестановок коробок 100! (факториал), совершенно огромное число, из него надо вычесть все варианты циклов больше 50 умноженное на все варианты раскладки остатка. Но я не хочу так считать! Я не помню формул, меня пугают эти факториалы и я ленивый. К тому же, когда мы считаем вероятность красного в казино, мы не делим количество красных сегментов на общее кол-во сегментов. Мы знаем что цвета только два и они равновероятны, поэтому 1/2. Так проще! Вот и в этой задаче хочется найти инвариант, который позволит найти вероятность малыми числами и без трехэтажных формул.
Задача: требуется найти вероятность события, что в любой случайной расстановке нет циклов длиннее чем N/2 где N - количество элементов, в нашем случае 100. Цикл длиннее 50, может быть только один. Если мы определим вероятность наличия цикла заданной длины k, тогда искомая вероятность P = 1 - ( Q(k=51) + Q(k=52) + ... + Q(k=100) ).
Кому математика скучна, читайте дальше. Здесь в деталях привожу свой способ нахождения вероятности. Уверен, я не первооткрыватель, но было интересно самому найти решение.
Давайте двигаться вместе с заключенным. В идеале, открываем коробку на позиции x и в ней лежит наш номер. То есть в коробке х лежит число x, найден цикл длинной k=1 и вероятность обнаружить "свой номер" P(k1) = 1/N. Но если нет, идем дальше, определим вероятность P(k2) - вероятность, что мы попадем в цикл длинной 2. Она образуется из вероятности того, что мы .
не попали в цикл k=1 на первом шаге => 1 - P(k1) = 1 - 1/N
И на втором шаге нашли нужную цифру в оставшихся (N -1) коробках => 1/(N-1)
Эти вероятности надо перемножить: 
Забавно, не правда ли? похоже, что независимо от длинны цикла, вероятность попадания в него с некоторой позиции равна 1/N. проверим на k=3
Если мы попали в цикл к=1 то точно НЕ попадем в цикл k=2, если оказались в цикле k=2, то точно не были в цикле k=1, взаимоисключающие попадания. Значит, вероятность что мы не были ни там ни там:
, а вероятность оказаться в цикле длинной 3 - это обнаружить x в оставшихся (N - 2) номерах.
В общем виде 
(1)
Вероятности попадания в цикл любой длины, начиная с позиции x, обозначим P(x), равновероятны и равны 1/N. Хорошо, запомним это, но нам нужна другая вероятность. Мы ищем вероятность существования в раскладке цикла длинной k,обозначим ее через Q(k), которая очевидно выше, чем P(x). Но эти две вероятности связаны друг с другом, а именно P(x) можно выразить через два события, которые должны случиться одновременно
A - в раскладке есть цикл длинной k - это вероятность Q(k), которую мы ищем.
B - Элемент x должен быть в этом цикле.
P(B) - без комбинаторики - если бы цикл был единичной длины, то для нашего x только одно место и P(B) = 1/N. Если k=2, то для нашего x есть 2 ячейки P(B) = 2/N, а для цикла длинной k P(B) = k/N.
P(существует цикл длинной k и x находится в нем ) = P(B|A) = P(A) * P(B) = Q(k) * k/N
Но P(B|A) и P(x) это одно и тоже, их можно приравнять! То есть на один и тот же исход мы смотрим с разных сторон:
, следовательно 
Вероятность наличия в раскладе цикла длины k равна 1/k. Давайте посчитаем вероятность проигрыша для 16 заключенных. Нас интересуют суммы вероятностей длинных циклов:
а вероятность успеха 1 - 0.66 = 0.34
Можно сосчитать вручную, когда слагаемых мало, но для 100 заключенных лучше пользоваться приближенной формулой. Выше - частичная сумма гармонического ряда, по формуле Эйлера
1 - (H(N) - H(N/2)) = 1 - ln(N) + g - ln(N/2) - g = 1 - ln(2) = ~ 0.31
P = 1 - (1/51 + ... + 1/100) ~ 0.31
В Википедии приведено комбинаторное решение с подсчетом всех возможных перестановок, можете сравнить
Сразу будем рассматривать длинные циклы 
.Существует 
способов набрать разных номеров в этот цикл, и количество сочетаний номеров в цикле 
Количество сочетаний оставшихся номеров 
не забываем что длинный цикл может быть только один, тогда количество комбинаций, включающих цикл длинны
равна
= ......... 
вероятность НЕ встретить все длинные циклы:
То есть через формулы всех возможных комбинаций получили то же самый ответ - частичная сумма гармонического ряда. 100! везде сокращается, коротко и не страшно, но это если помнить все эти формулы, дружить с комбинаторикой, или если посмотреть готовое решение :)
Итого, вероятность всем выйти на свободу почти 1/3, это и много и мало. Но ведь есть еще правозащитник! Он может зайти первым, посмотреть все номера в коробках и если есть один (всегда только один) длинный цикл, то надо переставить две коробки так, чтобы разорвать его на два коротких. Одной перестановки всегда будет достаточно. А как определить какие именно две коробки переставить и не получится ли так, что после перестановки одна коробка замкнет маленький цикл, а вторая - сольет два других маленьких вместе и снова получится большой?
Алгоритм действий простой и основан на еще одном замечательном свойстве - с какой бы позиции мы не начали - замыкающий номер всегда последний в переходах по циклу! Это совершенно очевидная вещь - если мы пойдем по построенному циклу в обратную сторону, мы будем идти по "замыкающим" номерам. Это свойство также отвечает на вопрос: а где гарантия, что заключенный, открывая коробку со своим номером, не окажется в чужом цикле? Вот она гарантия - номер заключенного всегда в коробке последнего шага цикла. Можно было бы промахнуться, если открыть ящик не на "своем" месте, но стратегия иная: именно свой ящик - это то место, куда мы вернемся после прохождения цикла.
16 позиций, длинные циклы больше 8. Допустим правозащитник начал просмотр с позиции 1, там сейчас цифра 12, идя по циклу он обнаружил что расклад плохой и цикл длинный, замыкается на 11 шаге. давайте замнем его на 6 шаге. Делаем по циклу шаг назад, достаем карточку из коробки 10 (там единица), надо положить ее в ящик 6ого шага для разделения цикла пополам. Двигаясь от первой позиции по стрелкам на 6 шаге находим номер 5 на позиции 16. Меняем карточки. Поскольку длинный цикл может быть только один, других проверок можно не делать.
Очевидно, что красный цикл который мы замыкали, станет коротким, длинной в 6 шагов, А что будет с другими номерами этого цикла? Не попадут ли они в бирюзовый и не раздуют ли его? Нет, это исключено. Любые перестановки внутри своего цикла никак не повлияют на соседние. Оставшиеся номера образуют свой маленький цикл.
Возвращаемся к пятнашкам.
Отступление было необходимо для того, чтобы познакомиться с циклами перестановок и собрать их свойства, необходимые нам далее, вот они:
любое перемешивание элементов создает циклы.
перестановки элементов в одном цикле никак не влияет на другие.
конфигурация циклов зависит только от способа нумерации элементов последовательности. При нумерации слева направо сверху вниз - получим одно количество циклов и чисел в них, при нумерации сверху-вниз, справа-налево - другое.
Для визуализации я создал страничку стенд Пятнашки, с 4-мя разными способами нумерации элементов, меняя которые можно видеть, как складываются циклы на одной и той же расстановке фишек. Циклы показываются не на круговой диаграмме, а на матрице перестановок, которая имеет и человеко-читаемый и машинно-ориентированный вид, а способ нумерации показывается иконкой и расстановкой индексов ячеек маленькими цифрами.
Цель нашей игры - после перемешивания вернуть фишки на свои места, согласно выбранной нумерации. Формально это значит разбить все циклы на циклы единичной длины. На матрице в этом случае все элементы выстроятся по главной диагонали.
При нормальной нумерации ход по горизонтали никак не меняет порядок следование фишек, но перемещает свободную ячейку под соседние вертикальные колонки для следующего хода по вертикали. А ход по вертикали является значимым - совершает перестановку фишки на 4-ую ячейку через 3 при обычной нумерации или на 7-ую через 6 при нумерации "змейкой". Во втором случае перестановка идет через четное число ячеек и именно по этому нумерация змейкой используется при доказательстве "собираемости" теорией перестановок по свойству сохранения четности.
Но для доказательства "на пальцах" наглядней всего будет нумерация по четвертям. Поле разбивается на четыре равных четверти и в каждой четверти нумерация ставится по часовой стрелке начиная с левой верхней ячейки. Чем этот способ удобен? В пределах четверти любой ход и по горизонтали и по вертикали одинаково "бесполезен", он не меняет следование ячеек одна за одной в пределах четверти, но "поворачивает" последовательность на один шаг против или по часовой стрелке и смещает пустое поле для потенциального обмена фишек с другой четвертью: Кроме того, если в каждой четверти собраны свои числа, то циклы перестановок образуются только внутри четвертей. Те же 4-ре клетки являются минимальным полем для перемещения фишек по кругу.
На рисунке выше расстановка фишек выглядит случайной, но это не так. Матрица перестановок показывает, что фишки перемешаны только в пределах своих четвертей и характерный рисунок каждого цикла позволяет легко определить, как они были перемешаны. Например в четвертой четверти мы видим циклический сдвиг, поворот на одну ячейку по часовой стрелке. для совершения полного оборота надо сделать 12 ходов, сдвинуть фишки по кругу, по 3 хода на каждый шаг поворота. Если фишки выпали так, как в четвертой четверти, то восстановить последовательность можно без перестановок элементов внутри круга, надо просто повернуть круг пока значения не совпадут с индексами ячеек. Но для поворота нужна свободная ячейка, если мы выведем какую либо фишку из четверти, то поворот будет возможен, но вернуть эту же фишку на свое место уже будет нельзя - пустое поле ушло. Всему виной "топология" и правила игры. И мы видим, что в нашем распоряжении есть только 2 типа хода: вывод фишки из четверти на свободную ячейку и "карусель" фишек внутри четверти.
На рисунке только третья четверть и пару соседних ячеек из четвертой. По опыту, это заведомо проигрышная позиция. Надо поменять местами 10 и 11 (напомним, нумерация по кругу по четвертям) Есть только один способ это сделать: смещаем 10 вправо, в третьей четвери появляется пустое поле, значит можем "повернуть" ее по кругу, пока 11 не окажется в углу, затем задвигаем 10 назад. Эти ходы можно записать так (10, 11, 9, 12, 11, 10). "Стало" - последовательность цифр восстановлена, но пришлось повернуть четверть на один шаг по кругу. Одна перестановка - один шаг поворота в четверти. Значит нужно, чтобы перед поворотом 9ка стояла не на своем месте, а на шаге назад. Но куда тогда деть номер 12? Остается только одно место для него - место девятки. Но это значит что 12 и 9 поменялись местами.
Если нам не удалось поменять местами фишки в контуре одной четверти, может получится сделать это в другой? Нет, не получится. Две ячейки всегда входят в какой либо контур, который придется смещать для обмена, сдвигая фишки со своих мест.
Пример выше не совсем корректный, нет смысла возвращать 10 не на свое место. Можно прокрутить ходы назад от уже собранной позиции, чтобы проследить, где что должно быть для успешного завершения партии, но ... на 4-х клетках можно выставить всего 16 комбинаций, в которых будет 1, 2 или 3 перестановки. Мы можем отследить каждую из них. Комбинацию с одной перестановкой невозможно собрать потому что каждая перестановка это сдвиг, этот случай мы уже разобрали. 3 перестановки, после исправления двух становятся эквивалентом одной. 4 перестановки всегда эквивалент 2-х. Получается, что собрать можно только комбинации с четным количеством перестановок соседних фишек по "линии" способа нумерации.
Для любой комбинации перестановок в четверти несложно найти наименьшее число ходов для победы. Легко доказать, что для любого способа нумерации ячеек наименьшее число ходов для выигрыша одинаково. Давайте пронумеруем каждую фишку двумя числами. Верхнее число соответствует обычной расстановке фишек, нижнее - нумерации по четвертям. Тогда в верхнем ряду будут стоять фишки 1/1, 2/2, 3/5, 4/6 ... Решая пазл по нижним номерам в порядке следования нумерации по четвертям мы увидим, что верхние номера тоже становятся на свои места.
Определим стратегию решения пятнашек наименьшим числом ходов. Два этапа: сначала кратчайшим путем расставим числа по своим четвертям, не заботясь о порядке; затем решим каждую четверть известным наименьшим числом ходов.
Как видите, циклы перестановок оказались в итоге не нужны, но они плавно подвели к решению, свели задачу к минимально возможной в поле одной четверти и, кроме того, циклы бывают симметричными и красивыми:
Возможное практическое применение
В пятнашках по сути выполняется сортировка последовательности при ограниченном выборе элементов для перестановок. Нельзя менять каждый с каждым, можно только соседние или через "ряд". такие условия могут встречаться при такелажных работах, на складах, при маневрировании составов и т.п. Цель - выполнить сортировку за наименьшее число ходов.
Ни разу не встречал такого вида сортировки, как сортировка методом дробления циклов. И понятно почему - в обычных общепринятых алгоритмах сортировки нет ограничений на перестановки и редко встречаются последовательности без пропусков и повторов. Но если условия сортировки имеют ограничения, подобные пятнашкам, то циклы могут быть полезны.
Ссылки:
Пятнашки, стенд с разными способами нумерации, отрисовкой циклов, подсчетом ходов...
Код пятнашек - https://github.com/anton-zaharov/fifty
Савватеев А. Игра «Пятнашки» и другие задачи. https://www.youtube.com/watch?v=gZthXsFcFLo
zivarellehayes
Great breakdown! Using the 100 prisoners problem to intuitively explain permutation cycles and invariant rules makes a classic math puzzle so much easier to grasp without drowning in heavy group theory. Thanks for sharing this clever proof!