Q11 Matemática  (IMO Shortlist 2008)

Sejam $n$ e $k$ inteiros positivos com $k\ge n$ e $k-n$ um número par. Sejam dadas $2n$ lâmpadas rotuladas $1$, $2$, ..., $2n$, cada uma das quais pode estar ligada ou desligada. Inicialmente todas as lâmpadas estão apagadas. Consideramos sequências de etapas: a cada etapa uma das lâmpadas é ligada (de ligado para desligado ou de desligado para ligado). Seja $N$ o número de tais sequências consistindo de $k$ etapas e resultando no estado em que as lâmpadas $1$ a $n$ estão todas acesas e as lâmpadas $n+1$ a $2n$ estão todas apagadas. Seja $M$ o número de tais sequências consistindo de $k$ passos, resultando no estado em que as lâmpadas $1$ a $n$ estão todas acesas, e as lâmpadas $n+1$ a $2n$ estão todas apagadas, mas onde nenhuma das lâmpadas $n+1$ até $2n$ é ligada. Determine $\frac{N}{M}$. Autor: Bruno Le Floch e Ilia Smilga, França