Teorema
Le possibili risposte sono N/2 + 2
Dimostrazione
La dimostrazione consta di 3 step.
Notazione
Sia F una sequenza di frecce. Indichiamo con F[i], con 0 <= i < N, la freccia alla i-esima posizione. Indichiamo con F[i..j] la sotto-sequenza che ha come estremi i e j (inclusi). I possibili valori per F[i] sono (>) e (<).
Step 1
Sia n un intero, e F una sequenza di lunghezza 2n. Se F[0] = (>) e F[2n - 1] = (<), allora è possibile rendere la sequenza F equilibrata con al più n - 1 mosse.
Dimostriamo questo fatto per induzione estesa.
Passo Base: n = 1.
L'unica possibile F è (><), ed è effettivamente possibile renderla equilibrata in 0 mosse.
Passo Induttivo: sapendo il fatto per 1, 2, ..., n, dimostriamolo per n + 1.
Esaminiamo tre casi.
- Esiste 0 < i < n tale che F[2i - 1] = (<). Allora faccio le seguenti cose:
- con al più una mossa faccio sì che F[2i] = (>)
- con al più i - 1 mosse rendo F[0..2i - 1] equilibrata (posso farlo per ipotesi induttiva)
- con al più n - i - 1 mosse rendo F[2i..2n - 1] equilibrata (posso farlo per ipotesi induttiva)
In questo modo, usando al più n - 1 mosse, ho reso F equilibrata.
- Esiste 0 < i < n tale che F[2i] = (>). Con un ragionamento analogo al caso precedente, riesco a rendere F equilibrata usando al più n - 1 mosse.
- Se nessuno dei precedenti casi è verificato, ciò significa che F = (>><><><><>...<><><><><<). Si verifica facilmente che è possibile trasformare F in (>>>>>>>>>>...<<<<<<<<<<) con al più n - 1 mosse, rendendola di fatto equilibrata. ■
Notiamo che, se F è una sequenza di lunghezza N, con
al più 2 mosse possiamo far sì che F[0] = (>) e F[N] = (<). A questo punto, ponendo n = N/2, il fatto appena dimostrato ci dice che possiamo rendere la "nuova" F equilibrata in
al più N/2 - 1 mosse; in totale, una qualunque sequenza può essere resa equilibrata con
al più N/2 - 1 + 2 = N/2 + 1 mosse.
Step 2
D'altro canto, esiste sempre almeno una sequenza di lunghezza N per cui sono necessarie N/2 + 1 mosse per renderla equilibrata. Consideriamo ad esempio la sequenza (<>>>>>...>>>>>>): dobbiamo sicuramente usare 1 mossa per girare la prima freccia; inoltre, siccome dobbiamo avere esattamente N/2 frecce del tipo (<), dobbiamo girarne altre N/2, per un totale di N/2 + 1 mosse.
Step 3
Notiamo infine che, se esiste una sequenza F per cui sono necessarie almeno M mosse, allora esiste una sequenza G per cui ne sono necessarie almeno M - 1. Infatti, sia F' la sequenza equilibrata che può essere ottenuta da F; sia x tale che F'[x] =/= F[x]; allora basta scegliere G uguale a F, eccezion fatta per G[x], che è uguale a F'[x].
Queste tre osservazioni combinate ci dicono che esistono sequenze di lunghezza N per cui sono necessarie 0, 1, 2, ..., N/2 + 1 mosse, ma non ne esistono per cui sono necessarie più di N/2 + 1 mosse. Pertanto, le possibili risposte al problema sono N/2 + 2.
