Shortlist 2011, C1¶

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

Concepts : Récurrence et constructions récursives · Bijections et dénombrement

Solution officielle : Shortlist officielle 2011 (avec solutions), p. 27 (page 28 du PDF)

Problème 4 de l'OIM 2011

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

Énoncé¶

Let \(n > 0\) be an integer. We are given a balance and \(n\) weights of weight \(2^0, 2^1, \ldots, 2^{n-1}\). In a sequence of \(n\) moves we place all weights on the balance. In the first move we choose a weight and put it on the left pan. In each of the following moves we choose one of the remaining weights and we add it either to the left or to the right pan. Compute the number of ways in which we can perform these \(n\) moves in such a way that the right pan is never heavier than the left pan.

Indices : les idées clés

Retirer le poids \(1\) : une suite valide pour \(n\) poids donne une suite valide pour \(2, 4, \ldots, 2^{n-1}\), soit \(f(n - 1)\) façons après division par \(2\).
Réinsérer le poids \(1\) : en premier coup, il va forcément à gauche ; sinon il peut aller des deux côtés (l'écart est déjà au moins \(2\)). Cela fait \(2n - 1\) façons, donc \(f(n) = (2n - 1)f(n - 1)\) (récurrence).
Dénombrement alternatif (solution 2) : selon le moment où le poids \(2^{n-1}\) est posé, on obtient une formule de récurrence complète, qui redonne la même relation.

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2011 (deux solutions et quatre remarques).

Réponse : \(f(n) = (2n - 1)!! = 1 \cdot 3 \cdot 5 \cdots (2n - 1)\).

Solution 1¶

Soit \(n \geq 2\). Montrons que

\[f(n) = (2n - 1)f(n - 1). \tag{1}\]

Remarquons d'abord qu'après le premier coup, le plateau de gauche est toujours plus lourd d'au moins \(1\) que celui de droite. Donc toute façon valide de placer les \(n\) poids donne, en ignorant le poids \(1\), une façon valide de placer les poids \(2, 2^2, \ldots, 2^{n-1}\).

Si l'on divise chaque poids par \(2\), la réponse ne change pas. Ces \(n - 1\) poids peuvent donc être placés de \(f(n - 1)\) façons valides. Regardons maintenant le poids \(1\). S'il est posé au premier coup, il doit être mis à gauche ; sinon, il peut être mis à gauche ou à droite, car après le premier coup la différence entre les plateaux de gauche et de droite est au moins \(2\). Il y a donc exactement \(2n - 1\) façons d'insérer le poids \(1\) dans chacune des \(f(n - 1)\) suites valides pour les \(n - 1\) poids afin d'obtenir une suite valide pour les \(n\) poids. Cela prouve (1).

Comme \(f(1) = 1\), on obtient par récurrence, pour tout entier \(n \geq 1\),

\[f(n) = (2n - 1)!! = 1 \cdot 3 \cdot 5 \cdots (2n - 1). \qquad \blacksquare\]

Remarque 1. Le mot « calculer » de l'énoncé est sans doute trop vague. Une question différente mais plus artificielle pourrait demander le plus petit \(n\) pour lequel le nombre de façons valides est divisible par \(2011\). La réponse serait alors \(1006\).

Remarque 2. La réponse est la même pour tout ensemble de poids dans lequel chaque poids est plus lourd que la somme des plus légers. En effet, dans ce cas, la condition équivaut à demander que, pendant tout le processus, le poids le plus lourd posé sur la balance soit sur le plateau de gauche.

Remarque 3. Au lieu du poids le plus léger, on peut aussi considérer le dernier poids posé sur la balance. Si c'est \(2^{n-1}\), il doit être mis à gauche. Sinon, il peut être mis sur n'importe quel plateau ; l'inégalité ne serait pas violée, puisqu'à ce moment le poids le plus lourd est déjà à gauche. D'après la remarque précédente, dans chacun de ces \(2n - 1\) cas, le nombre de façons de placer les poids précédents est exactement \(f(n - 1)\), ce qui donne (1).

Solution 2¶

Voici une autre façon d'obtenir (1). Posons \(f(0) = 1\). Trouvons d'abord une formule de récurrence pour \(f(n)\).

Soit \(n \geq 1\). Supposons que le poids \(2^{n-1}\) soit posé au \(i\)-ème coup, avec \(1 \leq i \leq n\). Il doit être mis à gauche. Pour les coups précédents, on a \(\binom{n-1}{i-1}\) choix des poids, et d'après la remarque 2, \(f(i - 1)\) façons valides de les placer. Pour les coups suivants, il n'y a aucune contrainte sur la façon de placer les poids : les \((n - i)!\,2^{n-i}\) façons sont toutes possibles. Cela donne

\[f(n) = \sum_{i=1}^{n} \binom{n-1}{i-1} f(i - 1)(n - i)!\,2^{n-i} = \sum_{i=1}^{n} \frac{(n - 1)!\, f(i - 1)\, 2^{n-i}}{(i - 1)!}. \tag{2}\]

Prouvons maintenant (1). En remplaçant \(n\) par \(n - 1\) dans (2), on obtient

\[f(n - 1) = \sum_{i=1}^{n-1} \frac{(n - 2)!\, f(i - 1)\, 2^{n-1-i}}{(i - 1)!}.\]

Donc, à nouveau par (2),

\[f(n) = 2(n - 1) \sum_{i=1}^{n-1} \frac{(n - 2)!\, f(i - 1)\, 2^{n-1-i}}{(i - 1)!} + f(n - 1) = (2n - 2)f(n - 1) + f(n - 1) = (2n - 1)f(n - 1). \qquad \blacksquare\]

Remarque 4. Il existe d'autres façons d'obtenir la formule (2). En voici une. Supposons qu'au premier coup on utilise le poids \(2^{n-i+1}\). Alors les \(n - i\) poids plus légers peuvent être posés à n'importe quel moment et sur n'importe quel plateau, ce qui donne \(2^{n-i} \cdot \frac{(n - 1)!}{(i - 1)!}\) choix pour les coups (moments et plateaux) de ces poids. Les \(i - 1\) coups restants forment une suite valide pour les \(i - 1\) poids plus lourds, et c'est la seule exigence pour ces coups ; il y a donc \(f(i - 1)\) telles suites. En sommant sur \(i = 1, 2, \ldots, n\), on retrouve (2).