[L03/04] La strada della pulce

[Gerald Lambeau]

Una pulce si trova inizialmente nel punto $(0, 0)$ del piano cartesiano. Successivamente compie $n$ salti. Ogni salto viene effettuato in una a scelta delle quattro direzioni cardinali. Il primo salto è di lunghezza $1$, il secondo di lunghezza $2$, il terzo di lunghezza $4$, e così via, fino all'$n$-salto, che è di lunghezza $2^{n−1}$. Dimostrare che, se si conosce la posizione finale della pulce, allora è possibile determinare univocamente la sua posizione dopo ciascuno degli $n$ salti.

[alexthirty]

È un Cese se non mi sbaglio?

[Gerald Lambeau]

Sì lo è.

[carlotheboss]

Bel problema

Testo nascosto:

Se riesco a dimostrare che dalla casella finale è univoco il percorso fatto nel modo scelto che porta all'origine allora ho anche dimostrato il problema perché è possibile determinare univocamente le varie caselle. Ora noto due interessanti proprietà: la pulce può trovarsi solo in caselle del tipo $(2m, 2m+1)$ o $(2m+1, 2m)$ in quanto dopo il primo salto si troverà in una cella con una coordinata dispari e una pari e i salti dopo, essendo tutti di lunghezza pari, lasciano invariata la parità delle due coordinate e inoltre se dopo $n$ salti mi trovo in $(a, b)$ deve valere $\sum_{i=0}^{n-1} 2^i = 2^n - 1 \geq |a| + |b|$, sennò non sarei stato in grado di arrivare lì con $n$ salti.
Ora suppongo di trovarmi in $(a, b)$ dopo $n+1$ salti e voglio determinare univocamente la casella precedente (ovvero quella da cui ho fatto un salto di $2^n$ e sono arrivato dove sono).
Se $a=0$ oppure $b=0$ è immediato, lo dimostro solo per $b=0$, ovvero quando sono sull'asse $x$, dato che il ragionamento è uguale per $a=0$. Sia $a < 0$ WLOG. Il salto di $2^n$ che mi porta in $(a-2^n, 0)$ è chiaramente da scartare in quanto da lì, saltando in avanti, non riuscirei nemmeno a raggiungere $a$ (e a maggior ragione l'origine) poiché $\sum_{i=0}^{n-1} 2^i = 2^n - 1 < 2^n$. I due salti lungo l'asse delle $y$ sono poi anch'essi da scartare perché mi porterebbero in $(a, 2^n)$ e $(a, -2^n)$ e da lì, per lo stesso motivo di prima, non riuscirei a riandare in una casella con $y=0$. Dunque ho escluso 3 salti su 4, il che vuol dire che in caselle del tipo $(a, 0)$ so univocamente qual è la casella precedente [in questo caso è $(a+2^n, 0)$]. Il caso di $a>0$ è simmetrico.

Tolti questi casi "degeneri" mi rimane da analizzare il caso $(a, b)$ con $a \neq 0$ e $b \neq 0$. Suppongo WLOG di essere in una casella del terzo quadrante $(a, b)$ (cioé $a, b < 0$) dopo $n+1$ salti: devo quindi determinare univocamente un salto di $2^n$. Due salti li escludo a priori per motivi simili a prima e questi due salti sono $(a-2^n, b)$ e $(a, b-2^n)$ che mi porterebbero ad allontanarmi ulteriormente dall'origine [vedi sopra]. Mi rimangono due salti tra cui scegliere e siano $(-d, c)$ (secondo quadrante) e $(2^n - d, -(2^n - c))$ (quarto quadrante) le caselle in cui essi mi portano con $0 < d,c < 2^n$ [sono due vertici opposti di un quadrato di lato $2^n$]. A questo punto mi ricordo della seconda proprietà citata inizialmente, cioé se vado in $(-d, c)$ deve valere $\sum_{i=0}^{n-1} 2^i = 2^n - 1 \geq |-d| + |c| = d + c$ mentre se vado in $(2^n - d, -(2^n - c))$ deve valere $2^n - 1 \geq (2^n - c) + (2^n - d) = 2^{n+1} - (d+c)$. Sommando le due disuguaglianze ottengo $2^{n+1} - 2 \geq 2^{n+1}$ che è impossibile dunque non possono valere entrambe contemporaneamente. Ora dimostro che una delle due deve valere per forza e sarà la casella corrispondente quella dove dovrò andare: infatti se $d+c \leq 2^n - 1$ vale la prima disuguaglianza, sennò (essendo $d+c$ dispari) vale $d+c \geq 2^n + 1$ e quindi $2^{n+1} - (d+c) \leq 2^{n+1} - 2^n - 1 = 2^n - 1$, cioé vale la seconda disuguaglianza.

Ho dunque dimostrato che è possibile determinare univocamente la casella precedente da qualunque punto (a cui la pulce è arrivata seguendo un percorso fatto in quel modo, ovviamente). Sono sicuro che questo procedimento arriva all'origine in quanto reiterando il procedimento ogni volta la distanza (vista come $|\Delta x| + |\Delta y|$) dall'origine diminuisce ed è sempre minore o uguale alla somma dei salti che mi restano da fare quindi alla penultima iterazione sarò in una casella a distanza esattamente uguale a $1$ dall'origine e quindi con un salto di $2^0 = 1$ sarò nell'origine.
P.S: non posso arrivare "prima del tempo" nell'origine in quanto finché non faccio un salto di lunghezza dispari, cioé $1$, sono sempre in celle con $x$ e $y$ dalla parità diversa, quindi non l'origine.

[Gerald Lambeau]

Buona! La mia è un po' più semplice:

Testo nascosto:

Supponiamo di aver saputo trovare fino al $i-1$-esimo salto e di averli "cancellati" dalle coordinate (cioè per ogni $j<i$ sapevo sapevo su quale coordinata ho fatto $\pm 2^j$, e quindi annullo la mossa con $\mp 2^j$ sulla stessa coordinata).
Notiamo che così facendo, fino a $2^{i-1}$ (devo ora trovare $2^i$), abbiamo due coordinate una divisibile per $2^{i+1}$ e una no: a quella no devo aggiungere o sottrarre $2^i$ per farla diventare divisibile, ma come dato che diventa divisibile sia se aggiungo sia se sottraggo? Beh, noto che dopo aver fatto questo ci saranno o due coordinate una divisibile per $2^{i+2}$ e l'altra no, o entrambe divisibili o entrambe non divisibili (non sto a spiegare come si arriva in ogni caso): ovviamente non possiamo essere in uno degli ultimi due casi e quindi so se aggiungere o sottrarre l'$i$-esimo salto. Restano da determinare $2^{n-1}$ e $2^n$, ma a quel punto noto che per come abbiamo modificato le coordinate è come aver fatto solo quei due salti, e provando ogni combinazione possibile vanno tutte in punti diversi e quindi so come li ho fatti.

[Rho33]

Uh, che figo questo problema, vediamo se ciò che scrivo va bene:

Testo nascosto:

Lemma overkill: Ogni intero positivo $n$ ha un'unica espansione in base $b$ intero positivo (lo specifico perché ciò non è più vero in base $\phi$ oppure $\pi$ se non erro )

Dimostrazione: Esistenza Scriviamo $n=q_0b+a_0$ ed iteriamo la divisione euclidea ottenendo man mano $q_0=q_1b+a_1 ,..., q_{r-1}=0b+a_r$ dove ad ogni passo $q_k>q_{k-1}$ . Alla fine si ottiene quindi che $n= \sum _{i=0}^r a_ib^i$ che è proprio la rappresentazione in base $b$ con $a_i < b$ .

Unicità: induzione

Bene, detto ciò, applichiamo il lemma alla base $2$, quella che ci interessa. Siano ora $a,b,c,d$ quattro interi positivi diversi tra loro e consideriamo la somma e la differenza tra potenze di due:

$\bullet$ Un intero si scrive in modo unico come somma di potenze di due distinte: supponiamo per assurdo che la tesi sia falsa e consideriamo $2^a+2^b=2^c+2^d$ . WLOG $a>1$ è il più piccolo tra i quattro ( se uno dei quattro è uguale ad $1$ si ottiene subito l'assurdo) , allora divido per $2^a \rightarrow 1+2^{b'}=2^{c'}+2^{d'}$ assurdo ( per la parità ovviamente!)

$\bullet$ Un intero positivo si scrive in modo unico come differenza di potenze di due: analoga alla precedente

Consideriamo ora le coordinate dell'ultima posizione, sia l'ascissa che l'ordinata saranno somme e differenze di potenze di due, quindi esprimibili in modo unico. Fine.


Ed infine, una breve soluzione alternativa del lemma con le generatrici:

Sia $g(x)=(1+x)(1+x^2)...(1+x^{2^n})$ , chiaramente il coefficiente di ogni termine esprime il numero di modi di scrivere un intero positivo come somma di potenze di due. Voglio dimostrare che i coefficienti sono tutti $1$.

Moltiplico ambo i membri per $(1-x)$ ed ottengo:

$(1-x)g(x)=(1-x)(1+x)(1+x^2)... \iff (1-x)g(x)=1 \iff g(x)= \dfrac {1}{1-x} \iff g(x)= 1+x+x^2+...$ dove il magheggio iniziale vale vedendo la convergenza, credo.

[Gerald Lambeau]

Quasi perfetta, però le coordinate sono somme e differenze di più di due potenze di $2$, quindi la dimostrazione che ciò sia fattibile in modo unico non è identica a quella di due sole potenze! Pensandoci così al volo ti dico che lo stesso ragionamento fatto sulle due potenze, unito a un'induzione, dovrebbe andare.
PS: il lemma che hai usato penso si possa dare per noto.

[Rho33]

Ok, in realtà ammetto di averlo dimenticato, comunque concordo, si dovrebbe poter fare induzione sul numero di addendi, sia per la somma che per la differenza.

P.S. Il lemma l'ho dimostrato perché lo conoscevo soltanto abbastanza intuitivamente e poi volevo sfoggiare le generatrici

[Gerald Lambeau]

Ok, comunque bella dimostrazione del lemma