IT-CESENATICO 2009 Problem 4

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.