Prueba de Selección de Equipos de Marruecos 2018 Problema 5

5 Sea $n$ un entero positivo. Define un camaleón como cualquier secuencia de $3n$ letras, con exactamente $n$ ocurrencias de cada una de las letras $a, b$ y $c$. Define un intercambio como la transposición de dos letras adyacentes en un camaleón. Demuestra que para cualquier camaleón $X$, existe un camaleón $Y$ tal que $X$ no puede transformarse en $Y$ usando menos de $3n^2/2$ intercambios.

0

0

Kevin

Inicia sesión para agregar soluciones y pistas

Problemas Recomendados