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).