Percorsi nel piano

[Pachisi]

Un percorso è chiamato normale se non passa per lo stesso punto due volte. Sia $f(n)$ il numero di percorsi normali di lunghezza $n$ che cominciano all'origine. Dimostrare che $2^n

Cita

Segnala

---

Risposte

consec

24 set 2016, 19:47

Non ho capito, per percorso si intende la successione di spostamenti che vanno da un punto a uno contiguo che si può raggiungere con un movimento di lunghezza unitaria? Allora $2^n$ è il numero di percorsi che si può ottenere spostandosi dall'origine di volta in volta solo in $2$ direzioni, diciamo est o nord (notiamo che ogni percorso di questo tipo rientra nella definizione perché non torna mai indietro) ma è un'evidente minorazione perché le direzioni possibili sono $4$. Per il secondo lato della disuguaglianza, $4*3^(n-1)$ è il numero di percorsi che si ricavano scegliendo come prima mossa uno qualsiasi dei punti cardinali e poi di volta in volta si esclude dalle $4$ direzioni possibili l'opposta della precedente (sud/nord e est/ovest) che è una condizione necessaria per ogni percorso normale. Questa però è una maggiorazione, basta pensare al percorso $(0,0) -> (1,0) -> (1,1) -> (0,1)$ dove per l'ultimo caso solo due direzioni sarebbero ammissibili in un percorso normale.

Cita

Segnala

---

Pachisi

25 set 2016, 17:03

Si

Cita

Segnala

---

consec

25 set 2016, 17:12

In generale il lato sinistro della disequazione mi sembra un po' grossolano, si vede subito allo stesso modo che $f(n)>=4(2^n-1)$, dove l'uguaglianza è valida solo per $n<=2$

Cita

Segnala

---

consec

28 set 2016, 12:15

Ma esiste una formula chiusa per questo problema?
Se ho fatto bene i calcoli, dovrebbe valere che
$f(n)>=4(2^n-1+\sum_{i=1}^{n-1}(2^i-2)(2^(n-i)-(n-i)) )$ e sono abbastanza sicuro che l'uguaglianza valga per lo meno fino a $n=4$

Cita

Segnala

---

Pachisi

28 set 2016, 13:45

Non esiste una formula chiusa.
Come hai trovato la disuguaglianza?

Cita

Segnala

---

consec

28 set 2016, 22:44

Dovrei aver ottenuto un'altra stima inferiore, stavolta sono fiducioso che l'uguaglianza valga anche per $n=5$, ma forse sbaglio a essere così ottimista se hai un elenco dei valori della funzione, puoi passarmelo?
$f(n)>=4(2^n-1+(\sum_{i=1}^{n-1}(2^i-2)(2^(n-i)-(n-i)))+2(\sum_{q=0}^{n-3}(\sum_{t=1}^{floor((n-q-1)/2)}(\sum_{j=1+2t}^{floor(n/2-q/2+t)}(2^(n-q-j)-2^(n-q-2j+2t)-1)+\sum_{k=floor(n/2-q/2+t+1)}^{n-q}(2^(n-q-k)-1)))))$
Direi che i casi semplici che potevano essere trattati in blocco in maniera elementare sono stati esauriti tutti, i casi più rognosi richiedono maggiori attenzioni e poi la formula inizia a complicarsi sensibilmente, quindi penso di chiuderla qui. Il problema presenta però simmetrie interessanti ed è stato istruttivo lavorarci, anche perché non mi ero mai cimentato nell'affrontare un problema così per gradi, e sono sicuro che un utente più esperto potrebbe fare di meglio, anche perché i margini di miglioramento dell'accuratezza ci sono e sono evidenti, specialmente se si legge con attenzione la terza parte. Se qualcuno vuole divertirsi a trovare stime dal basso più consistenti (o magari abbassare il bound superiore), lo prenda come un rilancio del problema. Allego una dimostrazione della formula in spoiler.

Innanzitutto il $4$ a inizio della parentesi è dovuto alla simmetria per i quattro quadranti. Dividiamo la formula in tre blocchi.

$a = 2^n-1$
$b = \sum_{i=1}^{n-1}(2^i-2)(2^(n-i)-(n-i))$
$c = 2(\sum_{q=0}^{n-3}(\sum_{t=1}^{floor((n-q-1)/2)}(\sum_{j=1+2t}^{floor(n/2-q/2+t)}(2^(n-q-j)-2^(n-q-2j+2t)-1)+\sum_{k=floor(n/2-q/2+t+1)}^{n-q}(2^(n-q-k)-1))))$

Nel seguito, chiamerò direzioni coniugate rispetto a un quadrante le direzioni che portano ad allontanarsi dall'origine senza uscire da un quadrante (ossia nord/est per il primo, nord/ovest per il secondo, sud/ovest per il terzo, sud/est per il quarto) e direzione opposta ad un'altra direzione quella che annullerebbe un movimento (quindi le doppiette nord/sud e est/ovest). Per essere più chiaro userò esempi che si riferiscono solo al primo quadrante, per simmetria il prodotto iniziale ci permette di contare tutti i casi simili negli altri quadranti.
Nei primi due casi, ci limitiamo a studiare i casi meno problematici, ossia tutte quelle mosse che ci portano ad allontanarci dall'origine. Nel terzo caso, si affronta una delle situazioni più facili da analizzare dei movimenti che prevedono una svolta ad "U" che sono però ancora ammissibili.

Blocco $a$
Il più semplice. Consideriamo una coppia di direzione coniugate e contiamo tutti i movimenti che proseguono in solo quelle due direzioni. L'uno che viene sottratto è dovuto al fatto che i movimenti monodirezionali (sono nord, solo est, solo sud, solo ovest) sono conteggiate due volte, una per ogni coppia di direzioni coniugate con quel punto cardinale in comune.

Blocco $b$
Innanzitutto notiamo che il primo fattore della sommatoria, della forma $2^i-2$, considera tutti i movimenti da $i$ spostamenti che prevedono almeno un cambio di direzione (con riferimento al primo quadrante, vengono esclusi da $2^i$ i movimenti esclusivamente verso nord e esclusivamente verso est). Poiché ogni movimento considerato consiste in almeno due spostamenti con direzione diversa, vuol dire che a seconda di ogni coppia coniugata di direzione ci addentriamo in un determinato quadrante, quindi non abbiamo mosse da bilanciare per preservare la simmetria. Il principio per proseguire è il seguente: ogni movimento da $i$ spostamenti ci manda in un punto del quadrante della forma $P(a,i-a)$. Alla fine di ogni movimento del genere, aggiungiamo uno spostamento nella direzione opposta alla coniugata dell'ultima che abbiamo percorso per arrivare al punto in questione. Ad esempio, in un percorso da $3$ mosse, se arriviamo al punto $P(1,2)$ attraverso la sequenza $(0,0)=>(0,1)=>(0,2)=>(1,2)$ poiché l'ultimo movimento è stato in direzione est, aggiungiamo uno spostamento all'opposta della coniugata di est, ossia l'opposta di nord, quindi sud. Se invece il percorso fosse stato $(0,0)=>(1,0)=>(1,1)=>(1,2)$, poiché siamo giunti a destinazione spostandoci verso nord, allora procediamo di un passo verso l'opposta della coniugata di nord, ossia l'opposta di est, quindi ovest. In pratica, quello che facciamo è che, se siamo arrivati al punto finale da uno immediatamente precedente con ascissa [rispettivamente ordinata] minore in valore assoluto, allora proseguiamo in modo che l'ascissa [rispettivamente ordinata] non decresca mai, sempre in valore assoluto. Ora, continuando dal secondo esempio, supponiamo che abbiamo fatto questo fatidico passo verso ovest. Se abbiamo fatto $i$ mosse, considerando un generico $2^i-2$, a cui abbiamo aggiunto un altro passo, ci rimango $2^(n-i-1)$ mosse da distribuire ancora. Notiamo che ora, un generico percorso che procede nell'ultima direzione, quella che abbiamo aggiunto artificialmente, e nella coniugata dell'opposta, ossia nord se come nell'esempio l'ultimo passo è stato ovest, si allontanerà sempre dall'origine e non incrocerà mai i punti che abbiamo percorso. quindi per ora abbiamo ($2^i-2)(2^(n-i-1))$. Però, considerando che una volta fatto il passo a ovest, potremo farne un alto a nord e riprendere a contare con le due direzioni coniugate di partenza, oppure due passi a ovest e uno a nord, o tre passi a ovest e uno a nord e così via, non intralceremmo nessun cammino normale fatto finora, dobbiamo aggiungere alla seconda parentesi un addendo $2^(n-i-2)$, un addendo $2^(n-i-3)$, un addendo $2^(n-i-4)$ (...) un addendo $2^1$ e un addendo $2^0$. Gli esponenti vanno a decrescere perché ci portiamo al punto di partenza facendo $1$ passi a nord e $0,1,2,3..$ ulteriori passi a ovest (che si vanno a sommare a quello aggiunto in partenza). Va però tolto un percorso ad ognuno di questi addendi ora aggiunti, perché il percorso che farebbero spostandosi solo a nord senza mai svoltare ad est sarebbe già considerato nella doppietta nord/ovest a cui contribuisce il fattore $2^(n-i-1)$. Abbiamo quindi un $(n-i-1)$ da sottrarre. La somma delle potenze di $2$ da $2^0$ a $2^(n-i-1)$ la scriviamo come $2^(n-i)-1$. Andando a fare questi percorsi per ogni possibile $1<=i<=n-1$ (ovviamente i percorsi da $n$ mosse non ci interessano perché non potremmo aggiungere il passo su cui abbiamo costruito questo discorso), perveniamo quindi a $\sum_{i=1}^{n-1}(2^i-2)(2^(n-i)-(n-i))$

Blocco $c$
Consideriamo ora tutti i punti del primo quadrante della forma $(a,1)$, con il primo e unico movimento verso nord compiuto come prima mossa e $1<=a<=n-1$ (il fattore che raddoppia serve a tenere conto anche dei punti $(1,b)$) a cui, come prima, aggiungiamo un movimento verso sud (dato che per come li abbiamo costruiti possiamo solo arrivarci da ovest muovendoci verso est). L'indice della sommatoria sta per i passi così compiuti, che sono $1$ verso nord, $1$ verso sud e $1<=j-2<=n-2$ verso est, quindi $j$ varia da $3$ a $n$. Quello che ci proponiamo di fare ora è contare tutti quei $2^(n-j)$ percorsi che puntano verso sud ovest, tendendo quindi ad avvicinarsi all'origine, che non passano però per l'origine. In generale, poiché stiamo proseguendo verso sud e verso ovest, da un punto ad ascissa $0$ (il movimento iniziale verso nord viene cancellato da quello che aggiungiamo verso sud) c'è un unico modo di arrivare all'origine, e da lì in poi si diramano $2^(n-j-(j-2))=2^(n-2j+2)$ movimenti che dobbiamo sottrarre (insieme ad un altro, il mono-sud, conteggiato nel blocco $b$). Se potessimo dire a un calcolatore di considerare pari a $0$ tutte le potenze ad esponente negativo, potremmo usare un'unica sommatoria, ma per comodità la spezziamo in $2$ usando la funzione floor perché possa funzionare per numeri pari e dispari. In generale, abbiamo bisogno di sottrarre qualcosa quando i $2^(n-j)$ percorsi possono allungarsi tanto verso ovest da poter, almeno potenzialmente, passare per l'origine. Questo vale quando $n-j>=j-2=>j<=n/2+1$. Quando $j>n/2+1$, allora tutti i percorsi (tranne uno) sono ammissibili in quanto non possono toccare l'origine. Da queste considerazioni, le due sommatorie finali.
EDIT: nel terzo caso, ragionando in maniera similare, inserisco una sommatoria che mi conta con $t$ il numero di salite verso nord che vengono effettuate all'inizio (che è uguale a quelle che servono per ritornare sull'asse dell'ascisse, stavolta verso sud). La dimostrazione è identica, semplicemente prima avevamo commentato solo il caso $t=1$.
SECONDO EDIT: stesso di prima, semplicemente la sommatoria con indice $q$, sempre con riferimento agli esempi precedenti, mi quantifica il numero di passi verso est compiuti (senza cambiare direzione) prima di svoltare verso nord $t$ volte, camminare verso est $j-2t$ volte e poi riportarsi sull'asse delle ascisse con $t$ passi verso sud

EDIT: migliorata un po' la formula
EDIT: ci sto prendendo gusto, aggiunta un'altra sommatoria

Cita

Segnala

---

Rispondi

Per rispondere a questa discussione devi prima effettuare il login.

[consec]

Non ho capito, per percorso si intende la successione di spostamenti che vanno da un punto a uno contiguo che si può raggiungere con un movimento di lunghezza unitaria? Allora $2^n$ è il numero di percorsi che si può ottenere spostandosi dall'origine di volta in volta solo in $2$ direzioni, diciamo est o nord (notiamo che ogni percorso di questo tipo rientra nella definizione perché non torna mai indietro) ma è un'evidente minorazione perché le direzioni possibili sono $4$. Per il secondo lato della disuguaglianza, $4*3^(n-1)$ è il numero di percorsi che si ricavano scegliendo come prima mossa uno qualsiasi dei punti cardinali e poi di volta in volta si esclude dalle $4$ direzioni possibili l'opposta della precedente (sud/nord e est/ovest) che è una condizione necessaria per ogni percorso normale. Questa però è una maggiorazione, basta pensare al percorso $(0,0) -> (1,0) -> (1,1) -> (0,1)$ dove per l'ultimo caso solo due direzioni sarebbero ammissibili in un percorso normale.

[Pachisi]

Si

[consec]

In generale il lato sinistro della disequazione mi sembra un po' grossolano, si vede subito allo stesso modo che $f(n)>=4(2^n-1)$, dove l'uguaglianza è valida solo per $n<=2$

[consec]

Ma esiste una formula chiusa per questo problema?
Se ho fatto bene i calcoli, dovrebbe valere che
$f(n)>=4(2^n-1+\sum_{i=1}^{n-1}(2^i-2)(2^(n-i)-(n-i)) )$ e sono abbastanza sicuro che l'uguaglianza valga per lo meno fino a $n=4$

[Pachisi]

Non esiste una formula chiusa.
Come hai trovato la disuguaglianza?

[consec]

Dovrei aver ottenuto un'altra stima inferiore, stavolta sono fiducioso che l'uguaglianza valga anche per $n=5$, ma forse sbaglio a essere così ottimista se hai un elenco dei valori della funzione, puoi passarmelo?
$f(n)>=4(2^n-1+(\sum_{i=1}^{n-1}(2^i-2)(2^(n-i)-(n-i)))+2(\sum_{q=0}^{n-3}(\sum_{t=1}^{floor((n-q-1)/2)}(\sum_{j=1+2t}^{floor(n/2-q/2+t)}(2^(n-q-j)-2^(n-q-2j+2t)-1)+\sum_{k=floor(n/2-q/2+t+1)}^{n-q}(2^(n-q-k)-1)))))$
Direi che i casi semplici che potevano essere trattati in blocco in maniera elementare sono stati esauriti tutti, i casi più rognosi richiedono maggiori attenzioni e poi la formula inizia a complicarsi sensibilmente, quindi penso di chiuderla qui. Il problema presenta però simmetrie interessanti ed è stato istruttivo lavorarci, anche perché non mi ero mai cimentato nell'affrontare un problema così per gradi, e sono sicuro che un utente più esperto potrebbe fare di meglio, anche perché i margini di miglioramento dell'accuratezza ci sono e sono evidenti, specialmente se si legge con attenzione la terza parte. Se qualcuno vuole divertirsi a trovare stime dal basso più consistenti (o magari abbassare il bound superiore), lo prenda come un rilancio del problema. Allego una dimostrazione della formula in spoiler.

Innanzitutto il $4$ a inizio della parentesi è dovuto alla simmetria per i quattro quadranti. Dividiamo la formula in tre blocchi.

$a = 2^n-1$
$b = \sum_{i=1}^{n-1}(2^i-2)(2^(n-i)-(n-i))$
$c = 2(\sum_{q=0}^{n-3}(\sum_{t=1}^{floor((n-q-1)/2)}(\sum_{j=1+2t}^{floor(n/2-q/2+t)}(2^(n-q-j)-2^(n-q-2j+2t)-1)+\sum_{k=floor(n/2-q/2+t+1)}^{n-q}(2^(n-q-k)-1))))$

Nel seguito, chiamerò direzioni coniugate rispetto a un quadrante le direzioni che portano ad allontanarsi dall'origine senza uscire da un quadrante (ossia nord/est per il primo, nord/ovest per il secondo, sud/ovest per il terzo, sud/est per il quarto) e direzione opposta ad un'altra direzione quella che annullerebbe un movimento (quindi le doppiette nord/sud e est/ovest). Per essere più chiaro userò esempi che si riferiscono solo al primo quadrante, per simmetria il prodotto iniziale ci permette di contare tutti i casi simili negli altri quadranti.
Nei primi due casi, ci limitiamo a studiare i casi meno problematici, ossia tutte quelle mosse che ci portano ad allontanarci dall'origine. Nel terzo caso, si affronta una delle situazioni più facili da analizzare dei movimenti che prevedono una svolta ad "U" che sono però ancora ammissibili.

Blocco $a$
Il più semplice. Consideriamo una coppia di direzione coniugate e contiamo tutti i movimenti che proseguono in solo quelle due direzioni. L'uno che viene sottratto è dovuto al fatto che i movimenti monodirezionali (sono nord, solo est, solo sud, solo ovest) sono conteggiate due volte, una per ogni coppia di direzioni coniugate con quel punto cardinale in comune.

Blocco $b$
Innanzitutto notiamo che il primo fattore della sommatoria, della forma $2^i-2$, considera tutti i movimenti da $i$ spostamenti che prevedono almeno un cambio di direzione (con riferimento al primo quadrante, vengono esclusi da $2^i$ i movimenti esclusivamente verso nord e esclusivamente verso est). Poiché ogni movimento considerato consiste in almeno due spostamenti con direzione diversa, vuol dire che a seconda di ogni coppia coniugata di direzione ci addentriamo in un determinato quadrante, quindi non abbiamo mosse da bilanciare per preservare la simmetria. Il principio per proseguire è il seguente: ogni movimento da $i$ spostamenti ci manda in un punto del quadrante della forma $P(a,i-a)$. Alla fine di ogni movimento del genere, aggiungiamo uno spostamento nella direzione opposta alla coniugata dell'ultima che abbiamo percorso per arrivare al punto in questione. Ad esempio, in un percorso da $3$ mosse, se arriviamo al punto $P(1,2)$ attraverso la sequenza $(0,0)=>(0,1)=>(0,2)=>(1,2)$ poiché l'ultimo movimento è stato in direzione est, aggiungiamo uno spostamento all'opposta della coniugata di est, ossia l'opposta di nord, quindi sud. Se invece il percorso fosse stato $(0,0)=>(1,0)=>(1,1)=>(1,2)$, poiché siamo giunti a destinazione spostandoci verso nord, allora procediamo di un passo verso l'opposta della coniugata di nord, ossia l'opposta di est, quindi ovest. In pratica, quello che facciamo è che, se siamo arrivati al punto finale da uno immediatamente precedente con ascissa [rispettivamente ordinata] minore in valore assoluto, allora proseguiamo in modo che l'ascissa [rispettivamente ordinata] non decresca mai, sempre in valore assoluto. Ora, continuando dal secondo esempio, supponiamo che abbiamo fatto questo fatidico passo verso ovest. Se abbiamo fatto $i$ mosse, considerando un generico $2^i-2$, a cui abbiamo aggiunto un altro passo, ci rimango $2^(n-i-1)$ mosse da distribuire ancora. Notiamo che ora, un generico percorso che procede nell'ultima direzione, quella che abbiamo aggiunto artificialmente, e nella coniugata dell'opposta, ossia nord se come nell'esempio l'ultimo passo è stato ovest, si allontanerà sempre dall'origine e non incrocerà mai i punti che abbiamo percorso. quindi per ora abbiamo ($2^i-2)(2^(n-i-1))$. Però, considerando che una volta fatto il passo a ovest, potremo farne un alto a nord e riprendere a contare con le due direzioni coniugate di partenza, oppure due passi a ovest e uno a nord, o tre passi a ovest e uno a nord e così via, non intralceremmo nessun cammino normale fatto finora, dobbiamo aggiungere alla seconda parentesi un addendo $2^(n-i-2)$, un addendo $2^(n-i-3)$, un addendo $2^(n-i-4)$ (...) un addendo $2^1$ e un addendo $2^0$. Gli esponenti vanno a decrescere perché ci portiamo al punto di partenza facendo $1$ passi a nord e $0,1,2,3..$ ulteriori passi a ovest (che si vanno a sommare a quello aggiunto in partenza). Va però tolto un percorso ad ognuno di questi addendi ora aggiunti, perché il percorso che farebbero spostandosi solo a nord senza mai svoltare ad est sarebbe già considerato nella doppietta nord/ovest a cui contribuisce il fattore $2^(n-i-1)$. Abbiamo quindi un $(n-i-1)$ da sottrarre. La somma delle potenze di $2$ da $2^0$ a $2^(n-i-1)$ la scriviamo come $2^(n-i)-1$. Andando a fare questi percorsi per ogni possibile $1<=i<=n-1$ (ovviamente i percorsi da $n$ mosse non ci interessano perché non potremmo aggiungere il passo su cui abbiamo costruito questo discorso), perveniamo quindi a $\sum_{i=1}^{n-1}(2^i-2)(2^(n-i)-(n-i))$

Blocco $c$
Consideriamo ora tutti i punti del primo quadrante della forma $(a,1)$, con il primo e unico movimento verso nord compiuto come prima mossa e $1<=a<=n-1$ (il fattore che raddoppia serve a tenere conto anche dei punti $(1,b)$) a cui, come prima, aggiungiamo un movimento verso sud (dato che per come li abbiamo costruiti possiamo solo arrivarci da ovest muovendoci verso est). L'indice della sommatoria sta per i passi così compiuti, che sono $1$ verso nord, $1$ verso sud e $1<=j-2<=n-2$ verso est, quindi $j$ varia da $3$ a $n$. Quello che ci proponiamo di fare ora è contare tutti quei $2^(n-j)$ percorsi che puntano verso sud ovest, tendendo quindi ad avvicinarsi all'origine, che non passano però per l'origine. In generale, poiché stiamo proseguendo verso sud e verso ovest, da un punto ad ascissa $0$ (il movimento iniziale verso nord viene cancellato da quello che aggiungiamo verso sud) c'è un unico modo di arrivare all'origine, e da lì in poi si diramano $2^(n-j-(j-2))=2^(n-2j+2)$ movimenti che dobbiamo sottrarre (insieme ad un altro, il mono-sud, conteggiato nel blocco $b$). Se potessimo dire a un calcolatore di considerare pari a $0$ tutte le potenze ad esponente negativo, potremmo usare un'unica sommatoria, ma per comodità la spezziamo in $2$ usando la funzione floor perché possa funzionare per numeri pari e dispari. In generale, abbiamo bisogno di sottrarre qualcosa quando i $2^(n-j)$ percorsi possono allungarsi tanto verso ovest da poter, almeno potenzialmente, passare per l'origine. Questo vale quando $n-j>=j-2=>j<=n/2+1$. Quando $j>n/2+1$, allora tutti i percorsi (tranne uno) sono ammissibili in quanto non possono toccare l'origine. Da queste considerazioni, le due sommatorie finali.
EDIT: nel terzo caso, ragionando in maniera similare, inserisco una sommatoria che mi conta con $t$ il numero di salite verso nord che vengono effettuate all'inizio (che è uguale a quelle che servono per ritornare sull'asse dell'ascisse, stavolta verso sud). La dimostrazione è identica, semplicemente prima avevamo commentato solo il caso $t=1$.
SECONDO EDIT: stesso di prima, semplicemente la sommatoria con indice $q$, sempre con riferimento agli esempi precedenti, mi quantifica il numero di passi verso est compiuti (senza cambiare direzione) prima di svoltare verso nord $t$ volte, camminare verso est $j-2t$ volte e poi riportarsi sull'asse delle ascisse con $t$ passi verso sud

EDIT: migliorata un po' la formula
EDIT: ci sto prendendo gusto, aggiunta un'altra sommatoria