Teorema cinese del resto (senza dimostrazione)
Teorema cinese del resto (senza dimostrazione)
Questo stumento può risultare molto utile e non so se fa parte del bagaglio olimpionico degli studenti liceali...
Teorema Cinese del Resto
Siano $ a_1,\ldots,a_n\in\mathbb{N} $ coprimi. Siano $ b_1,\ldots,b_n\in\mathbb{N} $ tali che $ b_i<a_i $ per ogni $ i = 1,\ldots,n $. Allora esiste una soluzione al sistema di equazioni congruenziali
$ \left\{ \begin{array}{l} x \equiv_{a_1} b_1\\ x \equiv_{a_2} b_2\\ \vdots\\ x \equiv_{a_n} b_n\\ \end{array} \right. $
Inolte la soluzione è unica modulo $ a_1\cdot\ldots\cdot a_n $
Tralascio la dimostrazione perché ho un po' di cose da fare. Chi vuole può provare a farlo per esercizio.
Un simile teorema può essere utile per risolvere problemi come il seguente:
Abbiamo una collezione di biglie. Raccogliendole 3 a 3 ne rimangono 2, raccogliendole 5 a 5 ne rimangono 4, raccogliendole 14 a 14 ne rimangono 10. Quante palline ho? (sono meno di 210)
Il teorema non fornisce il numero di palline, dice solo che una tale situazione è possiblile. Tuttavia è facile trovare una soluzione a problemi semplici. Per cose più teoriche il teorema fornisce le condizioni per l'esistenza di una data soluzione.
Detto questo, tra qualche giorno proporrò un problema che richiederà l'uso di questo teorema.
Ps (per i gestori):
Un esercizio che richieda il teorema cinese del resto può essere messo sotto matematica elementare? Non si tratta di fare conti, ma di usare il teorema vero e proprio.
Teorema Cinese del Resto
Siano $ a_1,\ldots,a_n\in\mathbb{N} $ coprimi. Siano $ b_1,\ldots,b_n\in\mathbb{N} $ tali che $ b_i<a_i $ per ogni $ i = 1,\ldots,n $. Allora esiste una soluzione al sistema di equazioni congruenziali
$ \left\{ \begin{array}{l} x \equiv_{a_1} b_1\\ x \equiv_{a_2} b_2\\ \vdots\\ x \equiv_{a_n} b_n\\ \end{array} \right. $
Inolte la soluzione è unica modulo $ a_1\cdot\ldots\cdot a_n $
Tralascio la dimostrazione perché ho un po' di cose da fare. Chi vuole può provare a farlo per esercizio.
Un simile teorema può essere utile per risolvere problemi come il seguente:
Abbiamo una collezione di biglie. Raccogliendole 3 a 3 ne rimangono 2, raccogliendole 5 a 5 ne rimangono 4, raccogliendole 14 a 14 ne rimangono 10. Quante palline ho? (sono meno di 210)
Il teorema non fornisce il numero di palline, dice solo che una tale situazione è possiblile. Tuttavia è facile trovare una soluzione a problemi semplici. Per cose più teoriche il teorema fornisce le condizioni per l'esistenza di una data soluzione.
Detto questo, tra qualche giorno proporrò un problema che richiederà l'uso di questo teorema.
Ps (per i gestori):
Un esercizio che richieda il teorema cinese del resto può essere messo sotto matematica elementare? Non si tratta di fare conti, ma di usare il teorema vero e proprio.
Ultima modifica di pazqo il 15 mar 2005, 18:55, modificato 3 volte in totale.
Stefano 'Pazqo' Pascolutti
A good mathematical joke is better, and better mathematics, than a dozen of mediocre papers -John Edensor LITTLEWOOD-
Use [tex]\LaTeX[/tex] in your math messages!
www.pazqo.altervista.org
A good mathematical joke is better, and better mathematics, than a dozen of mediocre papers -John Edensor LITTLEWOOD-
Use [tex]\LaTeX[/tex] in your math messages!
www.pazqo.altervista.org
Re: Teorema cinese del resto (senza dimostrazione)
Vai tranquillo: il teorema cinese del resto rientra appieno nel "programma olimpico", da Febbraio in su ci sono esercizi che lo usano (well, a febbraio piu' o meno coscientemente...) e compare anche nelle Sacre Dispense del Gobbino.pazqo ha scritto: Ps (per i gestori):
Un esercizio che richieda il teorema cinese del resto può essere messo sotto matematica elementare? Non si tratta di fare conti, ma di usare il teorema vero e proprio.
Pero', giusto per ribadire il concetto visto che si parla di "matematica elementare"... In questo forum non c'e' una categoria chiamata "matematica elementare", c'e' una categoria chiamata "problem solving olimpico". Nella mia (opinabile) idea personale del forum dovrebbero andarci soprattutto esercizi di "sicura olimpicita'" (in particolare, esericizi presi da gare vecchie di tutti i tipi, italiane e non) e non "problemi self-posed" o che derivano da corsi universitari.
ciao,
--federico
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
2 ulteriori domande:
1)
mi sapete dire da dove salta fuori la $ \Gamma $ che si vede accanto al sistema? Bisogna asteriscare anche qua, per togliere la numerazione???? che diamine è?
2) son d'accordo sugli esercizi universistari e sulla maggior parte dei self-posed. ma ci sono esercizi interessanti di matematica "elementare" (a questo punto si potrebbe aggiungere oltre che problem solving olimpico e matematica avanzata un livello intermedio, per mettere gli esercizi semplici, affrontabili senza aver troppe conoscenze, ma più istituzionali. Non da olimpiadi, insomma. Non saprei dove mettere certi problemi, altrimenti. Ovviamente tutti i post di Euler potrebbero confluire lì da teoria dei numeri. O no? Pensateci
ciaoo
1)
Codice: Seleziona tutto
[tex]\left\{
\begin{array}{l}
x \equiv_{a_1} b_1\\
x \equiv_{a_2} b_2\\
\vdots\\
x \equiv_{a_n} b_n\\
\end{array}
\right\.[/tex]
2) son d'accordo sugli esercizi universistari e sulla maggior parte dei self-posed. ma ci sono esercizi interessanti di matematica "elementare" (a questo punto si potrebbe aggiungere oltre che problem solving olimpico e matematica avanzata un livello intermedio, per mettere gli esercizi semplici, affrontabili senza aver troppe conoscenze, ma più istituzionali. Non da olimpiadi, insomma. Non saprei dove mettere certi problemi, altrimenti. Ovviamente tutti i post di Euler potrebbero confluire lì da teoria dei numeri. O no? Pensateci
ciaoo
Stefano 'Pazqo' Pascolutti
A good mathematical joke is better, and better mathematics, than a dozen of mediocre papers -John Edensor LITTLEWOOD-
Use [tex]\LaTeX[/tex] in your math messages!
www.pazqo.altervista.org
A good mathematical joke is better, and better mathematics, than a dozen of mediocre papers -John Edensor LITTLEWOOD-
Use [tex]\LaTeX[/tex] in your math messages!
www.pazqo.altervista.org
Potremmo semplicemente rinominare "matematica non elementare" in "altra matematica" o "matematica non olimpica", vi andrebbe bene?pazqo ha scritto: 2) son d'accordo sugli esercizi universistari e sulla maggior parte dei self-posed. ma ci sono esercizi interessanti di matematica "elementare" (a questo punto si potrebbe aggiungere oltre che problem solving olimpico e matematica avanzata un livello intermedio, per mettere gli esercizi semplici, affrontabili senza aver troppe conoscenze, ma più istituzionali. Non da olimpiadi, insomma. Non saprei dove mettere certi problemi, altrimenti. Ovviamente tutti i post di Euler potrebbero confluire lì da teoria dei numeri. O no? Pensateci
ciaoo
\begin{joke}
Comunque se e' una scusa per spostare da li' i post di Euler io sono d'accordo
\end{joke}
ciao,
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
in effetti mi ero confuso. però non capisco perché quel \. genera una gamma....
a fare copia incolla ho aggiunto un pezzo che non c'era. Quanto al rinominare il forum: Ok, a patto che però vengano accettate discussioni di ogni livello (alto, medio, basso). Non vorrei che si riempisse di integrali inutili (inutili per me, perlomeno).
vabbè, vedremo. ora correggo il post.
a fare copia incolla ho aggiunto un pezzo che non c'era. Quanto al rinominare il forum: Ok, a patto che però vengano accettate discussioni di ogni livello (alto, medio, basso). Non vorrei che si riempisse di integrali inutili (inutili per me, perlomeno).
vabbè, vedremo. ora correggo il post.
Stefano 'Pazqo' Pascolutti
A good mathematical joke is better, and better mathematics, than a dozen of mediocre papers -John Edensor LITTLEWOOD-
Use [tex]\LaTeX[/tex] in your math messages!
www.pazqo.altervista.org
A good mathematical joke is better, and better mathematics, than a dozen of mediocre papers -John Edensor LITTLEWOOD-
Use [tex]\LaTeX[/tex] in your math messages!
www.pazqo.altervista.org
Cattivi e pure un po' a sproposito...
Ufff... E pure fph a rincarare la dose, eh? Ri-uffffff... Ma siamo alla congiura?!?pazqo ha scritto:Son d'accordo sugli esercizi universistari e sulla maggior parte dei self-posed. ma ci sono esercizi interessanti di matematica "elementare" (a questo punto si potrebbe aggiungere oltre che problem solving olimpico e matematica avanzata un livello intermedio, per mettere gli esercizi semplici, affrontabili senza aver troppe conoscenze, ma più istituzionali. Non da olimpiadi, insomma. Non saprei dove mettere certi problemi, altrimenti. Ovviamente tutti i post di Euler potrebbero confluire lì da teoria dei numeri. O no?
Sentite, eh... Sono pienamente d'accordo con voi sul conto di quei problemi (click per un esempio!) che coinvolgono risultati non strettamente olimpici, per quanto elementarmente deducibili. A proposito, fph... Confermi quel che mi ha già detto Mind sull'altro topic? E' vero che il teorema di Dirichlet (sui primi nelle progressioni aritmetiche) ha da ritenersi fuori concorso, ché non ci azzecca proprio niente con il problem solving olimpico? No, m'informo per il futuro, tutto qui! E tu, sommo Flyer, non te la prendere, su, se vo' cercando riscontro pure altrove... Del resto, è a te e a te soltanto che riservo certi attributi...
Ciò detto, mi si lasci aggiungere, come del resto dimostrano le poche soluzioni pervenute ai self-posed che ho proposto nella sezione dedicata alla Teoria dei Numeri, che - a costo di sembrarvi parziale nel giudizio - stanno bene lì dove stanno, ché tutti (fatta eccezione per quelli in cui fosse coinvolto il teorema di Dirichlet) non usano altro che truccosi stratagemmi e qualche timido risultato di base della teoria delle congruenze.
Cito qualche esempio? Leggetevi la dimostrazione del nostro amato Mind relativa al problema #1 del topic "Primi e binomiali", o la soluzione di Boll al problema #3 dello stesso filo (un click proprio qui, grazie!). Certo, la soluzione di Marco al problema #2 di quello stesso topic è un tantinello complicata (tant'è che ancora non l'ho letta per intero!), ma n'esiste almeno un'altra mooolto più elementare: la mia!!! Anche se - questo devo dirlo - utilizza un risultato (tale teorema di Lagrange) che probabilmente non è un argomento affine alla Matematica olimpica. Boh, vedremo... E per il resto? Beh, per il restooo... Vogliamo forse parlare delle soluzioni di ma_go e Simo_the_Wolf (fra i pochi ad esprimersi in materia!) ad alcuni problemi proposti a questo, questo e quest'altro indirizzo?!? Si direbbero soluzioni totalmente olimpiche (per inciso, la soluzione di Simo al problema #1 del topic "Sul modello del teorema di Wilson" debbo ancora verificarla, per cui pigliatela con riserva).
Dunque, mi chiedo... Come si può giudicare tutti gli altri problemi, quando ancora delle soluzioni non gli sono pervenute? Ok, d'accordo, magari sono formulati a testa di min***a, non lo escludo: certe notazioni mi eccitano (con tutte le virgolette del caso!!!), che posso farci? Ma questo non è un motivo sufficiente (a mio modestissimo avviso) per ritenerli "altro che olimpici"! Se la traccia di un problema è del tutto o in parte oscura, si può sempre chiedere al proponente o ad ogni altro buon samaritano di chiarirla, non vi pare? E qui taccio!!!
la differenza tra matematica olimpionica e matematica elementare c'è. Quelli che tu proponi sono esercizi di matematica elementare, non problem solving. Questa differenza mi è stata fatta notare da fph proprio oggi:
Detto questo: Come si può fare? Un Tread di benvenuto esercizi, in cui si discute della sezione più corretta in cui inserire un esercizio? sarebbe una buona soluzione, se non altro per creare una specie di "raccolta di esempi e controesempi di ciò che è (o non è) problem solving olimpico".
Ribadisco: non critico gli esercizi di Euler, che i giovani farebbero bene a provare, ma solo la loro collocazione... Si tratta di mettersi d'accordo.
Anche la sezione "matematica non elementare" è inadatta. Un forum intermedio non ci starebbe male, dopotutto. Attendo giudizi dall'alto[/quote]
Personalmente, problem solving olimpico è qualcosa che non conosco bene. Non son mai arrivato oltre il 7° posto (avevo fatto 61 punti, ma c'era gente del calibro di Cobbe, Tassinari e Montagner...) e quindi non posso pronunciarmi troppo. Il mio metro di paragone è il seguente: Quanto mi diverte un esercizio. se mi son divertito a pensarlo o a risolverlo e non richiede conosce extra ma solo un A-ha Gardnerdiano, allora mi pare un problema proponibile. Questa posizione è discutibile, senza dubbio. soprattutto tenendo conto che qualcuno può divertirsi martellandosi i coglioni e non per questo quella pratica diventa qualcosa di proponibile...fph ha scritto:In questo forum non c'e' una categoria chiamata "matematica elementare", c'e' una categoria chiamata "problem solving olimpico". Nella mia (opinabile) idea personale del forum dovrebbero andarci soprattutto esercizi di "sicura olimpicita'" (in particolare, esericizi presi da gare vecchie di tutti i tipi, italiane e non) e non "problemi self-posed" o che derivano da corsi universitari.
Detto questo: Come si può fare? Un Tread di benvenuto esercizi, in cui si discute della sezione più corretta in cui inserire un esercizio? sarebbe una buona soluzione, se non altro per creare una specie di "raccolta di esempi e controesempi di ciò che è (o non è) problem solving olimpico".
Ribadisco: non critico gli esercizi di Euler, che i giovani farebbero bene a provare, ma solo la loro collocazione... Si tratta di mettersi d'accordo.
Anche la sezione "matematica non elementare" è inadatta. Un forum intermedio non ci starebbe male, dopotutto. Attendo giudizi dall'alto[/quote]
Stefano 'Pazqo' Pascolutti
A good mathematical joke is better, and better mathematics, than a dozen of mediocre papers -John Edensor LITTLEWOOD-
Use [tex]\LaTeX[/tex] in your math messages!
www.pazqo.altervista.org
A good mathematical joke is better, and better mathematics, than a dozen of mediocre papers -John Edensor LITTLEWOOD-
Use [tex]\LaTeX[/tex] in your math messages!
www.pazqo.altervista.org
-
- Moderatore
- Messaggi: 1053
- Iscritto il: 01 gen 1970, 01:00
- Località: Pescara
So che è OT, xò ormai l'argomento è partito quindi dico la mia. Personalmente ritengo che i problemi di Euler siano risolvibili spesso con tecniche elementari, ma magari sono proposti in modo oscuro... Ad esempio un problema simile a quello dei numeri di Cullen era stato proposto al PreIMO del 2004 ma un po' + semplice. E comunque teniamo conto è un ragazzo che cerca di avvicinarsi alla matematica olimpionica e vede i problemi di Euler non è tanto spinto a risolverli forse non tanto per la difficoltà che comunque in alcuni casi non è neanche tanto elevata (anche se quasi sempre richiede conoscenze post-Cesenatico), ma quanto per il modo in cui sono proposti... Personalmente anch'io a volte faccio un po' di fatica a leggere i testi dei suoi problemi, a capire ciò che realmente chiedono... (senza offesa, HiT).
Uhmmm...
...ma pure no, volendo! Si osservi infatti che, per ogni $ n \in\mathbb{N}_0 $ ed ogni $ k = 2, 3, \ldots, n+1 $: $ k \mid \left((n+1)! + k\right) $, e del resto: $ (n+1)! + k > k $, sicché tutti gli interi (positivi) dell'insieme $ \mathcal{S}_n := \{(n+1)! + 2, (n+1)! + 3, \ldots, (n+1)! + n+1\} $ sono composti. Poiché $ |\mathcal{S}_n| = n $, posto $ n := 2005 $, ne fa pertanto seguito l'asserto.Marco ha scritto:Problema in cui si usa il TCR: "dimostrare che esistono 2005 numeri composti consecutivi."
Se non sbaglio qui si parlava del teorema cinese del resto...
Sfogliando il gobbino mi sono imbatutto nello stesso...e mi è venuto un dubbio...
Dato un sistema di congruenze che ammetta un'unica soluzione (cioè con tutti i moduli a due a due relativamente primi) la soluzione che si trova con il metodo indicato dal gobbino è la più piccola possibile?
Magari la domanda è banale ma a me è capitato che non fosse la più piccola...
Grazie in anticipo
Sfogliando il gobbino mi sono imbatutto nello stesso...e mi è venuto un dubbio...
Dato un sistema di congruenze che ammetta un'unica soluzione (cioè con tutti i moduli a due a due relativamente primi) la soluzione che si trova con il metodo indicato dal gobbino è la più piccola possibile?
Magari la domanda è banale ma a me è capitato che non fosse la più piccola...
Grazie in anticipo
Beh, quindi ti sei risposto da solo, no?
Il fatto è che, in generale, quando si ragiona con le congruenze, non è importante scegliere il rappresentante più piccolo (ossia il più piccolo intero che soddisfa la congruenza prescritta). Certo, quando poi devi fare i conti a mente, magari, se riduci i numeri che saltano fuori, ti semplifichi la vita...
Il fatto è che, in generale, quando si ragiona con le congruenze, non è importante scegliere il rappresentante più piccolo (ossia il più piccolo intero che soddisfa la congruenza prescritta). Certo, quando poi devi fare i conti a mente, magari, se riduci i numeri che saltano fuori, ti semplifichi la vita...
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."