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

Наука и жизнь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: баварское купе, которое на самом деле седан

Автопилот
Русско-американские отношения в XIX веке. Часть 2 Русско-американские отношения в XIX веке. Часть 2

Какими были отношения США и России накануне войны между Севером и Югом

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

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

Знание – сила
Авианосцы ВМС Индии XXI века Авианосцы ВМС Индии XXI века

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

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

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

Знание – сила
Революция со счастливым концом Революция со счастливым концом

Рубеж XIX и XX веков отмечен бурными событиями в целом ряде наук

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

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

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

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

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

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

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

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

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

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

Знание – сила
Новый поход ветеранов Троянской войны Новый поход ветеранов Троянской войны

Филистимляне и троянцы против египетских фараонов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Наука и техника
Мы с тобой ровесники Мы с тобой ровесники

Как в американском фильме, все началось с фуд-трака

Seasons of life
Наполеоновские планы Наполеоновские планы

Консервы, производство свекольного сахара – это началось в Наполеоновскую эпоху

Вокруг света
Крепкий фундамент Крепкий фундамент

Особенности взаимоотношений российских яхтенных дилеров с британскими верфями

Y Magazine
Машина — зверь Машина — зверь

Анималистика в автомобильных эмблемах и именах

Автопилот
Сердце африканского духа Сердце африканского духа

У трапа Париж – Кайенна пассажиры словно по команде достают зеленые буклеты

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