Parentesi

Immaginate di scrivere un'espressione composta da un certo numero di parentesi aperte e dello stesso numero di parentesi chiuse, e di voler verificare se l'espressione è "ben formata", nel senso che non ci siano mai più parentesi chiuse che aperte, e quindi siano tutte accoppiabili come "aperta+chiusa". Un'espressione come ()(()) è per esempio ben fatta; le parentesi in posizione 1 e 2 si possono eliminare come quelle in posizione 4 e 5, lasciando quelle in posizione 3 e 6 che a questo punto si possono eliminare. Un'espressione come ())(()() non lo è: possiamo eliminare le parentesi in posizione 1 e 2, in posizione 5 e 6, e in posizione 7 e 8 ma restano 3 e 4 che sono chiusa+aperta. La domanda è: è sempre possibile prendere un certo numero (eventualmente nessuna) di parentesi dal fondo di un'espressione e trasportarle all'inizio nello stesso ordine per avere un'espressione ben formata? In questo caso potrei spostare cinque parentesi e ottenere (()()()).

   

   

(trovate un aiutino sul mio sito, alla pagina http://xmau.com/quizzini/p541.html; la risposta verrà postata lì il prossimo mercoledì. Problema di James Tanton.)