Почему головоломка «Пятнашки» может не иметь решения?

Наука и жизньFan

Перестановки в математике и игра «Пятнашки»

В высшей математике есть раздел, который называется теория групп. В этом разделе изучаются свойства элемента, которому математики дали название «перестановка». Давайте рассмотрим набор из 5 чисел {1, 2, 3, 4, 5}. В этом наборе полный порядок — числа возрастают от 1 до 5. А теперь давайте перемешаем их. Для простоты поменяем местами 1 и 2: {2, 1, 3, 4, 5}. Оба таких набора чисел математики называют перестановкой. Вы можете переставить местами ещё пару, тройку, любое количество чисел, и каждый раз будете получать перестановку. Стоит отметить, что обычно математики пользуются набором из N чисел, поскольку очень не любят заниматься частными случаями. Так что любая последовательность из N чисел от 1 до N называется перестановкой.

Если в упорядоченном наборе чисел поменять местами пару чисел, то в новой перестановке большее число окажется перед меньшим. Математики эту простую операцию называют инверсией. Взяв какую-нибудь перемешанную последовательность чисел, математики предлагают посчитать в данной перестановке количество инверсий. (Человек, далёкий от математики, эту простую задачу сформулировал бы так: посчитайте в последовательности чисел количество пар, у которых левый элемент больше правого.) Понятно, что в последовательности {2, 4, 1, 3, 5} таких «неправильных пар» три — это 2 и 1, 4 и 1, 4 и 3.

Но математики не остановились на достигнутом. Ясно, что количество «неправильных пар» (то есть инверсий) может быть числом чётным или нечётным. Перестановку предложили назвать чётной, если у неё количество инверсий («неправильных пар») равняется чётному числу, и нечётной в другом случае.

O'qishni davom ettirish uchun tizimga kiring. Bu tez va bepul.

Roʻyxatdan oʻtish orqali men foydalanish shartlari 

Tavsiya etilgan maqolalar

Июньская метель снежноцвета Июньская метель снежноцвета

Снежноцветы считаются красивейшими деревьями, и с этим трудно не согласиться

Наука и жизнь
Непотопляемый Непотопляемый

Амфибии Amphicar, выпущенные более 60 лет назад, до сих пор в строю

ТехИнсайдер
Она вышивает мечты Она вышивает мечты

Самая яркая звезда на небосклоне высокой моды Поднебесной — талантливая Гуо Пей

Y Magazine
Как молния выбирает цель Как молния выбирает цель

Как молния находит молниеотвод среди множества других привлекательных целей?

Наука и жизнь
Глаз-синхротрон Глаз-синхротрон

О том, как научить искусственный интеллект понимать, а не угадывать химию

Наука и жизнь
«Эффект коктейля» для керамических покрытий «Эффект коктейля» для керамических покрытий

Керамика на основе карбида гафния и карбида циркония для агрессинвых сред

Наука и жизнь
Музей как увлечение Музей как увлечение

Единственный в своем роде: музей при Институте космических исследований РАН

Знание – сила
Терраса с видом на море Терраса с видом на море

Как выглядит Majesty 112 Terrace, продолжающая концепцию яхт Majesty

Y Magazine
Как в кино Как в кино

Новые технологии в кино – динамически меняющийся фотореалистичный фон

ТехИнсайдер
Передвижники и императорская власть Передвижники и императорская власть

Как передвижники получили признание императора Александра III

Знание – сила
Жук-лягушка, не знающий вывихов Жук-лягушка, не знающий вывихов

Как работает механизм блокировки вывиха у жуков-лягушек Sagra femorata

Наука и жизнь
Четыре всадника прогресса Четыре всадника прогресса

Футуролог — о неизбежности ИИ, крахе фармы, космической платине и энергетики

ТехИнсайдер
Изумрудный истребитель Изумрудный истребитель

Какой рыбак не знает зимородка, этого красавца в изумрудно-синем камзоле?

Наука и жизнь
Что следует знать начинающему инвестору Что следует знать начинающему инвестору

Что надо знать, когда планируете начать инвестировать?

Наука и техника
Величавый коровяк Величавый коровяк

Величавый коровяк: высокий, стройный, мощный, прочно вросший в землю

Наука и жизнь
Просто красота Просто красота

Дизайнер Кристиан Гранде — о творческом пути в яхтенном дизайне

Y Magazine
Код нации Код нации

Генетическая база данных поможет бороться с наследственными заболеваниями

ТехИнсайдер
Под ливнем наград Под ливнем наград

История создания кастомной яхты Benetti Kasper 7

Y Magazine
Главное – остаться незамеченным Главное – остаться незамеченным

В чем состоит военная (а возможно, и не только) хитрость стелс-технологии?

Наука и техника
Культура всегда со страной Культура всегда со страной

Разговор с директором Эрмитажа о роли, которую играют сейчас музеи

Знание – сила
Буль-буль Буль-буль

Фантастический рассказ Владислава Кулигина «Буль-буль»

Знание – сила
Банановые перспективы российских субтропиков Банановые перспективы российских субтропиков

Инвесторы хотят импортозаместить экзотические фрукты

Агроинвестор
Сделать посетителя немного исследователем Сделать посетителя немного исследователем

Что отличает современные музеи? Открытость и исследовательский подход

Знание – сила
2026: от рекомендаций до ИИ-агентов 2026: от рекомендаций до ИИ-агентов

За привычным интерфейсом Авито работают сложные алгоритмы машинного обучения

ТехИнсайдер
Автономный шестилапый робот «MICROBRO» Автономный шестилапый робот «MICROBRO»

Как создать ровер, который сам везет ваш багаж туда, куда вам нужно?

Наука и техника
Круизы: новая глава Круизы: новая глава

Rei — проект 196‑метровой круизной яхты от конгломерата Viken Group

Y Magazine
Солнце в спирали Солнце в спирали

Стеллараторы — новые фавориты в гонке за будущую термоядерную энергетику

ТехИнсайдер
Весна императора Весна императора

Цезарь — политик-хищник, с чьим именем неотрывно связана Римская империя

Знание – сила
Эра литий-ионных аккумуляторов Эра литий-ионных аккумуляторов

Почему ученые трудятся над тем, чтобы повысить безопасность батареек

Наука и техника
Архив богини Фауны Архив богини Фауны

Зоологический музей Московского университета – «отражение самой природы»

Знание – сила
Открыть в приложении