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

Question

Я пытаюсь понять Доказательство здесь о том, почему пространство состояния в 15 головоломки разделено на две отдельные части, но объяснение для меня сложное.

Может ли кто -нибудь объяснить это более простыми терминами? Я боролся с этим в течение нескольких дней :(

Answer 1

Возможно, самый простой способ понять доказательство - это идея консервативное количество : Найдите некоторое количество, которое может быть получено из конфигурации, и покажите, что каждое движение сохраняет это количество. Статическая версия идеи найдена в следующей старой головоломке:

Снимите северо -восточный и юго -западный угловые квадраты с стандартной шахматной доски 8x8. Могут ли оставшиеся 62 квадрата быть выложены с использованием 31 домино?

Здесь принцип паритета прост: каждый домино занимает ровно один черный и один белый квадрат на шахматной доске, поэтому любая форма, которая может быть закреплена домино, должна иметь столько же белых квадратов, сколько черные. Поскольку форма площадью 62 квадрата имеет 32 квадрата одного цвета и 30 квадратов другого, невозможно пройти его.

Принцип сохранения для 15-й кулсы немного сложнее, но он довольно близок к этому: это также принцип паритета. Давайте накапливаем пустой квадрат. Тогда мы можем поговорить о состоянии головоломки как о перестановка чисел (1 ... 16). Теперь, учитывая произвольную перестановку чисел (1 ... $ n $), мы можем подсчитать, сколько пар цифр мы должны поменять, чтобы вернуть все цифры в их «исходное место». Существует много разных наборов свопов, которые можно сделать - например, если у вас есть перестановка (3, 2, 1), вы можете вернуться к (1, 2, 3), заменив первую и третью позиции (3 с 1) или путем замены первого и второго позиций (3 с 2), затем вторые и третьи позиции (3 с 1), затем первые и вторые позиции (1 с 2). (Минимальное количество изменений, которые необходимо сделать, называется количеством инверсии из перестановки, и это интересное количество само по себе, но здесь это не важно). Однако вы меняете числа, однако, общее количество изменений либо всегда будет нечетным (как это для (3, 2, 1)), либо всегда равно; Мы называем этот номер паритет перестановки.

Теперь, возвращаясь к пятнадцати головоломке: каждый шаг должен поменять пустой квадрат (тот, который мы пометили как «16») с каким -то другим квадратом, в одном блоке от текущей позиции квадрата. Это означает, что обмен всегда поставляется с движением одного квадрата - поэтому, если вы рассмотрите количество «общее количество замены, которые я сделал» + », перемещается, 16 находится вдали от своего домашнего квадрата», то это количество всегда будет ровным. В частности, когда 16 возвращается на ее домашний квадрат (0 уходит), тогда общее количество выполняемых изменений должно быть равномерным. Это означает, что паритет перестановки чисел (1..16), соответствующих нашей результирующей позиции, всегда ровно. Но теперь представьте себе положение оригинальной головоломки, где 14 и 15 обменялись местами; 16 дома, но был сделан только один «обмен». Поскольку это нечетное количество свопов, а не равномерное число, его нельзя добраться из базовой конфигурации.

Есть еще один незначительный улов: это показывает, что есть в наименее две категории, в которые могут попасть в 15-х положения, но не показывают, что есть Только два. Для этого необходим немного более сложный результат: а именно, что любая ровная перестановка может быть разложена как продукт того, что известно как 3-й цикл (IE меняет $ a rightarrow b rightarrow c rightarrow a $). Я не буду пытаться доказать это здесь, но самые простые доказательства работают алгоритмически - аналогично тому, как сортировка пузырей показывает, что каждая перестановка может быть получена путем замены только соседних элементов. Тем не менее, с этим результатом легко получить ровную перестановку: мы можем получить произвольный 3-цикл, перемещая наши три элемента в позиции 11, 12 и 15 на головоломке (с пустым квадратом в позиции 16, из Курс), а затем перемещая пустой квадрат вверх, влево, вниз, вправо - вы можете убедить себя, что это движение циклирует три элемента. Как только мы это сделали, мы просто отменить Те же самые движения, которые получили три элемента в эти позиции, оставляя окончательные позиции всех других элементов без изменений с их стартовых позиций. Этот способ получить произвольный 3-цикл, наряду с теоремой, позволяющей выражать любую ровную перестановку в терминах 3 циклов, а затем дает способ получить все достижимые (т. Е., соответствующую равномерной перестановке).