Teorema cinese del resto (senza dimostrazione)

Cosa sono il pigeonhole e l'induzione? Cosa dice il teorema di Ceva? 1 è un numero primo?
Rispondi
Avatar utente
pazqo
Messaggi: 155
Iscritto il: 01 gen 1970, 01:00
Località: san giorgio di nogaro
Contatta:

Teorema cinese del resto (senza dimostrazione)

Messaggio da pazqo » 15 mar 2005, 13:36

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.
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

fph
Site Admin
Messaggi: 3662
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Teorema cinese del resto (senza dimostrazione)

Messaggio da fph » 15 mar 2005, 14:56

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.
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. :-)

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]

Avatar utente
pazqo
Messaggi: 155
Iscritto il: 01 gen 1970, 01:00
Località: san giorgio di nogaro
Contatta:

Messaggio da pazqo » 15 mar 2005, 15:20

2 ulteriori domande:
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]
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
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

EvaristeG
Site Admin
Messaggi: 4777
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Messaggio da EvaristeG » 15 mar 2005, 17:33

pazqo ... ma perchè "\right\." ?
non dovrebbe essere "\right." ?
il comando "\." non esiste...

fph
Site Admin
Messaggi: 3662
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Messaggio da fph » 15 mar 2005, 18:10

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
Potremmo semplicemente rinominare "matematica non elementare" in "altra matematica" o "matematica non olimpica", vi andrebbe bene?
\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]

Avatar utente
pazqo
Messaggi: 155
Iscritto il: 01 gen 1970, 01:00
Località: san giorgio di nogaro
Contatta:

Messaggio da pazqo » 15 mar 2005, 18:54

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.
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

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Cattivi e pure un po' a sproposito...

Messaggio da HiTLeuLeR » 15 mar 2005, 20:06

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?
Ufff... E pure fph a rincarare la dose, eh? Ri-uffffff... Ma siamo alla congiura?!? :evil: :wink:

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!!!

Avatar utente
pazqo
Messaggi: 155
Iscritto il: 01 gen 1970, 01:00
Località: san giorgio di nogaro
Contatta:

Messaggio da pazqo » 15 mar 2005, 20:57

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:
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.
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... :-)

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

Simo_the_wolf
Moderatore
Messaggi: 1036
Iscritto il: 01 gen 1970, 01:00
Località: Pescara

Messaggio da Simo_the_wolf » 15 mar 2005, 23:53

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... :lol: (senza offesa, HiT).

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 16 mar 2005, 00:41

Simo_the_wolf ha scritto:Personalmente anch'io a volte faccio un po' di fatica a leggere i testi dei suoi problemi, a capire ciò che realmente chiedono... :lol: (senza offesa, HiT).
Offendermi?!? Io? Asd... Debbo ancora trovarlo, un tale in grado di riuscirci!!! Su, su, non ti montare la testa. :twisted:

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 17 mar 2005, 09:31

Ragazzi, dividete il thread. Qui avete parlato di LaTeX, di che cosa è e non è p.s.o. Scusate, ma torniamo a parlare di TCR.

Problema in cui si usa il TCR:

Dimostrare che esistono 2005 numeri composti consecutivi.

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Uhmmm...

Messaggio da HiTLeuLeR » 17 mar 2005, 14:12

Marco ha scritto:Problema in cui si usa il TCR: "dimostrare che esistono 2005 numeri composti consecutivi."
...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.

Zok
Messaggi: 140
Iscritto il: 01 gen 1970, 01:00
Località: Cambridge - Verona

Messaggio da Zok » 19 lug 2005, 11:04

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

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 19 lug 2005, 13:00

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...
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

Rispondi