OliForum Matematico

Sarei curioso di capire l'errore nella dimostrazione che ho fatto di questo problema, ci ho pensato un po' ma non sono riuscito a trovarlo...

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.

Non ho (ancora) letto il tuo post, ma se dici quanti punti hai preso può essere d'aiuto nel trovare l'errore.

Ho avuto 2 punti su 7. Ho cercato di scrivere più o meno le parole che ho scritto, senza andare a migliorare la forma...

Davide90 ha scritto: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

Ah, ok. E' proprio qui l'errore. Prova a costruire un controesempio della tua affermazione.
Penso che come soluzione non valga più di un paio di punti, poi non so quali erano i criteri di valutazione.

EDIT: ok, 2 punti.

Davide90 ha scritto: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.

È questo il punto sbagliato: metti che l'ultimo salto fosse verso est, se c'erano stati prima salti verso ovest allora la coordinata est sarà minore di 2^{n-1} e quindi cade la tua dimostrazione. Bisognava fare una piccola aggiunta e il tutto funzionava.

edit: preceduto..

riedit:

Tibor Gallai ha scritto:

Davide90 ha scritto: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

Ah, ok. E' proprio qui l'errore. Prova a costruire un controesempio della tua affermazione.

sei sicuro? io ho dimostrato, in modo diverso, proprio quello, e ho preso 7 punti

Scusate, dovevo quotare l'intera frase.

julio14 ha scritto: È questo il punto sbagliato: metti che l'ultimo salto fosse verso est, se c'erano stati prima salti verso ovest allora la coordinata est sarà minore di 2^{n-1} e quindi cade la tua dimostrazione. Bisognava fare una piccola aggiunta e il tutto funzionava.

Ancora non capisco perchè sia scorretto quello che ho detto...
Provo a formularlo meglio.
Immaginiamo che la pulce faccia tutti i salti a est tranne l'ultimo a ovest: la sua posizione è (1;0). Ora, qualunque numero di salti abbia fatto in un'altra direzione anzichè a ovest, l'ascissa della posizione della pulce diventa 1+k, mentre la sua ordinata diventa al massimo k.
Quindi in modulo $ |x_i|>|y_i| $ ...
Tu julio cosa hai scritto?

Quello che provi a dimostrare è vero, quindi certo che non funzionano i controesempi. Il problema è che le due coordinate interagiscono, e questo deve entrare nella dimostrazione in qualche modo.

Intanto sono partito dalla tesi e ho dimostrato l'ipotesi, specificando che era una coimplicazione.
Ora, wlog l'ultima direzione sia ovest. Chiamiamo k la somma degli spostamenti verso est. Il minimo per la coordinata ovest è $ $2^{n-1}-k $, mentre il massimo per la coordinata nord o sud è $ $\sum_{i=1}^{n-2}2^i-k=2^{n-1}-1-k<2^{n-1}-k $

edit: mi sono appena accorto che la cosa del k ora l'hai messa. Ma in gara l'hai scritta?

julio14 ha scritto: Ora, wlog l'ultima direzione sia ovest. Chiamiamo k la somma degli spostamenti verso est. Il minimo per la coordinata ovest è $ $2^{n-1}-k $, mentre il massimo per la coordinata nord o sud è $ $\sum_{i=1}^{n-2}2^i-k=2^{n-1}-1-k<2^{n-1}-k $

edit: mi sono appena accorto che la cosa del k ora l'hai messa. Ma in gara l'hai scritta?

Purtroppo no, l'ho data per scontata.... Quindi solo per questo non ho preso l'oro?? che pacco...

Io ho preso 6 in questo....forse perchè non era scritta benissimo...

Anch'io ho avuto 6... ma mi son fatto spiegare l'errore da fph...

Molto sinteticamente ho fatto una specie di ricorsione che per determinare una posizione usava i due salti successivi.
Purtroppo però ho dimenticato che la penultima posizione andave calcolata a mano perchè non avevo più due salti successivi disponibili... (oppure bisognava che immaginassi che la pulce facesse un salto in più...).

Peccato perchè questa disattenzione mi è costata molto cara...

Davide90 ha scritto:Quindi solo per questo non ho preso l'oro?? che pacco...

non so... a me sembra l'unico "errore". Più che altro che leggendo la dimostrazione senza più che una dimenticanza sembra proprio un errore concettuale.

Hai ragione, detta come l'ho detta è sbagliata ed è giusto penalizzarla... Però mentalmente l'avevo pensata giusta, non l'ho formalizzato ritenendolo superfluo.
Vabbè, servirà da lezione epr gare più importanti...

Sembra che fosse proprio un esercizio di formalizzazione. Perché se uno si trova con in mano il punto, riesce a capire abbastanza facilmente quale dev'essere il percorso, ma la difficoltà sta nello spiegare perché e percome tutto funziona.
Comunque scusa per il commento poco accurato di prima, forse ti ho sviato momentaneamente dalla vera comprensione dell'errore.

C'era un'altra soluzione carina, che si basava sull'iniettività.
Supponiamo per assurdo che le coordinate x e y si possano scrivere in due modi diversi come somme di potenze distinte di 2. (con le somme intendo somme algebriche, cioé lascio perdere + e -)
$ $x=\sum_{i\in A}2^i=\sum_{i\in B}2^i $
$ $y=\sum_{i\in C}2^i=\sum_{i\in D}2^i $
$ $A\neq B \wedge C\neq D $
Ora c'è una parte un po' noiosetta. Riferendomi a x, chiamo $ $a $ la somma delle potenze che appaiono in entrambe le somme con lo stesso segno, $ $b $ la somma di quelle che appaiono in entrambe con segno diverso, $ $c $ quelle che appaiono nell'LHS e appariranno nel RHS della y con lo stesso segno, idem con $ $d $ ma segno diverso, idem con $ $e $ e $ $f $ con il RHS di x e il LHS di y, e infine $ $g $ in RHS e LHS di y con stesso segno e $ $h $ idem con segno diverso. Si sono coperti tutti i casi, quindi a,b,c,d,e,f,g,h sono tutte e sole le potenze di due che ci servono e sono completamente disgiunte per la loro definizione.
Abbiamo quindi
$ $x=a+b+c+d=a-b+e+f $
$ $y=g+h+e-f=g-h+c-d $
Sommo il tutto e ottengo
$ $a+b+c+d+g+h+e-f=a-b+e+f+g-h+c-d $
$ $2b+2d+2h-2f=0\rightarrow b+d+h-f=0 $
Abbiamo quindi una somma algebrica di potenze di 2 distinte che è uguale a zero, assurdo modulo la seconda più piccola.