Olimpiadi della Matematica: problema stellato del 2019

[@bassigiuseppe]

Nell'ultimo calcolo in aritmetica modulare ho commesso un errore abbastanza importante, scrivendo 2^1000=1 mod 10000. In realtà si dovrebbe dire 2^(500+k)=2^k mod 10000, risultato che si ottiene scomponendo mod 10000 in 625 e 16 e poi applicando il teorema cinese del resto. Il risultato che si ottiene è comunque 2^2018=2^18 mod 10000, quindi tutto il procedimento non cambia.

[@lucazani2730]

Video molto istruttivo, problema completo direi Grazie!

[@franksaved3893]

Ciao. Vedendo il tuo video ho provato a risolvere il problema per conto mio. Sono arrivato alla stessa conclusione nel calcolo di p(2019), ma poi ho perso un sacco di tempo nel calcolare 3^2018-2^2018 (mod 10000), Per 3 si può usare il piccolo teorema di Fermat, e l'ordine di 3 modulo 10000 è un divisore di 4000, e dopo numerosi calcoli ho visto che è 500. Per 2 il discorso è diverso dato che non è primo con 10000. Allora basta ridurre 2^2000 modulo 625 (questo si può fare ancora con Fermat), e poi moltiplicare per 2^18 il tutto. Volevo sapere se hai fatto lo stesso ragionamento oppure c'è un modo più diretto senza fare grandi calcoli. Grazie e complimenti per il video.

[@bassigiuseppe]

Ora che me lo hai fatto notare, ho scritto nel video un errore clamoroso! Ho scritto 2^1000=3^1000=1 mod 10000, che è chiaramente falso. Per quanto riguarda il 3^1000=1 mod 10000 è vero e quello che ho usato è uno strumento piuttosto avanzato, cioè il concetto di ordine moltiplicativo universale. Non è niente di difficile, una volta capiti gli ordini è facilissimo capirli. La cosa che ti interessa è che con la formula degli ordini universali puoi migliorare di molto il teorema di eulero. Quindi invece di avere che 3^4000=1 mod 10000 hai addirittura che 3^500=1 mod 10000, che è un risultato abbastanza incredibile. Prova a cercare su internet per approfondire. Prima o poi, ma temo molto avanti, farò anche io un video su questo. Invece per 2^1000 non posso farlo così banalmente mod 10000. Devo farlo mod 625 e chiaramente 2^1000=(2^500)²=1²=1 mod 625, poi farlo mod 16 ed è chiaramente 0. Non ha senso qui il concetto di ordine di 2 mod 10000 (non è coprimo con 10000), però da quello che abbiamo appena ricavato possiamo dire che 2^(500+k)=2^k mod 10000, da cui quello che ho scritto, cioè 2^2018=2^18 mod 10000. Mi scuso per l'errore abbastanza clamoroso

[@bassigiuseppe]

Quindi alla fine si, il tuo metodo è identico. L'unica differenza è che hai dovuto fare numerosi calcoli per ottenere 3^500=1 mod 10000 che si può ottenere subito grazie all'ordine moltiplicativo universale. In realtà puoi fare anche senza. Dividi come al solito in mod 16 e mod 625. In mod 625 hai che 3^500=1 mod 625. In mod 16 hai che 3^4=81=1 mod 16. Quindi hai che (3^4)^125=3^500=1 mod 16. Per il teorema cinese del resto se a=b mod x e a=b mod y allora a=b mod xy (con x e y coprimi). Quindi hai ottenuto, con solo conoscenze base, che 3^500=1 mod 10000. Questo trucco magari potrà esserti molto utile

[@franksaved3893]

@@bassigiuseppe Chiaro, grazie. Interessante usare il teorema cinese del resto. Cercherò in rete l'ordine moltiplicativo universale.

[@MatteoP04ita]

Ciao Giuseppe, ho trovato un problema simile a questo e mi chiedevo se a prima vista lo avesti svolto con l'interpolazione di Lagrange o altri metodi. Sia f un polinomio di grado 1007 tale che f(k) = 2^k per k = 0,1,...,1007. Determinare f(2015). Lo stavo facendo passo passo con il video ma mi sono accorto che essendo 1007 e 2015 molto distanti bisogna procedere diversamente in alcuni punti.

[@bassigiuseppe]

Il problema di cui parli è analogo ma un po' più facile, ovvero richiederà meno passaggi la manipolazione della sommatoria (perché non c'è n davanti all'esponenziale). Si può risolvere allo stesso modo, oppure si può risolvere con il metodo delle differenze finite, dovrebbe uscire abbastanza bene. Il fatto che richieda f(2015) al posto di f(1008) non è un problema, nel senso che non cambia nulla. Scrivi il polinomio come interpolazione e poi cambierà un po' la sommatoria da risolvere

[@antosorre4652]

Ciao, volevo chiederti come sei arrivato a 3^1000 congruo a 1

[@bassigiuseppe]

Ciao! Quello che ho utilizzato è una variante più avanzata del teorema di Eulero. Il teorema di Eulero afferma che 3^4000=1 mod 10000. Tuttavia, esiste anche il concetto di ordine moltiplicativo universale, che migliora molto il Teorema di Eulero. In questo caso ci dice addirittura che a^500=1 mod 10000 (con a coprimo con 10000), quindi a maggior ragione 3^1000=9^500=1 mod 10000. È un passaggio tecnico che non ho voluto trattare nel video perché non era quello l’obiettivo, tuttavia effettivamente non è banale e riguarda teoremi abbastanza complessi di teoria dei numeri. Non a caso il problema era stellato e non era stato risolto da nessuna squadra

[@MatteoRocca_]

Ciao! Volevo chiederti una cosa: oltre i tuoi video, quali libri/materiali potrei usare per migliorare ed esercitarmi nella matematica delle olimpiadi?

[@bassigiuseppe]

Premetto che io mi occupo solo di matematica olimpica e al più scolastica, non universitaria, di cui non ne so abbastanza. Detto ciò, si dà il caso che di materiale gratis su internet ce ne sia tantissimo, solo un po' nascosto. Tutto dipende però dal livello, più il livello è alto e più si trova materiale in inglese di alta qualità. Qui riporterò il materiale di livello accessibile a tutti, mentre se ti serve qualcosa di più avanzato fammi sapere. Il materiale che citerò si trova molto facilmente in pdf su internet: - Dispense di Matematica Olimpionica - Schede Olimpiche (Gobbino) - La gara di febbraio (Pruneri Fabio) - Analisi Combinatoria (Ercole Suppa) In più c'è anche questo: - Umath: collana di libri di matematica olimpica (questi però non si trovano in pdf e vanno acquistati) - www.problemisvolti.it/Olimpiadi.html corso di Emanuele Callegari - matteosalicandro.altervista.org/ sito di Matteo Salicandro, con vecchie gare e vecchi stage - olimpiadi.dm.unibo.it/ sito ufficiale delle olimpiadi, per esercitarsi con vecchie edizioni Se poi spulci nei miei video più vecchi troverai anche qualche altra fonte che ho consigliato ad altri che mi hanno posto in passato la stessa domanda.

[@MatteoRocca_]

@@bassigiuseppe grazie mille, davvero gentilissimo! Comunque l’obiettivo (non so se raggiungibile per me) sarebbe la finale a Cesenatico il prossimo anno. Grazie mille ancora!

[@MatteoRocca_]

@@bassigiuseppe Ciao, sono ancora io, ti chiedo un’altra cosa sperando di non disturbarti, secondo te per quanto riguarda il materiale, è meglio consultarlo in un ordine "preciso" o semplicemente guardando quello che posso ritenere più utile?

[@bassigiuseppe]

@@MatteoRocca_ Non c’è proprio un ordine preciso. Ti consiglio di dare un’occhiata a tutto e ti renderai conto facilmente di cosa è più adatto a te

[@FraTra_]

Ciao, provando a risolvere l'ultima parte ho incontato una leggera difficoltà nel capire il passaggio 2^(500+k)=2^k mod 10000. Perchè capure che 2^500=1 mod 652 e 2^500=0 mod 16 non è un problema, anzi ci ero anche arrivato da solo, il problema, e ciò che non capisco, è come si arrriva a 2^(500+k)=2^k mod 10000. Il discorso sul 3, invece l'ho ben chiaro, basta conoscere la teoria sull'ordine moltiplicativo universale. Grazie del chiarimento

[@bassigiuseppe]

2^(500+k)=2^k mod 10000 se e solo se lo è mod 625 e mod 16. Ovviamente è vero mod 16 se k>3 (come in questo caso), mentre è vero mod 625 sempre

[@FraTra_]

@@bassigiuseppe perfetto, grazie mille della risposta

[@bassigiuseppe]

@@FraTra_ figurati!