Cesenatico 2009, problema n. 4
Inizialmente una pulce si trova 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.
Dimostrazione mia (provo a ricostruirla, più o meno l'ho scritta così)
Indichiamo la posizione della pulce all' i-esimo salto con $ P_i(x_i;y_i) $ .
Troviamo la posizione della pulce al salto precedente con il seguente algoritmo:
- Consideriamo tra $ x_i $ e $ y_i $ quello maggiore in valore assoluto. Assumiamo wlog che $ |x_i| > |y_i| $ : allora la direzione in cui ha effettuato l'i-esimo salto deve essere lungo la direzione Est-Ovest, in quanto $ 2^{i-1}> 2^{i-1}-1=2^{i-2}+2^{i-3}+\dots+2^2+2^1+1 $ , dunque ad ogni salto la pulce si allontana dall'origine di più nella direzione dell'ultimo salto che nell'altra. (forse è questo il passaggio spiegato male? però come idea dovrebbe essere giusta)
- Ora scriviamo le coordinate $ P_{i-1}(x_{i-1};y_{i-1}) $ , sapendo che $ y_i=y_{i-1} $ e che $ x_{i-1}=x_i-2^{i-1} $ se $ x_i >0 $, e $ x_{i-1}=x_i+2^{i-1} $ se $ x_i <0 $.
Poichè possiamo determinare ad ogni posizione la posizione precedente, la tesi è dimostrata.
che pacco... 
