Pagina 1 di 1
Percorsi, formula.
Inviato: 19 feb 2010, 14:01
da ghilu
Prendiamo una tabella con $ x\ \ righe $ e $ x+y\ \ colonne $. (x,y nonnegativi).
Coloriamo di bianco le prime $ y+1\ $ caselle della prima riga,
le prime $ y+2 $ caselle della seconda...
...
fino a tutte quelle dell'ultima (x-esima).
Le restanti le coloriamo di nero.
Trovare una formula chiusa per contare il numero dei percorsi che partono nella casella in alta a sx e terminano in basso a dx passando solo per le caselle bianche, potendo passare di casella in casella con 2 sole mosse:
-giù di una; - a dx di una.
Inviato: 19 feb 2010, 21:44
da amatrix92
posso chiederti una delucidazione sul testo?
se le colonne sono $ x + y $ ; e le caselle che coloriamo di bianco per ogni riga sono $ y + 2 $ ; a meno che $ x $ non sia uguale a $ 2 $, il numero di colonne è magigore al numero di caselle colorate; e perciò le caselle $ y+2<n<x+y $ saranno obbligatoriamente nere, allora come faccio ad arrivare ad una casella nera se posso passare solo dalle bianche?
Inviato: 20 feb 2010, 21:11
da ghilu
C'era scritto y+1: per vederlo basta muovere il cursore sulla formula.
Ora ho aggiunto uno spazio per renderlo meglio visualizzabile.
Inviato: 24 feb 2010, 22:43
da gibo92
(x+y su x) - (x+y+1 su x-1)
ora sono molto stanco quindi scrivo veloce:
tutti i percorsi possibili su un normale rettangolo (x+y) per (x) sono (x+y su x) a cui devo togliere le mosse "illecite" ossia ke passano sul nero.
allora faccio ke da quando arrivo sulla prima casella illecita del mio persorso faccio la mossa opposta a quella ke dovrei fare ossia se devo andare giù vado a destra e se devo andare a destra vado giù, in questo modo creo un percorso alternativo ke esce dal percorso normale circa in questo modo
quindi tutti i percorsi illeciti sono tutti i percorsi di lunghezza x+y+1 e larghezza x-1 da cui la formula (x+y su x) - (x+y+1 su x-1)
Inviato: 02 mar 2010, 16:41
da cromat
(x+y su x) - (x+y+1 su x-1)
ora sono molto stanco quindi scrivo veloce:
tutti i percorsi possibili su un normale rettangolo (x+y) per (x) sono (x+y su x) a cui devo togliere le mosse "illecite" ossia ke passano sul nero.
allora faccio ke da quando arrivo sulla prima casella illecita del mio persorso faccio la mossa opposta a quella ke dovrei fare ossia se devo andare giù vado a destra e se devo andare a destra vado giù, in questo modo creo un percorso alternativo ke esce dal percorso normale circa in questo modo
quindi tutti i percorsi illeciti sono tutti i percorsi di lunghezza x+y+1 e larghezza x-1 da cui la formula (x+y su x) - (x+y+1 su x-1)
a me sinceramente venivano numeri diversi e una soluzione solo abbozzata...
anche io avevo cominciato vedendo tutti i possibili percorsi in un rettangolo (X; X+Y) e mi venivano (2X+Y-2) su (X-1) il latex scarseggia.. per poi sottrarre quelle che passavano per il nero
ma a testimoniare l'inutilità dle mio primo passaggio
poi avevo pensato che i percorsi accettabili sono quelli che se soddisfano la seguente condizione:
posso fare l'N-esimo passo verso destra (->) solo se ho già fatto almeno [N(->) - Y ] passi verso il basso... poi ora bisognerebbe calcolare quanti sono
