OliForum Matematico

Ciao a tutti
Ho bisogno di aiuto:
mi serve sapere in quanti modi posso attraversare una matrice andando da un vertice a quello opposto e muovendomi soltanto orizzontalmente, obliquamente e verticalmente, ma senza mai tornare indietro (essenzialmente tra un movimento e quello successivo la differenza tra gli indici fra l'ultima e la penultima cella, sarà comunque positiva).
Cerco di spiegarmi meglio:
ad esempio, se ho una matrice di 4 celle formanti un quadrato del tipo:
2,1 2,2
1,1 1,2
so che posso attraversare la matrice (nel modo che ho specificato) soltanto 3 volte mediante i seguenti i movimenti (1) 1,1 - 1,2 - 2,2 (2) 1,1 - 2,2 e (3) 1,1 - 2,1 - 2,2.
Per una matrice di 9 celle si ha invece:
3,1 3,2 3,3
2,1 2,2 3,2
1,1 1,2 1,3
che secondo i miei calcoli dovrebbe essere attraversata da 9 cammini possibili.
A questo punto mi verrebbe da pensare che il mio problema ha risoluzione 3^(n-1) dove n è il numero di righe e colonne (nel caso in cui la matrice sia quadrata), però non ne sono affatto certo. Inoltre avrei bisogno di avere una risposta analoga anche quando righe e colonne non hanno la stessa dimensione.
Qualcuno mi sa aiutare?
Grazie di cuore

Aggiunto spazi al latex per far andare a capo il browser. -- EG

Ciao!
Questo quesito è molto interessante, ma la questione non è affatto così semplice come può sembrare; intanto la matrice 3X3 non ha 9 cammini possibili, ma 13, quindi già in partenza la formula $ 3^{n-1} $ entra in crisi; ma a parte questo penso che ce la possiamo scordare una formula così semplice!
Io sono arrivato a un risultato parziale, che ti permette, in un tempo ragionevole (purché la matrice sia ragionevole!), di calcolare il numero di percorsi possibili di una generica matrice nXm (per convenzione considererò il primo numero quello dlele colonne e il secondo quello delle righe, ma comunque non cambia niente).
Indicherò con $ P_{(nXm)} $ il numero di percorsi possibili di una matrice nXm.
Ho ricavato alcune proprietà che ora, per questioni di tempo, posto senza dimostrazione:

1° considerazione:
se $ P_{(aXb)} = c $ allora $ P_{(bXa)} = c $

2° considerazione:
$ P_{(2Xa)} = 3 + 2(a-2) $ (ovvero il numero di percorsi di una matrice 2Xa è l' (a-1)esimo termine di una progressione aritmetica che ha per primo termine 3 e per ragione 2)

FORMULA:

$ P_{(nXm)} = P_{(2Xm)} + 2[n-2+\sum_{k=2}^{n-1}{(\sum_{i=2}^{m-1}{P_{(kXi)})]} $

Per la serie: è più facile farlo che dirlo.

Esempio:

$ P_{(3X3)} = P_{(3X2)} +2(3-2+P_{(2x2)}) = 3+ 2(3-2) + 2(1+3)= 13 $

$ P_{(4x4)} = P{(4X2)} +2 (4-2+P_{(2x2)} +P_{(2x3)}+P_{(3x2)}+P_{(3x3)}) = $3 +2(4-2) +2(2+3+5+5+13)=63

$ P_{(6X4)} = P_{(6x2)} + 2(6-2+P_{(2x2)}+ $ $ P_{(2x3)}+P_{(3x2)}+P_{(3x3)}+P_{(4x2)}+ $ $ P_{(4x3)}+P_{(5x2)}P_{(5x3)}) $
$ = 11+2(4+3+5+5+13+7+ $ $ (P_{(4X2)}+2(4-2+P_{(2x2)}+ $
$ P_{(2x3)}))+9+(P_{(5x2)}+2(5-2+P_{(2x2)}+P_{(2x3)}+P_{(2x4)})) $
$ =11+2(4+3+5+5+13+7+25+9+41) $ $ = 235 $

In pratica, ogni volta che applicando la formula trovi un P troppo grande, lo scomponi a sua volta con la formula stessa e cos' via fino a ottenere una formula che contiene solo P "noti" (cioè del tipo P_{(2xm)} o di un tipo che ti ricordi a memoria per averlo già calcolato precedentemente).
Una volta che prendi la mano fai in un attimo (a patto di non esagerare con i valori delle righe e dlele colonne!).
Il problema è che questa formula, per quanto utile, non mi basta: io volevo generalizzare queste semplificazioni includendole in una formula GENERALE, in cui compaiano solo le variabili n ed m.
Procedendo su questa strada mi sono accorto che il P di qualunque matrice può essere espresso come:

$ P_{(nXm)} = a\cdot P_{(2X2)} + b\cdot P_{(2X3)}+ c\cdot P_{(2X4)}...+ z\cdotP_{(2X(m-1))} + w $

ovvero può essere espresso come un polinomio di primo grado con m-1 incognite, rappresentate dai termini della progressione già citata di $ P_{(2Xm)} $, con i coefficienti che ci indicano il numero di volte che dobbiamo prendere ogni termine dlela progressione e con un termine noto.
Quindi per trovare la formula GENERALE bisogna trovare una relazione che mi permetta di calcolare i coefficienti (a,b,c,d...z) e il termine noto (w) in funzione del numero di righe e colonne dlela matrice, dal momento che le "incognite" del polinomio, a dispetto del loro nome, le conosciamo benissimo, essendo i pluricitati termini della progressione aritmetica con primo termine 3 e ragione 2.
Purtroppo per ora sono riuscito solo a trovare la formula per il termine noto, che è la seguente:

$ w $ di $ P_{(nXm)} = 2\cdot(n-2)+ $$ \sum_{i=2}^{n-3}{2^{n-1-i} $$ \cdot{[\frac{(n+1+i)\cdot(n-2-i)}{2}-2\cdot(n-2-i)]}} $

mentre i coefficienti continuano a sfuggirmi... e anche se ho raccotlo qualche osservazione, il loro comportamento generale in funzione di righe e colonne non mi è ancora chiaro.
Non appena farò progressi mi farò sentire...

Caspita, complimenti! ..Alla fine ho risolto il mio problema con una altro metodo (lo dico nel caso in cui non volessi continuare a cercare di trovare la soluzione generalizzata al mio quesito). Ti spiego.
Il mio problema era quello di calcolare il costo di attraversamento di una matrice, in particolare sto parlando della matrice delle distanze tra due serie storiche. Per costo di attraversamento intendo il costo pari alla somma del valore delle celle della stessa, sommate nel modo in cui ti ho parlato nel mio primo post (quindi muovendomi solo orizzontalmente, obliquamente, e verticalmente). Il motivo della questione era il calcolo del dynamic time warping che è una misura di distanza tra serie storiche appunto, che mi serve poi per implementare un algoritmo di classificazione. In pratica il dynamic time warping è un algoritmo che restituisce la minima distanza tra serie storiche scegliendo di volta in volta l'effettivo minor valore di distanza e non, come succede nella distanza euclidea, la semplice distanza tra punti aventi lo stesso indice. Ti faccio un esempio. Se ho la serie storica Q con punti q1, q2, q3, ..., qn e la serie C con punti c1, c2, c3, ..., cm dove poniamo n=m, la matrice delle distanze tra punti sarà quella che ha come valore di ciascuna cella la differenza tra il punto q1 ed il punto c1, tra il punto q1 ed il punto c2, tra q1 e c3... tra q1 e cm per il solo primo punto di Q; a questo punto la seconda riga avrà in ciascuna cella la distanza tra il punto q2 e c1, q2 e c2, q2 e c3, e così via... Allora il dynamic time warping individua il cammino della matrice delle distanze (così come definita sopra) in modo tale da minimizzare la somma delle celle tra un vertice della matrice e quello opposto in modo tale che la distanza tra il primo punto della prima serie storica e della seconda serie storica e l'ultimo punto della prima serie storica e della seconda serie storica sia definita come distanza euclidea (quindi come semplice distanza tra punti aventi lo stesso indice). Ecco ti propongo qualche foto per rendere l'idea.

Questa rappresenta il dtw come somma delle minime distanze:


Questa immagine invece rappresenta la distanza euclidea tra due serie storiche:


E questa rappresenta invece il dtw:


Per concludere, il problema l'ho risolto nel seguente modo (che poi è anche quanto consiglia la letteratura.. Io sono un pò testardo, quindi appena ho letto della questione del dtw ho pensato di poterla risolvere a modo mio...): sommo di volta in volta il valore della cella i-esima j-esima alla cella (i-1)-esima j-esima, (i-1)-esima (j-1)-esima, i-esima (j-1)-esima in modo tale da minimizzare la somma; le celle (i-1)-esima j-esima, (i-1)-esima (j-1)-esima, i-esima (j-1)-esima saranno a loro volta calcolate come sopra; essenzialmente si pone il problema della ricorsione, anche se di problema non si tratta dato che ho poi formalizzato il tutto in un programma scritto in C. Facendo in questo modo e riempiendo quindi tutta la matrice n x m (che ho chiamato delle minime distanze per distinguerla dal caso precedente), posso a questo punto individuare il cammino che minimizza la somma delle distanze partendo dal vertice opposto della matrice e muovendomi verso il vertice di partenza, scegliendo di volta in volta semplicemente la cella di minor valore.
Ecco che il problema è risolto senza considerare tutti i possibili cammini della matrice delle distanze; all'inizio pensavo di dovere calcolare ogni possibile cammino per poi selezionare quello avente il minor valore, senza probabilmente fare i conti con l'elevatissima difficoltà computazionale della questione.. Tanto più che sto lavorando con serie da 100 o 150 elementi in db da 300 o 400 serie... Comunque grazie per la risposta; se ti va di continuare a cercare la soluzione generalizzata sarei felice se mi facessi partecipe della soluzione stessa; anche se ho abbandonato la questione dopo che ho trovato la soluzione sopraccitata, mi sono spaccato la testa sufficientemente per potere gioire quando avrò sotto agli occhi la risoluzione del problema dei possibili cammini... Ancora complimenti per la soluzione!! Mi raccomando di avvisarmi quando troverai quella definitiva!!

Ma siamo sicuri che sia Mne? o sono idiota o il problema è più facile di quel che sembra...

Detto x il numero di spostamenti orizzontali, banalmente quelli verticali sono x e quelli diagonali n-1-x. Tenendo x fisso, in quanti modi possiamo fare x spostamenti verticali, x orizzontali e n-1-x diagonali? Dobbiamo fare in totale n-1+x mosse, quindi:
$ $\binom{n-1+x}{x}\cdot\binom{n-1}{x} $
dove nel primo binomiale scegliamo quali saranno le mosse verticali, nel secondo quelle orizzontali. Ovviamente quelle diagonali rimangono obbligate.
Quindi la soluzione è
$ $\sum_{x=0}^{n-1}{\binom{n-1+x}{x}\cdot\binom{n-1}{x}} $

P.S. gargantua puoi spezzare la tua supertexata che inizia con $ P_{6X4} $ se no è impossibile leggere

julio14 ha scritto:Detto x il numero di spostamenti orizzontali, banalmente quelli verticali sono x e quelli diagonali n-1-x. Tenendo x fisso, in quanti modi possiamo fare x spostamenti verticali, x orizzontali e n-1-x diagonali? Dobbiamo fare in totale n-1+x mosse, quindi:
$ $\binom{n-1+x}{x}\cdot\binom{n-1}{x} $
dove nel primo binomiale scegliamo quali saranno le mosse verticali, nel secondo quelle orizzontali. Ovviamente quelle diagonali rimangono obbligate.
Quindi la soluzione è
$ $\sum_{x=0}^{n-1}{\binom{n-1+x}{x}\cdot\binom{n-1}{x}} $

Scusa, puoi fare un esempio pratico, per capirci meglio?
Che sò... calcola con questo metodo il numero di percorsi possibili della matrice 4X5. Grazie!!

P.S. si, tra un po' spezzetto la formula per renderla più leggibile. [Una volta un fisico disse: se una formula è più lunga di un quarto di pagina, non leggerla e buttala via: la natura non può essere così complicata!]

julio14 ha scritto:Ma siamo sicuri che sia Mne? o sono idiota o il problema è più facile di quel che sembra...

MNE non ha niente a che vedere con il facile/difficile. Anche "calcolare la derivata della funzione y=x^2+1" è MNE.

@gargantua sarà perchè gli esempi fatti erano quadrati (4 e 9) ma ero convinto che la matrice dovesse essere quadrata. Ora controllo, non dovrebbe essere troppo difficile riadattare a una matrice qualunque.

@fph chiedo venia.... so cos'è Mne, ma fraintendendo il testo del problema, ho dato una soluzione che usa strumenti elementari, proprio per questo che dicevo che non mi sembrava Mne... non so se la soluzione del problema vero sia elementare o meno, ma la mia lo era.

Ok la mia soluzione è facilmente adattabile ad una matrice axb.

wlog, $ a\ge b $. Detto $ x\le a-1 $ il numero di mosse orizzontali, quelle diagonali, per spostarsi in in totale di $ a-1 $ caselle orizzontalmente, sono $ a-1-x $, con lo stesso ragionamento le mosse verticali sono $ b-1-a+1+x=x-a+b $, da cui peraltro si vede che $ x $ dev'essere maggiore o uguale ad $ a-b $ per non avere un numero negativo di mosse verticali. Il numero di mosse totali sarà $ x+a-1-x+x-a+b=b-1+x $. Scegliamo in quali posizioni mettere le mosse orizzontali (prima, seconda...$ b-1+x $esima), abbiamo $ $\binom{b-1+x}{x} $ possibilità. Ci rimangono $ b-1+x-x=b-1 $ mosse e da disporre quelle verticali, quelle diagonali rimarranno obbligate. Le possibilità sono $ $\binom{b-1}{x-a+b} $.
In definitiva, la soluzione è
$ $\sum_{x=a-b}^{a-1} \binom{b-1+x}{x}\cdot \binom{b-1}{x-a+b} $

@gargantua: la formula è piuttosto complessa e calcolosa, a meno che qualcuno non riesca a semplificarla o a scrivere un programmino è lungo fare una 4X5... ti faccio vedere con una 3X2

$ $P_{3X2}=\binom{1+1}{1}\binom{1}{1-3+2}+\binom{1+2}{2}\binom{1}{2-3+2} $$ =2\cdot1+3\cdot 1=5 $


fph... non voglio essere maleducato... ma la mia soluzione mi sembra giusta e elementare, anche se non facilissima...

Ho fatto un programmino in python per il calcolo, la matrice 4x5 viene 129.

julio14 ha scritto:fph... non voglio essere maleducato... ma la mia soluzione mi sembra giusta e elementare, anche se non facilissima...

Ok, concordo che tutto quello che hai scritto sopra è elementare. Il motivo che mi porta a considerare questo problema come MNE è che non è un problema olimpico, ma un problema "self-posed" o "nato in contesto non elementare" derivante da un'applicazione di ingegneria o altro; da come lo pone giangyalb, l'impressione è che bisogni poi lavorare con le entrate della matrice e fare qualcosa tipo programmazione dinamica per minimizzare una distanza, e non solo calcolare il numero di percorsi. La parte che hai fatto tu finora è la soluzione elementare di un problema elementare, ma il lungo post di giangyalb mi fa intuire che si tratti di solo una limitata parte della questione, e che il resto sconfina nel non-olimpico. Dal punto di vista olimpico, poi, il passo successivo sarebbe cercare di chiudere la sommatoria, e non mi è chiaro neppure che si riesca a fare questo: non possiamo lasciare in combinatoria un problema in cui non è detto che la soluzione sia fattibile "con mezzi olimpici" e "in tempi olimpici", poi chi legge potrebbe essere invogliato a sprecarci molto tempo su pensando "la soluzione c'è ma io non riesco a trovarla" quando magari la soluzione non c'è.

Se non ti sembra chiaro dimmi e cerco di chiarire...

chiarissimo!
grazie e scusa ancora se rompo un po'...