Breve domandina prima di dormire.
Mi stavo trastullando col Vieta Jumping, e tra le altre cose ho ripreso in mano il problema numero $ $5$ $ assegnato alle IMO di quest'anno.
In particolare, oltre al vero e proprio Vieta Jumping, c'era un simpatico conto di divisibilità, che riporto:
Dall'ipotesi:
$ $4ab-1 \mid (4a^2-1)^2$ $
si deduceva che:
$ $4ab-1 \mid b^2(4a^2-1)^2 - (4ab-1)(4a^3b-2ab+a^2)$ $
e quindi:
$ $4ab-1 \mid (a-b)^2$ $
Da cui poi derivava tutto il problema. Ora la mia domanda è questa:
quali sono i fili conduttori dell'euristica che porta dall'ipotesi al risultato postato qui su?
Esiste una strategia per "meccanizzare" (anche parzialmente) i conti con le divisibilità di questo tipo?
meditans
Euristica per IMO 2007/5
Sì.
Intanto l'idea principale di quel passaggio è di simmetrizzare l'espressione. Si parte da:
simmetrico | asimmetrico
e si arriva a:
simmetrico | simmetrico
Per rendere più eleganti questi passaggi, si possono usare le congruenze.
Visto che abbiamo "4ab-1 divide qualcosa", per trasformare il "qualcosa" lavoriamo negli interi moduo 4ab-1. Cosa sono gli interi modulo 4ab-1? Un bel modo di vederli ì questo: prendiamo gli interi, però ordiniamo a loro che 4ab faccia 1. Loro per adattarsi a questo dovranno "trasformarsi" in qualche modo, in modo che somma e prodotto funzionino bene e che 4ab sia proprio uguale ad 1.
Quindi, divagando meno, l'ipotesi è che, negli interi modulo 4ab-1, si ha:
$ ~ (4a^2-1)^2 \equiv 0 $
Inoltre possiamo fare buon uso del fatto che $ ~ 4ab \equiv 1 $. Al posto dell'1 possiamo scrivere 4ab!
$ ~ (4a^2-4ab)^2 \equiv 0 $
$ ~ (4a)^2(a-b)^2 \equiv 0 $
Ora il bello è che, essendo (4a)^2 e 4ab-1 coprimi, nell'ultima congruenza possiamo dividere per (4a)^2 e ottenere:
$ ~ (a-b)^2 \equiv 0 $
$ ~ 4ab-1 \mid (a-b)^2 $
e ci rendiamo conto che ogni passaggio era invertibile; cioè la formula iniziale e questa finale sono equivalenti.
La potenza delle congruenze... poi, sapendo meglio cosa sono le congruenze (anello commutativo, quoziente di Z) si riesce anche ad evitare errori del tipo "non si scherza con il fuoco" (dividere quando non si può, fare sostituzioni quando non si può...)
Ah, per la cronaca, predico bene e razzolo male!
Alle IMO questo passaggio non l'ho neanche fatto... però ero arrivato a simmetrizzare comunque l'espressione in un altro modo, che sintetizzo così:
$ ~ k(4ab-1) = (4a^2-1)^2 $
$ ~ (4ac-1)(4ab-1) = (4a^2-1)^2 $
Si può porre c=a+k, b=a-j, e semplificando diventa:
$ ~ (4a^2-1)(k-j)=4akj $
Il problema è che quando uno trova qualcosa di così promettente non torna più indietro... volendo si può continuare a far sostituzioni simpatiche, ad esempio porre a'=2a, k=e+2ad,j=e-2ad, arrivando a:
$ ~ a'^2d^2 + a'^2d - d $ che deve essere un quadrato, con l'ipotesi aggiuntiva che a è pari, mentre la tesi è che l'unica soluzione è con d=0.
Intanto l'idea principale di quel passaggio è di simmetrizzare l'espressione. Si parte da:
simmetrico | asimmetrico
e si arriva a:
simmetrico | simmetrico
Per rendere più eleganti questi passaggi, si possono usare le congruenze.
Visto che abbiamo "4ab-1 divide qualcosa", per trasformare il "qualcosa" lavoriamo negli interi moduo 4ab-1. Cosa sono gli interi modulo 4ab-1? Un bel modo di vederli ì questo: prendiamo gli interi, però ordiniamo a loro che 4ab faccia 1. Loro per adattarsi a questo dovranno "trasformarsi" in qualche modo, in modo che somma e prodotto funzionino bene e che 4ab sia proprio uguale ad 1.
Quindi, divagando meno, l'ipotesi è che, negli interi modulo 4ab-1, si ha:
$ ~ (4a^2-1)^2 \equiv 0 $
Inoltre possiamo fare buon uso del fatto che $ ~ 4ab \equiv 1 $. Al posto dell'1 possiamo scrivere 4ab!
$ ~ (4a^2-4ab)^2 \equiv 0 $
$ ~ (4a)^2(a-b)^2 \equiv 0 $
Ora il bello è che, essendo (4a)^2 e 4ab-1 coprimi, nell'ultima congruenza possiamo dividere per (4a)^2 e ottenere:
$ ~ (a-b)^2 \equiv 0 $
$ ~ 4ab-1 \mid (a-b)^2 $
e ci rendiamo conto che ogni passaggio era invertibile; cioè la formula iniziale e questa finale sono equivalenti.
La potenza delle congruenze... poi, sapendo meglio cosa sono le congruenze (anello commutativo, quoziente di Z) si riesce anche ad evitare errori del tipo "non si scherza con il fuoco" (dividere quando non si può, fare sostituzioni quando non si può...)
Ah, per la cronaca, predico bene e razzolo male!
Alle IMO questo passaggio non l'ho neanche fatto... però ero arrivato a simmetrizzare comunque l'espressione in un altro modo, che sintetizzo così:
$ ~ k(4ab-1) = (4a^2-1)^2 $
$ ~ (4ac-1)(4ab-1) = (4a^2-1)^2 $
Si può porre c=a+k, b=a-j, e semplificando diventa:
$ ~ (4a^2-1)(k-j)=4akj $
Il problema è che quando uno trova qualcosa di così promettente non torna più indietro... volendo si può continuare a far sostituzioni simpatiche, ad esempio porre a'=2a, k=e+2ad,j=e-2ad, arrivando a:
$ ~ a'^2d^2 + a'^2d - d $ che deve essere un quadrato, con l'ipotesi aggiuntiva che a è pari, mentre la tesi è che l'unica soluzione è con d=0.
)