Problem 5 IMO 2008

Notation:C(p,n) nombre de combinaisons de p éléments parmi n éléments.
Donnons-nous une séquence du second genre.Les n dernières lampes sont intouchables.Si k_i désigne le nombres d'opérations faites sur la lampe i,alors k1,k2,...,k_n sont impairs car les lampes correspondantes doivent rester allumées à la fin.Posons k_i=2m_i+1.On remarque que 2m_i correspond au nombre d'opérations faites sur la lampe i après l'avoir allumée.On peut dire donc que 2m1+2m2+...+2m_n=k-n ainsi m1+...+m_n=a avec a=(k-n)/2.Cherchons le nombre de solutions de cette équation.Si l'on représente m_i par m_i barres(ou unités) alors on remarque que le nombre cherché correspond au nombre de possibilités de placer n-1 signes + entre les barres, c'est donc C(n-1,n-1+a),mais l'ordre chronologique des opérations importe,donc il faut multiplier ce nombre par k!.
Pour les séquences du premier genre on aura de mm l'équation m1+m2+...+m_2n=a.
Ainsi le rapport cherché est C(2n-1,2n-1+a)/C(n-1,n-1+a) qui se simplifie en ((2n-1+a)!/(n-1+a)!)*((n-1)!/(2n-1)!).
(sauf erreur)
On remarque que pour a=0 le rapport est 1 ce qui est déjà bien.

La solution qui suit est, mot pour mot, celle du condidat Jean-Fran¸cois
Martin. de France qui a obtenu 7/7
On part d’une certaine séquence qui comptera pour M. On prend maintenant une lampe fixée, de numéro
i 2 {1, ..., n}. Elle subit alors ai opérations avec ai = 1 (mod 2). On prend alors b de ces opérations, avec b 0
(mod 2) et 0 6 b 6 ai. On les fait subir `a la lampe n+i, en lieu et place de la lampe i (au moment o`u la lampe
i aurait dˆu les subir). Il y a alors ai
b possibilités de choisir ces b opérations. Si on prend tous les b, le nombre
de possibilit´es sera alors de ai

2 × 2ai = 2ai−1.
Mais, en prenant tous les i, et en d´enombrant tous les cas, il y a en tout
n Yi=1
2ai−1 = 2Pn
i=1(ai−1) = 2Pn
i=1 ai−n = 2k−n.
Mais, au lieu de se fixer `a une s´equence donn´ee comptant pour M, on peut faire tous ces changements sur toutes
les s´equences comptant pour M. Il y a alors M × 2k−n s´equences r´esultantes. Mais il est clair que cela donne
toutes les s´equences comptant pour N. Donc N = M × 2k−n, d’o`u N
M = 2k−n.
Remarque. Comme mentionn´e ci-dessus, ce probl`eme a ´et´e propos´e par la France, cr´e´e par Ilia Smilga et Bruno
Le Floch, tous deux anciens membres de l’´equipe de France. Initialement, il s’agissait de calculer le nombre
de certains chemins de longueur donn´ee reliant deux sommets oppos´es de l’hypercube en dimension k. Cet
(( habillage )) n’ayant aucune chance d’ˆetre accept´e pour les O.I.M., l’id´ee est ensuite venue d’introduire les
interrupteurs.

Si N/M=2k-n,alors pour k=n on aura N/M=n.
Mais on remarque que si k=n les seules opérations qu'on peut faire c'est allumer une seule fois chacune des lampes 1,2,...,n et on s'arrete.Donc N/M=1...(??)

oui parceque dans ce cas n=1 et ai = 1 parcequ'on aura que deux lampe et dans la premiére moitié il n'y aura qu'une seul lampe qui ne subira qu'une seul opération ( enfin je pense ) !!