perché-il-puzzle-a-15-pezzi-è-insolubile

Perché il puzzle a 15 pezzi non è risolvibile

Il "puzzle a 15 pezzi", noto anche come "problema digitale a 15", non è insolubile, ma piuttosto lo stato obiettivo non può essere raggiunto in alcuni stati iniziali.

Descrizione del gioco

Il "puzzle a 15 pezzi" è un gioco di scorrimento in cui il tabellone è una griglia 4x4 con 15 caselle scorrevoli numerate da 1 a 15 e uno spazio vuoto. L'obiettivo del giocatore è spostare le caselle in ordine da sinistra a destra e dall'alto in basso, ottenendo una sequenza ordinata da 1 a 15, con lo spazio vuoto nell'angolo in basso a destra.

Casi insolubili

La situazione non può essere legalmente spostata per raggiungere lo stato target se e solo se il numero di coppie invertite nello stato iniziale è dispari. Una coppia invertita è una coppia di numeri in una serie che sono chiamati una coppia invertita se le loro posizioni anteriore e posteriore sono nell'ordine di grandezza opposto, ovvero il numero davanti è maggiore del numero dietro. Ad esempio, nella serie 2, 4, 3, 1, le coppie inverse sono (2, 1), (4, 3), (4, 1), (3, 1), per un totale di quattro.

Dimostrazione.

Il movimento delle caselle sul tabellone può essere considerato come una trasformazione dell'assetto di queste caselle. Ogni volta che una casella viene spostata, uno spazio viene effettivamente scambiato con una casella adiacente. E questa operazione di scambio modifica la parità del logaritmo inverso dell'assetto. Il logaritmo inverso dello stato target è 0, che è pari. Se il logaritmo inverso dello stato iniziale è dispari, indipendentemente dal numero di volte che viene spostato, il suo logaritmo inverso non può essere cambiato in pari, e lo stato target non può essere raggiunto.

Se ti piace giocare anche a Puzzles ball, è totalmente gratuito, divertente e facile.