ISL 2004/3
ISL 2004/3
Puo' esistere una funzione $ s:\colon \mathbb{Q}\rightarrow \{-1, 1 \} $ tale che se x e y sono numeri razionali distinti che soddisfano $ xy=1 $ o $ x+y \in \{0, 1\} $ allora $ s(x)s(y)=-1 $?
Era un peccato lasciare da solo questo problema... allora, a me viene che la funzione esiste.
Intanto riscrivo in maniera più comoda le condizioni.
$ x+y=0 \Rightleftarrow y=-x $;$ f(x)=-f(-x) $, con x diverso da 0.
$ x+y=1 \Rightleftarrow y=1-x $;$ f(x)=-f(1-x)=f(x-1) $, con x diverso da 1/2 e -1/2.
Ora definisco la funzione sui razionali positivi in questo modo.
Sia x un razionale positivo.
Applico questo algoritmo:
- da x tolgo un intero k tale che 0 <= x-k < 1
- inverto x-k e ricomincio finchè non trovo 0.
Questo algoritmo termina dopo un po' di passi, per dimostrarlo metto x=a/b e osservo che i denominatori sono una successione strettamente descresente. L'algoritmo è praticamente l'algoritmo di Euclide per trovare il massimo comun divisore tra a e b.
Ora, chiamo "ordine" di x il numero di passi che ha impiegato l'algoritmo prima di fermarsi. Altra interpretazione, più carina: scrivo x in forma di frazione continua. L'ordine è "quanto è alta la frazione continua".
Se l'ordine è pari, f(x)=1. Altrimenti, f(x)=-1. Ora dimostro che f soddisfa le condizioni (sui razionali positivi)
Se a=b+1, allora a e b sono "congrui" modulo 1, hanno la stessa parte decimale, quindi dopo la prima riga di codice il programma si trova nella stessa situazione, sia con a che con b. Quindi hanno lo stesso ordine e f(a)f(b)=1.
Se ab=1, wlog prendiamo che a sia minore di 1. Allora quando l'algoritmo termina il primo ciclo con a, ottiene 1/a, quindi b. Quindi l'ordine di a è quello di b + 1. Sono di disparità diversa, quindi f(a)f(b)=-1
Se x+y=1, o a/n+b/n=1, o a+b=n (a < b), la cosa è un pochino più complicata. Dopo aver osservato che l'algoritmo è pressochè identico a quello di euclide per il mcd, voglio dimostrare che dopo il primo passaggio su b, la sequenza generata da b ed a sarà identica.
Sequenza per a: n, a, a_2, a_3, ... dove $ a_2\equiv n-a \pmod a, a_2 < a $ ecc.
Ora: $ a \equiv n-b=a \pmod b $, ovviamente, e a<b, quindi la sequenza di b comincia così:
n,b,a,...
Siccome $ b \equiv n \pmod a $, da (n,a) o (b,a) si trova lo stesso elemento successivo, che è a_2.
Quindi la sequenza di b è:
n,b,a,a_2,...
Ma due termini bastano per dedurre il successivo, quindi d'ora in poi la sequenza "euclidea" di (n,b) sarà uguale a quella di (n,a), abbiamo saltato solo un passaggio, quindi f(a)f(b)=-1.
Noto che queste condizioni sono soddisfatte, è facile estendere la f a tutti i razionali. Mettiamo f(-x)=-f(x) e verifichiamo che tutte le condizioni sono soddisfatte. f(0) lo possiamo addirittura scegliere noi.
Ora rilancio questo problema: esiste una siffatta funzione sui reali?
Che proprietà interessanti avrebbe?
Intanto riscrivo in maniera più comoda le condizioni.
$ x+y=0 \Rightleftarrow y=-x $;$ f(x)=-f(-x) $, con x diverso da 0.
$ x+y=1 \Rightleftarrow y=1-x $;$ f(x)=-f(1-x)=f(x-1) $, con x diverso da 1/2 e -1/2.
Ora definisco la funzione sui razionali positivi in questo modo.
Sia x un razionale positivo.
Applico questo algoritmo:
- da x tolgo un intero k tale che 0 <= x-k < 1
- inverto x-k e ricomincio finchè non trovo 0.
Questo algoritmo termina dopo un po' di passi, per dimostrarlo metto x=a/b e osservo che i denominatori sono una successione strettamente descresente. L'algoritmo è praticamente l'algoritmo di Euclide per trovare il massimo comun divisore tra a e b.
Ora, chiamo "ordine" di x il numero di passi che ha impiegato l'algoritmo prima di fermarsi. Altra interpretazione, più carina: scrivo x in forma di frazione continua. L'ordine è "quanto è alta la frazione continua".
Se l'ordine è pari, f(x)=1. Altrimenti, f(x)=-1. Ora dimostro che f soddisfa le condizioni (sui razionali positivi)
Se a=b+1, allora a e b sono "congrui" modulo 1, hanno la stessa parte decimale, quindi dopo la prima riga di codice il programma si trova nella stessa situazione, sia con a che con b. Quindi hanno lo stesso ordine e f(a)f(b)=1.
Se ab=1, wlog prendiamo che a sia minore di 1. Allora quando l'algoritmo termina il primo ciclo con a, ottiene 1/a, quindi b. Quindi l'ordine di a è quello di b + 1. Sono di disparità diversa, quindi f(a)f(b)=-1
Se x+y=1, o a/n+b/n=1, o a+b=n (a < b), la cosa è un pochino più complicata. Dopo aver osservato che l'algoritmo è pressochè identico a quello di euclide per il mcd, voglio dimostrare che dopo il primo passaggio su b, la sequenza generata da b ed a sarà identica.
Sequenza per a: n, a, a_2, a_3, ... dove $ a_2\equiv n-a \pmod a, a_2 < a $ ecc.
Ora: $ a \equiv n-b=a \pmod b $, ovviamente, e a<b, quindi la sequenza di b comincia così:
n,b,a,...
Siccome $ b \equiv n \pmod a $, da (n,a) o (b,a) si trova lo stesso elemento successivo, che è a_2.
Quindi la sequenza di b è:
n,b,a,a_2,...
Ma due termini bastano per dedurre il successivo, quindi d'ora in poi la sequenza "euclidea" di (n,b) sarà uguale a quella di (n,a), abbiamo saltato solo un passaggio, quindi f(a)f(b)=-1.
Noto che queste condizioni sono soddisfatte, è facile estendere la f a tutti i razionali. Mettiamo f(-x)=-f(x) e verifichiamo che tutte le condizioni sono soddisfatte. f(0) lo possiamo addirittura scegliere noi.
Ora rilancio questo problema: esiste una siffatta funzione sui reali?
Che proprietà interessanti avrebbe?