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 o “Problema Digital de 15”, não é insolúvel, mas sim que o estado-objetivo 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 do jogo é uma grade 4×4 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 no canto inferior direito.

Casos insolúveis

A situação não pode ser legalmente movida para atingir 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 inicial e final estiverem na ordem inversa de grandeza, ou seja, o número na frente é maior que o número atrás. 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 do arranjo desses deslizadores. Cada vez que um deslizador é movido, um espaço é na verdade trocado com um deslizador vizinho. E esta operação de troca altera a paridade do logaritmo inverso do arranjo. O logaritmo inverso do estado objetivo é 0, que é par. Se o logaritmo inverso do estado inicial for ímpar, não importa quantas vezes ele seja movido, seu logaritmo inverso não poderá ser alterado para par, e o estado objetivo não poderá ser alcançado.

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