Strategie Euristiche e Algebra Lezione 2

Strategie Euristiche e Algebra Lezione 2

Lezione del 02/03/2011

Stage di Acireale Progetto Olimpiadi

Induzione

• Il principio di induzione serve a dimostrare una qualche affermazione per tutti i numeri naturali maggiori di un certo numero iniziale.

• La dimostrazione con questo principio si compone di due passi:

1. Il passo base, dove si dimostra l’affermazione per il numero iniziale

2. Il passo induttivo, dove si dimostra che se

l’affermazione vale per n, allora vale anche per n+1

• NOTA BENE: nel secondo passo non si dimostra che vale per n, si dimostra solo che nel caso in cui sia vera per un certo n allora è vera anche per il successivo

Induzione: esercizio esempio 1

• Dimostrare che la somma dei primi n numeri è data da P(n)=n(n+1)/2

• Passo base: la somma dei numeri fino ad 1 è 1, e P(1)=1*2/2=1 OK

• Passo induttivo: per ipotesi la proprietà vale per n, quindi la somma dei numeri fino ad un certo n vale P(n)=n(n+1)/2. Allora la somma dei numeri fino ad n+1 vale P(n)+n+1

=n(n+1)/2+n+1=(n+1)(n+2)/2=P(n+1) OK

Induzione: esercizio esempio 2

• Dimostrare che la somma dei primi n quadrati vale P(n)=n(n+1)(2n+1)/6

• Passo base: la somma dei quadrati fino ad 1 è 1, e P(1)=1*2*3/6=1 OK

• Passo induttivo: per ipotesi la proprietà vale per n, quindi la somma dei quadrati fino al quadrato di un certo n vale P(n)=n(n+1)(2n+1)/6. Allora la somma dei quadrati fino a quello di n+1 vale

P(n)+(n+1)2

=n(n+1)(2n+1)/6+(n+1)2=(n+1)(2n2+n+6n+6)/6

=(n+1)(n+2)(2n+3)/6=P(n+1) OK

Induzione: altri esercizi

• Somma della progressione geometrica a

=r*a

è a

*(r

-1)/(r-1)

• Il termine n-esimo della successione a

=r*a

+ b è a

r

+b*(r

-1)/(r-1)

Induzione: Torre di Hanoi

• Dimostrare che posso spostare una pila di n dischi in 2ⁿ-1

mosse mantenendo l’ordine

• Passo Base: un disco lo sposto in una mossa

• Passo induttivo: con mosse sposto 2ⁿ-1 n dischi sulla terza colonna, con una mossa

sposto l’n+1-esimo disco nella seconda colonna, con altre 2ⁿ- 1 mosse sposto i primi n dischi sopra l’n+1-esimo disco, per un totale di 2ⁿ⁺¹-1 mosse.

Discesa infinita

• È equivalente al principio di induzione, si usa per dimostrazioni distruttive (non esistenza)

• Esempio: dimostra che l’equazione x3+2y3=4z3 non ha soluzioni intere non nulle

• Ipotesi per assurdo: esiste soluzione intera. Ma allora x è pari.

Pongo x=2a, e ottengo che posso dividere tutto per 2, e che y è pari per lo stesso motivo di prima. Pongo Y=2b e ottengo che posso

dividere ancora tutto per 2 e che z è pari. Pongo z=2c e dividendo tutto per due ottengo di nuovo l’equazione iniziale. Allora se esiste una soluzione (x,y,z), ne esiste anche una (a,b,c)=(x/2,y/2,z/2) con valore assoluto più piccolo. Posso continuare all’infinito perché sono tornato ad avere un’equazione nella stessa forma di quella iniziale. Quindi se esiste una soluzione intera ne esistono infinite intere con valore assoluto sempre più piccolo. Questo è un assurdo perché l’insieme dei numeri naturali ha un elemento minimo (l’1).

Disuguaglianze fra le medie

• Disuguaglianza fondamentale: a²>=0

• Valida sempre per ogni numero , inoltre vale il segno di uguale se e solo se a=0

• a=sqrt(x)-sqrt(y)=>(x+y)/2>=sqrt(xy) AM>=GM

• a=x-y=> (x²+y²)/2>=(x+y)/2 QM>=AM

• A=1/sqrt(x)-1/sqrt(y)=> sqrt(xy)>=2/(1/x+1/y) GM>=HM

• Ricapitolando, QM>=AM>=GM>=HM (anche per medie di più di due numeri) e vale il segno di

uguaglianza se e solo se tutti i termini sono uguali

Massimizzazione in presenza di vincoli

• Uso le medie

• Esempio 1: massimo prodotto di due numeri con somma 2

• x+y=2, sqrt(xy)<=(x+y)/2 => xy<=1

• Esempio 2: minima somma di due numeri con prodotto 4

• xy=4, (x+y)/2>=sqrt(xy)=> x+y>=4

• Esempio 3: massimo di xy² di due numeri con somma 3

• x+y=x+y/2+y/2=3 , sqrt[3](xy²/4)<=(x+y/2+y/2)/3 =>

xy²<=4