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

Наука и жизнь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
Инвесторы стали избирательнее и осторожнее Инвесторы стали избирательнее и осторожнее

Агробизнес продолжает планировать инвестиции в развитие

Агроинвестор
О чем молчат рекорды HoReCa О чем молчат рекорды HoReCa

Будут ли все последствия смещения потребления с кухни в ресторан положительными?

Агроинвестор
Под ливнем наград Под ливнем наград

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

Y Magazine
Чёрные мысли на белом снегу Чёрные мысли на белом снегу

Рассказ Елены Ворон «Чёрные мысли на белом снегу»

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

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

Знание – сила
Архив богини Фауны Архив богини Фауны

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

Знание – сила
Посвящено Беатриче Посвящено Беатриче

Данте обнаружил, осознал, как мало он знает

Наука и жизнь
Круизы: новая глава Круизы: новая глава

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

Y Magazine
Рыбный день Рыбный день

Рыба — один из древнейших символов в ювелирном искусстве...

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

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

Наука и жизнь
Карманные мозги, что управляют всем: микроконтроллеры от первых 4-бит до IoT-революции Карманные мозги, что управляют всем: микроконтроллеры от первых 4-бит до IoT-революции

История микроконтроллеров от их зарождения до современных тенденций

Наука и техника
Okean в океане Okean в океане

Актуальная модельная линейка Okean интересного бренда Okean Yachts

Y Magazine
Свеклосахарная отрасль теряет маржу Свеклосахарная отрасль теряет маржу

Валовой сбор сахарной свеклы в этом году, вероятно, будет выше, чем в прошлом

Агроинвестор
Не только еда, но и впечатления Не только еда, но и впечатления

Как в России развивается гастрономический туризм

Агроинвестор
«Мы уже не живем в своей колыбели» «Мы уже не живем в своей колыбели»

Чем дышит и живет Институт космических исследований РАН?

Знание – сила
Узорочье древних славянок Узорочье древних славянок

Древняя мода: как выглядела одежда на Руси до XIII века

Знание – сила
Светлое темное будущее Светлое темное будущее

Электроземледелие — технология, которая обещает обеспечить пищей человечество

ТехИнсайдер
Жук-лягушка, не знающий вывихов Жук-лягушка, не знающий вывихов

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

Наука и жизнь
Пустые кресла и забытые письма: одиночество как экспонат Пустые кресла и забытые письма: одиночество как экспонат

Мы приезжаем в музей смотреть не на экспонаты, а внутрь себя

Знание – сила
О пользе «бумажной волокиты» О пользе «бумажной волокиты»

На каком языке говорили евреи, вернувшиеся из вавилонского пленения?

Знание – сила
Четыре всадника прогресса Четыре всадника прогресса

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

ТехИнсайдер
Гелий Гелий

Известно, что каждый элемент имеет свой, только ему одному принадлежащий спектр

Наука и жизнь
Скелетные мышцы самолета – система управления Скелетные мышцы самолета – система управления

Зачем самолетам демпферы, гидроусилители, закрылки и предкрылки?

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

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

Наука и техника
В ожидании Меркурия В ожидании Меркурия

Меркурий единственная планета Солнечной системы без атмосферы с магнитным полем

Наука и жизнь
Код нации Код нации

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

ТехИнсайдер
Вьетнамский вклад в импортозамещение Вьетнамский вклад в импортозамещение

Концерн TH Group открыл завод по переработке молока в Калужской области

Агроинвестор
Открыть в приложении