Olimpiada Internacional de Matemáticas 2008 – Problema 5: Calcula la razón

Quinto problema de la Olimpiada Internacional de Matemáticas de 2008:

Sean n y k enteros positivos tales que k¸ n y k - n es par. Se tienen 2n lámparas numeradas 1, 2, \ldots , 2n 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).
Sea N el número de sucesiones de k pasos al cabo de los cuales las lámparas 1,2, \ldots , n quedan todas encendidas y las lámparas n + 1, \ldots , 2n quedan todas apagadas.
Sea M el número de sucesiones de k pasos al cabo de los cuales las lámparas 1,2, \ldots , n quedan todas encendidas y las lámparas n + 1, \ldots , 2n quedan todas apagadas sin haber sido nunca encendidas.
Calcular la razón \cfrac{N}{M}.

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

14 Comentarios

  1. 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 Solo hay 1 ordenacion en ambos conjuntos, que es encender las n primeras bombillas. Para el caso k=n+2, el conjunto N se obtienen las 2n bombillas que se han encendido y apgado, mientras en M solo ocurre con las n primeras asi que la razón.

    De cara al futuro, no deja de ser una combinaciones con repeticion, asi que:

    \displaystyle \frac{N}{M}=2^{\frac{k-n}{2}}\forall k, k\ mod\ 2=0

    Publica una respuesta
  2. 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.

    Publica una respuesta
  3. 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 (no es necesario desarrollar nada)

    Total N: 12+12+8 = 32

    N/M = 4

    Publica una respuesta
  4. ¿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…

    Publica una respuesta
  5. 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.

    Publica una respuesta
  6. Mi razonamiento es como sigue. Para M, las lámparas 1,\dots,n deben accionarse cada una un número impar de veces, y las n+1,\dots,2n ninguna vez. Eso equivale a descomponer k en sumas de la forma k=\sum_{j=1}^n (2r_j+1), o lo que es lo mismo, \frac{k-n}{2}=\sum_{j=1}^nr_j. El número de formas de descomponer el número entero \frac{k-n}{2} (no olvidemos que k-n es par) en sumas de n números enteros no negativos es \binom{n+\frac{k-n}{2}-1}{n-1}=\binom{\frac{k+n}{2}-1}{n-1}. Así que ya tenemos M=\binom{\frac{k+n}{2}-1}{n-1}.

    Para N, las lámparas 1,\dots,n deben accionarse cada una un número impar de veces, y las n+1,\dots,2n cada una un número par de veces. Eso equivale a descomponer k en sumas de la forma k=\sum_{j=1}^n (2r_j+1)+\sum_{j=1}^n (2p_j), o lo que es lo mismo, \frac{k-n}{2}=\sum_{j=1}^nr_j+\sum_{j=1}^np_j. El número de formas de descomponer el número entero \frac{k-n}{2} en sumas de 2n números enteros no negativos es \binom{2n+\frac{k-n}{2}-1}{2n-1}=\binom{\frac{k+3n}{2}-1}{2n-1}. Esto da N=\binom{\frac{k+3n}{2}-1}{2n-1}.

    El cociente se puede simplificar de varias formas y escribir

    \frac{M}{N}=\binom{\frac{k+n}{2}-1}{n-1}\binom{\frac{k+3n}{2}-1}{2n-1}^{-1}=\binom{2n-1}{n}\binom{\frac{k+3n}{2}-1}{n}^{-1}=\frac{(2n-1)(2n-2)\cdots n}{\left(\frac{k+3n}{2}-1\right)\left(\frac{k+3n}{2}-2\right)\cdots\frac{k+n}{2}}.

    Publica una respuesta
  7. Hay una cosa que he pasado por alto el razonamiento anterior, y es que tanto M como N deben ir multiplicadas por k! 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 2^{k-n}. Si éste es el resultado correcto, ¿qué está mal en el razonamiento que he hecho?

    Publica una respuesta
  8. 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 2^{k-n}. Es sólo el resultado que obtengo con un sencillo programa de ordenador, con unos cuantos casos particulares, pero puedo haberme equivocado haciendo el programa, claro.

    Publica una respuesta
  9. Vamos a ver que por cada M-sucesión se pueden construir exactamente 2^{k-n} N-sucesiones distintas (o dicho de otro modo, que hay exactamente 2^{k-n} N-sucesiones distintas que generan la misma M-sucesión). Llamemos a las lámparas L_1,\ldots,L_n,L_{n+1},\ldots,L_{2n}.

    Primero notar que a partir de una N-sucesión dada podemos construir una M-sucesión del modo siguiente: dada una N-sucesión podemos tomar los cambios de estado (que están dados en cantidad par) de la lámpara L_{n+i} y asignárselos a la lámpara L_i, 1\leq i\leq n, con lo cual obtenemos una M-sucesión. La gracia está en saber cuántas N-sucesiones determinan la misma M-sucesión. Y esto es lo que vamos a hacer a continuación.

    Consideremos ahora una M-sucesión. La lámpara L_i, \;1\leq i\leq n, habrá cambiado de estado un número impar de veces, pongamos 2r_i+1 veces (r_i\geq 0). Puesto que las lámparas de índice superior a n no han sido alteradas, se tiene que \sum_{i=1}^n (2r_i+1)=k (número total de pasos, o cambios de estado). Entonces, dada una M- sucesión, podemos construir N-sucesiones sustrayendo cambios de estado en cantidad par de la lámpara L_i y traspasándolos a la lámpara L_{n+i}, para cada i\in\{1,\ldots,n\}. Y además éstas son todas las formas de construir N-sucesiones.

    Ahora bien, dados los 2r_i+1 cambios de estado de la lámpara L_i, el número de sustracciones de cantidades pares (es decir, el número de subconjuntos de cantidad par) que podemos tomar es

    {2r_i+1 \choose 0} + {2r_i+1 \choose 2} + \ldots + {2r_i+1 \choose 2r_i} = 2^{2r_i}.

    Por tanto, para las n primeras lámparas tendremos un total de sustracciones pares dado por

    \prod_{i=1}^n 2^{2r_ i}=2^{\sum_{i=1}^n 2r_i}.

    Pero resulta que \sum_{i=1}^n (2r_i+1)=k, lo cual implica que \sum_{i=1}^n 2r_i=k-n.

    Publica una respuesta
  10. 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.

    Publica una respuesta
  11. Gracias Sive, no me había percatado de la repetición. Eso significa que cada combinación de r_is y de p_is (en la notación de mi post) contribuye un factor \frac{k!}{(2r_1+1)!\cdots(2r_n+1)!(2p_1)!\cdots(2p_n)!}. Esta cuenta resulta muy fácil con funciones generatrices. Según esto, el coeficiente de orden k de la función \left(\sum_{r=0}^{\infty}\frac{z^{2r+1}}{(2r+1)!}\right)^n=\sinh^nz es el número de N-sucesiones, y el coeficiente de orden $k$ de \left(\sum_{r=0}^{\infty}\frac{z^{2r+1}}{(2r+1)!}\right)^n \left(\sum_{r=0}^{\infty}\frac{z^{2r}}{(2r)!}\right)^n=\sinh^nz\cosh^nz=2^{-n}\sinh^n(2z) es el número de $N-$sucesiones. El susodicho coeficiente, a_k, de \sinh^nz no sé cuál es, pero sea el que sea, el de 2^{-n}\sinh^n(2z) será 2^{k-n}a_k, y de ahí se sigue el resultado correcto \frac{N}{M}=2^{k-n}.

    Publica una respuesta
  12. (Perdón, corrijo algunas erratas.) El coeficiente de orden k de la función \left(\sum_{r=0}^{\infty}\frac{z^{2r+1}}{(2r+1)!}\right)^n=\sinh^nz es el número de M-sucesiones, y el coeficiente de orden k de \left(\sum_{r=0}^{\infty}\frac{z^{2r+1}}{(2r+1)!}\right)^n \left(\sum_{r=0}^{\infty}\frac{z^{2r}}{(2r)!}\right)^n=\sinh^nz\cosh^nz=2^{-n}\sinh^n(2z) es el número de N-sucesiones. El susodicho coeficiente, a_k, de \sinh^nz no sé cuál es, pero sea el que sea, el de 2^{-n}\sinh^n(2z) será 2^{k-n}a_k, y de ahí se sigue el resultado correcto \frac{N}{M}=2^{k-n}.

    Publica una respuesta
  13. también se puede obteniendo la suma de los coeficientes del desarrollo (L_1+\ldots+L_{2n})^k

    que contienen:

    1) sólo potencias impares de L_1,\ldots,L_n (para obtener M)

    2) sólo potencias impares de L_1,\ldots,L_n y potencias pares de L_{n+1},\ldots,L_{2n} (para obtener N).

    Publica una respuesta

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *