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

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

Погружение в Африку Погружение в Африку

Маршрут доктора Дэвида Ливингстона вглубь Африки спустя 160 лет

Вокруг света
Десять цветов Десять цветов

Самые древние и почитаемые традиционные ремесла – часть культурного кода Мьянмы

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

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

Наука и жизнь
Керосиновая история Керосиновая история

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

Знание – сила
Фантастический сюжет Фантастический сюжет

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

Наука и жизнь
Сошедший с орбиты Сошедший с орбиты

Как австралийцы изобрели «орбитальный» двигатель внутреннего сгорания

Наука и жизнь
Первый украинский губернатор Первый украинский губернатор

В истории портретов случаются удивительные метаморфозы

Дилетант
Зажигаем звезды Зажигаем звезды

Подборка историй о людях, которые двигают прогресс небывалым

ТехИнсайдер
Внуки лунохода Внуки лунохода

Экскурсия в инженерный центр беспилотных технологий «Яндекса»

Популярная механика
Беззубый театр. Беседа на спорные темы Беззубый театр. Беседа на спорные темы

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

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

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

Наука и техника
Китайское техно Китайское техно

Краткая история технологического идеализма

ТехИнсайдер
Система Юпитера: Ганимед и Каллисто Система Юпитера: Ганимед и Каллисто

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

Наука и техника
Время спать Время спать

Хотите впасть в спячку до весны? Теоретически для этого нет никаких препятствий

ТехИнсайдер
Кочевая кузница Кочевая кузница

Путешествие в край шаманов за секретами якутских мастеров

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

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

Наука и техника
Липецк: за рулем и пешком Липецк: за рулем и пешком

Как в Липецкой области мастера восстанавливают связь между прошлым и настоящим

Вокруг света
Созданы в России Созданы в России

Доля семян российской селекции в посевах приблизилась к 68%

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

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

Знание – сила
Техпарад Техпарад

Выстрел «Авророй», космос на 3D-принтере и тактильные виртуальные переживания

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

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

Знание – сила
Аграрный PR как часть стратегии развития компании Аграрный PR как часть стратегии развития компании

Какие эффективные инструменты маркетинговых коммуникаций используют в 2025 году

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

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

Наука и техника
Монеты в восточной пыли Монеты в восточной пыли

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

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

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

Знание – сила
Лингвистические фантомы Лингвистические фантомы

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

Наука и жизнь
Апрель: «нашествие» хохлаток Апрель: «нашествие» хохлаток

Хохлатки-эфемероиды — радостный вскрик пробуждающейся природы

Наука и жизнь
«Сейчас период повышения внутренней эффективности» «Сейчас период повышения внутренней эффективности»

Дмитрий Фосман — о перспективах развития экспорта и работе по привлечению кадров

Агроинвестор
«Галилея археологов» «Галилея археологов»

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

Знание – сила
Бурялом Бурялом

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

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