ONEM 2024 - Etapa Nacional - Nivel 3 - P4

[cde_felix]

Considere un alfabeto formado por $n$ letras diferentes. Queremos formar una palabra que cumpla las siguientes dos condiciones:

1. No puede tener dos letras iguales consecutivas.
2. Ninguna subpalabra de longitud $4$ es de la forma $XYXY$ con $X\neq Y$ (es decir, no pueden repetirse las mismas dos letras de forma alternada).

Determine, en función de $n$, la mayor longitud posible de una palabra que cumple estas condiciones.

Aclaración: Una subpalabra de una palabra $P$ es una sucesión de letras que aparecen en $P$, manteniendo el mismo orden en el que aparecen en $P$, pero no necesariamente de manera consecutiva. Por ejemplo, $EDDC$ es una subpalabra de $TEADDVCB$.

[cde_felix]

¿No creen que se parece demasiado a Nacional 2003 N2 P6?

[Kenay555]

Sea $X$ una palabra válida, $sX$ su longitud, y $XL$ otra palabra. Es claro que $s(XL)>sX$.
Sea $...A...B...A...=P$ otra palabra. Si bien $s(PB)>sP$, es $PB$ inválido al prohibir $ABAB$ como subpalabra.
Sea $...Q=R$ otra palabra. También $s(RQ)>sR$, pero analógicamente no es posible al impedir $...QQ$ por regla.
Simplifica la primera letra y segunda de una palabra a $A$ y $B$, y todas las palabras comenzarían por $ABA...$ o por $ABC...$. Usa las reglas para añadir letras, descritas anteriormente, para encontrar tres patrones constantes principales:

Spoiler: mostrar

$ABACADAEA...AYAZA$, con $N$ As y $N-1$ otras letras;
$ABCDE...XYZYX...BA$, con $N$ letras de ida y $N-1$ de vuelta;
y $ABCD...XYX...BAZA$, con $N-1$ letras de ida, $N-2$ de vuelta y $+2$ por acabar en ZA,

Spoiler: mostrar

Asi que si $Nm$ es la palabra más larga de $N$ letras, sería $s(Nm)=2N-1$