Percorsi, formula.

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
ghilu
Messaggi: 178
Iscritto il: 06 gen 2008, 18:14
Località: bergamo

Percorsi, formula.

Messaggio da ghilu » 19 feb 2010, 14:01

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.
Ultima modifica di ghilu il 20 feb 2010, 21:10, modificato 1 volta in totale.
Non si smette mai di imparare.

amatrix92
Messaggi: 818
Iscritto il: 21 nov 2008, 17:19
Località: Firenze

Messaggio da amatrix92 » 19 feb 2010, 21:44

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? :shock:

Avatar utente
ghilu
Messaggi: 178
Iscritto il: 06 gen 2008, 18:14
Località: bergamo

Messaggio da ghilu » 20 feb 2010, 21:11

C'era scritto y+1: per vederlo basta muovere il cursore sulla formula.
Ora ho aggiunto uno spazio per renderlo meglio visualizzabile.
Non si smette mai di imparare.

Avatar utente
gibo92
Messaggi: 95
Iscritto il: 27 dic 2009, 20:39

Messaggio da gibo92 » 24 feb 2010, 22:43

(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
Immagine
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)

cromat
Messaggi: 70
Iscritto il: 24 feb 2007, 22:32
Località: roma

Messaggio da cromat » 02 mar 2010, 16:41

(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 :D 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 :cry:

Rispondi