Shortlist 2010, C1

Domaine : Combinatoire · Difficulté : ★★☆☆☆ · Proposé par : Austria

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

Solution officielle : Shortlist officielle 2010 (avec solutions), p. 23 (page 24 du PDF)

Figures reprises du livret officiel de la Shortlist.

Énoncé

In a concert, \(20\) singers will perform. For each singer, there is a (possibly empty) set of other singers such that he wishes to perform later than all the singers from that set. Can it happen that there are exactly \(2010\) orders of the singers such that all their wishes are satisfied?

Indices : les idées clés

• Produit : si \(n_1\) est réalisable par \(k_1\) chanteurs et \(n_2\) par \(k_2\), alors \(n_1n_2\) l'est par \(k_1 + k_2\) (on fait passer tout le second groupe après le premier).
• Factorisation : \(2010 = 5 \cdot 6 \cdot 67\), réalisés par \(4\), \(3\) et \(13\) chanteurs.
• Dénombrement : pour \(67\), une chaîne fixée \(a_1, \ldots, a_{11}\) et deux chanteurs \(x\), \(y\) donnent \(9 \cdot 7 + 4\) constructions d'ordres.

Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2010 (une solution et une remarque).

Réponse : oui, un tel exemple existe.

Solution

Un ordre des chanteurs est dit bon s'il satisfait tous leurs souhaits. On dit ensuite qu'un nombre \(N\) est réalisable par \(k\) chanteurs (ou \(k\)-réalisable) si, pour un certain ensemble de souhaits de ces chanteurs, il y a exactement \(N\) bons ordres. Il faut donc prouver que le nombre \(2010\) est \(20\)-réalisable.

Commençons par le lemme simple suivant.

Lemme. Supposons que les nombres \(n_1\), \(n_2\) sont réalisables par \(k_1\) et \(k_2\) chanteurs respectivement. Alors le nombre \(n_1n_2\) est \((k_1 + k_2)\)-réalisable.

Preuve. Soient \(A_1, \ldots, A_{k_1}\) des chanteurs (avec certains souhaits entre eux) qui réalisent \(n_1\), et \(B_1, \ldots, B_{k_2}\) des chanteurs (avec certains souhaits entre eux) qui réalisent \(n_2\). Ajoutons à chaque chanteur \(B_i\) le souhait de chanter après tous les chanteurs \(A_j\). Alors chaque bon ordre de l'ensemble obtenu est de la forme \((A_{i_1}, \ldots, A_{i_{k_1}}, B_{j_1}, \ldots, B_{j_{k_2}})\), où \((A_{i_1}, \ldots, A_{i_{k_1}})\) est un bon ordre des \(A_i\) et \((B_{j_1}, \ldots, B_{j_{k_2}})\) un bon ordre des \(B_j\). Réciproquement, tout ordre de cette forme est évidemment bon. Le nombre de bons ordres est donc \(n_1n_2\). \(\square\)

Vu le lemme, montrons comment construire des groupes de \(4\), \(3\) et \(13\) chanteurs réalisant respectivement les nombres \(5\), \(6\) et \(67\). Le nombre \(2010 = 6 \cdot 5 \cdot 67\) sera alors réalisable par \(4 + 3 + 13 = 20\) chanteurs. Ces groupes de chanteurs sont représentés sur les figures 1 à 3 ; les souhaits sont représentés par des flèches, et le nombre de bons ordres de chaque figure est indiqué entre parenthèses.

Pour la figure 1, il y a exactement \(5\) bons ordres : \((a, b, c, d)\), \((a, b, d, c)\), \((b, a, c, d)\), \((b, a, d, c)\), \((b, d, a, c)\). Pour la figure 2, chacun des \(6\) ordres est bon, puisqu'il n'y a aucun souhait.

Enfin, pour la figure 3, l'ordre de \(a_1, \ldots, a_{11}\) est imposé ; dans cette file, le chanteur \(x\) peut se placer avant chacun des \(a_i\) (\(i \leq 9\)), et le chanteur \(y\) après chacun des \(a_j\) (\(j \geq 5\)), ce qui donne \(9 \cdot 7 = 63\) cas. De plus, les positions de \(x\) et \(y\) dans cette file déterminent l'ordre complet de façon unique, sauf si tous deux se placent entre la même paire \((a_i, a_{i+1})\) (donc \(5 \leq i \leq 8\)) ; dans ces derniers cas, il y a deux ordres au lieu d'un, selon l'ordre de \(x\) et \(y\). Le nombre total de bons ordres est donc \(63 + 4 = 67\), comme voulu. \(\blacksquare\)

Remarque

Le nombre \(20\) dans l'énoncé n'est pas optimal ; il est là pour respecter la formulation d'origine. Si nécessaire, on peut donc ajuster la difficulté du problème en remplaçant \(20\) par un nombre plus petit. Voici quelques améliorations de l'exemple, qui conduisent à un nombre plus petit de chanteurs.

Bien sûr, tout exemple avec moins de \(20\) chanteurs peut être complété par des « vedettes » qui chantent à la toute fin dans un ordre imposé. Chacune de ces améliorations fournit donc une autre solution du problème. De plus, la grande variété des idées derrière ces exemples laisse penser qu'il en existe beaucoup d'autres.

1. Au lieu de construire des exemples réalisant \(5\) et \(6\), il est plus économique de construire un exemple réalisant \(30\) ; cela peut même sembler plus simple. Deux exemples possibles, avec \(5\) et \(6\) chanteurs, sont représentés sur la figure 4 ; on peut donc descendre de \(20\) à \(19\) ou \(18\).

Pour la figure 4a, l'ordre de \(a_1, \ldots, a_4\) est imposé, il y a \(5\) façons d'insérer \(x\) dans cet ordre, puis \(6\) façons d'insérer \(y\) dans l'ordre obtenu de \(a_1, \ldots, a_4, x\). Il y a donc \(5 \cdot 6 = 30\) bons ordres.

Pour la figure 4b, les \(5\) chanteurs \(a, b_1, b_2, c_1, c_2\) ont \(5! = 120\) ordres en tout. Évidemment, exactement la moitié d'entre eux satisfont le souhait \(b_1 \leftarrow b_2\), et exactement la moitié de ceux-là satisfont l'autre souhait \(c_1 \leftarrow c_2\) ; il y a donc exactement \(5!/4 = 30\) bons ordres.

1. On peut combiner plus astucieusement les exemples pour \(30\) et \(67\) des figures 4b et 3, et obtenir un groupe de \(13\) chanteurs représentant \(2010\). Cet exemple est représenté sur la figure 5 ; une flèche partant du groupe \(\{b_1, \ldots, b_5\}\) ou y arrivant signifie qu'il existe une telle flèche pour chaque membre de ce groupe.

Ici, comme pour la figure 4b, on voit qu'il y a exactement \(30\) ordres de \(b_1, \ldots, b_5, a_6, \ldots, a_{11}\) qui satisfont tous leurs souhaits internes. De plus, on peut prouver comme pour la figure 3 que chacun de ces ordres peut être complété par \(x\) et \(y\) d'exactement \(67\) façons, ce qui donne \(30 \cdot 67 = 2010\) bons ordres en tout.

De même, on peut combiner les exemples des figures 1 à 3 pour représenter \(2010\) par \(13\) chanteurs, comme sur la figure 6.

1. Enfin, voici deux autres améliorations ; les preuves sont laissées au lecteur. Le graphe de la figure 7 montre comment \(10\) chanteurs peuvent représenter \(67\). De plus, on peut même trouver un groupe de \(10\) chanteurs représentant \(2010\) ; il est représenté sur la figure 8.