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

Наука и жизнь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

Кунсткамера Кунсткамера

Переименование растений, самая маленькая в мире лягушка и памятник жуку

Наука и жизнь
«Двойка» за хорошее поведение «Двойка» за хорошее поведение

BMW M2 Gran Coupe: баварское купе, которое на самом деле седан

Автопилот
Вместе с семьёй Вместе с семьёй

Этот дом можно назвать воплощением мечты любого горожанина

Идеи Вашего Дома
Звезды манящие Звезды манящие

Ослепительная вспышка, которой уже некого слепить, миг неуловимый

Знание – сила
Система Юпитера: Ганимед и Каллисто Система Юпитера: Ганимед и Каллисто

Что делает Ганимед и Каллисто очень интересными космическими телами?

Наука и техника
Неуместные следы и водоплавающий единорог: злоключения Карла Бау Неуместные следы и водоплавающий единорог: злоключения Карла Бау

«Научный» креационизм. Мифы и предубеждения

Наука и техника
Водяные козлы – аристократы саванн Водяные козлы – аристократы саванн

«Водяных козлов я часто встречал в восточноафриканской саванне»

Знание – сила
Космический буксир: мирный атом или ненаучная фантастика? Космический буксир: мирный атом или ненаучная фантастика?

Чем интересна перспектива использования ядерного двигателя в космосе?

Наука и техника
Возвращение гребного колеса Возвращение гребного колеса

Первые упоминания о гребном колесе относятся еще к древнейшим временам...

Наука и техника
Биология на рубеже веков, или Сто лет тому вперед Биология на рубеже веков, или Сто лет тому вперед

Биология в 1900-х годах по темпам своего развития ничуть не отставала от физики

Знание – сила
Островский – революция в русском театре Островский – революция в русском театре

Гончаров, известный трилогией на букву «О», был интересным и метким критиком

Знание – сила
Когда медицинские практики прошлого у нас в крови… Когда медицинские практики прошлого у нас в крови…

На протяжении почти 2000 лет для лечения болезней использовалось кровопускание

Знание – сила
Беззубый театр. Беседа на спорные темы Беззубый театр. Беседа на спорные темы

Продолжение статьи худрука Марка Розовского о современном театре

Знание – сила
Новости науки Новости науки

Обнаруженная в ранней Вселенной грандиозная галактика и другие новости науки

Знание – сила
В тени новой биологии, или Вверх по лестнице, ведущей вниз В тени новой биологии, или Вверх по лестнице, ведущей вниз

Сравнительная анатомия – старая наука, интеллектуальный опыт которой очень богат

Знание – сила
Культура сбережений: зачем откладывать на завтра то, что можно потратить сегодня? Культура сбережений: зачем откладывать на завтра то, что можно потратить сегодня?

Зачем каждому гражданину нужно выработать у себя привычку делать сбережения?

Наука и техника
Керосиновая история Керосиновая история

Жизнь в послевоенном социализме делится на «время керосина» и «время газа»

Знание – сила
Вновь о темной материи Вновь о темной материи

Проблема темной материи всерьез привлекает ученых

Знание – сила
Физика в поисках ответа на разгадку бытия: от Эйнштейна до Хокинга и Лоуренса Краусса Физика в поисках ответа на разгадку бытия: от Эйнштейна до Хокинга и Лоуренса Краусса

Почему существует Вселенная? Почему существует мир, почему в нем есть мы?

Знание – сила
Гладкая мускулатура самолета – электродвигатели Гладкая мускулатура самолета – электродвигатели

Как выглядят авиационные электродвигатели, где установлены и как управляются?

Наука и техника
Недоросли, скотинины, бригадиры и Стародум Недоросли, скотинины, бригадиры и Стародум

И спустя 200 лет пьесы Дениса Фонвизина остаются интересны и востребованы

Знание – сила
Перовскитные солнечные элементы как перспективное направление зеленой энергетики Перовскитные солнечные элементы как перспективное направление зеленой энергетики

Как перовскитные солнечные элементы сделают энергетическую систему экологичнее?

Наука и техника
Авианосцы ВМС Индии XXI века Авианосцы ВМС Индии XXI века

История постройки авианосца «Викрант»

Наука и техника
Сарацинка, воительница, христианка Сарацинка, воительница, христианка

В эпоху джахилийи у разных племен бедуинов положение женщин различалось

Знание – сила
Монеты в восточной пыли Монеты в восточной пыли

Важным источником наших знаний об античной истории являются монеты

Знание – сила
«Галилея археологов» «Галилея археологов»

Археологи давно борются с искушением перекопать поглубже всю Святую Землю

Знание – сила
Ударные АПЛ европейских стран НАТО Ударные АПЛ европейских стран НАТО

Лодки класса «Трафальгар» проектировались для противостояния советским подлодкам

Наука и техника
Шале на Волге Шале на Волге

Автор проекта обыграла стиль шале, предложив оригинальное авторское решение

Идеи Вашего Дома
Годовые кольца: 1610 Годовые кольца: 1610

Открытие Гудзонова залива и революция в астрономии: что случилось в 1610 году

Вокруг света
«Русланы» уходят. Часть 1 «Русланы» уходят. Часть 1

История Ан-124 «Руслан» уходит во времена зарождения реактивной авиации

Наука и техника
Открыть в приложении