Quinto problema de la Olimpiada Internacional de Matemáticas de 2008:
Sean
y
enteros positivos tales que
es par. Se tienen
lámparas numeradas
cada una de las cuales puede estar encendida o apagada. Inicialmente todas las lámparas están apagadas. Se consideran sucesiones de pasos: en cada paso se selecciona exactamente una lámpara y se cambia su estado (si está apagada se enciende, si está encendida se apaga).
Seael número de sucesiones de
quedan todas encendidas y las lámparas
quedan todas apagadas.
Seael número de sucesiones de
Calcular la razón.
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
Este si que es el mas facil de todos. Para cualquuiera de los dos conjuntos, podemos dividir en dos partes: Parte A: Movimientos necesarios para encender las bombillas 1, …, n Parte B: Movimientos necesarios una de las lamparas 1, …, 2n en N y 1, …., n en M quede encendida o apagada de manera que quede como pide la condicion. Las posibles ordenaciones de los conjuntos N y M segun las partes A y B son identicas, asi que solo dependera de numero de bombillas a las cuales aplicar el movimiento que hace cumplir la condicion. Para k=n… Lee más »
Creo que no es correcto.
Pero vamos, el resultado que he obtenido yo tampoco lo es.
Es que lo he hecho a lo bestia con n=2 y k=2 y a menos que haya entendido mal el enunciado o me haya equivocado accionando interruptores imaginarios, debería ser 7/2 en este caso.
Vale, quise decir con n=2 y k=4. Y además se me olvidaron algunas combinaciones y el resultado que me sale ahora es 4. Mejor Pongo el desarrollo, llamando a las lámparas A B C y D: M: 4 accionado 3 veces B: ABBB BABB BBAB BBBA 4 Accionado 3 veces A: BAAA ABAA AABA AAAB Total: 8 N: Las de M: 8 3 comenzando en A y usando C: ABCC ACBC ACCB 3 comenzando en B y usando C: BACC BCAC BCCA 6 comenzando en C: CABC CACB CBAC CBCA CCAB CCBA Total usando C: 12 Total usando D: 12… Lee más »
el valor pedido es
¿Podrías compartir con nosotros tu razonamiento?
Yo sospecho fuertemente que esa es la respuesta correcta, pero vamos, porque tengo el C++ de mi parte, que si no…
Sive, si te parece, dejemos un tiempo para ver si alguien quiere aportar otras ideas diferentes.
Honestamente, aún no he mirado con detalle la respuesta de Javier.
Mi razonamiento es como sigue. Para , las lámparas deben accionarse cada una un número impar de veces, y las ninguna vez. Eso equivale a descomponer en sumas de la forma , o lo que es lo mismo, . El número de formas de descomponer el número entero (no olvidemos que es par) en sumas de números enteros no negativos es . Así que ya tenemos . Para , las lámparas deben accionarse cada una un número impar de veces, y las cada una un número par de veces. Eso equivale a descomponer en sumas de la forma , o… Lee más »
Hay una cosa que he pasado por alto el razonamiento anterior, y es que tanto
como 
deben ir multiplicadas por 
debido a que el orden en que se accionan las lámparas es relevante para identificar las secuencias. Pero eso no cambia el resultado final, que es muy distinto de 
. Si éste es el resultado correcto, ¿qué está mal en el razonamiento que he hecho?
Pues por ejemplo, de una combinación de cuatro pasos, no salen 24 (4!) variantes, cambiando el orden, si alguna lámpara se repite en algún paso. Por ejemplo, de la secuencia AAAB, importando el orden sólo salen otras tres: AABA, ABAA, y BAAA. Aún se puede intentar algo más por ese camino, pero me parece que se pone demasiado engorroso, y yo quiero pensar que hay una idea féliz que lleva a la solución de una forma más elegante. Pero no la encuentro… 🙁 Por otro lado, yo no puedo garantizar que la solución sea . Es sólo el resultado que… Lee más »
Vamos a ver que por cada sucesión se pueden construir exactamente sucesiones distintas (o dicho de otro modo, que hay exactamente sucesiones distintas que generan la misma sucesión). Llamemos a las lámparas . Primero notar que a partir de una sucesión dada podemos construir una sucesión del modo siguiente: dada una sucesión podemos tomar los cambios de estado (que están dados en cantidad par) de la lámpara y asignárselos a la lámpara , , con lo cual obtenemos una sucesión. La gracia está en saber cuántas sucesiones determinan la misma sucesión. Y esto es lo que vamos a hacer a… Lee más »
Pues para mi la demostración es tan válida, como brillante.
Yo también invertí casi todo mi tiempo en la idea de convertir secuencias de M en N, o al revés, para obtener el cociente. Supongo que todos los que desistimos de calcular el cardinal de M y N para después dividir, intentamos eso. Pero no se me ocurrió ninguna forma útil de hacerlo.
Felicidades.
Gracias Sive, no me había percatado de la repetición. Eso significa que cada combinación de
s y de 
s (en la notación de mi post) contribuye un factor 
. Esta cuenta resulta muy fácil con funciones generatrices. Según esto, el coeficiente de orden 
de la función 
es el número de 
sucesiones, y el coeficiente de orden $k$ de 
es el número de $N-$sucesiones. El susodicho coeficiente, 
, de 
no sé cuál es, pero sea el que sea, el de 
será 
, y de ahí se sigue el resultado correcto 
.
(Perdón, corrijo algunas erratas.) El coeficiente de orden
de la función 
es el número de 
sucesiones, y el coeficiente de orden 
de 
es el número de 
sucesiones. El susodicho coeficiente, 
, de 
no sé cuál es, pero sea el que sea, el de 
será 
, y de ahí se sigue el resultado correcto 
.
también se puede obteniendo la suma de los coeficientes del desarrollo
que contienen:
1) sólo potencias impares de
(para obtener 
)
2) sólo potencias impares de
y potencias pares de 
(para obtener 
).