Algebra - Aritmetica

In questo forum si discute delle Olimpiadi di Matematica

Moderatore: tutor

Avatar utente
Boll
Messaggi: 1076
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Messaggio da Boll »

Bah, Euler, poichè sia per mio che per tuo errore dovrei rifare tutti i conti, e ne ho poca voglia, lascio ad altri il gravoso compito, tanto l\'idea dimostrativa l\'ho azzeccata <IMG SRC="images/forum/icons/icon_biggrin.gif"><IMG SRC="images/forum/icons/icon_biggrin.gif"><IMG SRC="images/forum/icons/icon_biggrin.gif">
"Ma devo prendere una n-upla qualsiasi o una n-upla arbitraria?" (Lui)
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR »

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2005-01-23 22:24, thematrix wrote:
<BR>2) (34!) / (5^7*2^7) = N * 2^25; poichè 1*3*7*9==9(10), abbiamo <!-- BBCode Start --><B>N==9*9*9*3*(15/5)*(30/(2*5))==3(10)</B><!-- BBCode End -->. Inoltre, dato che 2^25==2(10), <!-- BBCode Start --><B>(N* 2^25)==6(10). Quindi, a=6.</B><!-- BBCode End -->
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Boh, proprio non capisco come arrivi alle conclusioni evidenziate qui sopra!!! In ogni caso, per fugare ogni dubbio, ecco come provare ch\'è a = 2.
<BR>
<BR>---------
<BR>
<BR>Si è già mostrato che dev\'essere b = 0, e che inoltre 2<sup>32</sup> || 34!. Ergo, in particolare: 0 = 34! = 3 · 10<sup>10</sup> + 5 · 10<sup>9</sup> + a · 10<sup>8</sup> mod 2<sup>11</sup>, e perciò nondimeno: 0 = 3 · 2<sup>2</sup> · 5<sup>10</sup> + 5 · 2 · 5<sup>9</sup> + a · 5<sup>8</sup> mod 2<sup>3</sup>. Del resto: phi(2<sup>3</sup>) = 4, sicché - per il solito teorema di Euler-Fermat: 5<sup>8</sup> = 1 mod 2<sup>3</sup>, e dunque - dalla precedente: 0 = 3 · 2<sup>2</sup> · 5<sup>2</sup> + 5 · 2 · 5 + a mod 2<sup>3</sup>, e di qui a = 2 mod 8. Dacché \'a\' è nell\'insieme {0, 1, ..., 9}, la congruenza indicata implica necessaraimente che dev\'essere a = 2, q.e.d.
<BR>
<BR>-------------
<BR>
<BR>Adesso a voi il piacere di calcolare le due cifre residue... <IMG SRC="images/forum/icons/icon_wink.gif"> <font color=white><BR><BR>[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 24-01-2005 13:36 ]
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR »

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2005-01-24 13:10, Boll wrote:
<BR>Bah, Euler, poichè sia per mio che per tuo errore dovrei rifare tutti i conti, e ne ho poca voglia, lascio ad altri il gravoso compito, tanto l\'idea dimostrativa l\'ho azzeccata
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Come ho già detto, il TUO errore è indipendente dal mio lapsus tastierae, quindi... è inutile che <!-- BBCode Start --><I>ce provi, tanto cor sottoscritto nun te riesce</I><!-- BBCode End -->...<font color=white><BR><BR>[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 24-01-2005 20:35 ]
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR »

Vabbe\', concludo la soluzione (in parte già abbozzata) del problema n° 12 e ne approfitto per tirare un po\' su questo thread...
<BR>
<BR>-------------
<BR>
<BR><font color=green><!-- BBCode Start --><B>Problema 12:</B><!-- BBCode End --></font> sapendo che, in rappresentazione decimale, risulta essere 34! = 295232799cd96041408476186096435ab000000, calcolare le cifre incognite \'a\', \'b\', \'c\', \'d\' che figurano a secondo membro.
<BR>
<BR>Soluz.: a = 2 e b = 0, come già in precedenza si è mostrato. D\'altro canto, operando mod 9 e mod 11, si trova che le cifre decimali incognite residue \'c\' e \'d\' sono tali da soddisfare il sistema di congruenze lineari: i) c + d = 3 mod 9;
<BR>ii) d - c = 3 mod 11. Dalla i): c + d = 3 vel c + d = 12, ovvero c = 3 - d vel c = 12 - d, dacché comunque c, d € {0, 1, ..., 9}.
<BR>
<BR>In base alla ii), e rispettivamente nei due casi indicati, si deduce pertanto dover essere: 2d = 6 mod 11 vel 2d = 15 mod 11, ossia: d = 3 mod 11 vel d = 2 mod 11. Di qui d = 3 vel d = 2, e ancora c = 0 vel c = 10.
<BR>
<BR>Le limitazioni imposte sul range di variabilità delle incognite \'c\' e \'d\' suggeriscono pertanto che, necessariamente: c = 0 e d = 3, e ciò conclude la soluzione del problema.<font color=white><BR><BR>[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 27-01-2005 10:21 ]
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR »

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2005-01-23 12:24, MASSO wrote:
<BR>perciò se esistesse una terna che rispetti le condizioni essa avrebbe m=7; ma quindi la somma a sinistra è congrua a 3 modulo 10 e quindi k deve essere 3, (<!-- BBCode Start --><B>deve essere della forma 4p+3</B><!-- BBCode End --> ma già 3^7 è troppo grande) [...]
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Vedo soltanto adesso la tua correzione, e vorrei capire per quale verso ti riesce di escludere che possa aversi k = 1 mod 4. Ok, è chiaro che dev\'essere gcd(n,10) = 1, con n intero > 1. E\' chiaro nondimeno che ci si può limitare a testare gli esponenti dispari interi k > 1 della forma 4p + r, con r = 1 vel r = 3, dacché mcm(phi(2), phi(5)) = 4, e dunque ord<sub>10</sub>(n) | 4. Tuttavia, non capisco come tu possa escludere il caso k = 1 mod 4. Ti va di spiegarmelo?!? Grassie...
<BR>
<BR>EDIT: ho aggiunto un paio di problemi freschi di soluzione alla lista di pagina 1. Adesso non resta che cercare dei volenterosi disposti a risolverli... <IMG SRC="images/forum/icons/icon_confused.gif"> <font color=white><BR><BR>[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 27-01-2005 15:23 ]
matthewtrager
Messaggi: 132
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da matthewtrager »

ma qui? ci sono ancora un sacco di problemi irrisolti! uppo e intanto butto giu\' qualcosa per questo...
<BR>
<BR><!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2005-01-22 11:01, HiTLeuLeR wrote:
<BR>
<BR><font color=red><!-- BBCode Start --><B>Problema 6:</B><!-- BBCode End --></font> dimostrare che, per ogni m € N ed ogni n € Nesiste almeno un intero a > 0 tale che, per ogni k = 0, 1, ..., m: n | phi(a+k).
<BR>
<BR>NOTA: in vero, si può mostrare una tesi più forte, i.e. che n\'esistono infiniti.
<BR>
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>innanzitutto osserviamo che se un primo p_i|x allora (p_i-1)|phi(x).
<BR>
<BR>allora possiamo scegliere m+1 primi p_0, p_1,...p_m tali che
<BR>p_i==1 mod n.*
<BR>
<BR>in questo modo per il teorema cinese del resto possiamo trovare (infinite) soluzioni al sistema:
<BR>
<BR>a==0 mod p_0
<BR>a==-1 mod p_1
<BR>a==-2 mod p_2
<BR>...
<BR>a==-m mod p_m
<BR>
<BR>in questo modo p_k|(a+k) per k da 0 a m e quindi
<BR>n|(p_k-1)|phi(a+k).
<BR>
<BR>____________
<BR>* questo e\' un fatto che so per certo che e\' vero, cioe\' che ci sono infiniti primi congrui a 1 per qualsiasi modulo (anche congrui a qualsiasi altro valore rel. primo con il modulo) ma non so come si dimostri... se qualcuno conosce la dimostrazione mi piacerebbe vederla, anche se non sono sicuro che ne esista una elementare...
<BR>
<BR>comunque non penso sia questa la dimostrazione che voleva Hitleuler, perche\' usando questo fatto mi sembra un po\' troppo facile... <IMG SRC="images/forum/icons/icon_razz.gif"> <BR><BR>[ Questo Messaggio è stato Modificato da: matthewtrager il 09-02-2005 14:42 ]
Avatar utente
Boll
Messaggi: 1076
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Messaggio da Boll »

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>* questo e\' un fatto che so per certo che e\' vero, cioe\' che ci sono infiniti primi congrui a 1 per qualsiasi modulo (anche congrui a qualsiasi altro valore rel. primo con il modulo) ma non so come si dimostri... se qualcuno conosce la dimostrazione mi piacerebbe vederla, anche se non sono sicuro che ne esista una elementare...
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>Se ho ben capito cosa vuoi dire, tale risultato è noto come Teorema di Dirilecht
<BR><!-- BBCode Start --><A HREF="http://mathworld.wolfram.com/DirichletsTheorem.html" TARGET="_blank">clicca qui</A><!-- BBCode End -->
<BR>
<BR>Tempo fa Hitleuler disse di averne trovato una proof \"elementare\" ma qualcuno l\'aveva preceduto, se non ricordo male.. <IMG SRC="images/forum/icons/icon_razz.gif">
"Ma devo prendere una n-upla qualsiasi o una n-upla arbitraria?" (Lui)
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR »

Ahime\', si cresce... Ma un po\' di tempo, di tanto in tanto, lo si trova pure! In fondo, basta volerlo!!! Dunque, dunque...
<BR>
<BR>@matthew: sì, esattamente la mia stessa idea. In quanto al livello del problema, mi limito a tre sole considerazioni: i) anche a costo di ripetere una storia raccontata tante e tante volte da sembrare ormai leggenda, la difficoltà di un problema, eccetto che in rarissimi casi e molto illustri, non è un fattore intrinseco; ii) se ho postato il problema ch\'era ancora il 22 gennaio dell\'anno del Signore 2005 e se una soluzione (la tua, giusto per inciso) è arrivata soltanto oggi, beh... permettimi di dissentire, ma così facile, in fondo in fondo, non è che poi dovesse esserlo davvero; iii) il teorema di Dirichlet, per quanto sia un risultato familiare ai problem solvers di livello sup, certo non è un risultato propriamente elementare.
<BR>
<BR>@boll: sì, quel che dici è vero, soltanto che mi tocca una rettifica! La dimo di Gauchmann o Bauchmann o come diamine si chiama lui è ben diversa dalla mia, e fra parentesi pure (parecchio) più complicata. Sia come sia, ne riparleremo, promesso. Au propose, qualcuno disposto a scrivere per me un decina di paginette sotto dettatura? Mi sono scoperto proprio un inetto, in fatto di Mathematichenglish... <IMG SRC="images/forum/icons/icon_cool.gif"> <IMG SRC="images/forum/icons/icon27.gif">
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR »

Oh, sia chiaro... Per quel che mi compete, la tua soluzione è proprio figa, matthew. Magari si può sistemarla qua e là (lo dico giusto per pararmi le chiappe del *ulo, ché non l\'ho esaminata con la dovuta pignoleria), ma l\'idea ci sta comunque tutta. MOLTO BRAVO, una volta di più. Bravo, bravo, bravo!
lz2110
Messaggi: 55
Iscritto il: 01 gen 1970, 01:00

Messaggio da lz2110 »

forse questo messaggio é leggemento off topic nel senso che non so formulare nessuna illuminante risposta ai problemi che ci sono <IMG SRC="images/forum/icons/icon_cool.gif"> però la mia è una richiesta di aiuto che probabilmente mi rovinerà permanentemente la reputazione...
<BR>comunque... a^pgreco cosa significa??? quando me lo ha spiegato il prof ho solo capito che NON significa un numero a moltiplicato per se stesso pgreco volte... <IMG SRC="images/forum/icons/icon_eek.gif">
EvaristeG
Site Admin
Messaggi: 4896
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Messaggio da EvaristeG »

Prima che MindFlyer veda il tuo post e ti sbrani a insulti, permettimi di consigliarti, caro lz2110, di aprire un nuovo thread (basta cliccare su \"nuovo\" invece che su \"rispondi\") la prossima volta che vuoi fare una domanda o proporre qlcs che non sia già l\'argomento di una qualche discussione ... detto questo, non è che per caso fai il liceo dini a pisa? perchè la storia di a^pigreco mi suona orrendamente familiare ...
lz2110
Messaggi: 55
Iscritto il: 01 gen 1970, 01:00

Messaggio da lz2110 »

thanks per il consiglio, spero di sopravvivere almeno finchè non avrò una risposta ai miei dubbi...
<BR>riguardo alla scuola che frequento complimentoni per l\'intuito (anche se non credo che solo il dini tratti di a^pgreco) e mi sa che hai già capito chi sono <IMG SRC="images/forum/icons/icon21.gif"> .
<BR> riguardo all\' \'ORRIBILMENTE familiare\' sono completamente d\'accordo!
<BR>P.S.: credo che con i miei post infarciti di ignoranza assoluta abbia ormai rovinato la serietà del sito... <IMG SRC="images/forum/icons/icon_frown.gif">
Avatar utente
Antimateria
Messaggi: 651
Iscritto il: 01 gen 1970, 01:00
Località: Vergate sul Membro

Messaggio da Antimateria »

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2005-02-12 16:24, EvaristeG wrote:
<BR>Prima che MindFlyer veda il tuo post e ti sbrani a insulti
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Ormai MindFlyer non dirà più nulla, perché ha 666 messaggi e non li vuole aumentare. Inoltre, a questo punto dichiaro legali gli OT, e qualunque altra forma di mancanza di rispetto delle norme del forum. Tanto, tempo una settimana e tutto questo sarà sparito...
EvaristeG
Site Admin
Messaggi: 4896
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Messaggio da EvaristeG »

Bene, visto che si può ...
<BR>allora, l\'intuito non c\'entra : o ci ho preso perchè so da chi hai sentito questa storia di a^pigreco (nel qual caso a=2 penso) o ho avuto una fortuna spropositata nel beccare uno del dini.
<BR>Di recente alcuni studenti del dini hanno partecipato ad alcune lezioni pomeridiane di matematica olimpica ... in una di queste (algebra&combinatoria) si chiedeva quante soluzioni ha l\'equazione
<BR>2^(x^2-4x+3)=1
<BR>o qualcosa di simile.
<BR>Il povero \"docente\", a quel punto, si è ricordato che fino alla terza o addirittura alla quarta liceo, nessuno parla di funzione esponenziale e che quindi questa scrittura poteva non aver molto senso per i discenti, ma non ha potuto far altro che dire \"beh, esiste, fidatevi\" e sottolineare che 2^x con x razionale si poteva ancora interpretare in termini di potenze e radici intere, mentre ad esempio 2^pigreco non aveva il lusso di una simile interpretazione.
<BR>
<BR>Cmq, che tu fossi o non fossi tra quei liceali del dini, ecco come si può dire 2^pigreco :
<BR>pigreco è un numero irrazionale, ovvero non esistono a,b interi tali che pigreco=a/b
<BR>però, se scegli una precisione arbitraria p (ad esempio 1/1000 o 1/10000 o un numero piccolo quanto vuoi) esistono due interi a,b tali che
<BR>|pigreco - a/b|< p
<BR>
<BR>Ora, scegliamo come precisioni i numeri
<BR>P={1, 1/10, 1/100, 1/1000 , ..., 1/10<sup>n</sup>, ... }
<BR>(questo è un insieme infinito : per ogni naturale n contiene il numero 1/10<sup>n</sup>) chiamiamo i suoi elementi, nell\'ordine decrescente, p<sub>0</sub>, p<sub>1</sub> ... , p<sub>n</sub> ,...
<BR>Sappiamo che esistono, fissato n, due numeri interi (che dipendono da p<sub>n</sub>, e quindi da n) a<sub>n</sub> e b<sub>n</sub> tali che
<BR>|pigreco - a<sub>n</sub>/b<sub>n</sub>|< p<sub>n</sub>
<BR>(possiamo anche dire che
<BR>lim<sub>n--->inf</sub>a<sub>n</sub>/b<sub>n</sub>=pigreco
<BR>ma così arriviamo all\'analisi prima del tempo, ovvero prima del prossimo paragrafo).
<BR>
<BR>Ora, possiamo definire l\'insieme
<BR>A={2<sup>a<sub>0</sub>/b<sub>0</sub></sup>, 2<sup>a<sub>1</sub>/b<sub>1</sub></sup>, ....}
<BR>e si può dimostrare che, con il crescere di n (ovvero prendendo frazioni sempre più vicine a pigreco), questi numeri diventano sempre più vicini; in particolare, fissata una precisione, da un certo n in poi distano tutti tra loro meno di quella precisione e dunque si avvicinano sempre di più a un certo numero (come le frazioni si avvicinavano a pigreco); questo numero a cui gli elementi di A si avvicinano (il limite della successione che essi formano) è il valore di 2^pigreco.
<BR>
<BR>Spero di essere stato abbastanza oscuro (ora come alle lezioni al dini)
<BR>
<BR>Ciao<BR><BR>[ Questo Messaggio è stato Modificato da: EvaristeG il 12-02-2005 22:42 ]
Simo_the_wolf
Moderatore
Messaggi: 1053
Iscritto il: 01 gen 1970, 01:00
Località: Pescara

Messaggio da Simo_the_wolf »

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2005-01-22 11:01, HiTLeuLeR wrote:
<BR>
<BR><font color=blue><!-- BBCode Start --><B>Problema 13:</B><!-- BBCode End --></font> siano n un dispari intero > 1 ed S := {k € N: 0 < k < n & gcd(n,k) = gcd(n,k+1) = 1}. Dopo aver osservato che S è non vuoto, si mostri che: prod<sub>k € S</sub> k = 1 mod n, ove la produttoria s\'intende estesa a tutti e soli gli elementi di S. Dedurne una dimostrazione del teorema di Wilson.
<BR>
<BR>Nota: per quanti non dovessero conoscerne l\'enunciato, il th. di Wilson stabilisce che, se p è un numero primo naturale, allora p | (p-1)! + 1.
<BR>
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>Ok, vogliamo dimostrare che se a€S e a>1 allora c\'è un b=/=a t.c. b€S e ab==1 (mod n).
<BR>Dobbiamo dimostrare che se (a,n)=(a+1,n)=1 allora se ab==1 (n) allora (b,n)=(b+1,n)=1. ma abbiamo (b+1,n)=(a(b+1),n)=(1+a,n)=1 e, proprio perchè ab==1 (n) avremo (b,n)=1. Dobbiamo dimostrare ora che a=/=b.
<BR>Infatti se fosse a=b si avrebbe a²==1 (mod n). Ciò implicherebbe
<BR>n|(a+1)(a-1) ma (n,a+1)=1 quindi n|a-1 e quindi o a=1 (ma non è il caso contemplato) oppure n < a contro l\'ipotesi che se a€S allora 0 < a < n.
<BR>In sintesi, prendendo tutti gli elementi di S (a parte l\'uno se c\'è) possiamo accoppiarli in modo tale che i prodotti delle coppie risultino 1 e quindi il prodotto totale sia 1. Se n è pari allora 1 non appartiene ad S e quindi siamo a posto, se invece n è dispari allora 1€S e comunque il prodotto viene 1. Da questo possiamo dedurre il th. di Wilson. Infatti se n=p è primo allora appartengono ad S tutti gli interi compresi tra 0 ed p-1. Quindi abbiamo:
<BR>(p-2)!==1 (mod p) ==> (p-1)!=(p-2)!(p-1)==(-1)*1==-1 (mod p)
<BR>e quindi p|(p-1)!+1
Bloccato