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

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

Ускользающие инопланетяне Ускользающие инопланетяне

Новая шкала инопланетных цивилизаций

Популярная механика
Мускулы крылатой машины – система управления Мускулы крылатой машины – система управления

Как пилот заставляет слушаться машину в десятки тонн, контролируя ее в воздухе?

Наука и техника
Отчаянные головоломки: «Счастливая семёрка» Отчаянные головоломки: «Счастливая семёрка»

Трёхмерная аналогия «Пятнашек»

Наука и жизнь
Жабрей и зябра, они же пикульники Жабрей и зябра, они же пикульники

Пикульники — настоящие джентльмены среди растения, хотя и каждый со своим нравом

Наука и жизнь
Фантастический сюжет Фантастический сюжет

Кем стал никогда не бросавший пера Проспер Мериме?

Наука и жизнь
Не всякая поганка — гриб Не всякая поганка — гриб

Почему красивых и изящных водоплавающих птиц назвали поганками?

Наука и жизнь
Как в Даурии радужный камень нашли Как в Даурии радужный камень нашли

Флюорит — завораживающий минерал, появившийся в природной «лаборатории»

Наука и жизнь
Наука в фантастике: эпизоды истории Наука в фантастике: эпизоды истории

Сказочная повесть — фантастика с просветительской задачей

Наука и жизнь
Иллюзия успеха Иллюзия успеха

Четыре истории о талантливых мастерах пускать пыль в глаза

Популярная механика
Жизнь и открытия Степана Куторги: от классиков до звероящеров Жизнь и открытия Степана Куторги: от классиков до звероящеров

«Удивительные ошибки» гения: как российский ученый открыл звероящеров

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

Как масло для дерева может стать причиной пожара?

Наука и жизнь
Безмолвный пациент, или вакцинация в аквакультуре Безмолвный пациент, или вакцинация в аквакультуре

Кто, как и зачем вакцинирует рыб в аквахозяйствах?

Наука и жизнь
Когда ещё был лес… Когда ещё был лес…

Рассказ Саши Тэмлейн «Когда ещё был лес…»

Наука и жизнь
Евпатория Евпатория

Евпатория — город, существующий во многих измерениях

Знание – сила
Современные подводные лодки постройки Швеции и Нидерландов Современные подводные лодки постройки Швеции и Нидерландов

Швеция и Нидерланды: как изменилась отечественная школа подводного судостроения

Наука и техника
Социология утопии, или Почему у Стругацких в их «Мире Полудня» нет котиков и попугайчиков Социология утопии, или Почему у Стругацких в их «Мире Полудня» нет котиков и попугайчиков

Почему на Прекрасной Земле Будущего полностью отсутствуют домашние питомцы

Знание – сила
Что скрывается за модным словом «роялти» ? Что скрывается за модным словом «роялти» ?

Пассивный доход на интеллектуальной собственности: как работает роялти?

Наука и техника
Мир экзопланет: что для космоса «норма»? Мир экзопланет: что для космоса «норма»?

Уже можно говорить о планетах необычных. Как выглядят «обычные» – установлено

Наука и техника
Есть ли жизнь на Марсе? Есть ли жизнь на Марсе?

Пройдемся по имеющимся фактам в вопросе о жизни на Марсе

Наука и техника
Чтобы изучать Вселенную, надо выходить в космос Чтобы изучать Вселенную, надо выходить в космос

Институт астрономии РАН запустит УФ-обсерваторию и создаст лунную базу

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

Сергей Богун о проблемах защиты редких степных видов

Знание – сила
Полет Fram2 Полет Fram2

Командиром этого полета был Ван Чунь – миллионер, оплативший полет участников

Наука и техника
«Дом А. Ф. Лосева» «Дом А. Ф. Лосева»

О том, как создавалась уникальная структура Дома Лосева

Знание – сила
Мост – это мир со своими законами Мост – это мир со своими законами

Наш сегодняшний разговор – не о фантастике, а о фантастических мостах

Знание – сила
Греки на краю мира Греки на краю мира

Какие сокровища нашлись у северных берегов Чёрного моря, но не в Греции?

Наука и жизнь
Дейнотерий – слон с берегов Дона Дейнотерий – слон с берегов Дона

Слоны – одни из самых стабильных в эволюционном плане животных...

Наука и техника
Свиноводство вступило в зрелую стадию Свиноводство вступило в зрелую стадию

За последние 20 лет свиноводческий сектор радикально трансформировался

Агроинвестор
Непотопляемый Непотопляемый

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

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

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

Знание – сила
Петербургские мосты в XVIII веке Петербургские мосты в XVIII веке

Как и когда были возведены первые мосты Петербурга

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