Tutti gli S finiti
Tutti gli S finiti
(Easy. Apmo2004). Trovare tutti gli insiemi finiti S di interi positivi tali che se a e b sono in S allora lo è anche (a+b)/gcd(a,b)
The only goal of science is the honor of the human spirit.
Noto prima di tutto che se sono presenti 2 a,b coprimi allora l'insieme è infinito per forza:
basta vedere che io posso trasformare
$ (a,b)\to (a,a+b) $
Se sono coprimi generando un'altra coppia di coprimi in S con un elemento strettamente maggiore.
Ora dimostro che se ci sono 2 elementi allora ce ne sono anche 2 coprimi, viene facilmente per discesa infinita... praticamente lo stesso metodo di prima, soltanto che uno dei 2 elementi sarà strettamente minore:
$ (a,b)\to (a,c) $ Assumendo WLOG a<b. E continuando così se non diventassero mai coprimi creerei una successione decrescente di naturali.
Il caso in cui c'è un solo elemento... beh vanno bene tutti, e anche l'insieme vuoto mi pare soddisfi.
Non so se è giusta ma dato che ho tempo provo anche a dare una spiegazione di come farla.
Leggendo il testo la prima cosa che mi è venuta in mente è che fosse impossibile, questo è puro caso (non è intuizione ve lo assicuro ;)) mi è capitato una volta (sempre con un problema postato da jordan) di convincermi che quello da dimostrare fosse "il contrario" del vero... in quel caso c'è poco da fare.
Una volta scelto cosa dimostrare tocca pensare a come farlo... prima di tutto mi è venuto in mente il Vieta jumping, idea subito scartata sia per il tag EASY sia perchè non ci sarebbe un'equazione a cui applicarlo. Poi ho notato quel gcd(a,b) che ovviamente fa pensare alla scomposizione in primi... la prima cosa che viene in mente è assumere a,b coprimi (o perfino primi) e notare che succede... cosa accade è chiaro... ora sappiamo che se ce ne sono 2 coprimi abbiamo concluso. Dovrebbe essere automatico pensare che ce ne siano sempre 2 coprimi... come fare, qui mi è venuta prima in mente l'induzione... scartata subito dato che l'idea era tipo... se ci sono n elementi nell'insieme allora ce ne sono 2 coprimi... allora vale la stessa cosa per n+1... ovviamente confusionario (nonchè falso sotto alcuni punti di vista) Al che ho pensato al cugino dell'induzione, la discesa infinita... prima generavo un numero maggiore, ora dovevo generarne uno minore... come fare? Stesso identico metodo ed ha funzionato :) Concluso.
In generale pur essendo facilotto racchiude 2 strumenti interessanti: la discesa infinita e l'idea di assumere una proprietà e dimostrarla in seguito (la coprimalità)...
Tutto sto papocchio che non leggerà mai nessuno l'ho scritto perchè ritengo abbastanza inutile postare dimostrazioni letteralmente calate dal cielo sul forum... se uno ha tempo (e voglia) dovrebbe postare come si può arrivare alla conclusione..
p.s. il colmo è se ho completamente segato la dimostrazione xD
basta vedere che io posso trasformare
$ (a,b)\to (a,a+b) $
Se sono coprimi generando un'altra coppia di coprimi in S con un elemento strettamente maggiore.
Ora dimostro che se ci sono 2 elementi allora ce ne sono anche 2 coprimi, viene facilmente per discesa infinita... praticamente lo stesso metodo di prima, soltanto che uno dei 2 elementi sarà strettamente minore:
$ (a,b)\to (a,c) $ Assumendo WLOG a<b. E continuando così se non diventassero mai coprimi creerei una successione decrescente di naturali.
Il caso in cui c'è un solo elemento... beh vanno bene tutti, e anche l'insieme vuoto mi pare soddisfi.
Non so se è giusta ma dato che ho tempo provo anche a dare una spiegazione di come farla.
Leggendo il testo la prima cosa che mi è venuta in mente è che fosse impossibile, questo è puro caso (non è intuizione ve lo assicuro ;)) mi è capitato una volta (sempre con un problema postato da jordan) di convincermi che quello da dimostrare fosse "il contrario" del vero... in quel caso c'è poco da fare.
Una volta scelto cosa dimostrare tocca pensare a come farlo... prima di tutto mi è venuto in mente il Vieta jumping, idea subito scartata sia per il tag EASY sia perchè non ci sarebbe un'equazione a cui applicarlo. Poi ho notato quel gcd(a,b) che ovviamente fa pensare alla scomposizione in primi... la prima cosa che viene in mente è assumere a,b coprimi (o perfino primi) e notare che succede... cosa accade è chiaro... ora sappiamo che se ce ne sono 2 coprimi abbiamo concluso. Dovrebbe essere automatico pensare che ce ne siano sempre 2 coprimi... come fare, qui mi è venuta prima in mente l'induzione... scartata subito dato che l'idea era tipo... se ci sono n elementi nell'insieme allora ce ne sono 2 coprimi... allora vale la stessa cosa per n+1... ovviamente confusionario (nonchè falso sotto alcuni punti di vista) Al che ho pensato al cugino dell'induzione, la discesa infinita... prima generavo un numero maggiore, ora dovevo generarne uno minore... come fare? Stesso identico metodo ed ha funzionato :) Concluso.
In generale pur essendo facilotto racchiude 2 strumenti interessanti: la discesa infinita e l'idea di assumere una proprietà e dimostrarla in seguito (la coprimalità)...
Tutto sto papocchio che non leggerà mai nessuno l'ho scritto perchè ritengo abbastanza inutile postare dimostrazioni letteralmente calate dal cielo sul forum... se uno ha tempo (e voglia) dovrebbe postare come si può arrivare alla conclusione..
p.s. il colmo è se ho completamente segato la dimostrazione xD