INTRO

TEORIA DEI NUMERI SUCCESSIONI

Liceo Scientifico “G. Salvemini” Corso di preparazione per la gara provinciale delle

OLIMPIADI DELLA MATEMATICA

NUMERI INTERI

QUESITO

Sulla lavagna c'e scritto un numero di 17 cifre composto da soli 1 e 2. Paolo entra e riscrive il numero in sequenza inversa, allineandolo sotto il precedente. Gianni entra e scrive sotto ogni colonna la cifra massima che compare in quella colonna. Alberto entra e scrive sotto ogni colonna la cifra minima che compare in quella colonna, poi cancella le prime due righe. Carla entra e trova scritti i numeri 12212212221221221 e 11211111211111211 e le viene spiegato che cosa hanno fatto Paolo, Gianni e Alberto. Quanti sono i diversi numeri che potevano essere scritti sulla lavagna come primo numero?

Un quesito (facile) sulle cifre:

SUGGERIMENTO

Consideriamo le righe che legge Carla:

Cifra minima

Cifra massima

Possiamo prevedere facilmente molte cifre dei numeri cancellati ..

SOLUZIONE

Dall’analisi delle ultime due righe ricaviamo:

Cifra minima

Cifra massima

Nelle posizioni residue abbiamo sempre un 1 e un 2. Ma scelta una cifra se ne determinano univocamente altre 3

1 1

2

2

Le posizioni sono 4 e il numero è dato dalle permutazioni di 2 cifre:

* * *

24 = 16

NOTAZIONE POSIZIONAE

Data una base x il numero ..bca in base x vale: ..bcabase x = a⋅x0 + b⋅x1 + c⋅x2 + ... = a + b⋅x + c⋅x2 + ...

Esempi: 723 base10 = 3 + 2⋅10 + 7⋅100 10110 base2 = 0 + 1⋅2 + 1⋅4 + 0⋅8 + 1⋅16 = 22base10

41320 base5 = 0 + 2⋅5 + 3⋅52 + 1⋅53 + 4⋅54 = = 5⋅(2 + 3⋅5 + 1⋅52 + 4⋅53)

Un numero in base x che termina con n zeri si può scrivere come xn⋅A

QUESITO

Sia x il numero di zeri con cui termina 2000! quando è scritto in base 5, e y il numero di zeri con cui termina 2013! quando è scritto in base 10. Calcolare x-y. (Ricordiamo che il numero n!, per n intero positivo, è il prodotto di tutti gli interi positivi minori o uguali a n.)

(A) -2 (B) 0 (C) 2013 (D) 13! (E) Nessuna delle precedenti.

SUGGERIMENTO

Il numero 2013! = 10y·p (con y = numero di zeri finali del numero). Il fattore p non contiene ulteriori fattori 5 e quindi vale anche 2013! = 5y·2y·p = 5y·n. Analogamente si ha che 2000! = 5x·m (con y = numero di zeri finali del numero quando è scritto in base 5) Adesso valutiamo

SOLUZIONE

Il numero 2013! = 10y·p (con y = numero di zeri finali del numero). Il fattore p non contiene ulteriori fattori 5 e quindi vale anche 2013! = 5y·2y·p = 5y·n. Analogamente si ha che 2000! = 5x·m (con y = numero di zeri finali del numero quando è scritto in base 5) Adesso valutiamo

Visto che non contiene fattori 5 il rapporto

contiene un numero di fattori 5 contenuti nel prodotto

2001·2002·..·2013.

E' facile verificare che essi sono solo 2 (fattori di 2005 e

2010). Quindi y - x = 2. (Risposta A)

DIVISIONE

Dati due numeri interi a , b con a ≥ b è sempre possibile trovare altri 2 numeri interi q ed r tali che:

a = bq + r

Quoziente della divisione tra a e b Resto della divisione tra a e b

a div b = q

a mod b = r

DIVISIBILITA’ Si dice che a divide b, o che a è divisore di b, o che b è multiplo di a (in simboli a|b) se effettuando la divisione con resto di b per a si ottiene che r = 0. Più esplicitamente a|b se esiste un intero q tale che b = aq. Notare che tra i divisori di un numero b sono sempre presenti 1 e b stesso e che tutti i numeri dividono lo 0. Com’è facile verificare, la caratteristica di “essere multipli” si preserva con le combinazioni lineari: in altre parole se a,b sono multipli di d allora ha+kb è anche multiplo di d per qualsiasi scelta di h,k interi.

NUMERI PRIMI

Si dice inoltre che p è un numero primo se ogni qualvolta divide un prodotto divide anche almeno uno dei fattori, cioè Questa definizione è equivalente a quella più nota, secondo cui un numero è primo se non ha divisori all’infuori di 1 e se stesso. Notare che 1 non è considerato un numero primo.

QUESITO

Determinare il più grande numero di due cifre tale che: a) sia un numero primo; b) scambiando di posto le due cifre resti un numero primo; c) il prodotto delle due cifre sia un numero primo.

SUGGERIMENTO

Per la condizione c) il prodotto delle due cifre deve essere un numero primo. Perchè questo avvenga è necessario che una delle due cifre sia 1, altrimenti il numero che ne deriva moltiplicando è composto.

SOLUZIONE

Supponendo che 1 sia la cifra delle decine, la condizione a) restringe le possibilità ai soli 11, 13, 17, 19, unici numeri primi tra 10 e 19 compresi. Scambiando l’ordine delle cifre 11, 31, 71 sono primi mentre 91 = 13×7. Di conseguenza il più grande numero che soddisfa le tre condizioni a), b), c) è 71.

NUMERI PRIMI

I numeri primi hanno un ruolo particolare nella teoria dei numeri, soprattutto poiché ogni intero è scrivibile in modo unico come prodotto di potenze di numeri pi primi distinti:

Verificare se un numero a è primo o meno è un problema complesso, tuttavia sono note alcune strategie per farlo. Una prima strategia (utile anche per trovare la fattorizzazione di un numero non primo) consiste nel dividere il numero a per tutti i primi noti in ordine crescente, fino ad arrivare a . A quel punto, se nessuno dei primi che abbiamo provato era un divisore esatto di a, allora a è certamente primo

a

FATTORIZZAZIONE DI UN NUMERO

Sia n un numero naturale. L'insieme degli eventuali fattori primi di n è formato da tutti i numeri primi che dividono n e che sono ≤ . Se n non possiede divisori primi < è un numero primo.

n

n

In sintesi:

FATTORIZZAZIONE DI UN NUMERO

Per scomporre un numero provare a dividere per i principali numeri primi (o suoi multipli). Principali criteri di divisibilità:

per 2 un numero è divisibile per 2 se termina con zero o una cifra pari per 3 un numero è divisibile per 3 se la somma delle sue cifre è 3 o un multiplo di 3 per 4 un numero è divisibile per 4 se le ultime due cifre sono 00 oppure formano un numero multiplo di 4

FATTORIZZAZIONE DI UN NUMERO

per 5 un numero è divisibile per 5 se la sua ultima cifra è 0 o 5 per 6 un numero è divisibile per 6 se è contemporaneamente divisibile per 2 e per 3 per 7 un numero con più di due cifre è divisibile per 7 se la differenza del numero ottenuto escludendo la cifra delle unità e il doppio della cifra delle unità è 0, 7 o un multiplo di 7. » per es. 95676 è divisibile per 7 se lo è il numero 9567-2*6=9555; questo è divisibile per 7 se lo è il numero 955-2*5=945; questo è divisibile per 7 se lo è 94-2*5=84 che è divisibile per 7 dunque lo è anche il numero 95676. per 8 un numero è divisibile per 8 se termina con tre zeri o se è divisibile per 8 il numero formato dalle sue ultime 3 cifre per 9 un numero è divisibile per 9 se la somma delle sue cifre è 9 o un multiplo di 9 per 10 un numero è divisibile per 10 se la sua ultima cifra è 0

FATTORIZZAZIONE DI UN NUMERO

per 11 un numero è divisibile per 11 se la differenza (presa in valore assoluto), fra la somma delle cifre di posto pari e la somma delle cifre di posto dispari, è 0, 11 o un multiplo di 11 » per es. 625834 è divisibile per 11 in quanto (2+8+4)-(6+5+3)=14-14=0 per 12 un numero è divisibile per 12 se è contemporaneamente divisibile per 3 e per 4 per 13 un numero con più di due cifre è divisibile per 13 se la somma del quadruplo della cifra delle unità con il numero formato dalle rimanenti cifre è 0, 13 o un multiplo di 13 » per es. 7306 è divisibile per 13 se lo è il numero 730+4*6=754; questo è divisibile per 13 in quanto 75+4*4=91 è multiplo di 13 (13*7=91) per 17 un numero con più di due cifre è divisibile per 17 se la differenza (presa in valore assoluto), fra il numero ottenuto eliminando la cifra delle unità e il quintuplo della cifra delle unità è 0, 17 o un multiplo di 17 » per es. 2584 è divisibile per 17 se lo è il numero 258-5*4=238; questo è divisibile per 17 se lo è il numero 23-5*8=17 per 25 un numero è divisibile per 25 se il numero formato dalle ultime 2 cifre è divisibile per 25, cioè 00, 25, 50, 75 per 100 un numero è divisibile per 100 se le ultime due cifre sono 00

QUESITO

Un numero si dice “moderno” se, in base 10, può essere espresso concatenando “un pò” di scritture decimali di 2006: ad esempio 200620062006 è moderno, mentre 20200606 e 2006200 non lo sono. Quante cifre ha il più piccolo quadrato perfetto moderno positivo? (A) 32 (B) 64 (C) 100 (D) 1000 (E) non esiste un tale numero.

SUGGERIMENTO

Un numero moderno è sempre divisibile per 2006, e quindi si può scrivere come 2006 (1000100010001…..10001) = 21003(1000100010001…..10001). Il terzo fattore è dispari ..

SOLUZIONE

Un numero moderno è sempre divisibile per 2006, e quindi si può scrivere come 2006 (1000100010001…..10001) = 21003(1000100010001…..10001). Il terzo fattore è dispari e quindi un numero moderno, che è sicuramente pari, non può avere come divisore 4. Pertanto un numero moderno non può essere un quadrato perfetto (E).

QUESITO

Un folletto vive nel mondo delle fate. Un certo giorno sceglie 12 coppie di numeri positivi: quelli della prima sono dispari, quelli della seconda danno resto 1 se divisi per 3, quelli della terza danno resto 1 se divisi per 4, e così via fino alla dodicesima. Poi calcola la differenza dei quadrati dei numeri di ciascuna coppia e scrive su una lavagna il prodotto di tutte le differenze ottenute. Dalla mattina successiva, divide per 12 il numero sulla lavagna e, se il risultato è intero, scrive questo risultato al posto del numero che era sulla lavagna; se non è intero, cancella tutto e si trasferisce nel mondo degli umani a fare scherzetti. Per quanti giorni (escluso quello iniziale in cui il folletto sceglie i numeri) siamo sicuri che non avremo problemi nel nostro mondo? (A) 4 (B) 5 (C) 6 (D) 8 (E) 12.

SUGGERIMENTO 1

I due numeri dispari danno resto 1 se divisi per 2

Se k-1 è la fila (per 2 k 13) la coppia si può scrivere:

(a , b) = (nk+1 , mk+1)

La differenza dei quadrati vale:

a2 – b2 = (a - b)(a + b) = = (nk-mk)(nk+mk+2) = (n-m)k(nk+mk+2)

Di conseguenza il prodotto scritto dal folletto sulla lavagna è sicuramente divisibile per ..

SUGGERIMENTO 2

Di conseguenza il prodotto scritto dal folletto sulla lavagna è

sicuramente divisibile per 13!. Scomponiamo 13! =

2345678910111213 = 210·35·52·7·11·13.

Quindi il prodotto è sicuramente divisibile per ..

SOLUZIONE

Quindi il prodotto è sicuramente divisibile per 125.

Quindi sicuramente il folletto potrà dividere per 12 almeno per 5 giorni di fila trovando sempre un risultato intero.

Ma se il folletto scegliesse ad esempio le coppie (2k+1, k+1) per k = 4,7,10,13 e le coppie (k+1, 1) per i k restanti, le differenze dei quadrati (rispettivamente 3k2 + 2k e k2 + 2k = k(k + 2)) conterrebbero in tutto esattamente 5 fattori 3, perciò il loro prodotto risulterebbe divisibile per 12 non più di 5 volte. Ma allora in quel caso il sesto giorno la divisione produrrebbe un numero non intero; quindi possiamo contare su 5 giorni, ma non di più. (B)

QUESITO

Quattro interi positivi a1 < a2 < a3 < a4 sono tali che, dati due qualunque di essi, il loro massimo comun divisore è maggiore di 1, ma mcd(a1, a2, a3, a4) = 1. Qual è il minimo valore che può assumere a4? (A) 10 (B) 12 (C) 15 (D) 30 (E) 105.

SUGGERIMENTO

Ovviamente esiste almeno un valore ak dispari. Infatti se fossero tutti pari non avrebbero MCD = 1

Prova che almeno uno dei 4 numeri ha 2 fattori primi distinti. Se, per assurdo, tutti e quattro avessero un solo fattore primo ..

SOLUZIONE

Ovviamente esiste almeno un valore ak dispari. Infatti se fossero tutti pari non avrebbero MCD = 1

Proviamo che almeno uno dei 4 numeri ha 2 fattori primi distinti. Se, per assurdo, tutti e quattro avessero un solo fattore primo (ak = ps) l’ipotesi che il MCD di due dei numeri è>1 non potrebbe essere soddisfatta perché i due numeri dovrebbero avere un fattore in comune.

Quindi c’è almeno un numero ak che ha almeno due fattori primi diversi da due, e quindi vale almeno 35 = 15. D’altra parte, si verifica che la quaterna 6, 10, 12, 15 soddisfa tutte le ipotesi del problema, quindi 15 è veramente il minimo che cerchiamo.

INSIEME DELLE PARTI

QUESITO

Caboyara, famoso circense australiano, si esibisce anche quest'anno in un gran trucco. Predispone una scala spettacolare con N = p1·p2·...·p2015 gradini, dove p1,p2,....,p2015 sono numeri primi distinti; i gradini che corrispondono a divisori di N (compresi il primo e l'N-esimo gradino) sono speciali e sono inizialmente illuminati di verde. Durante lo spettacolo, 2015 canguri ammaestrati salgono uno dopo l'altro la scala; per i = 1,2,......,2015, l'i-esimo canguro salta pi gradini alla volta, partendo ai piedi della scala (salta sul gradino pi, poi sul 2pi, e così via finché non raggiunge il gradino N). Ogni volta che un canguro salta su un gradino speciale, questo cambia colore: da verde diventa rosso, da rosso verde. Quanti saranno i gradini speciali illuminati di verde alla fine dell'esibizione? (A) 22015 - 21008 (B) 22014 (C) 22014 - 21007 (D) 22013 (E) 2015·21008

SUGGERIMENTO 1

Se d è un divisore di N esso è il prodotto di k tra i divisori primi di N: { p1,p2,....,p2015 }. L'i-esimo canguro passerà sul gradino speciale posto nella posizione d se pi è uno dei k divisori. Se k è pari segue che .. , se k è dispari segue che ..

SOLUZIONE 1

Se d è un divisore di N esso è il prodotto di k tra i divisori primi di N: { p1,p2,....,p2015 }. L'i-esimo canguro passerà sul gradino speciale posto nella posizione d se pi è uno dei k divisori. La luce cambierà quindi colore tante volte quanti sono i fattori primi di d: se k è pari sarà verde , se k è dispari sarà rossa.

SUGGERIMENTO 2

Supponiamo che k sia pari, essendo 2015 dispari, esiste un divisore d' formato da 2015-k fattori (dispari) .. Analogamente se k è dispari .. Quindi il numero dei k pari è ..

SOLUZIONE 2

Supponiamo che k sia pari, essendo 2015 dispari, esiste un divisore d' formato da 2015-k fattori (dispari). Analogamente se k è dispari siste un divisore d' formato da 2015-k fattori (pari). Quindi per ogni possibile combinazione pari di fattori ne corrisponde una dispari e viceversa. Segue che il numero delle combinazioni pari (che ricordiamo lascia il gradino speciale di colore verde) è uguale a quello delle combinazioni dispari ed entrambi sono uguali alla metà del numero dei sottoinsiemi di {p1,p2,....,p2015} = (Risposta B)

SUCCESSIONI

SUCCESSIONI

Una successione è una sequenza ordinata di numeri appartenenti ad un insieme assegnato: ad esempio, si possono avere successioni di numeri interi, razionali, reali, complessi. Il primo elemento della sequenza viene, convenzionalmente, chiamato a0 , il secondo a1 e così via discorrendo:

a0 , a1 , …. , an , …

SUCCESSIONI I modi in cui vengono di norma descritte le successioni sono due:

1. con una legge: ciascun termine an è assegnato mediante una funzione che, in generale, dipende da n. Ad esempio, an= 2n+1, n N è la successione dei numeri dispari;

2. ricorsivamente: ciascun termine an è assegnato mediante una funzione ricorsiva che, in generale, dipende dai termini precedenti an-1,an-2,..,a1,a0. Ad esempio, la successione definita da è la celeberrima successione di Fibonacci

1, 1, 2, 3, 5, 8, 13, . . .

SUCCESSIONI I modi in cui vengono di norma descritte le successioni sono due:

1. con una legge: ciascun termine an è assegnato mediante una funzione che, in generale, dipende da n. Ad esempio, an= 2n+1, n N è la successione dei numeri dispari;

2. ricorsivamente: ciascun termine an è assegnato mediante una funzione ricorsiva che, in generale, dipende dai termini precedenti an-1,an-2,..,a1,a0. Ad esempio, la successione definita da è la celeberrima successione di Fibonacci

1, 1, 2, 3, 5, 8, 13, . . .

PROGRESSIONI ARITMETICHE Una successione di numeri a0 , a1 , …. , an , … si dice progressione aritmetica se è definita ricorsivamente nel seguente modo:

Cioè se la differenza tra due termini consecutivi è costante ed uguale alla ragione d della progressione. Sulle progressioni aritmetiche si possono dimostrare facilmente le seguenti formule:

Il generico termine ar si può esprimere come

La somma dei termini da ar a as è:

PROGRESSIONI GEOMETRICHE Una successione di numeri a0 , a1 , …. , an , … si dice progressione geometrica se è definita ricorsivamente nel seguente modo:

Cioè se il rapporto tra due termini consecutivi è costante ed uguale alla ragione k della progressione.

Il generico termine ar si può esprimere come

La somma dei termini da ar a as è:

Il prodotto dei termini da ar a as è:

QUESITO

Una sequenza a1 .... a100 di numeri reali è tale che la media aritmetica fra due termini consecutivi sia sempre uguale all'indice del secondo termine (ad esempio, si ha ). Quanto vale la somma dei 100 numeri della sequenza? (A) 2550 (B) 5050 (C) 5100 (D) 10100 (E) Non si può determinare: dipende da a1

SUGGERIMENTO

La somma richiesta è

SOLUZIONE

La somma richiesta è = 2·(2 + 4 + 6 + .. + 98 + 100) = 4·(1 + 2 + .. + 49 + 50). La somma dei primi n numeri naturali è:

segue che = 5100 (Risposta C)

QUESITO DIMOSTRATIVO

Determinare tutte le terne di interi strettamente positivi (a,b,c) tali che - a b c ; - MCD(a , b , c) = 1; - a è divisore di b+c, b è divisore di c+a e c è divisore di a+b.

SOLUZIONE

Cominciamo a dimostrare che i 3 numeri sono a due a due coprimi:

Infatti sia d = MCD(a,b) d/a d/b+c Ma d/b quindi d/b+c-b d/c Dunque d è il MCD di tutti e tre che per ipotesi è 1 Analogamente si dimostra per le altre coppie

Adesso dimostra che ogni numero divide a+b+c ..

Infatti a/b+c a/(b+c)+a e così via per gli altri.

SOLUZIONE

Visto che abc/(a+b+c) abc a+b+c

è un divisore di a+b+c

Ma essendo a b c abc a+b+c 3c

ab 3

Ma i numeri sono a due a due coprimi quindi il prodotto abc ..

SOLUZIONE

Abbiamo due terne possibili:

CASO 1 a = 1 e b = 1

Abbiamo ottenuto la condizione ab 3, ma sappiamo anche che c a + b quindi le terne non saranno molte:

(1,1,1) (1,1,2)

Entrambe soddisfano le condizioni richieste

SOLUZIONE

L’unica terna possibile è:

CASO 2 a = 1 e b = 2

che soddisfa le condizioni richieste

(1,2,3)

L’unica terna possibile è:

CASO 3 a = 1 e b = 3

che NON soddisfa le condizioni richieste

(1,3,4)

GRIGLIA DI VALUTAZIONE

Elencare le soluzioni: 1 punto. Affermare che i numeri sono a due a due coprimi: 2 punti. Dimostrare la precedente asserzione: 2 punti. Dedurre che allora abc divide a + b + c: 4 punti. A chi deduce (erroneamente) la divisibilità dalla sola informazione MCD(a,b,c) = 1 assegnare comunque 2 punti. Passare dall'informazione di divisibilità (abc divide a+b+c) alla disuguaglianza abc a+b+c: 2 punti. Dedurne la disuguaglianza abc 3c: 2 punti. Elencare correttamente i casi possibili e trattarli: 2 punti.

TOT = 15 PUNTI

2016

= 25·32·7

= 1+2+..+63