16-puzzle: confusión sobre el número de inversiones

Question

Para uno de mis preguntas sobre los deberes, nos dieron un 16-rompecabezas y teníamos que averiguar si es solucionable; y luego resolverlo. Mi 16-puzzle es

\begin{array}{|c|c|c|c|}\hline 1&2&3&4\\\hline 5&6& &11\\\hline 10&9&7&8\\\hline 13&14&15&12 \\\hline \end{array}

Ahora, yo sé todo acerca de la paridad de permutaciones y todo eso. Puedo encontrar el número de inversiones. Que va a ser

$$ 0 + 0 + 0 + 0 + 0 + 0 + 4 + 3 + 2 + 0 + 0 + 1 + 1 + 1 +0 = 12 $$

Incluso. Así que este 16-rompecabezas se puede resolver. Mi confusión viene de cuando me deslice mi 7 azulejo hacia arriba la creación de \begin{array}{|c|c|c|c|}\hline 1&2&3&4\\\hline 5&6&7&11\\\hline 10&9& &8\\\hline 13&14&15&12\\\hline \end{array}

Ahora si que me marque el número de inversiones llego

$$ 0+0+0+0+0+0+0+3+2+1+0+1+1+1+0=9 $$

Lo cual es extraño. Eso no debería ser posible, aunque. Hice algo mal?

Answer 1

Como se explica en Wikipedia, te olvidaste de agregar el taxi de distancia de la plaza vacía en la esquina inferior derecha de la paridad de la permuation. No es sorprendente que la permutación de los cambios de paridad cuando se aplica una transposición, como una transposición negativo de la paridad. También se olvidó de agregar el número de inversiones para la plaza vacía (de forma ficticia etiquetados $16$); lo que pasa es que su movimiento no cambia la paridad de ese número.