IMO 2008 - P5

[Gianni De Rico]

Sea $n$ y $k$ enteros positivos tales que $k\geq 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 las 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 $\frac{N}{M}$.

[juandodyk]

Spoiler: mostrar

Sorprendentemente facil usando funciones generatrices. Sean $a_1,\ldots,a_{2n}\geq0$ la cantidad de veces que prendemos/apagamos cada lampara. Hay $\frac{(a_1+\cdots+a_{2n})!}{a_1!\ldots a_{2n}!} = \frac{k!}{a_1!\ldots a_{2n}!}$ secuencias con esas cantidades.

Para calcular $N$ miramos las cantidades tales que $a_1,\ldots,a_n$ son impares y $a_{n+1},\ldots,a_{2n}$ son pares. Entonces $N$ es $k!$ por el coeficiente de $x^k$ en
$$f(x) = \left(\frac{x}{1!} + \frac{x^3}{3!} + \cdots\right)^n \left(1 + \frac{x^2}{2!} + \frac{x^4}{4!} + \cdots\right)^n = \left(\frac{e^x - e^{-x}}2\right)^n \left(\frac{e^x + e^{-x}}2\right)^n = \frac1{2^{2n}} (e^{2x} - e^{-2x})^n.$$
Es decir, $N = f^{(k)}(0)$, la $k$-esima derivada de $f$ evaluada en $0$. Ahora $f(x) = \frac1{2^{2n}} \sum_{j=0}^n \binom{n}{j} (-1)^j e^{2(n-2j)x}$, asi que $f^{(k)}(x) = \frac1{2^{2n}} \sum_{j=0}^n \binom{n}{j} (-1)^{j} (2(n-2j))^k e^{2(n-2j)x}$ y obtenemos
$$N = f^{(k)}(0) = 2^{k-2n} \sum_{j=0}^n \binom{n}{j} (-1)^{j} (n-2j)^k.$$

Para $M$ consideramos $a_1,\ldots,a_n$ son impares y $a_{n+1},\ldots,a_{2n}$ son $0$. Entonces $M$ es $k!$ por el coeficiente de $x^k$ en
$$g(x) = \left(\frac{x}{1!} + \frac{x^3}{3!} + \cdots\right)^n = \frac1{2^n} (e^x - e^{-x})^n = \frac1{2^n} \sum_{j=0}^n \binom{n}{j} (-1)^j e^{(n-2j)x},$$
es decir $M = g^{(k)}(0)$. Ahora $g^{(k)} = \frac1{2^n} \sum_{j=0}^n \binom{n}{j} (-1)^j (n-2j)^k e^{(n-2j)x},$ y
$$M = g^{(k)}(0) = 2^{-n} \sum_{j=0}^n \binom{n}{j} (-1)^j (n-2j)^k.$$

Asi que $\frac{N}{M} = 2^{k-n}$.

[tuvie]

Spoiler: mostrar

Respuesta: El cociente da $2^{k-n}$.

Solución: Vamos a agrupar cada posible secuencia de $M$ con $2^{k-n}$ secuencias de $N$. Esto va a justificar que $N/M$ da efectivametne ese valor.

Supongamos que tenemos una secuencia $s$ (formada por oprimir $x_1, \ldots, x_k$) de $M$, en la cual se aprieta la tecla $i$ unas $a_i$ veces. Observar que $a_i$ debe ser impar, pues debe quedar prendida la tecla $i$, para cada $1\leq i \leq n$. Ahora, las posibles secuencias asociadas a $s$ que pertenecen a $N$ serán aquellas en las cuales se realizan las operaciones en el mismo orden $y_1, \ldots, y_k$ pero si una operación era sobre la lámpara $i$, podemos optar por presionar la tecla $i$ o $n+i$. Para la tecla $i$, como se aprieta $a_i$ veces en $s$, tenemos $2^{a_i}$ posibles secuencias en las cuales nos permitimos apretar $i$ o $n+i$, dos posibilidades para cada una de las $a_i$ oprimidas. Pero de las $2^{a_i}$, solo la mitad hace que se apriete la tecla $i$ una cantidad impar de veces y la tecla $n+i$ par de veces (la otra mitad corresponde al caso inverso, par para $i$ e impar para $n+i$). Luego, a cada sucesión $s$ la estamos asignando a $2^{a_1-1}\cdot\ldots\cdot 2^{a_n-1}=2^{k-n}$ ya que $a_1+\ldots+a_n=k$.

Por lo tanto, agrupamos a cada sucesion de $M$ con $2^{k-n}$ secuencias de $N$. Es claro que no dejamos afuera a ninguna secuencia de $N$ y que no hay una secuencia de $M$ asociada a dos secuencias de $N$ distintas.

La respuesta es entonces $2^{k-n}$.