RMM 2024 P1

[Stef2008]

Ciao, ho fatto questo problema, mi è sembrato carino... se qualcuno prova e ha bisogno posterò degli hint...Intanto il problema:

Sia $n$ un intero positivo. Inizialmente, un alfiere è piazzato nella prima riga di una scacchiera $2^n \times 2^n$; questi alfieri sono numerati da $1$ a $2^n$ da sinistra destra. Un salto è una mossa simultanea fatta da tutti gli alfieri in modo tale che ciascun alfiere si muova diagonalmente, di un certo numero di quadrati e alla fine del salto tutti gli alfiieri stanno in quadrati diversi della stessa riga.

Trova il numero totale di permutazioni $\sigma$ dei numeri $1, 2, \ldots, 2^n$ con la seguente proprietà: Esiste una sequenza di salti tale che tutti gli alfieri finiscono sulla riga inferiore disposti nell'ordine $\sigma(1), \sigma(2), \ldots, \sigma(2^n)$, da sinistra a destra.