Problema 5 de la fase nacional de la 57 Olimpiada Matemática Española (2021) Se dirige a una edad de: 16-17 años
Disponemos de 2n bombillas colocadas en dos filas (A y B) y numeradas del 1 al n en cada fila.
Algunas (o ninguna) de las bombillas están encendidas y el resto, apagadas; decimos que esto es un “estado”.
Dos estados son distintos si hay una bombilla que está apagada en uno de ellos y encendida en el otro.
Diremos que un estado es “bueno” si hay la misma cantidad de bombillas encendidas en la fila A que en la B.
Demuestra que el número total de estados buenos (EB) dividido por el número total de estados (ET), es: EB/ET = (1·3·5·…·(2n – 1))/(2n·n!).
Solución:
En el ejemplo que se ve en la imagen, se aprecian los 20 estados buenos de los 64 totales en el caso de n = 3, donde se confirma que 20/64 = 5/16 = (1·3·5)/(2³·3!) = 15/48 = 5/16.
En estos problemas de combinatoria, se suele aplicar uno de los siguientes tres métodos de ataque: inducción sobre uno de los elementos, aunque en este caso no he visto la manera de abordarlo así, simplificación a partir de fórmulas conocidas, o bien manipulación de propiedades.
Tras una primera revisión de los casos más sencillos, se aprecia que para n = 1 se da la igualdad (hay en total 4 estados, de los que 2 son buenos), y para n = 2 también (hay 16 estados, de los que 6 son buenos, uno con cero bombillas encendidas, otro con todas encendidas y 4 con dos bombillas encendidas).
El número total de estados diferentes es muy sencillo justificar que es 22n, ya que cada bombilla de las 2n puede estar independientemente en dos estados.
No me pareció sencillo calcular la cifra general de estados buenos, aunque es rápido llegar a la conclusión de que es igual a sumar los cuadrados de los números combinatorios de n elementos, no conocía ninguna fórmula que me permitiese simplificarlo (después de hacer el problema, descubrí que hay una fórmula que garantiza que la suma de los cuadrados de todos los números combinatorios de n elementos es igual al número combinatorio resultado de tomar n elementos de un total de 2n, pero no fue así como lo resolví realmente).
Después de pelearme con el problema de las formas más evidentes (combinatoria básica e inducción) de forma infructuosa, resolví tratar de reformular la igualdad para ver si me sugería algo.
Puesto que el número de estados es 22n, el que la fórmula sea válida es equivalente a probar que EB = 22n·(1·3·5·…·(2n – 1))/(2n·n!) = 2n·(1·3·5·…·(2n – 1))/(n!).
Para intentar expresar el producto de números impares como un único factorial, puedo introducir todos los factores pares necesarios entre 1 y 2n, y, puesto que dispongo de n factores 2 y eso coincide con un factor 2 para cada número par, sólo tendré que introducir la mitad de cada número par, es decir, que esa fracción coincide con 2n·n!·(1·3·5·…·(2n – 1))/(n!·n!) = (1·2·3·4·5·6·…·(2n – 2)(2n – 1)(2n))/(n!·n!) = (2n)!/(n!·n!), que es exactamente el número combinatorio que representa la cantidad de formas de tomar n elementos de un total de 2n.
Es decir, que demostrar la validez de la fórmula equivale a ver que el número de estados buenos coincide con la cantidad de formas de tomar n elementos de un total de 2n.
Basta, pues, establecer una correspondencia entre una elección tal y un estado bueno y ver que es una correspondencia biunívoca, es decir, que a estados buenos distintos corresponden elecciones diferentes y viceversa.
La clave está en elegir n posiciones de las 2n bombillas y, por ejemplo, en la fila A, encender las bombillas elegidas y dejar apagadas las no elegidas, y en la fila B actuar al contrario, dejando apagadas las elegidas y encendiendo las no elegidas.
Puesto que la elección es de n bombillas, el número de bombillas no elegidas coincide con las elegidas, por lo que la cantidad de bombillas encendidas será el mismo en las dos filas, así que cada elección corresponde a un estado bueno, y si tenemos un estado bueno, diremos que están elegidas las bombillas encendidas de la fila A y las apagadas de la fila B, que serán un total de n, por lo que cada estado bueno corresponde a una elección de n bombillas.
Por lo tanto, así completamos la demostración.
