SCUOLA GALILEIANA DI STUDI SUPERIORI — CLASSE DI SCIENZE NATURALI ESAME DI AMMISSIONE, PROVA DI MATEMATICA — 13 SETTEMBRE 2011
Problema 1. Sia Z l’insieme dei numeri interi.
a) Sia F 100 l’insieme delle funzioni f : Z −→ Z tali che
f (f (n)) = n + 100, per ogni n ∈ Z.
L’insieme F 100 ` e vuoto? Oppure non ` e vuoto e ha un numero finito di elementi? Oppure ` e infinito?
b) Sia F 101 l’insieme delle funzioni g : Z −→ Z tali che
g(g(n)) = n + 101, per ogni n ∈ Z.
L’insieme F 101 ` e vuoto? Oppure non ` e vuoto e ha un numero finito di elementi? Oppure ` e infinito?
Soluzione — Traccia risoluzione: nel caso pari, ci sono infinite funzioni. Basta pensare per esempio a una funzione che manda un n dispari in n + 9 e un n pari in n + 91. Al posto di 9 e 91 si possono mettere x e (100 − x) con x un qualunque intero dispari.
Invece nel caso dispari non c’` e nessuna funzione con la caratteristica richiesta. Infatti applicando la g ai due membri di g(g(n)) = n + 101
si ottiene
g(g(g(n))) = g(n + 101) A sinistra abbiamo
g(g(g(n))) = g
2(g(n)) = g(n) + 101 quindi
g(n) + 101 = g(n + 101) Da questa si ricava subito che, per ogni k,
g(n) + 101k = g(n + 101k) (0.1)
Questa equazione dice che il resto di g(n) modulo 101 dipende solo dal resto di n modulo 101. Dalla g ricaviamo dunque una funzione h che va dall’insieme dei resti modulo 101 in s` e. Questa h soddisfa h
2=Identit` a. Siccome l’insieme dei resti ha un numero dispari di elementi, una involuzione deve avere un punto fisso. Tradotto in termini della g questo vuol dire che deve esistere un numero a tale che
g(a) = a + 101s (0.2)
per un certo intero s. Ma allora
a + 101 = g(g(a)) = g(a + 101s) = g(a) + 101s
in cui nell’ultima uguaglianza abbiamo usato la (0.1). Applichiamo ancora la (0.2) e otteniamo
a + 101 = g(g(a)) = g(a + 101s) = g(a) + 101s = a + 101 · 2s
da cui 2s = 1, assurdo.
Problema 2. Consideriamo nel piano cartesiano l’insieme Z × Z dei punti a coordinate intere. Diremo che un punto P a coordinate intere ` e ‘visibile’ dall’origine O se il segmento OP non contiene altri punti di Z × Z diversi da O e da P .
a) Quali sono i punti visibili?
b) Dimostrare che per ogni intero positivo n ` e possibile trovare nel piano un segmento di lunghezza n, con estremi a coordinate intere positive, che non contiene alcun punto visibile.
c) Dimostrare che per ogni intero positivo n ` e possibile trovare nel piano un quadrato di lato n che non contiene alcun punto visibile.
Soluzione — I punti visibili sono tutti e soli quelli con coordinate (a, b) con a, b primi tra loro. Che un punto con coordinate non prime fra loro non sia visibile si vede subito. Invece, sia (a, b) con a, b primi tra loro e dimostriamo che ` e visibile. Se non lo fosse, ci sarebbe un punto a coordinate intere (c, d) tale che r(a, b) = (c, d) con 0 < r < 1 e r razionale. Allora r = p/q con p < q. Dunque p(a, b) = q(c, d) cio` e (pa, pb) = (qc, qd). Allora M CD(pa, pb) = M CD(qc, qd), che si pu` o riscrivere come pM CD(a, b) = qM CD(c, d) e ancora come M CD(a, b) = q/pM CD(c, d). Visto che q/p > 1 allora M CD(a, b) > 1 assurdo.
Per trovare il quadrato, si cercano due interi a, b tali che a, a + 1, a + 2, . . . a + r, b, b + 1, b + 2, . . . , b + r soddisfino M CD(a + i, b + j) > 1. Per questo essenzialmente si scelgono (r + 1)
2primi distinti p
ij(i, j compresi fra 0 e r) e si risolvono i sistemi cinesi a ≡ −i mod p
ije b ≡ −j mod p
ij. A quel punto a + i e b + j non sono coprimi.
Per la variante facilitata del segmento non occorrono ragionamenti tipo ‘teorema cinese’, basta prendere una lista di n + 1 interi positivi consecutivi a + 0, a + 1, a + 2, . . . , a + n e scegliere per ogni i un numero primo p
idalla fattorizzazione del numero a + i. A quel punto basta prendere b = p
0p
1p
2· · · p
ne il segmento di estremi (a, b) e (a + n, b) funziona (ovviamente ` e possibile
‘economizzare’ facendo coincidere, quando possibile, i p
i).
Problema 3. Siano a, b, c tre numeri reali strettamente positivi. Supponiamo che, per ogni intero positivo n, esista un triangolo T n i cui lati hanno lunghezza a n , b n , c n . Dimostrare che ogni triangolo T n ` e isoscele.
Soluzione — Si pu` o assumere a ≥ b ≥ c. Allora i numeri a
n, b
n, c
n. sono lunghezze dei lati di un triangolo se e solo se a
n< b
n+ c
n.
Vista la scelta a ≥ b ≥ c ricaviamo
a
n< b
n+ c
n≤ 2b
n. Facendo la radice n-esima otteniamo
a < √
n2 b da cui, riassumendo le condizioni che abbiamo su b,
a
√
n2 < b ≤ a Visto che √
n2 → 1 per n → +∞ concludiamo che deve essere a = b.
Problema 4. Dato un numero reale α > 0, definiamo
a 1 = α + 1
2 , a 2 = 1 2
a 1 + α
a 1
, a 3 = 1 2
a 2 + α
a 2
, . . . .
Dimostrare che se α < 104 applicando 11 volte il procedimento sopra descritto si riesce a calcolare la √
α fino alla seconda cifra decimale.
Soluzione. S`ı, Maria vincer` a la scommessa. Infatti, la successione (a
n) verifica le condizioni a
0= α, a
n+1=
an2a2+αn
per ogni n ∈ N. Sia allora δ
n= a
n− √
α. Si ha δ
n+1= a
n+1− √
α = a
n2 + α 2a
n− √
α = (a
n− √ α)2 2a
n= δ
n2 2(δ
n+ √
α) = δ
n2 · δ
nδ
n+ √ α . In particolare δ
0= α − √
α ≤ α e 0 ≤ δ
n+1≤
δ2n, e da ci` o si deduce facilmente per induzione che 0 ≤ δ
n≤ 2
−nα per ogni n ∈ N. ` E dunque chiaro che la successione descritta da Maria tende a stabilizzarsi intorno al valore di √
α. Supponiamo ora α ≤ 104. Si ha allora √
α ≤ 102 < 128 = 2
7, per cui δ
7≤ 2
−7α ≤
√αα= √
α. Osserviamo ora che se δ
k≤ 2
−p√
α, allora δ
k+1≤
δ2k·
δ δkk+√
α
≤ (2
−p−1√ α) ·
2−p√α
√α
= 2
−2p−1√
α. Poich´ e δ
7≤ 2
−0√
α, si ottiene allora δ
8≤ 2
−1√
α, δ
9≤ 2
−3√ α, δ
10≤ 2
−7√
α, e δ
11≤ 2
−15√
α. Poich´ e √
α ≤ 100 < 2
7si ha dunque δ
11≤ 2
−8. Poich´ e 2
−8= 1/256 < 0.005, se ne deduce che l’approssimazione δ
11` e minore di 5 · 10
−3, per cui a
11e √
α coincidono fino alla seconda cifra decimale.
Problema 5. Mostrare che ogni insieme di numeri interi contenente 5 elementi contiene almeno 3 elementi la cui somma ` e un multiplo di 3.
Soluzione. L’insieme Z degli interi `e l’unione di tre sottoinsiemi disgiunti [0] = {n : n ` e divisibile per 3}, [1] = {n : n − 1 ` e divisibile per 3}, [0] = {n : n − 2 ` e divisibile per 3}.
Osserviamo preliminarmente che:
(1) se l, m, n appartengo allo stesso insieme [a], con a = 0, 1, 2, allora l + m + n ` e divisibile per 3;
(2) se l ∈ [0], m ∈ [1] e n ∈ [2], allora l + m + n ` e divisibile per 3.
Ci sono due possibilit` a: (i) esiste un a ∈ {0, 1, 2} per cui [a] contiene tre elementi di Σ e (ii) per ogni a ∈ {0, 1, 2} ci sono al massimo due elementi di Σ, che appartengono a [a].
Nel caso (i) il risultato segue da (1).
Nel caso (ii) il risultato segue da (2).
Problema 6. Consideriamo un orologio a lancette classico, per cui assumiamo che la posizione della lancetta delle ore e di quella dei minuti siano individuate da una coppia h ed m di numeri reali tali che 0 6 h < 12, 0 6 m < 12.
a) Trovare una relazione tra h e m.
Per errore in un orologio vengono montate la lancetta delle ore e quella dei minuti di uguale lunghezza, cos`ı che non
` e possibile stabilire quale delle due segni l’ora e quale i minuti. Considerato che un essere umano non commette un errore di valutazione dell’ora superiore alle 6 ore, si chiede:
b) quali e quante sono le posizioni delle lancette in cui ` e impossibile determinare l’ora?
c) Per le posizioni di cui al punto precedente determinare l’errore massimo (in ore, minuti e secondi) che una persona pu` o commettere leggendo l’orologio.
Soluzione — a) La parte frazionaria di h ` e la frazione di 60 minuti tra un’ora e un’altra. Se m ∈ [0, 12] ` e la lancetta dei minuti allora
{h} = m
12 , ⇐⇒ m = 12{h}.
b) Chiamiamo x e y le posizioni delle due lancette. Abbiamo
x = ora, y = minuti, =⇒ x = 12{y}, y = ora, x = minuti, =⇒ y = 12{x}
Nel caso in cui x = 12{y} e y = 12{x}, cio` e nelle intersezioni tra le rette ` e impossibile stabilire l’ora, a meno che x = y. Queste
2 4 6 8 10 12
2 4 6 8 10 12
configurazioni sono in totale 143 − 11 = 132.
c) Immediatamente si vede che le coppie (x, y) per cui ` e impossibile stabilire l’ora giacciono sulle rette y = x + k 12
13 , k = ±1, ±2, . . . , ±11.
Siccome poi |y − x| 6 6, abbiamo
2 4 6 8 10 12
2 4 6 8 10 12