Olimpiada India IMO Training Camp 2007 Problema 3
3 Dada una cadena finita $S$ de símbolos $X$ y $O$ , denotamos $\Delta(s)$ como el número de $X'$ s en $S$ menos el número de $O'$ s (Por ejemplo, $\Delta(XOOXOOX)=-1$ ) . Llamamos equilibrada a una cadena $S$ si toda subcadena $T$ de (símbolos consecutivos) $S$ tiene la propiedad $-1\leq \Delta(T)\leq 2.$ (Así, $XOOXOOX$ no está equilibrada, pues contiene la subcadena $OOXOO$ cuyo valor de $\Delta$ es $-3.$ Halle, con demostración, el número de cadenas equilibradas de longitud $n$ .
0
0
Kevin
Inicia sesión para agregar soluciones y pistas