Soluţii corecte: Doru Calcai, Zoltan Szabo, Angela Sandu, Aurel Ionescu, Stefan Gatachiu
Zoltan Szabo:
O configuraţie a jocului corespunde unei permutări de 9 elemente, spaţiul având valoarea 9.
Configuraţia de bază a jocului:
1 2 3
4 5 6
7 8 9
corespunde permutării (1,2,3,4,5,6,7,8,9).
Această permutare este pară (numărul inversiunilor este 0) şi poziţia spaţiului este impară ( poziţia 9).
Studiind permutarea după o mişcare orizontală, mutăm 8 spre dreapta şi obţinem:
1 2 3
4 5 6
7 9 8
corespunde permutării (1,2,3,4,5,6,7,9,8).
Această permutare este impară (numărul inversiunilor este 1) şi poziţia spaţiului este pară (poziţia 8).
Din configuraţia de bază, efectuând o mutare verticală, mutăm 6 în jos, obţinem
1 2 3
4 5 9
7 8 6
corespunde permutării (1,2,3,4,5,9,7,8,6).
Această permutare este impară (numărul inversiunilor este 5) şi poziţia spaţiului este pară (poziţia 6).
Se poate demonstra în general, că toate configuraţiile în care paritatea şi poziţia spaţiului au fie ambele parităţi diferite, fie ambele aceesi paritate sunt compatibile, deci există o succesiune de mutări prin care se poate ajunge dintr-o configuraţie în alta.
[Nota: vedeti spre exemplu Johnson & Story (1879) https://en.wikipedia.org/wiki/15_puzzle ]
Să studiem acum a doua configuraţie a problemei:
1 2 3
8 9 4
7 6 5
corespunde permutării (1,2,3,8,9,4,7,6,5).
Această permutare este impară (numărul inversiunilor este 11) şi poziţia spaţiului este impară (poziţia 5), deci permutarea are paritate diferita fata de pozitia initiala, dar poziţia spaţiului ramane impara!
Ceea ce demonstrează, că nu este compatibilă cu prima configuraţie, deci problema nu se poate rezolva.
Doru Calcai (observatie suplimentara):
La această concluzie se poate ajunge și metodic, realizând graful tuturor stărilor posibile pornind de la configurația inițială și urmărind ajungerea în starea finală.
Sau pentru cei cu înclinații practice, se poate recomanda jocul online :
Stefan Gatachiu:
Fiecărei configurații a cifrelor îi vom asocia o permutare de gradul 8, citind cifrele pe linii, de sus în jos, căsuța liberă nefiind luată în considerație. Astfel configurației de start îi corespunde permutarea (1, 2, 3, 8, 4, 7, 6, 5), care are 7 inversiuni, deci este o permutare impară. Configurației finale îi corespunde permutarea identică (1, 2, 3, 4, 5, 6, 7, 8), cu 0 inversiuni și este o permutare pară.
Vom arăta că în urma unei mutări paritatea permutării nu se schimbă.
Mutarea pe orizontală a unei cifre duce la aceeași permutare. Rămâne să analizăm mutările pe verticală.
La o mutare pe verticală se schimbă poziția relativă a 3 cifre. Să considerăm o secvență de 3 cifre de pe poziții consecutive (x1, x2, x3) a permutării. Printr-o mutare pe verticală se ajunge fie la secvența (x2,x3,x1), fie la secvența (x3,x1,x2). Vom considera prima secvență, cealaltă tratându-se analog.
Fie n numărul de inversiuni ale permutării celor 8 cifre. Prin mutarea pe verticală, inversiunile formate de celelalte cifre între ele sau de celelalte cifre în raport cu cifrele x1, x2, x3 nu se schimbă. Deci ne vom raporta la inversiunile formate de cifrele x1, x2, x3.
1. Dacă secvența (x1, x2, x3) nu are inversiuni, atunci x1<x2<x3.
Rezultă că secvența (x2, x3, x1) are 2 inversiuni, deci permutarea va avea n+2 inversiuni.
2. Dacă secvența (x1, x2, x3) are o inversiune, avem cazurile:
a) x1>x2, x1<x3, x2<x3
Atunci în secvența (x2, x3, x1) avem x3>x1, deci o inversiune, astfel că permutarea va avea tot n inversiuni.
b) x1<x2, x1<x3, x2>x3
Atunci în secvența (x2, x3, x1) avem x2>x3, x2>x1, x3>x1, deci 3 inversiuni, astfel că permutarea are n+2 inversiuni.
3. Dacă secvența (x1, x2, x3) are 2 inversiuni, avem cazurile:
a) x1>x2, x1>x3, x2<x3
Atunci în secvența (x2, x3, x1) nu avem nicio inversiune, deci permutarea are n-2 inversiuni.
b) x1<x2, x1>x3, x2>x3
Atunci în secvența (x2, x3, x1) avem x2>x3, x2>x1, deci 2 inversiuni, astfel că permutarea are n inversiuni.
3. Dacă secvența (x1, x2, x3) are 3 inversiuni, atunci x1>x2>x3.
Atunci în secvența (x2, x3, x1) avem x2>x3, deci o inversiune, astfel că permutarea are n-2 inversiuni.
Rezultă că numărul de inversiuni ale permutării obținute printr-o mutare pe verticală rămâne același sau se mărește/micșorează cu 2 unități, deci paritatea numărului de inversiuni nu se schimbă.
Atunci, ținând cont că permutarea de start este impară, toate permutările obținute prin mutarea cifrelor, pe orizontală sau verticală, vor fi tot impare. Cum permutarea finală este pară, rezultă că problema nu are soluție.
Logic
