Cesenatico 2009 n. 4: caccia all'errore

[EvaristeG]

Hmm secondo me la cosa più facile era questa:
chiamiamo R(n) l'insieme dei punti raggiungibili in n mosse dall'origine; supponiamo di sapere che, per un certo n e per ogni punto di R(n), c'è un'unica successione di n mosse che porta fin lì. Allora, se ci fosse un punto di R(n+1) che si può raggiungere in n+1 mosse in due modi diversi (neghiamo la tesi per assurdo), evidentemente vorrebbe dire che può essere raggiunto, con la n+1-esima mossa, da due punti distinti di R(n); questo vuol dire che per quei due punti $ (x_1,y_1),\ (x_2,y_2) $ vale
$ |x_1-x_2|+|y_1-y_2|=2\cdot2^n $
ma
$ |x_1-x_2|+|y_1-y_2|\leq|x_1|+|y_1|+|x_2|+|y_2|\leq2(2^n-1) $
e quindi è impossibile. Dunque ogni punto di R(n+1) si raggiunge in modo unico tramite n+1 mosse.
il caso R(1) è ovvio e così si procede per induzione.

[jordan]

E qualcuno si sarà anche ricordato un po questo..

@Jacobi, vabbo mica era tanto vecchio? se me lo ricordavo io..

[Jacobi]

ormai la necrofilia e diventata una moda, vero jordan?
ps: se continuiamo a rikiamare qsti thread dagli abissi degli inferi, finiremo x alterare l'ecosistema dell'oliforum!!

[julio14]

E qualcuno si sarà anche ricordato un po questo..

Uh già in effetti mi ricordavo qualcosa del genere... allora mi sento un po' infame ad aver rubato l'oro a stoppia e agli altri del gruppo 777600 XD

[SkZ]

e perche'? se tu te lo sei ricordato e loro no tu sei stato piu' bravo a tenere a mente le nozioni
insomma, il motto e' "lavoro, lavoro, lavoro" perche' chi vede piu' casi vince. Qualcuno fara' bene per intuito, ma l'aver visto piu' casi possibili aiuta a primeggiare.
Julio14, non sentirti in colpa per aver fatto esercizi, ti prego.

[julio14]

lol ero ironico... ti pare che mi sento veramente in colpa per aver preso un oro?
(e comunque come esempio di $ $L^3 $ sono un esempio tutt'altro che da imitare...)

[Elzaralian]

... spero di essere ancora in tempo per scrivere in questo post...
io avevo pensato a delle osservazioni di tipo geometrico che portano a una dimostrazione simile a quella sopra:
1)All'n-esimo salto $ |x_P|+|y_P| \leq 2^{n}-1 $
2)questo vuol dire che all'n-esimo salto la pulce si troverà in un quadrato di vertici: $ V_1(2^{n}-1,0); V_2(0,2^{n}-1); V_3(-2^{n}+1,0); V_4(0,-2^{n}+1) $
3)Se l'(n+1)-esimo salto è in alto la pulce all'(n+1)-esima mossa si troverà all'interno del quadrato di prima traslato in alto di $ 2^n $, ... idem per le altre direzioni.
4)i quadrati che si ottengono traslando nelle 4 direzioni quello iniziale di $ 2^n $ non hanno nessun punto in comune a due a due. (è ovvio ma non riesco a trovare un modo per formalizzarlo bene e in fretta)
5)a questo punto si ha che non ci sono punti a cui si possa arrivare facendo l'ultima mossa in due direzioni diverse.
ora la dimostrazione si può completare per induzione.
Una dimostrazione del genere può raggiungere sette punti? Anche se il punto 4 non è spiegato benissimo? E si può considerare "elegante" anche se non è la più veloce? (è comunque bella da visualizzare!)

[dario2994]

... spero di essere ancora in tempo per scrivere in questo post...
io avevo pensato a delle osservazioni di tipo geometrico che portano a una dimostrazione simile a quella sopra:
1)All'n-esimo salto $ |x_P|+|y_P| \leq 2^{n}-1 $
2)questo vuol dire che all'n-esimo salto la pulce si troverà in un quadrato di vertici: $ V_1(2^{n}-1,0); V_2(0,2^{n}-1); V_3(-2^{n}+1,0); V_4(0,-2^{n}+1) $
3)Se l'(n+1)-esimo salto è in alto la pulce all'(n+1)-esima mossa si troverà all'interno del quadrato di prima traslato in alto di $ 2^n $, ... idem per le altre direzioni.
4)i quadrati che si ottengono traslando nelle 4 direzioni quello iniziale di $ 2^n $ non hanno nessun punto in comune a due a due. (è ovvio ma non riesco a trovare un modo per formalizzarlo bene e in fretta)
5)a questo punto si ha che non ci sono punti a cui si possa arrivare facendo l'ultima mossa in due direzioni diverse.
ora la dimostrazione si può completare per induzione.
Una dimostrazione del genere può raggiungere sette punti? Anche se il punto 4 non è spiegato benissimo? E si può considerare "elegante" anche se non è la più veloce? (è comunque bella da visualizzare!)

Direi che è giusta E se ci aggiungi un poco come fai induzione, cioè che determini mano mano sempre l'ultima mossa, sicuramente è da 7

[Ein]

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.

Scusate l'intromissione, ma mi chiedevo: se io come soluzione propongo un algoritmo che ricostruisce tutto il percorso della pulce (perché è la prima cosa che mi è venuta in mente) quanto valida può esser considerata come risposta? So che non è molto elegante perché mi si chiede se è possibile e non come è possibile, ma su 7 punti quanti ne prenderei?

[dario2994]

ma su 7 punti quanti ne prenderei?

7

[fph]

Se proponi un algoritmo, e dimostri che ricostruisce esattamente l'unico possibile percorso della pulce per arrivare a quel punto prendi 7 punti. Se no, bisogna vedere com'è fatto il tuo algoritmo e quanto ti manca per "arrivare in fondo" e completare una dimostrazione.