OIM 2008, ziua 2, pb 2

[Claudiu Mindrila]

Fie \( n \) si \( k \) numere naturale nenule astfel incat \( k \geq n \) si \( k-n \) numar par. Consideram \( 2n \) becuri notate \( 1,2,...,2n \) ce se pot afla in starile aprins sau stins. La inceput toate becurile sunt in starea stins. Consideram secventele de pasi: la fiecare pas unul si numai un bec este aprins daca era stins, sau stins daca era aprinsa.
Fie \( N \) numarul de astfel de secvente, formate din \( k \) pasi, ce duc la starea in care becurile de la \( 1 \) la \( n \) sunt toate aprinse, iar becurile de la \( n+1 \) la \( 2n \) sunt toate stinse.
Fie \( M \) numarul de secvente, formate din \( k \) pasi ce duc la starea in care toate becurile de la \( 1 \) la \( n \) sunt toate aprinse, iar becurile de la \( n+1 \) la \( 2n \) sunt toate stinse, dar nici unul dintre becurile de la \( n+1 \) la \( 2n \) nu a fost aprins pe parcursul secventei.
Aflati numarul \( \frac{N}{M} \).

Bruno Le Floch and Ilia Smilga, France