Maratona di problemi
Proviamo a fare questa cosa: comincio col proporre io un problema (abbastanza facile), poi chi lo risolve propone a sua volta un problema etc etc. Se il risolutore di un problema non ha niente da proporre, puo' dare il permesso ad altri di proporne uno.
Sarebbe bello se si riuscisse a spaziare in piu' campi, e non tenersi solo in uno. Poi, non sarebbe l'ideale proporre problemi esageratamente difficili, cosi' non si ferma tutto.
Problema 1
Siano $a,b,c$ tre interi distinti, e sia $P$ un polinomio a coefficienti interi. Dimostrare che e' impossibile avere che $P(a)=b,P(b)=c,P(c)=a$.
Sarebbe bello se si riuscisse a spaziare in piu' campi, e non tenersi solo in uno. Poi, non sarebbe l'ideale proporre problemi esageratamente difficili, cosi' non si ferma tutto.
Problema 1
Siano $a,b,c$ tre interi distinti, e sia $P$ un polinomio a coefficienti interi. Dimostrare che e' impossibile avere che $P(a)=b,P(b)=c,P(c)=a$.
Risposte
"sk0rpio":
[quote="Mega-X"] procediamo per assurdo (negando la tesi) quindi $P(A) = P(B) = P(C)$ (Li scrivo grandi per evitare confusioni con i coefficienti del polinomio)
Il problema sta già qui...non si chiede che siano $P(A) = P(B) = P(C)$ , ma che $P(A)=b, P(B)=c, P(C)=a $
[/quote]ok sono proprio cieco allora..
ma alla fine pure se si chiedesse ciò si potrebbe troncare la serie al primo termine?
"Piera":
grazie karl!
davvero semplice la tua soluzione, il problema è come arrivarci!
Sì, molto più semplice di quello che mi aspettavo. Proponi tu il prossimo problema, karl?
Siano r,s,a,b numeri naturali.
1)Dimostrare che se r ed s sono coprìmi (attenti all'accento !!)
allora sono coprìmi anche i numeri r+s ed r*s
2)Siano a-b e a+b coprìmi.
Dimostrare che sono coprìmi anche i valori seguenti:
$U=2a+(1+2a)*(a^2-b^2) $ , $V=2a(a^2+2a-b^2)*(a^2-b^2)$
karl
1)Dimostrare che se r ed s sono coprìmi (attenti all'accento !!)
allora sono coprìmi anche i numeri r+s ed r*s
2)Siano a-b e a+b coprìmi.
Dimostrare che sono coprìmi anche i valori seguenti:
$U=2a+(1+2a)*(a^2-b^2) $ , $V=2a(a^2+2a-b^2)*(a^2-b^2)$
karl
1) sapendo che in generale $(a,b) = (a,b+ax)$ per $a,b,x \in ZZ$, si ha che
$1=(r,s)=(r,r+s)$ e $1=(r,s)=(s,r+s)$ implica $(rs, r+s)=1$
2) dall'ipotesi si ha $1=(a-b,a+b)=(2a,a+b)=(2a,b-a)=(2a,a-b)= (2a,a^2-b^2)$
inoltre $(2a,2a+1) = 1$ dunque $(2a,(a^2-b^2)(2a+1))=1$ e per $1)$ si puo' scrivere
$(2a+(a^2-b^2)(2a+1), 2a(a^2-b^2)(2a+1))=1$ e dunque in particolare $(2a+(a^2-b^2)(2a+1), 2a(a^2-b^2))$.
resta da mostrare che $(U,a^2-b^2+2a)=1$:
ma se supponiamo $d|U$ e $d|a^2-b^2+2a$ allora $d|(a^2-b^2)(2a+1)-(a^2-b^2)$ dunque $d|(a^2-b^2)(2a)$. Abbiamo gia' detto
che questo accade sse $d=1,-1$ e dunque $(U,a^2-b^2+2a)=1$.
Questo implica la tesi.
$1=(r,s)=(r,r+s)$ e $1=(r,s)=(s,r+s)$ implica $(rs, r+s)=1$
2) dall'ipotesi si ha $1=(a-b,a+b)=(2a,a+b)=(2a,b-a)=(2a,a-b)= (2a,a^2-b^2)$
inoltre $(2a,2a+1) = 1$ dunque $(2a,(a^2-b^2)(2a+1))=1$ e per $1)$ si puo' scrivere
$(2a+(a^2-b^2)(2a+1), 2a(a^2-b^2)(2a+1))=1$ e dunque in particolare $(2a+(a^2-b^2)(2a+1), 2a(a^2-b^2))$.
resta da mostrare che $(U,a^2-b^2+2a)=1$:
ma se supponiamo $d|U$ e $d|a^2-b^2+2a$ allora $d|(a^2-b^2)(2a+1)-(a^2-b^2)$ dunque $d|(a^2-b^2)(2a)$. Abbiamo gia' detto
che questo accade sse $d=1,-1$ e dunque $(U,a^2-b^2+2a)=1$.
Questo implica la tesi.
Bene...
Adesso pero' tocca a vl4d postare un esercizio a risolvere.
karl
Adesso pero' tocca a vl4d postare un esercizio a risolvere.
karl
eccomi, sempre facilino?
quanti sono i sottoinsiemi $S_i$ di ${1,2,...,30}$ tali che, per ogni $S_i$, $\sum_{s\in S_i}s >232$ ?
quanti sono i sottoinsiemi $S_i$ di ${1,2,...,30}$ tali che, per ogni $S_i$, $\sum_{s\in S_i}s >232$ ?
Vi propongo un problema:
il perimetro di un rombo è 40 cm e la somma delle diagonali è 28 cm. Calcola l'area del rombo.
il perimetro di un rombo è 40 cm e la somma delle diagonali è 28 cm. Calcola l'area del rombo.
Dovevi aprire un topic apposta, qui si fa in un altro modo
"vl4d":
eccomi, sempre facilino?
quanti sono i sottoinsiemi $S_i$ di ${1,2,...,30}$ tali che, per ogni $S_i$, $\sum_{s\in S_i}s >232$ ?
Sia $f(S_i)=\sum_{s \in S_i} s$ e $S={1,\ldots,30}$. Abbiamo $f(S)=465$, quindi per ogni sottoinsieme di $S$, $S_i$, abbiamo o che $f(S_i)<232.5$ o $f(S_i)>232.5$. Se prendiamo il complemento di un sottoinsieme di $S$ per cui si ha $F(S_i)>232.5$, allora la sua$f(\cdot)$ sarà minore $232.5$, e viceversa. Quindi possiamo accoppiare questi due tipi di insieme, cioè sono fifty-fifty
. Dunque il numero di sottoinsiemi cercato è $2^30/2=2^29$.Problema
Trovare tutti gli interi positivi $d$ tali che dividono sia $n^2+1$ che $(n+1)^2+1$, per qualche intero positivo $n$.
quindi si ha che $(n^2+1)equiv0modd$ e $((n+1)^2+1)equiv0modd$
quindi tutti i numeri che hanno in comune il divisore d e formano tutte le combinazioni di numeri sono la somma di quei due casi, quindi si ha $((n+1)^2+1)+(n^2+1)equiv0modd$
da notare che quando n è pari, $(n^2+1)$ è dispari e $((n+1)^2+1)$ è pari e viceversa.
sviluppando i calcoli si ha che $(2n^2+2n+3)equiv0modd
da notare anche che non tutti gli interi positivi n danno soluzione al problema, tipo n=1 si ha che uno è 2 l'altrpo e 5.
se n=2 si ha $15equv0modd$ e quindi d=3,5 ma 3 non scompone $((n+1)^2+1)$ e quindi si può accettare solo 5.
in generale, per gli interi n che si possono dividere, l'unico intero d è 5 e vale solo per qualche intero n.
giusto?
quindi tutti i numeri che hanno in comune il divisore d e formano tutte le combinazioni di numeri sono la somma di quei due casi, quindi si ha $((n+1)^2+1)+(n^2+1)equiv0modd$
da notare che quando n è pari, $(n^2+1)$ è dispari e $((n+1)^2+1)$ è pari e viceversa.
sviluppando i calcoli si ha che $(2n^2+2n+3)equiv0modd
da notare anche che non tutti gli interi positivi n danno soluzione al problema, tipo n=1 si ha che uno è 2 l'altrpo e 5.
se n=2 si ha $15equv0modd$ e quindi d=3,5 ma 3 non scompone $((n+1)^2+1)$ e quindi si può accettare solo 5.
in generale, per gli interi n che si possono dividere, l'unico intero d è 5 e vale solo per qualche intero n.
giusto?
Sì, c'è anche $d=1$, naturalmente , ma non mi convince la tua dimostrazione. Tu verifichi il caso in cui $n=2$, poi dici "in generale [...]". Dovresti giustificare quel generale, perché, così, tu non escludi che ci siano $d>5$.
, ma non mi convince la tua dimostrazione. Tu verifichi il caso in cui $n=2$, poi dici "in generale [...]". Dovresti giustificare quel generale, perché, così, tu non escludi che ci siano $d>5$.
ok ora ti dico anche in generale perchè:
se si va avanti, un numero pari al quadrato èpiù uno da un numero dispari mentre l'altro membro da un numero pari,così tutti i divisori per d>5 pari son esclusi.
inoltre l'unico caso che si può verificare che due numeri di questo tipo abbiano un divisore in comune, è quando uno finisce per 5 e l'altro per 0 (es. n=7, uno è 50 l'altro è 65), altrimenti essendo uno pari e l'altro dispari, non ammettono diviso in comune perchè se ci fosse un primo dispari che potesse dividerli entrambi, entrambi i numeri che si generano devono essere multipli di quel numero, ma questo non può mai accadere,
vediamo la serie che si genera
2,5,10,17,26,37,50,65,82,101...
quindi quando uno vale n, l'altro vale n+1.
proviamo a sottrarre $a_n-a_(n-1)$
5-2=3
10-5=5
17-10=7
26-17=9
37-26=11
50-37=13
65-50=15
82-65=17
101-82=19
..
da qui possiamo riscrivere la serie 2,5,10,17,26,37,50,65,82,101... ricorsivamente come
${(a_0=2),(a_1=5),(a_n=a_(n-1)+a_(n-1)-a_(n-2)+2):}
che riscritta è uguale a ${(a_0=2),(a_1=5),(a_n=2a_(n-1)-a_(n-2)+2):}
la differenza termina per 5 tra $a_(n)-a_(n-1)$ quando la differenza tra $a_(n-1)-a_(n-2)=k3$ dove k rappresenta le decine e le centinaia del numero.
le altre volte la differenza è un numero che o è primo (e quindi non si hanno mai divisori in comune) o è divisibile per tre, ma visto che i due numeri iniziali della serie non son divisibili per tre, non è possibile che due numeri consecutivi all'interno della serie diano divisori di tre consecutivi. stesso ragionamento per tutti gli altri divisori.
l'unica volta in cui la differenza da un numero che finisce per 5, è l'unico caso in cui 5 è per forza un divisore comune, oltre all'1.
per questo non possono esistere divisori interi per d>5.
è chiara come dimostrazione della parte che non era convincente prima?spero di aver scritto in modo chiaro...
se si va avanti, un numero pari al quadrato èpiù uno da un numero dispari mentre l'altro membro da un numero pari,così tutti i divisori per d>5 pari son esclusi.
inoltre l'unico caso che si può verificare che due numeri di questo tipo abbiano un divisore in comune, è quando uno finisce per 5 e l'altro per 0 (es. n=7, uno è 50 l'altro è 65), altrimenti essendo uno pari e l'altro dispari, non ammettono diviso in comune perchè se ci fosse un primo dispari che potesse dividerli entrambi, entrambi i numeri che si generano devono essere multipli di quel numero, ma questo non può mai accadere,
vediamo la serie che si genera
2,5,10,17,26,37,50,65,82,101...
quindi quando uno vale n, l'altro vale n+1.
proviamo a sottrarre $a_n-a_(n-1)$
5-2=3
10-5=5
17-10=7
26-17=9
37-26=11
50-37=13
65-50=15
82-65=17
101-82=19
..
da qui possiamo riscrivere la serie 2,5,10,17,26,37,50,65,82,101... ricorsivamente come
${(a_0=2),(a_1=5),(a_n=a_(n-1)+a_(n-1)-a_(n-2)+2):}
che riscritta è uguale a ${(a_0=2),(a_1=5),(a_n=2a_(n-1)-a_(n-2)+2):}
la differenza termina per 5 tra $a_(n)-a_(n-1)$ quando la differenza tra $a_(n-1)-a_(n-2)=k3$ dove k rappresenta le decine e le centinaia del numero.
le altre volte la differenza è un numero che o è primo (e quindi non si hanno mai divisori in comune) o è divisibile per tre, ma visto che i due numeri iniziali della serie non son divisibili per tre, non è possibile che due numeri consecutivi all'interno della serie diano divisori di tre consecutivi. stesso ragionamento per tutti gli altri divisori.
l'unica volta in cui la differenza da un numero che finisce per 5, è l'unico caso in cui 5 è per forza un divisore comune, oltre all'1.
per questo non possono esistere divisori interi per d>5.
è chiara come dimostrazione della parte che non era convincente prima?spero di aver scritto in modo chiaro...
Guarda, ho provato a capire cosa intendi, ma non riesco a seguire alcuni punti. Potresti cercare di formalizzare il tutto un po' più comprensibilmente?
se $n^2+1=0(mod d)$ e $(n+1)^2+1=n^2+2n+2=0(mod d)$ il che implica che $2n+1=0(mod d$ di nuovo $n^2=-1(mod d) e 2n=-1(mod d)$ quindi $n^2=2n(mod d)$ ora credo si possa dividere per n che è primo con d in quanto $n^2=-1(mod d)$ ed ottengo $n=2(mod d)$ elevo al quadrato e sommo 1 ed ottengo $n^2+1=5(mod d)$ questo implica che $5=0(mod d)$ quindi d può essere o 1 o 5.
quindi si ha che $(n^2+1)equiv0modd$ e $((n+1)^2+1)equiv0modd$
quindi tutti i numeri che hanno in comune il divisore d e formano tutte le combinazioni di numeri sono la somma di quei due casi, quindi si ha $((n+1)^2+1)+(n^2+1)equiv0modd$
da notare che quando n è pari, $(n^2+1)$ è dispari e $((n+1)^2+1)$ è pari e viceversa.
sviluppando i calcoli si ha che $(2n^2+2n+3)equiv0modd
da notare anche che non tutti gli interi positivi n danno soluzione al problema, tipo n=1 si ha che uno è 2 l'altrpo e 5.
se n=2 si ha $15equiv0modd$ e quindi d=3,5 ma 3 non scompone $((n+1)^2+1)$ e quindi si può accettare solo 1 e 5.
vediamo la serie che si genera
2,5,10,17,26,37,50,65,82,101...
proviamo a sottrarre $a_n-a_(n-1)$
5-2=3
10-5=5
17-10=7
26-17=9
37-26=11
50-37=13
65-50=15
82-65=17
101-82=19
..
da qui possiamo riscrivere la serie 2,5,10,17,26,37,50,65,82,101... ricorsivamente come
${(a_0=2),(a_1=5),(a_n=a_(n-1)+a_(n-1)-a_(n-2)+2):}
che riscritta è uguale a ${(a_0=2),(a_1=5),(a_n=2a_(n-1)-a_(n-2)+2):}
bisogna verificare in che casi si ha $(a_n,a_(n+1))!=0$ cioè quando due coppie successive tra loro hanno un divisore in comune.
riscriviamo questo come $((2a_(n-1)-a_(n-2)+2)$,$(2a_n-a_(n-1)+2))$ che riscritto ancora, sostituendo il valore di $a_n$ nella seconda viene
$((2a_(n-1)-a_(n-2)+2)$,$(2((2a_(n-1)-a_(n-2)+2))-a_(n-1)+2))$ sviluppando i calcoli nella seconda si ottiene
$((2a_(n-1)-a_(n-2)+2)$,$(3a_(n-1)-2a_(n-2)+6))$
Hp che $a_(n-2)$ sia pari, quindi $a_(n-1)$ è dispari; ma stesso discorso vale se fosse dispari.
si avrebbe che nella parte a sinistra (che rappresenta il termine n) $((2a_(n-1)-a_(n-2)+2)$ è presente un numero pari, nella parte a destra (che rappresenta il termine n+1), $(3a_(n-1)-2a_(n-2)+6))$ è presente un numero dispari.
da notare che $a_n$ assume valore pari quando n è dispari.
quindi la domanda è: qual'è quel numero dispari che divide due numeri succevvi nella serie?
e cioè $(2a_(n-1)-a_(n-2)+2)equiv0modd$ e $(3a_(n-1)-2a_(n-2)+6)equiv0modd$?
ancora una volta sommiamo $a_n$ con $a_(n+1)$ in quanto un divisore comune ad uno, deve essere comune anche alla somma dei due numeri (la somma contiene sia i divisori comuni ad entrambi i numeri, sia altri divisori ma questo non influisce sul risultato).
si ottiene che $(2a_(n-1)-a_(n-2)+2+3a_(n-1)-2a_(n-2)+6)equiv0modd$ facciamo due calcoli e otteniamo
$5a_(n-1)-3a_(n-2)+8equiv0modd$ che è come dire $a_n+a_(n+1)equiv0modd$
quindi come ipotizzato prima $a_(n-2)$ è pari, se è pari allora la somma dei due numeri produce un numero dispari.
visto che i due numeri iniziali della serie erano 2 e 5, se si osserva, la somma di tutti gli $a_n+a_(n+1)$ dovrà dare dei numeri che sono divisibili per 1 o 3 o 5, però 3 non sarà divisore di uno dei due membri, in quanto i numeri pari che si generano non sono mai divisibili tre (oppure nessuno dei due numeri è divisibile per tre, ma questo è un caso particolare).
quando son divisori di cinque, entrambi devono essere divisibili per 5.
Quindi i divisori d di alcuni n interi appartenenti alla serie, sono 1 e 5.
ora è più comprensibile il ragionamento?...
quindi tutti i numeri che hanno in comune il divisore d e formano tutte le combinazioni di numeri sono la somma di quei due casi, quindi si ha $((n+1)^2+1)+(n^2+1)equiv0modd$
da notare che quando n è pari, $(n^2+1)$ è dispari e $((n+1)^2+1)$ è pari e viceversa.
sviluppando i calcoli si ha che $(2n^2+2n+3)equiv0modd
da notare anche che non tutti gli interi positivi n danno soluzione al problema, tipo n=1 si ha che uno è 2 l'altrpo e 5.
se n=2 si ha $15equiv0modd$ e quindi d=3,5 ma 3 non scompone $((n+1)^2+1)$ e quindi si può accettare solo 1 e 5.
vediamo la serie che si genera
2,5,10,17,26,37,50,65,82,101...
proviamo a sottrarre $a_n-a_(n-1)$
5-2=3
10-5=5
17-10=7
26-17=9
37-26=11
50-37=13
65-50=15
82-65=17
101-82=19
..
da qui possiamo riscrivere la serie 2,5,10,17,26,37,50,65,82,101... ricorsivamente come
${(a_0=2),(a_1=5),(a_n=a_(n-1)+a_(n-1)-a_(n-2)+2):}
che riscritta è uguale a ${(a_0=2),(a_1=5),(a_n=2a_(n-1)-a_(n-2)+2):}
bisogna verificare in che casi si ha $(a_n,a_(n+1))!=0$ cioè quando due coppie successive tra loro hanno un divisore in comune.
riscriviamo questo come $((2a_(n-1)-a_(n-2)+2)$,$(2a_n-a_(n-1)+2))$ che riscritto ancora, sostituendo il valore di $a_n$ nella seconda viene
$((2a_(n-1)-a_(n-2)+2)$,$(2((2a_(n-1)-a_(n-2)+2))-a_(n-1)+2))$ sviluppando i calcoli nella seconda si ottiene
$((2a_(n-1)-a_(n-2)+2)$,$(3a_(n-1)-2a_(n-2)+6))$
Hp che $a_(n-2)$ sia pari, quindi $a_(n-1)$ è dispari; ma stesso discorso vale se fosse dispari.
si avrebbe che nella parte a sinistra (che rappresenta il termine n) $((2a_(n-1)-a_(n-2)+2)$ è presente un numero pari, nella parte a destra (che rappresenta il termine n+1), $(3a_(n-1)-2a_(n-2)+6))$ è presente un numero dispari.
da notare che $a_n$ assume valore pari quando n è dispari.
quindi la domanda è: qual'è quel numero dispari che divide due numeri succevvi nella serie?
e cioè $(2a_(n-1)-a_(n-2)+2)equiv0modd$ e $(3a_(n-1)-2a_(n-2)+6)equiv0modd$?
ancora una volta sommiamo $a_n$ con $a_(n+1)$ in quanto un divisore comune ad uno, deve essere comune anche alla somma dei due numeri (la somma contiene sia i divisori comuni ad entrambi i numeri, sia altri divisori ma questo non influisce sul risultato).
si ottiene che $(2a_(n-1)-a_(n-2)+2+3a_(n-1)-2a_(n-2)+6)equiv0modd$ facciamo due calcoli e otteniamo
$5a_(n-1)-3a_(n-2)+8equiv0modd$ che è come dire $a_n+a_(n+1)equiv0modd$
quindi come ipotizzato prima $a_(n-2)$ è pari, se è pari allora la somma dei due numeri produce un numero dispari.
visto che i due numeri iniziali della serie erano 2 e 5, se si osserva, la somma di tutti gli $a_n+a_(n+1)$ dovrà dare dei numeri che sono divisibili per 1 o 3 o 5, però 3 non sarà divisore di uno dei due membri, in quanto i numeri pari che si generano non sono mai divisibili tre (oppure nessuno dei due numeri è divisibile per tre, ma questo è un caso particolare).
quando son divisori di cinque, entrambi devono essere divisibili per 5.
Quindi i divisori d di alcuni n interi appartenenti alla serie, sono 1 e 5.
ora è più comprensibile il ragionamento?...
"rubik":
se $n^2+1=0(mod d)$ e $(n+1)^2+1=n^2+2n+2=0(mod d)$ il che implica che $2n+1=0(mod d$ di nuovo $n^2=-1(mod d) e 2n=-1(mod d)$ quindi $n^2=2n(mod d)$ ora credo si possa dividere per n che è primo con d in quanto $n^2=-1(mod d)$ ed ottengo $n=2(mod d)$ elevo al quadrato e sommo 1 ed ottengo $n^2+1=5(mod d)$ questo implica che $5=0(mod d)$ quindi d può essere o 1 o 5.
mmm una cosa non capisco, ma se all'inizio l'ipotesi è $n^2+1=0(mod d)$, te per dimostrarla arrivi a dire che $n^2+1=5(mod d)$ non è contradditorio con l'ipotesi iniziale?...
non capisco...
devo dire innanzitutto che per d=1 il procedimento non vale (ma comunque si può dire che per d=1 va bene qualunque n). se poi il procedimento è giusto arrivo a dire che $n=2(mod d)$ è qua se prima elevi al quadrato entrambi i membri l'uguaglianza rimane quindi $n^2=4(mod d)$ sommi uno e $n^2+1=5(mod d)$ da qui sapendo che $n^2+1=0(mod d)$ si deduce che $5=0(mod d)$ essendo 5 primo d deve essere per forza 5. non so se giusto cerco conferme (o confutazioni) ma quel passaggio che dici sono sostanzialmente calcoli e dipende da quello fatto prima. comunque non è contraddittorio con l'ipotesi iniziale se $5=0(modd)$ e questo ci dice appunto che l'unico d può essere 5. spero di essermi spiegato ciao
"rubik":
se $n^2+1=0(mod d)$ e $(n+1)^2+1=n^2+2n+2=0(mod d)$ il che implica che $2n+1=0(mod d$ di nuovo $n^2=-1(mod d) e 2n=-1(mod d)$ quindi $n^2=2n(mod d)$ ora credo si possa dividere per n che è primo con d in quanto $n^2=-1(mod d)$ ed ottengo $n=2(mod d)$ elevo al quadrato e sommo 1 ed ottengo $n^2+1=5(mod d)$ questo implica che $5=0(mod d)$ quindi d può essere o 1 o 5.
Perfetto. A te il prossimo problema da proporre.
Scusa, fu^2, per mancanza di tempo, prendo la soluzione di rubik, anche se puo' darsi che anche la tua sia giusta.
non so fare il coefficiente binomiale con i comandi 
comunque sia $alpha,m,p in NN$ con p primo ed m coprimo con p dimostrare che:
coefficiente binomiale: $p^am$ su $p^a$ non è divisibile per p
comunque sia $alpha,m,p in NN$ con p primo ed m coprimo con p dimostrare che:
coefficiente binomiale: $p^am$ su $p^a$ non è divisibile per p
mi puzza di teorema di Sylow...
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo