por-que-o-quebra-cabeca-de-15-e-insoluvel

Por que o quebra-cabeça de 15 é insolúvel

O "Quebra-cabeça de 15", também conhecido como "Problema Digital de 15", não é insolúvel, mas sim o estado-alvo não pode ser alcançado em certos estados iniciais.

Descrição do jogo

"O quebra-cabeça de 15 é um jogo de deslizamento onde o tabuleiro de jogo é uma grade 4x4 com 15 deslizadores numerados de 1 a 15 e um espaço vazio. O objetivo do jogador é mover os deslizadores em ordem da esquerda para a direita e de cima para baixo, resultando numa sequência ordenada de 1 a 15, com o espaço vazio no canto inferior direito.

Casos insolúveis

A situação não pode ser legalmente movida para alcançar o estado-alvo se, e somente se, o número de pares em ordem inversa no estado inicial for ímpar. Um par em ordem inversa é um par de números numa série que é chamado de par em ordem inversa se suas posições anterior e posterior estiverem na ordem de grandeza oposta, ou seja, o número anterior é maior do que o número posterior. Por exemplo, na série 2, 4, 3, 1, os pares inversos são (2, 1), (4, 3), (4, 1), (3, 1), totalizando quatro.

Prova.

O movimento dos deslizadores no tabuleiro pode ser considerado como uma transformação da disposição desses deslizadores. Cada vez que um deslizador é movido, um espaço é trocado com um deslizador adjacente. E esta operação de troca altera a paridade do logaritmo inverso do arranjo. O logaritmo inverso do estado-alvo é 0, que é par. Se o logaritmo inverso do estado inicial for ímpar, não importa quantas vezes seja movido, seu logaritmo inverso não poderá ser alterado para par, e o estado-alvo não poderá ser alcançado.

Se você gosta de jogar Puzzles ball também, é totalmente grátis, divertido e fácil.