Решаемые и нерешаемые комбинации



(с нашего сайта)


Решаемые и нерешаемые комбинации

 

Начальную позицию можно разложить многими способами. Всего существует

16!=20 922 789 888 000 начальных позиций.

Это с учетом расположений пустой клетки. Например, вот такая позиция.


 

Если же рассмотреть, что пустая клетка всегда находится на одном месте (например, место 1 - левый верхний угол - или место 16 - правый нижний угол, пустая позиция), то получим

15!=1 307 674 368 000 позиций.

Например, вот такое начальное расположение


Здесь рассматривается четко, что пустая клетка всегда находится в правом нижнем углу.


Половина из всех раскладов решается. Другая половина не собирается, так как приходит вот к такому положению:


Как помним, это задача Лойда.

 

Надеюсь, вы поняли, что 50% раскладов собрать не удастся.

 

Любую начальную позицию можно проверить на решаемость. Причем не надо пытаться ее собрать и посмотреть на конечное расположение 15 и 14. Для этого достаточно лишь высчитать «Четность расклада», «Параметр беспорядка» (это понятие кто как хочет, так и называет). В реале действительно быстрее просто собрать за полминуты фишки и посмотреть что получилось, нежели считать в уме многоцифар. Но для полноты картины изучим теорию. Определение четности довольно сложное. Давайте посмотрим, что пишет Википедия:

 

Можно показать, что ровно половину из всех возможных 20 922 789 888 000 (=16!) начальных положений пятнашек невозможно привести к собранному виду: пусть квадратик с числом iрасположен до (если считать слева направо и сверху вниз) k квадратиков с числами меньшими  i.. Будем считать  ni=k, то есть если после костяшки с  i-м числом нет чисел, меньших  i, то  k=0.. Также введем число  e — номер ряда пустой клетки (считая с 1). Если сумма


является нечётной, то решения головоломки не существует

 

Есть еще одно определение, попавшееся на глаза:

 

головоломка имеет решение, если так называемый параметр беспорядка (число пар чисел, в которых большее число предшествует меньшему с прибавлением номера горизонтального ряда с пустой клеткой), четный

 

Хоть оно и проще, смысл по-прежнему сложно уловить.

Попытаемся объяснить более простым языком, как подсчитать Четность.

Для этого нужно сравнивать пары чисел. Считаем количество тех пар, в которых большее число предшествует меньшему. Сравнение ведется относительно правильного порядка. Только в конце не забываем прибавить номер ряда с пустой клеткой - это число от 1 (верхняя строка) до 4 (нижняя строка). Визуально можно представить так:


Здесь указаны номера позиций. Соответственно, чем меньше номер, тем более ранняя позиция (надеюсь, этот момент понятен).

 

Например, возьмем вот такой расклад:


 

Здесь сравнивая пару 5 и 2 видим, что 5 , которая стоит раньше, больше двойки (2) , значит это одна нужная нам для счета пара, ее мы посчитаем. А 8 меньше 11, и стоит раньше, значит такую пару не считаем.

Малость теории: Всего имеется 15 фишек, что образует 105 пар (14+13+12+...+1). На практике сравнить 105 пар не так уж и сложно, только надо их четко подсчитывать. Например, можно поступить так (см. рисунок выше):

Сначала берем первое число (у нас 12). Считаем, сколько чисел меньше находится после него. На примере это одиннадцать чисел (от 1 до 11 – эти числа меньше и расположены позже, то есть после рассматриваемого нами числа 12). Результат записали.

Теперь берем второе число (5). Считаем, сколько меньших чисел стоит после него (не «до», а именно «после» - это для невъезжающих). После пятерки только четыре числа младше (от 1 до 4). Результат прибавили к прошлому значению (11+4=15).

Теперь берем третье число (8) и считаем также количество меньших чисел, стоящих после (их шесть, то есть от 1 до 7 не считая 5, так как пятерка стоит раньше).

Так и продолжаем дальше.

Не забываем в самом конце прибавить ряд с пустой клеткой. У нас на примере это третий ряд.

Мы здесь не будем полностью считать четность, эти вычисления лишь пример как нужно делать. Да и нудно это математикой заниматься в таких объемах.

Всего подсчет займет минут 5-10. Если полученная сумма четная – позиция соберется. Если иначе (нечетная) – то не соберется.

Нерешаемый расклад (нерешаемое окончание) Лойда имеет четность «1» (там только 15 предшествует 14-и и больше него).





ВебСтолица.РУ: создай свой бесплатный сайт!  | Пожаловаться  
Движок: Amiro CMS