Se quieren pintar de negro algunas aristas de un dodecaedro regular de manera tal que cada cara tenga pintada una cantidad par de aristas. Determinar de cuántas maneras se puede realizar la coloración. (Un dodecaedro regular tiene $12$ caras pentagonales y en cada vértice concurren tres aristas. Los vértices del dodecaedro son todos distintos para el propósito de las coloraciones.)
Éste problema lo escribió Prillo, quedó en la SL y también nos lo dieron en el training Ibero 2018 (claramente el mejor problema de ese año)
La solución es en conjunto con @jujumas, @LichuAcuña y @¿hola?, aunque en realidad es en mayor parte de Juli
Dato: le pedimos a Flora el almanaque con forma de dodecaedro para poder pensarlo mejor
Primero hay que aclarar que en el problema se considera que todos los vértices son distintos.
Notemos que tenemos $\frac{12\cdot 5}3=20$ vértices.
Ahora, llamamos "switchear" a la operación de seleccionar un vértice y cambiar el estado de sus $3$ aristas (para cada arista, la pintamos si estaba despintada y la despintamos si estaba pintada).
Una "serie de switcheos" es una operación en la que partimos del dodecaedro completamente en blanco (nuestra configuración inicial) y switcheamos algunos de sus vértices.
Decimos que una configuración es "buena" si todas las caras tienen una cantidad par de aristas pintadas.
Ahora, vamos a demostrar los siguientes lemas:
Lema 1: toda serie de switcheos lleva a una configuración buena.
Notemos que cada switcheo afecta a $2$ aristas de cada cara. Ahora veamos que la paridad de aristas pintadas en cada cara no cambia: si ambas aristas afectadas por el switcheo tenían el mismo estado (estaban ambas pintadas o ambas despintadas), entonces luego del switcheo siguen teniendo el mismo estado. Si tenían estados distintos (una pintada y una despintada), entonces luego del switcheo siguen teniendo estados distintos (una despintada y una pintada).
Por lo tanto, si partimos de la configuración inicial (que es buena), y aplicamos una serie de switcheos, la cantidad de aristas pintadas en cara cada va a seguir siendo par, por lo que vamos a llegar a una configuración buena, como queríamos.
Lema 2: cualquier configuración buena es alcanzable a partir de la configuración inicial mediante una serie de switcheos.
Supongamos que tenemos una configuración buena. Como nuestra operación es reversible (switchear un vértice $2$ veces es lo mismo que no switchearlo), con demostrar que podemos ir de una configuración buena a la configuración inicial estamos demostrando el lema.
Partiendo de una configuración buena, hagamos un grafo cuyos vértices son las caras del dodecaedro, en el que 2 vértices están unidos si y solo si las caras que representan comparten una arista, y cada arista del grafo está pintada si y solo si la arista a la que representa está pintada en el dodecaedro.
Veamos primero otro lemita:
Lema de Charles: si en un grafo conexo todos los vértices tienen grado par, entonces podemos dividirlo en ciclos que no compartan aristas (pueden compartir vértices).
Sea $s$ la suma de los grados de todos los vértices. Procedamos por inducción fuerte en $s$.
Es fácil ver que $6\leq s$; y que el caso base $s=6$ solo es posible si tenemos una clique de tamaño $3$.
Supongamos ahora que se puede para $6\leq s<k$.
Veamos qué ocurre con $s=k$.
Tomemos un vértice de grado mayor a $0$; que existe ya que $6\leq s$. Ahora, empecemos a caminar por las aristas del grafo, yendo de vértice en vértice. Como todos los vértices tienen grado par, de cada vértice al que entramos podemos salir. Detengámonos entonces cuando llegamos a un vértice por el que ya pasamos (esto tiene que ocurrir ya que $s$ es finito). Notemos que acá se nos formó un ciclo (que no incluye necesariamente a todos los vértices por los que pasamos).
Ahora, si quitamos todas las aristas que pertenecen a éste ciclo, todos los vértices siguen teniendo grado par (ya que estamos quitando $2$ aristas de cada vértice que es parte del ciclo).
Como $s$ disminuyó, podemos aplicar la hipótesis inductiva y dividir el grafo resultante en ciclos sin aristas en común, como queríamos.
Ahora, como la configuración es buena, de cada vértice sale una cantidad par de aristas pintadas, y por lo tanto podemos dividir las aristas pintadas en ciclos sin aristas en común.
Ahora, para cada ciclo, "dibujémoslo" en el dodecaedro: cada vértice del grafo lo ubicamos en el centro de la cara a la que representa, y cada arista pintada del grafo la dibujamos como un segmento que une los $2$ centros de las caras. Como esto es un ciclo, nos determina $2$ regiones en el dodecaedro. Elijamos alguna de forma arbitraria. Ahora, si switcheamos exactamente los vértices que están en esta región, vemos que todas las aristas del ciclo pasan de estar pintadas a estar despintadas, y el resto de las aristas no cambia su estado. Esto es así ya que las aristas que son parte del ciclo tienen un vértice dentro de la región y otro fuera, y por lo tanto con esta operación les estamos cambiando el estado. Como estaban todas pintadas, pasan a estar todas despintadas. Las aristas que están adentro de la región tienen sus $2$ vértices adentro, y por lo tanto las estamos cambiando de estado $2$ veces, es decir que quedan como estaban. Las aristas que están fuera de la región tienen sus $2$ vértices fuera, y por lo tanto no las estamos modificando.
Es decir que con esta operación despintamos exactamente las aristas del ciclo.
Podemos repetir esto para todos los ciclos, y como no hay $2$ que compartan aristas, realizando estas operaciones estamos tomando todas las aristas pintadas de una configuración buena y, mediante una serie de switcheos, estamos llegando a la configuración del dodecaedro completamente en blanco, como queríamos
Ahora, decimos que dos series de switcheos son "complementarias" cuando se cumple que un vértice está switcheado en una si y solo si no está switcheado en la otra.
Lema 3: si dos series de switcheos llevan a la misma configuración de aristas, entonces son la misma serie, o bien son complementarias.
Para esto, comencemos numerando los vértices del dodecaedro del $1$ al $20$; de forma que el vértice $k$ esté unido con el $k+1$ para $1\leq k\leq 19$.
dodecaedro.png
Ahora, tomemos una configuración buena cualquiera. Supongamos que switcheamos el vértice $1$; entonces por cómo está hecha la numeración queda determinado si switcheamos o no el vértice $2$ (ya que la arista entre $1$ y $2$ depende únicamente de estos vértices). A partir de esto queda determinado si switcheamos o no el vértice $3$; y así, queda determinado el estado de cada uno de los vértices.
Es decir que el hecho de haber switcheado el vértice $1$ nos determina cuáles vértices debemos switchear y cuáles no. Así, es claro que el hecho de no haber switcheado el vértice $1$ nos conduce a la serie de operaciones complementaria. Por lo tanto, como el vértice $1$ sólo puede estar switcheado o no switcheado, queda demostrado el lema.
Ahora, sea $C$ el conjunto de las coloraciones en las que cada cara tiene pintada una cantidad par de aristas. Queremos ver la cantidad de elementos de $C$. Consideremos el conjunto $N$ que, para cada par de series complementarias, contiene únicamente a la que tiene el vértice $1$ switcheado. Vamos a ver una biyección entre los conjuntos $N$ y $C$.
Por el Lema 1, a cada serie de switcheos le corresponde un elemento de $C$. Está claro que éste elemento es único, puesto que una serie de switcheos tiene un único resultado.
Ahora, por el Lema 2, a cada elemento de $C$ le corresponde un elemento de $N$.
Además, por el Lema 3 y por cómo construimos $N$, vemos que éste elemento es único.
Ya tenemos la biyección deseada.
Ahora, contemos los elementos de $N$: el vértice $1$ está switcheado, y para cada uno de los $19$ vértices restantes tenemos $2$ opciones: puede estar switcheado, o puede no estarlo.
Entonces la cantidad de elementos de $N$ es $\# N=2^{19}$.
Por lo tanto $\# C=2^{19}$.
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
