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^ | Publicado el 26 de Agosto de 2008
Categorías: Juegos

14 comentarios

Javier | 26 de Agosto de 2008 | 9:50

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$
Sive | 26 de Agosto de 2008 | 18:04

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.
Sive | 26 de Agosto de 2008 | 18:18

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
M | 26 de Agosto de 2008 | 18:31

el valor pedido es $2^{k-n}$
Sive | 27 de Agosto de 2008 | 8:34

¿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…
M | 27 de Agosto de 2008 | 13:36

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.
zelig | 27 de Agosto de 2008 | 23:41

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}}$ .
zelig | 28 de Agosto de 2008 | 10:57

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?
Sive | 28 de Agosto de 2008 | 20:45

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.
M | 29 de Agosto de 2008 | 17:39

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$ .
Sive | 31 de Agosto de 2008 | 2:35

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.
zelig | 31 de Agosto de 2008 | 17:24

Gracias Sive, no me había percatado de la repetición. Eso significa que cada combinación de $r_i$ s y de $p_i$ s (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}$ .
zelig | 31 de Agosto de 2008 | 17:27

(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}$ .
M | 31 de Agosto de 2008 | 20:27

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$ ).