Soluţii corecte: Ionel-Vasile Pit-Rada.

Nota: Am primit mai multe incercari de calcul prin formule, dar niciuna dintre aceste incercari nu este corecta / completa. Numarul de cazuri de analizat este foarte mare, iar o rezolvare pe hartie / prin formule de calcul ne este momentan necunoscuta. Rezolvarea problemei printr-un program necesita de asemenea o implementare foarte eficienta, altfel timpul de executie face rezolvarea nefesabila.

 

Ionel-Vasile Pit-Rada:

Am presupus ca datele sunt mai mari de 64 biti, am rulat cu python si am obtinut acum raspunsul: 

19998889292265966317716

 

n, w, h = 24, 6, 4

 

dp = [[0 for i in range(n)] for mask in range(1 << n)]

 

for i in range(n):

    dp[1 << i][i] = 1

 

not_neighbors = [[False for j in range(n)] for i in range(n)]

for i in range(n):

    y1, x1 = i/w, i%w

    for j in range(n):

        y2, x2 = j/w, j%w

        not_neighbors[i][j] = not ((x1 == x2 and abs(y1 - y2) == 1) or (y1 == y2 and abs(x1 - x2) == 1))

 

for mask in range(1 << n):

    bits_in_mask = [b for b in range(n) if ((1 << b) & mask) != 0]

    bits_not_in_mask = [b for b in range(n) if ((1 << b) & mask) == 0]

    for i in bits_in_mask:

        if dp[mask][i] != 0:

            for j in bits_not_in_mask:

                dp[mask | (1 << j)][j] += not_neighbors[i][j] * dp[mask][i]

 

print(sum(dp[(1 << n) - 1]))

 

Zoltan Szabo face cateva observatii interesante:

Pe oeis.org am găsit următoarele articole care au legătură cu problema noastră:

A229429 – A(m,n) -Numărul de modalități de numerotare a celulelor unei matrice m*n, astfel încât oricare două elemente adiacente să nu aibă etichete adiacente;

A002464 – A(1,n) - Numărul permutațiilor de lungime n fără să aibă două numere naturale consecutive în ordine crescătoare sau descrescătoare.

A229430 - A(2,n) - Numărul de modalități de numerotare a celulelor unei matrice 2*n, astfel încât oricare două elemente adiacente să nu aibă etichete adiacente;

Tabelul de mai jos conține anumite numere ale matricei A. Din păcate elementul A(4,6)=A(6,4) lipsește.

A

0

1

2

3

4

0

1

1

1

1

1

1

1

1

0

0

2

2

1

0

0

24

1’660

3

1

0

24

12’072

16’595’940

4

1

2

1’660

16’595’940

696’497’375’736

5

1

14

160’524

46’053’512’896

16-17 cifre

6

1

90

21’914’632

14 cifre

20-22 cifre

Comparativ cu celelalte elemente, ne dăm seama că numărul natural cerut este format din 20-22 cifre, ceea ce înseamnă că foarte probabil nu se poate reprezenta în calculator ca un număr pe 64 de biți (unsigned long long).