Il succo del problema è:
Qual è la massima cardinalità di un sottoinsieme finito A degli interi positivi,tale che se $ m $ ed $ n $ stanno in A,allora $ \frac{m+n}{MCD(m,n)} $ sta in A?
I superstiti gara del pubblico cesenatico 2010
Vabbuò ,con la scusa uppo il thread 
Grazie,in ogni caso a me sembrava che solo l'insieme {2} andasse bene,mentre in quel post dario2994 dice che tutti gli insiemi con cardinalità 1 vanno bene.
Io,dopo aver dimostrato che gli insiemi con cardinalità >= 2 non vanno bene,supponendo che la cardinalità sia 1 e sia n l'unico elemento dell'insieme,
allora $ \frac{n+n}{MCD(n,n)}=2 $
E' sbagliato così?
Io,dopo aver dimostrato che gli insiemi con cardinalità >= 2 non vanno bene,supponendo che la cardinalità sia 1 e sia n l'unico elemento dell'insieme,
allora $ \frac{n+n}{MCD(n,n)}=2 $
E' sbagliato così?
Se non vado errato, in quella soluzione avevo assunto che l'ipotesi dovesse valere con numeri diversi... se non lo si assume viene che gli unici insiemi che vanno bene sono quello vuoto e l'insieme con come unico elemento 2.
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
Uhm... risolviamo il problema.
Mostro che il maggiore insieme finito ha cardinalità 2.
Un esempio è quello di Maioc.
Se sono presenti 2 elementi coprimi... è facile mostrare che l'insieme è infinito (se sono presente a,b è presente anche ka+b...).
Alur se è presente l'1 nell'insieme, e l'insieme massimizza la cardinalità, allora c'è almeno un altro elemento, allora l'insieme è infinito (l'1 è coprimi con tutti i numeri).
Se è presente il 2, e voglio che massimizzi la cardinalità, deve almeno esserci un altro elemento, chiamo n il minore presente nell'insieme diverso da 2. Se è coprimo allora l'insieme è infinito. Assumo per assurdo che non sia coprimo, è pari e vale 2k. Allora anche k+1 è nell'insieme... vale 2k>k+1>2 quindi k+1 è un elemento nell'insieme minore di 2k e maggiore di 2... ops assurdo.
Ora mostro che un insieme con più di 3 elementi senza 1,2 che rispetta le ipotesi non esiste.
Chiamo 2<a<b<c i 3 numeri minori. Definisco l'operazione:
$ $x*y=\frac{x+y}{(x,y)} $
Dato che l'insieme è finito a,b,c non sono coprimi a coppie, quindi vale:
$ $a*b<b $
Ma dato che a*b appartiene all'insieme ottengo:
$ $a*b=a\rightarrow a|b\rightarrow b=ka\rightarrow k+1=a\rightarrow b=a(a-1) $
Ho saltato qualche passaggio, spero si capisca.
Ora vale anche:
$ b*c<c $
quindi b*c=b oppure b*c=a.
Se b*c=b con ragionamenti analoghi ai precedenti ottengo $ $c=a(a-1)(a^2-a+1) $. Vale al solito $ $a*c<c $. Ora a*c non può valere a, altrimenti b=c, quindi a*c=b. Calcolo a*c ottenendo l'assurdo:
$ $a*c=1+(a-1)(a^2-a+1)\not= b $
quindi assurdo.
Se b*c=a allora vale:
$ $a|c\rightarrow c=ka\rightarrow \frac{a-1+k}{a-1,k}=a\rightarrow k=na+1\rightarrow c=a(na+1) $
Ora calcolo a*c... chiaramente non vale a altrimenti b=c, allora deve valere b (dato che <c), quindi ottengo l'assurdo:
$ a*c=b\rightarrow \frac{a+a(na+1)}{(a,a(na+1))}=a(a-1)\rightarrow na+2=a(a-1)\rightarrow a|2 $
Che è assurdo dato che a>2
Spero si capisca... e sia anche giusto magari xD
Mostro che il maggiore insieme finito ha cardinalità 2.
Un esempio è quello di Maioc.
Se sono presenti 2 elementi coprimi... è facile mostrare che l'insieme è infinito (se sono presente a,b è presente anche ka+b...).
Alur se è presente l'1 nell'insieme, e l'insieme massimizza la cardinalità, allora c'è almeno un altro elemento, allora l'insieme è infinito (l'1 è coprimi con tutti i numeri).
Se è presente il 2, e voglio che massimizzi la cardinalità, deve almeno esserci un altro elemento, chiamo n il minore presente nell'insieme diverso da 2. Se è coprimo allora l'insieme è infinito. Assumo per assurdo che non sia coprimo, è pari e vale 2k. Allora anche k+1 è nell'insieme... vale 2k>k+1>2 quindi k+1 è un elemento nell'insieme minore di 2k e maggiore di 2... ops assurdo.
Ora mostro che un insieme con più di 3 elementi senza 1,2 che rispetta le ipotesi non esiste.
Chiamo 2<a<b<c i 3 numeri minori. Definisco l'operazione:
$ $x*y=\frac{x+y}{(x,y)} $
Dato che l'insieme è finito a,b,c non sono coprimi a coppie, quindi vale:
$ $a*b<b $
Ma dato che a*b appartiene all'insieme ottengo:
$ $a*b=a\rightarrow a|b\rightarrow b=ka\rightarrow k+1=a\rightarrow b=a(a-1) $
Ho saltato qualche passaggio, spero si capisca.
Ora vale anche:
$ b*c<c $
quindi b*c=b oppure b*c=a.
Se b*c=b con ragionamenti analoghi ai precedenti ottengo $ $c=a(a-1)(a^2-a+1) $. Vale al solito $ $a*c<c $. Ora a*c non può valere a, altrimenti b=c, quindi a*c=b. Calcolo a*c ottenendo l'assurdo:
$ $a*c=1+(a-1)(a^2-a+1)\not= b $
quindi assurdo.
Se b*c=a allora vale:
$ $a|c\rightarrow c=ka\rightarrow \frac{a-1+k}{a-1,k}=a\rightarrow k=na+1\rightarrow c=a(na+1) $
Ora calcolo a*c... chiaramente non vale a altrimenti b=c, allora deve valere b (dato che <c), quindi ottengo l'assurdo:
$ a*c=b\rightarrow \frac{a+a(na+1)}{(a,a(na+1))}=a(a-1)\rightarrow na+2=a(a-1)\rightarrow a|2 $
Che è assurdo dato che a>2
Spero si capisca... e sia anche giusto magari xD
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai