[Lo4] Simulazione campigotto 17/03/2016 problema 19

[Stefano]

Sarà che ho qualche lacuna in combinatoria e algebra ma a me questo problema sembra molto mazzoso... di seguito il testo(specifico che la tabella in questione è costituita da 9caselle):
Su ciascuna delle caselle della tabella in figura 2 `e scritta una cifra da 1 a 9 in modo che, comunque si prendano due caselle
contigue, la cifra scritta su quella a destra `e maggiore o uguale di quella a sinistra.
Metto una pulce su una casella qualsiasi e le ordino: − Ogni volta che batter`o le mani, guarda il numero scritto sulla casella
in cui ti trovi e salta sulla casella la cui posizione, contando da sinistra, è esattamente quel numero. Ad esempio se sulla tua
casella c'è scritto il numero 1 devi saltare sulla prima casella, se c'è scritto 2 devi saltare sulla seconda, e così via.
Scopro che si verifica il fatto seguente: qualunque sia la casella dove piazzo inizialmente la pulce, dopo 2016 battiti di mani
essa va sempre a finire su una delle due caselle alle estremità della tabella.
In quanti modi diversi possono essere scritti i numeri sulla tabella?
non sono molto pratico con le successioni, comunque una successione di 9 elementi debolmente crescente si può formare in (17 su 9) modi se non erro... dal risultato dovrei togliere i casi in cui una cifra 1<a<9 occupi la posizione n=a... ma anche in questo caso proseguendo non ottengo molto... c'è qualcuno che l'abbia risolto alla simulazione o che sappia farlo, magari anche indicando un metodo generale per questo tipo di problemi??
Grazie mille in anticipo

[carlotheboss]

Non so tu cosa intenda per "mazzoso", se intendi "servono tanti conti abbastanza noiosi" allora hai ragione (almeno per come l'ho risolto io), quindi chiaramente non si risolveva in gara ma solo dopo D:
Comunque:

Testo nascosto:

Nota innanzitutto che non puoi avere cicli tra le caselle e che gli unici che puoi avere sono quando una casella ha il suo stesso numero, infatti se vi fosse un ciclo con almeno due caselle avresti che a un certo punto dovresti "tornare indietro" dopo essere andato avanti, quindi non avresti più un vettore ordinato. Chiaramente nelle caselle che non sono estremi non puoi avere lo stesso numero di casella sennò la pulce salterebbe sempre su quella, mentre $almeno$ in uno dei due estremi devi avere lo stesso numero della casella (così appena arrivi resti sempre fermo lì) [se non ci fossero in nessuna delle due, vedi subito che non potresti avere 1 e 9 da nessun'altra parte quindi non andresti mai negli estremi]. E qui noti che il $2016$ era messo a caso (potevano mettere 10 e andava bene ugualmente).
Ok ora vogliamo contare il numero di successioni non decrescenti tali che in almeno uno degli estremi ci sia lo stesso numero della casella e in nessun'altra casella intermedia ci sia lo stesso numero. Definiamo una funzione ricorsiva $f(c, n)$ che indica la risposta al problema partendo dalla casella $c$ (andando a destra verso la 9) e tale che in essa ci sia un numero $\geq n$ e iniziamo a contare tutti i modi in cui la casella $9$ ha il numero $9$.
Bene quindi i casi base sono $f(9, <numero>) = 1$ perché va bene solo il $9$. La formula ricorsiva è invece: se $n \neq c$ oppure $n = 1$allora $f(c, n) = f(c, n+1) + f(c+1, n)$ (cioé sono tutte le risposte con un numero $\geq n+1$ in $c$ e quelle in cui in $c$ si trova $n$, e quindi considero tutti i modi in cui in $c+1$ c'è un numero $\geq n$), mentre se $n = c$ ($n > 1$) allora $f(c, n) = f(c, n+1)$.
Ok quindi ora dopo aver completato la matrice $9 \times 9$, abbiamo $f(1, 1)$, cioé tutti i percorsi possibili con $9$ nella casella $9$. Ora vogliamo contare i rimanenti cioé quelli con $1$ nella casella $1$ ma senza il $9$ nella casella $9$ (sennò li conterei due volte) e ci basta prendere $f(1, 2)$ notando che se "invertiamo" la striscia e ad ogni numero $n$ sostituiamo $10 - n$ riotteniamo una striscia valida (ossia è come se la casella $9$ di prima diventasse la $1$ [con dentro $10-9=1$] e viceversa la $1$ diventasse la $9$ [per questo prendo da 2 in poi, non da 1 sennò "ridiventerebbe" 9 e riconterei due volte alcuni percorsi].

[Stefano]

grazie, comunque in effetti,essendo uno degli ultimi problemi è ovvio che sia mazzoso.... mi sembra più pulito il tuo metodo,rispetto a quello che stavo provando a fare io .tuttavia credo che si possa fare in un modo più semplice e immediato,solo che non so bene come

[carlotheboss]

Beh se trovi un bel metodo scrivilo qui

[Federico II]

Io ho fatto così (idea venuta a fine gara ma risultato trovato dopo):

Testo nascosto:

Sia $C_n$ l'$n$ esimo numero di Catalan, e $f(n)$ il numero scritto sull'$n$-esima casella. Le soluzioni sono di tre tipi:
1) $f(1)=1$ e $f(n)<n$ per $2\leq n\leq9$, e queste soluzioni sono $C_8$
2) $f(9)=9$ e $f(n)>n$ per $1\leq n\leq8$, e anche queste sono $C_8$
3) $f(1)=1$, $f(9)=9$ ed esiste $k$ con $1\leq k\leq8$ tale che $f(n)<n$ per $2\leq n\leq k$ e $f(n)>n$ per $k<n\leq8$, e queste soluzioni sono $C_0C_7+C_1C_6+\ldots+C_7C_0=C_8$.
Il risultato è quindi $3C_8=4290$.

[Stefano]

Ecco cosa cercavo, grazie mille Federico
Però se puoi, spiegheresti come hai visualizzato la presenza del numero di Catalan?

[Stefano]

Fa nient, crero di aver capito... Interi ordinabili mediante pila, vero?

[Federico II]

Testo nascosto:

Ho visualizzato la questione come dover contare il numero di percorsi sotto la diagonale in un quadrato, in cui se per esempio devi fare $f(n)<n$ allora ti tieni un indice che è inizialmente $1$, poi uno spostamento a destra significa "scrivo l'indice nella prima casella libera" mentre uno spostamento verso l'alto significa "aumento l'indice di $1$"