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

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

Причудливая лилия кардиокринум Причудливая лилия кардиокринум

Что помогает садоводам-любителям выращивать редкий кардиокринум?

Наука и жизнь
Фрагмент истории Фрагмент истории

Интерьер, в котором сохранили стену с аутентичной кирпичной кладкой

Идеи Вашего Дома
И снова в Канны И снова в Канны

Эту модель верфь выпустила в пару к уже строящейся As8 — более крупной яхте

Y Magazine
Неприметные живые фабрики Неприметные живые фабрики

Как живые организмы синтезируют токсичные вещества

Наука и жизнь
Свежий взгляд Свежий взгляд

Основательница компании Trinity Yachts Анна Гончарук о том, как начался ее путь

Y Magazine
Оазис в городе Оазис в городе

Функциональный современный интерьер без привязки к стилевым решениям

Идеи Вашего Дома
Мерзлота не вечная: взгляд в будущее Мерзлота не вечная: взгляд в будущее

Какими экономическими потрясениями грозит таяние вечной мерзлоты

Знание – сила
«Холодный мир – это наше достояние» «Холодный мир – это наше достояние»

Что такое криосфера? Можно ли использовать знания о ней в повседневной жизни?

Знание – сила
Место пермской силы, или Пять веков деревянного Урала Место пермской силы, или Пять веков деревянного Урала

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

Знание – сила
«Малые дела» для «малой родины» «Малые дела» для «малой родины»

Земские школы как образовательный проект

Знание – сила
Мягкая сила Мягкая сила

Искусствовед — о дарах и уроках Великого шелкового пути

Seasons of life
Вулкан как туристская достопримечательность Вулкан как туристская достопримечательность

«В провинции Масая имеется огромное огненное жерло, вечно горящее...»

Наука и жизнь
День мира День мира

Наш проект «День мира» родился из истории, начавшейся почти сто лет назад

Seasons of life
Тут как тут Тут как тут

Дорога из Дербента в Махачкалу на страницах скетчбука

Seasons of life
Образование в Российской империи было доступнее, чем кажется Образование в Российской империи было доступнее, чем кажется

Каким было образование в Российской империи начала XX века?

Знание – сила
Флагман дальнего плавания Флагман дальнего плавания

Bering 165 — это судно с отвесным форштевнем и высоким бортом до миделя

Y Magazine
«Я по роду своей профессиональной деятельности всегда говорю про детей…» «Я по роду своей профессиональной деятельности всегда говорю про детей…»

О Русских международных школах и перспективах российского образования за рубежом

Знание – сила
Очищают ли растения воздух в доме? Очищают ли растения воздух в доме?

Как комнатные растения могут избавить нас от избытка углекислого газа

Наука и жизнь
Москва — Дагестан Москва — Дагестан

У дагестанцев есть уникальное умение — перенимать новое и сохранять самость

Seasons of life
Это-большечем-фильмы Это-большечем-фильмы

Почему иранский кинематограф внезапно стал так важен?

Seasons of life
Львинохвостые макаки, или Вандеру Львинохвостые макаки, или Вандеру

Львинохвостые макаки – очень капризные и не желающие быть фотомоделями

Знание – сила
На чистую воду На чистую воду

Новинка итальянской верфи Columbus Yachts — моторная суперъяхта Acqua Chiara

Y Magazine
Нейросети в «стране городов» Нейросети в «стране городов»

Как ученые изучали «Страну городов» с помощью нейросетей

Наука и жизнь
Корабль с игрушками Корабль с игрушками

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

Y Magazine
«Нет ничего прекраснее антарктических льдов» «Нет ничего прекраснее антарктических льдов»

Почему важна наука гляциология и что она изучает?

Знание – сила
Тбилисские гости Тбилисские гости

«Наша жизнь состоит из моментов, когда ты встречаешься с друзьями»

Seasons of life
Отправь меня на Луну Отправь меня на Луну

Цифра «три», похоже, стала для яхты Orion символом

Y Magazine
Другая история Другая история

Человеческому терпению нет предела, но это явно не тот случай!

Знание – сила
Лофт для гедониста Лофт для гедониста

Элементы экстерьера получили продолжение в оформлении интерьера в стиле лофт

Идеи Вашего Дома
Остаться там откуда уезжают Остаться там откуда уезжают

Как Антонио Монтальто приехал в Армению по работе, а остался из-за любви

Seasons of life
Открыть в приложении