Aller au contenu

Shortlist 2008, C4

Domaine : Combinatoire · Difficulté : ★★★☆☆ · Proposé par : non indiqué

Concepts : Bijections et dénombrement · Double comptage

Solution officielle : Shortlist officielle 2008 (avec solutions), p. 25 (page 26 du PDF)

Problème 5 de l'OIM 2008

Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2008, où il était le problème 5 (jour 2).

Énoncé

Let \(n\) and \(k\) be fixed positive integers of the same parity, \(k \geq n\). We are given \(2n\) lamps numbered \(1\) through \(2n\); each of them can be on or off. At the beginning all lamps are off. We consider sequences of \(k\) steps. At each step one of the lamps is switched (from off to on or from on to off).

Let \(N\) be the number of \(k\)-step sequences ending in the state: lamps \(1, \ldots, n\) on, lamps \(n + 1, \ldots, 2n\) off.

Let \(M\) be the number of \(k\)-step sequences leading to the same state and not touching lamps \(n + 1, \ldots, 2n\) at all.

Find the ratio \(N/M\).

Indices : les idées clés
  • Parités : dans tout processus admissible, chaque lampe \(\ell \leq n\) est actionnée un nombre impair de fois, et chaque lampe \(\ell > n\) un nombre pair de fois.
  • Modification : dans un processus restreint, on remplace un nombre pair quelconque des \(k_\ell\) actions de la lampe \(\ell\) par des actions de la lampe \(n + \ell\) ; cela fait \(2^{k_\ell - 1}\) choix, soit \(2^{k - n}\) en tout.
  • Correspondance \(1\) à \(2^{k-n}\) : tout processus admissible s'obtient ainsi d'un unique processus restreint (on remplace chaque lampe \(\ell > n\) par \(\ell - n\)), d'où \(N/M = 2^{k-n}\).
Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2008 (une solution). C'est le problème 5 de l'OIM 2008.

Réponse : \(N/M = 2^{k-n}\).

Solution

Une suite de \(k\) actions aboutissant à l'état décrit dans l'énoncé (lampes \(1, \ldots, n\) allumées, lampes \(n + 1, \ldots, 2n\) éteintes) est appelée un processus admissible. Si, de plus, le processus ne touche pas les lampes \(n + 1, \ldots, 2n\), on dit qu'il est restreint. Il y a donc \(N\) processus admissibles, dont \(M\) sont restreints.

Dans tout processus admissible, restreint ou non, chacune des lampes \(1, \ldots, n\) passe d'éteinte à allumée, donc est actionnée un nombre impair de fois ; et chacune des lampes \(n + 1, \ldots, 2n\) passe d'éteinte à éteinte, donc est actionnée un nombre pair de fois.

Remarquons que \(M > 0\), c'est-à-dire que des processus admissibles restreints existent (il suffit d'actionner chacune des lampes \(1, \ldots, n\) une seule fois, puis d'en choisir une et de l'actionner \(k - n\) fois, ce qui est un nombre pair par hypothèse).

Considérons un processus admissible restreint quelconque \(\mathbf{p}\). Prenons une lampe \(\ell\), \(1 \leq \ell \leq n\), et supposons qu'elle a été actionnée \(k_\ell\) fois. Comme on l'a remarqué, \(k_\ell\) doit être impair. Choisissons arbitrairement un nombre pair de ces \(k_\ell\) actions et remplaçons chacune d'elles par l'action de la lampe \(n + \ell\). Cela peut se faire de \(2^{k_\ell - 1}\) façons (car un ensemble à \(k_\ell\) éléments a \(2^{k_\ell - 1}\) parties de cardinal pair). Remarquons que \(k_1 + \cdots + k_n = k\).

Ces choix sont indépendants, au sens où le choix relatif à la lampe \(\ell\) n'affecte pas celui relatif à une autre lampe. Il y a donc \(2^{k_1 - 1} \cdot 2^{k_2 - 1} \cdots 2^{k_n - 1} = 2^{k-n}\) façons de combiner ces choix. Dans chacune de ces combinaisons, chacune des lampes \(n + 1, \ldots, 2n\) est actionnée un nombre pair de fois et chacune des lampes \(1, \ldots, n\) reste actionnée un nombre impair de fois, donc l'état final est le même que celui du processus initial \(\mathbf{p}\).

Cela montre que tout processus admissible restreint \(\mathbf{p}\) peut être modifié de \(2^{k-n}\) façons, donnant \(2^{k-n}\) processus admissibles distincts (toutes les lampes étant permises).

Montrons maintenant que tout processus admissible \(\mathbf{q}\) s'obtient de cette manière. En effet, il suffit de remplacer chaque action d'une lampe d'étiquette \(\ell > n\) qui apparaît dans \(\mathbf{q}\) par l'action de la lampe correspondante \(\ell - n\) ; dans le processus \(\mathbf{p}\) obtenu, les lampes \(n + 1, \ldots, 2n\) ne sont pas touchées.

Les actions de chaque lampe d'étiquette \(\ell > n\) apparaissaient dans \(\mathbf{q}\) un nombre pair de fois. Les remplacements effectués ont donc affecté chaque lampe d'étiquette \(\ell \leq n\) aussi un nombre pair de fois ; l'état final de chaque lampe est donc resté le même. Cela signifie que le processus \(\mathbf{p}\) obtenu est admissible — et évidemment restreint, puisque les lampes \(n + 1, \ldots, 2n\) n'y interviennent plus.

Si l'on prend maintenant le processus \(\mathbf{p}\) et qu'on inverse tous ces remplacements, on retrouve le processus \(\mathbf{q}\). Ces remplacements inverses ne sont rien d'autre que les modifications décrites aux paragraphes précédents.

Il y a donc une correspondance un-à-\(2^{k-n}\) entre les \(M\) processus admissibles restreints et l'ensemble des \(N\) processus admissibles. Par conséquent, \(N/M = 2^{k-n}\). \(\blacksquare\)