Scuola Normale Superiore, ammissione al corso ordinario

Prova scritta di Matematica per Fisica, Informatica, Matematica

26 Agosto 2010

Esercizio 1. Dato un parallelepipedo rettangolo P , sia L la minima lun-ghezza di un cammino sulla superficie di P che congiunge due vertici oppo-sti (ossia, che non stanno su una stessa faccia). Tra tutti i parallelepipedirettangoli P di volume unitario, si trovi il valore minimo possibile di L.

Esercizio 2. Consideriamo un quadrilatero con lati di lunghezza a, b, c e d,inscritto in un semicerchio di diametro d, come nell’illustrazione qui sotto:

Esercizio 1. Consideriamo un quadrilatero con lati di lunghezza a, b, c ed, inscritto in un semicerchio di diametro d, come nell’illustrazione qui sotto:

AD

BC

a

b

c

d

Dimostrate che vale la relazione

d3 ! (a2 + b2 + c2)d! 2abc = 0 .

Esercizio 2. Dimostrate che se a, b e c sono interi positivi tali che abc = a+b+c,allora a, b e c sono 1, 2 e 3 (in qualche ordine).

Esercizio 3. Sia ABCD un quadrilatero iscritto in una circonferenza, che nonabbia lati paralleli. Siano E ed F i punti d’intersezione delle rette AD and BC.Dimostrate che le bisettrici degli angoli !DEC e !AFD che intersecano i segmentiDC e BC rispettivamente sono tra loro ortogonali.

D

A

B

C

E

F

1

Si dimostri che vale la relazione

d3 − (a2 + b2 + c2)d− 2abc = 0 .

Esercizio 3. Su una sbarra lunga L cm si muovono N formiche (puntiformi)alla velocita di 1cm/s, partendo da N punti distinti. Ogni formica, raggiuntauna delle estremita della sbarra, cade. Se due formiche si incontrano in unpunto, istantaneamente invertono il loro senso di marcia, continuando amuoversi alla stessa velocita.(a) Quanti secondi, al massimo, possono trascorrere prima che tutte le

formiche siano cadute?(b) Quante inversioni di marcia, al massimo, puo fare una formica?

Esercizio 4. Una pulce si trova su un vertice di un pentagono. Ogni secondola pulce salta, con probabilita 1/2 in senso orario e probabilita 1/2 in sensoantiorario, raggiungendo istantaneamente uno dei due vertici adiacenti. In-dichiamo con Pn la probabilita che, dopo n secondi, la pulce abbia visitatoalmeno una volta tutti i vertici del pentagono. Si mostri, giustificando larisposta, che P28 > 1/2.

(continua sul retro)

1

2

Esercizio 5. Nel pianeta di Abbab l’alfabeto consiste delle sole lettere A eB. Le frasi si scrivono senza spazi tra le parole e ogni sequenza di lettere haun significato preciso. I postini del pianeta si rifiutano pero di consegnaremessaggi che contengano due A consecutive. Percio gli abitanti di Abbabsono costretti ad usare metodi che trasformino il messaggio che desideranospedire in uno che non contenga due A consecutive, che a sua volta possa es-sere ritrasformato nel messaggio originale dal destinatario (che e ovviamentea conoscenza del metodo di conversione usato dal mittente).(a) Si descriva un possibile metodo che risponda ai requisiti di cui sopra e

che trasformi ciascun messaggio originale di n lettere in un messaggioper il postino di al piu (5/3)n lettere.

(b) Un produttore di software sostiene di avere un programma molto effi-ciente sui testi lunghi: qualunque messaggio di n lettere, con n almenouguale a 100, viene trasformato in uno di al piu (6/5)n lettere. Sidimostri che il produttore non dice la verita.

[Puo essere conveniente utilizzare il fatto che il logaritmo in base 2 di1 +

√5 vale approssimativamente 1, 69]

Esercizio 6. Anita e Paolo stanno facendo un gioco. Anita muove sempreper prima. La mossa del giocatore di turno consiste nel passare un numerointero all’avversario. Tale numero puo essere ottenuto o sottraendo 1 oppuredimezzando (e arrotondando, se occorre, all’intero piu piccolo) il numeroricevuto. Per esempio, chi riceve 28 puo passare all’altro 27 oppure 14,mentre chi riceve 27 puo passare all’altro 26 oppure 13. Il giocatore chericeve il numero 0 vince.(a) Supponendo che ogni giocatore usi la strategia migliore, chi vince se si

parte da 13? e da 24?(b) Per ciascun intero positivo n, sia q(n) il numero di interi tra 1 and n

che, se usati come numero iniziale, sono vincenti per Paolo. Poniamop(n) def= q(n)/n. Come si comporta p(n) se n va all’infinito?

Scuola Normale Superiore, ammissione al corso ordinario

Prova scritta di Matematica per Fisica, Informatica, Matematica

26 Agosto 2010

Soluzioni dei problemi

Esercizio 1. Dato un parallelepipedo rettangolo P , sia L la minima lun-ghezza di un cammino sulla superficie di P che congiunge due vertici oppo-sti (ossia, che non stanno su una stessa faccia). Tra tutti i parallelepipedirettangoli P di volume unitario, si trovi il valore minimo possibile di L.

Soluzione esercizio 1. Detti a, b, c i lati, vale abc = 1. Possiamo supporre,permutando (a, b, c) se necessario, che a ≤ b ≤ c. Se sviluppiamo su un piano2 facce adiacenti di P , operazione che non altera la lunghezza di un camminolungo le facce, abbiamo che la lunghezza L di una connessione vale

√

(a+ b)2 + c2 o√

(b+ c)2 + a2 o√

(c+ a)2 + b2.

Sviluppando i quadrati dentro le radici, si vede subito che il valore minimodei tre e il primo, dunque

L =√

(a+ b)2 + c2 =

√

(a+ b)2 +1

(ab)2,

dove abbiamo anche usato la relazione abc = 1. Dobbiamo quindi minimiz-zare L, o equivalentemente

L2 = (a+ b)2 +1

(ab)2,

tra tutti i numeri (a, b) tali che a ≤ b ≤ 1/(ab). Essendo l’espressione da mi-nimizzare simmetrica rispetto a uno scambio di a e b, possiamo dimenticareil vincolo a ≤ b. Proviamo per un attimo a dimenticare anche il secondovincolo che a e b non superano 1/(ab); se la soluzione del problema sara taleche max{a, b} ≤ 1/(ab) avremo comunque trovato la soluzione del problemavincolato.

Per minimizzare L2 senza vincoli, osserviamo che la sostituzione (a, b) 7→(a′, b′) con a′ = b′ = (a+ b)/2 non cambia il primo quadrato e fa diminuire1/(ab)2, per la nota disuguaglianza tra disuguaglianza aritmetica e quellageometrica. Quindi la soluzione puo essere cercata tra le coppie tali chea = b. Ci siamo quindi ridotti al problema di minimizzare

4a2 +1

a4

tra tutti i numeri a > 0. Derivando si ottiene 8a = 4/a5, da cui ricaviamo

subito a = b = 6√

1/2 e quindi c =6√4. Dato che a < 1 e c > 1 il vincolo e

soddisfatto.

Soluzione che non usa il calcolo differenziale. Identica alla prece-dente fino al calcolo dell’espressione da minimizzare. Dalla disuguaglianza(a+ b)2 ≥ 4ab (caso elementare della disuguaglianza tra media aritmetica emedia geometrica), risulta

L2 ≥ 4ab+1

(ab)2,

1

2

e vale l’uguaglianza se e solo se a = b. Vediamo il lato destro della disu-guaglianza sopra come la somma dei tre numeri 2ab, 2ab, 1/(ab)2. Allora ladisuguaglianza tra media aritmetica e media geometrica implica nuovamente

4ab+1

(ab)2≥ 3 · 3

√

(2ab)(2ab)1

(ab)2= 3 · 3

√4,

e vale l’uguaglianza se e solo se 2ab = 1/(ab)2. Abbiamo quindi mostratoche per ogni scelta di a > 0 e b > 0 risulta

L2 ≥ 3 · 3√4

e che l’uguaglianza vale se e solo se a = b e 2ab = 1/(ab)2, ossia

a = b =16√2.

Dato che

a = b =16√2<

3√2 =

1

(ab)2,

il vincolo a ≤ b ≤ 1/(ab) e soddisfatto. Concludiamo che il parallelepipedorettangolo cercato e quello i cui lati hanno lunghezze

16√2,

16√2,

3√2,

e che il minimo di L vale√3 · 3

√2.

Esercizio 2. Consideriamo un quadrilatero con lati di lunghezza a, b, c e d,inscritto in un semicerchio di diametro d, come nell’illustrazione qui sotto:

Si dimostri che vale la relazione

d3 − (a2 + b2 + c2)d− 2abc = 0 .

Soluzione esercizio 2.

bA

b D

bB

bC

a

b

c

dm

α

β

Poniamo αdef

= DAB e βdef

= BCD. Dal momento che il quadrilateroABCD e inscritto in una circonferenza, gli angoli opposti sono supplemen-tari, e quindi

cos β = − cosα = −a

d.

3

Sia m la lunghezza del segmento BD. Dal teorema del coseno abbiamol’uguaglianza

m2 = b2 + c2 − 2bc cos β

= b2 + c2 +2abc

d.

D’altra parte l’angolo ABD e retto, per cui d2 = a2 +m2, e quindi

d2 − a2 = b2 + c2 +2abc

d.

Razionalizzando e raccogliendo otteniamo il risultato.

Esercizio 3. Su una sbarra lunga L cm si muovono N formiche (puntiformi)alla velocita di 1cm/s, partendo daN punti distinti. Ogni formica, raggiuntauna delle estremita della sbarra, cade. Se due formiche si incontrano in unpunto, istantaneamente invertono il loro senso di marcia, continuando amuoversi alla stessa velocita.

(a) Quanti secondi, al massimo, possono trascorrere prima che tutte leformiche siano cadute?

(b) Quante inversioni di marcia, al massimo, puo fare una formica?

Soluzione esercizio 3.

(a) Se indichiamo con T l’istante nel quale tutte le formiche saranno cadute,basta osservare che uno scambio di identita tra due formiche che si in-contrano non altera T . Quindi, per calcolare T , possiamo anche pensareche le formiche si “ignorino” l’una con l’altra proseguendo ognuna perla sua strada. Il valore massimo di T e quindi, se espresso in secondi,pari a L. Si ottiene quando una delle formiche parte da una estremitadella sbarra e tutte le formiche si muovono nello stesso verso.

(b) L’argomento dello scambio di identita qui non vale, perche la domandasi riferisce a una specifica formica. Immaginiamo pero che ogni formicadisponga di un “testimone” che passa all’altra formica in occasione diogni “scontro”. Allora e evidente che ogni testimone viaggia sempre nellostesso verso con la stessa velocita delle formiche, quindi non ritorna maialla stessa formica. Ne segue che ogni singola formica ha a disposizione alpiu (N −1) testimoni diversi dal proprio, di conseguenza che il massimonumero di “scontri” che la formica avra e (N−1). Si noti che l’argomentodei testimoni vale anche per la soluzione di (a).

Se N e pari e meta delle formiche di destra va verso sinistra mentre lameta di sinistra va verso destra, allora le due formiche centrali invertonola marcia esattamente (N − 1) volte. Se N = 2k+1 e le k formiche piua destra vanno a sinistra mentre le k piu a sinistra vanno a destra, sarala formica al centro a invertire la marcia 2k = N − 1 volte.

Esercizio 4. Una pulce si trova su un vertice di un pentagono. Ogni secondola pulce salta, con probabilita 1/2 in senso orario e probabilita 1/2 in sensoantiorario, raggiungendo istantaneamente uno dei due vertici adiacenti. In-dichiamo con Pn la probabilita che, dopo n secondi, la pulce abbia visitatoalmeno una volta tutti i vertici del pentagono. Si mostri, giustificando larisposta, che P28 > 1/2.

4

Soluzione esercizio 4. Evidentemente P4 = 2/24 = 1/8, corrispondente aidue percorsi che visitano il pentagono in tempo minimo (orario o antiorario).Quindi la probabilita di non visita dopo 4 secondi e 7/8. Dopo 4×2 secondi,la probabilita di non visita e certamente minore di (7/8)2, dato che dopo4 secondi si ripropone sostanzialmente, modulo un eventuale cambiamentodel vertice di partenza, la situazione iniziale e la pulce non ha memoria deisalti precedenti (visto che continua a saltare con probabilita 1/2 in un versoo nell’altro). Continuando in questo modo si ottiene che 1− P4n < (7/8)n,i.e. P4n > 1− (7/8)n. Posto n = 7, se riusciamo a verificare che

1− (7/8)7 >1

2

abbiamo concluso. La disuguaglianza e equivalente a (8/7)7 > 2, scrittanella forma (1 + a)n > 2 con n = 7 a a = 1/7 basta usare la disuguaglianzaelementare (1 + a)n > 1 + na per ottenere (8/7)7 > 1 + 7 · 1

7= 2.

Esercizio 5. Nel pianeta di Abbab l’alfabeto consiste delle sole lettere A eB. Le frasi si scrivono senza spazi tra le parole e ogni sequenza di lettere haun significato preciso. I postini del pianeta si rifiutano pero di consegnaremessaggi che contengano due A consecutive. Percio gli abitanti di Abbabsono costretti ad usare metodi che trasformino il messaggio che desideranospedire in uno che non contenga due A consecutive, che a sua volta possa es-sere ritrasformato nel messaggio originale dal destinatario (che e ovviamentea conoscenza del metodo di conversione usato dal mittente).

(a) Si descriva un possibile metodo che risponda ai requisiti di cui sopra eche trasformi ciascun messaggio originale di n lettere in un messaggioper il postino di al piu (5/3)n lettere.

(b) Un produttore di software sostiene di avere un programma molto effi-ciente sui testi lunghi: qualunque messaggio di n lettere, con n almenouguale a 100, viene trasformato in uno di al piu (6/5)n lettere. Sidimostri che il produttore non dice la verita.

[Puo essere conveniente utilizzare il fatto che il logaritmo in base 2 di

1 +√5 vale approssimativamente 1, 69]

Soluzione esercizio 5.

(a) Esistono vari metodi che allungano il messaggio al piu di un fattore 2 (adesempio l’interposizione una lettera su due di una B, o la sostituzione deigruppi AA, ABA, ABBA, . . . con ABA, ABBA, ABBBA, . . . rispettivamente). Unmetodo che ha un fattore di allungamento 5/3 sostituisce, se il numeron di lettere del messaggio e multiplo di 3, blocchi di 3 con blocchi di 5,con la prima lettera del blocco da 5 a fare da “barriera”, quindi ugualea B. Gli 8 blocchi da 4 privi di 2 A consecutive da aggiungere alla B (valea dire ABAB, ABBA, ABBB, BABA, BABB, BBAB, BBBA, BBBB) possonoessere messi in corrispondenza biunivoca con gli 8 blocchi possibili da3 AAA, AAB, ABA, ABB, BAA, BAB, BBA, BBB in modo arbitrario. Sead esempio li sostituiamo esattamente nell’ordine elencato, il “codice”risultante sostituisce

ABAAABBBA con BABBBBABBABBBBA

5

Nel caso in cui n = 3m+1 si lascia invariata la prima lettera e si procedecome prima sul resto, il ricevente dalla lunghezza del messaggio 5m+ 1ricavera l’informazione che la prima lettera e immutata. Se n = 3m+2,infine, il primo blocco di 2 lettere, AA, AB, BA, BB, viene sostituito daun blocco di 3, rispettivamente ABB, BAB, BBA, BBB. Anche in questocaso, la lunghezza del messaggio, 5m+3, segnalera al ricevente che deveoperare in un modo sulle prime 3 lettere e in un altro sulle 5m rimanenti.

(b) Indichiamo con an il numero delle parole dell’alfabeto ammissibili per ipostini, i.e. prive di due A consecutive, con aAn quelle che terminano perA e con aBn quelle che terminano per B. Abbiamo evidentemente

aAn+1 = aBn e aBn+1 = an = aAn + aBn ,

da cui ricaviamo an+1 = aAn+1 + aBn+1 = an−1 + an.Quindi la successione an soddisfa la relazione di Fibonacci. Dalla

relazione di Fibonacci si ricava l’espressione (per induzione su n)

an = c

(

1 +√5

2

)n

+ d

(

1−√5

2

)n

.

Il valore delle costanti c e d potrebbe essere determinato esplicitamentetenendo conto del fatto che a2 = 3 e a3 = 5, ma questo non e essenziale.

Ora, se un metodo di conversione non allunga i messaggi piu di unfattore ℓ > 1 e consente di recuperare univocamente il messaggio inizia-le, deve essere aℓn ≥ 2n, visto che il numero dei messaggi possibili dilunghezza n e 2n. Studiamo quindi la disuguaglianza 2−na6n/5 ≥ 1 emostriamo che non puo valere per n grande. Tenendo conto dell’espres-sione di an e del fatto che il termine dominante e il primo, per n ≫ 1dovra essere

c2−n

(

1 +√5

2

)6n/5

≥ 1

2.

Passando ai logaritmi in base 2 otteniamo

n(6

5ln2(1 +

√5)− 11

5

)

≥ −1− ln2 c.

Dato che ln2(1 +√5) ∼ 1, 69 otteniamo che il fattore che moltiplica n e

negativo, di qui la contraddizione.

Esercizio 6. Anita e Paolo stanno facendo un gioco. Anita muove sempreper prima. La mossa del giocatore di turno consiste nel passare un numerointero all’avversario. Tale numero puo essere ottenuto o sottraendo 1 oppuredimezzando (e arrotondando, se occorre, all’intero piu piccolo) il numeroricevuto. Per esempio, chi riceve 28 puo passare all’altro 27 oppure 14,mentre chi riceve 27 puo passare all’altro 26 oppure 13. Il giocatore chericeve il numero 0 vince.

(a) Supponendo che ogni giocatore usi la strategia migliore, chi vince se siparte da 13? e da 24?

(b) Per ciascun intero positivo n, sia q(n) il numero di interi tra 1 and nche, se usati come numero iniziale, sono vincenti per Paolo. Poniamo

p(n)def

= q(n)/n. Come si comporta p(n) se n va all’infinito?

Soluzione esercizio 6.

6

(a) Iniziamo a studiare le partite a ritroso, mettendo nella prima riga inumeri positivi certamente vincenti per il giocatore che li riceve, nellaseconda i numeri certamente perdenti. Ovviamente 1 e nella secondariga, ne segue subito che 2 e 3 sono vincenti. Il 4 e perdente, perchequalsiasi mossa trasforma il 4 in un numero vincente, ne segue che 5, 8e 9 sono vincenti. Il numero 6 e anch’esso perdente (potendo generaresolo 5 e 3), ne segue che sono vincenti 7, 12, 13. Continuando in questomodo viene generata la seguente tabella:

V 2 3 5 8 9 7 12 13 11 20 21 . . .P 1 4 6 10 14 16 18 22 24 26 30 . . .

Analizzando la tabella si puo congetturare che (considerando nei pro-dotti i soli dispari maggiori di 1)

V ={

22m· dispari}

∪ {22m+1}

e

P ={

22m+1· dispari}

∪ {22m}

con m ≥ 0 intero. Per verificare che e effettivamente cosı, dobbiamoverificare che ogni numero in V e trasformabile (seguendo ovviamentele regole del gioco) in un numero in P e che ogni numero in P generanecessariamente un numero in V .

Se il numero in V e del tipo 22m+1 basta dividerlo per 2. Se e deltipo 22m(2ℓ + 1) con ℓ > 0 basta ancora dividerlo per 2, se m > 0. Sem = 0 il numero e della forma 2ℓ+1, che puo essere scritto nella forma2a+1d + 1 con n intero non negativo e d positivo dispari. Qui abbiamo4 casi:

d dispari> 1, a pari: sottraiamo 1.d dispari> 1, a dispari: dividiamo per 2.d = 1, a pari: dividiamo per 2.d = 1, a dispari: sottraiamo 1.Se ora il numero in P e del tipo 22m (non consideriamo il caso banale

m = 0) e lo dimezziamo, otteniamo un numero in V . Se invece sot-traiamo 1, otteniamo 22m − 1 = d con d dispari > 1, quindi ancora inV .

Infine, se il numero in P e del tipo 22m+1 · (2ℓ + 1) con ℓ > 0 e lodimezziamo, certamente il numero risultante e in V , se gli sottraiamo 1otteniamo un numero dispari, che quindi appartiene a V . Concludiamoquindi che tutti i numeri in V sono vincenti per Nicola e quelli in P sonovincenti per Paolo.

(b) Per n grande, possiamo trascurare il contributo alla probabilita datodai numeri del tipo 22m+1 in V e 22m in P , dato che la frequenza delleloro occorrenze in [0, n] tende a 0 per n che tende all’infinito. Per V(i.e. i numeri vincenti per Nicola) abbiamo quindi che la probabilita

7

vale asintoticamente1

2+

1

8+

1

32+ · · · = 1

2

[

1 +1

4+

1

16+ · · ·

]

=1

2· 43

=2

3.

Equivalentemente, per P (i.e. numeri vincenti per Paolo) vale

1

4+

1

16+

1

64+ · · · = 1

1− (1/4)− 1

=4

3− 1

=1

3.