|
1. Dimostrazione per induzione che bastano n-1 passi per trovare il massimo Per
n=2 è vero Infatti n-1=1,
con 1 passo trovo il massimo di 2 oggetti Se
è vero per n, allora è vero per n+1 Infatti
supponiamo di avere trovato il massimo di n
oggetti con n-1 passi. Se
abbiamo n+1 oggetti allora procediamo così Troviamo
il massimo di n oggetti, poi basta un solo passo per trovare il massimo
n+1 oggetti, perché basta confrontare l’n+1 oggetto con il massimo precedentemente
trovato. Abbiamo così trovato il massimo di n+1 oggetti con n passi Questa dimostrazione funziona. 2.
Dimostrazione per induzione che il numero di passi per n oggetti, N(n),
deve essere superiore a n-2 : N(n)
> n-2. Per n=2 è vero Infatti N -1 =1 > n 2 = 0,
con 1 passo trovo il massimo di 2 oggetti ed è evidente che non
posso fare meglio Se non posso fare meglio
per n, allora non posso fare meglio per n + 1 Infatti supponiamo che il numero di passi
N(n) > n-2. Se abbiamo n + 1 oggetti allora procediamo così Troviamo il massimo di n oggetti, poi occorre (e basta) un
passo per trovare il massimo di n+1 oggetti, perché è necessario
confrontare l’ n+1 oggetto con il massimo precedentemente trovato. Abbiamo così trovato il massimo di n + 1 oggetti con 1
passo in più rispetto al numero di passi che servono per n oggetti.
Quindi se per ipotesi non posso trovare il massimo di n oggetti con n - 2 passi, N(n) > n - 2 , ottengo che N(n + 1) = N(n) + 1 > n - 1 Non posso trovare il massimo di n + 1 oggetti con n - 1
passi. Questa dimostrazione non funziona
IMPORTANTE
La dimostrazione sopra riportata si basa su tre implicite
assunzioni: a)
posso trovare il massimo di due oggetti con 1 passo, e questo è
evidente. b)
posso trovare il massimo di n oggetti aggiungendo 1 passo a
quelli che servono per trovare il massimo di n-1 oggetti, questo è
evidente e segue immediatamente dal primo punto. c)
per trovare il massimo di n-1 oggetti devo trovare prima il
massimo di n-2 oggetti. Questo ultimo punto però non è ovvio. Infatti potrei dividere in modo diverso l’insieme, nel senso che non è detto che per trovare il massimo (o il minimo) io debba trovare il massimo e il minimo dell’insieme con un numero di oggetti inferiore Se ragiono allo stesso modo per trovare il massimo e
il minimo di n oggetti, potrei dimostrare che non posso fare meglio di
2n-3 passi, ma non è così. |