Shortlist 2018, C5¶

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

Concepts : Double comptage · Invariants et monovariants

Solution officielle : Shortlist officielle 2018 (avec solutions), p. 28 (page 30 du PDF)

Énoncé¶

Let \(k\) be a positive integer. The organising committee of a tennis tournament is to schedule the matches for \(2k\) players so that every two players play once, each day exactly one match is played, and each player arrives to the tournament site the day of his first match, and departs the day of his last match. For every day a player is present on the tournament, the committee has to pay \(1\) coin to the hotel. The organisers want to design the schedule so as to minimise the total cost of all players' stays. Determine this minimum cost.

Indices : les idées clés

Trier arrivées et départs séparément (solution 1) : le coût total vaut \(\sum (e_i - b_i + 1)\), et chaque terme se minore indépendamment.
Double comptage (solution 1) : on compte les matchs déjà joués avant une arrivée ou restant après un départ, en tenant compte des matchs comptés deux fois.
Construction explicite (solution 1) : deux groupes \(X\) et \(Y\) de \(k\) joueurs, qui réalisent toutes les minorations à la fois.
Coût d'un match (solution 2) : le nombre de joueurs présents ce jour-là ; le coût minimal d'un match se lit sur l'ordre d'arrivée et l'ordre de départ.
Monovariant (solution 2) : échanger deux termes de la permutation ne fait pas augmenter le coût et augmente le nombre d'inversions, jusqu'à la permutation renversée.

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2018 (deux solutions et une remarque).

Réponse : le coût minimal est \(\dfrac{k(4k^2 + k - 1)}{2}\).

Solution 1¶

Numérotons les jours du tournoi \(1, 2, \ldots, \binom{2k}{2}\). Soient \(b_1 \leq b_2 \leq \cdots \leq b_{2k}\) les jours d'arrivée des joueurs, rangés dans l'ordre croissant, et \(e_1 \geq \cdots \geq e_{2k}\) les jours de départ, rangés dans l'ordre décroissant (il peut arriver qu'un joueur arrive le jour \(b_i\) et parte le jour \(e_j\) avec \(i \neq j\)). Un joueur arrivé le jour \(b\) et parti le jour \(e\) coûte \(e - b + 1\). Le coût total est donc

\[\Sigma = \sum_{i=1}^{2k} e_i - \sum_{i=1}^{2k} b_i + 2k = \sum_{i=1}^{2k} (e_i - b_i + 1).\]

Minoration du coût total. Minorons \(e_{i+1} - b_{i+1} + 1\) pour \(0 \leq i \leq 2k - 1\). Avant le jour \(b_{i+1}\), seuls \(i\) joueurs étaient présents, donc au plus \(\binom{i}{2}\) matchs ont pu être joués : \(b_{i+1} \leq \binom{i}{2} + 1\). De même, au plus \(\binom{i}{2}\) matchs ont pu être joués après le jour \(e_{i+1}\), donc \(e_i \geq \binom{2k}{2} - \binom{i}{2}\) (Le livret écrit \(e_i\) ; il faut lire \(e_{i+1}\).). Ainsi

\[e_{i+1} - b_{i+1} + 1 \geq \binom{2k}{2} - 2\binom{i}{2} = k(2k - 1) - i(i - 1).\]

Cette minoration s'améliore pour \(i > k\) : faisons la liste des \(i\) joueurs arrivés les premiers et celle des \(i\) joueurs partis les derniers ; au moins \(2i - 2k\) joueurs figurent sur les deux listes. Les matchs entre ces joueurs ont été comptés deux fois ci-dessus, alors que chacun n'a été joué qu'une fois. Donc, si \(i > k\),

\[e_{i+1} - b_{i+1} + 1 \geq \binom{2k}{2} - 2\binom{i}{2} + \binom{2i - 2k}{2} = (2k - i)^2.\]

Un tournoi optimal. Décrivons un calendrier qui réalise simultanément toutes ces minorations. On partage les joueurs en deux groupes \(X\) et \(Y\) de \(k\) joueurs chacun, et le calendrier en trois parties. Dans la première partie, les joueurs de \(X\) arrivent un par un, et chaque nouvel arrivant joue immédiatement contre tous ceux déjà présents. Dans la troisième partie (une fois tous les joueurs de \(X\) partis), les joueurs de \(Y\) partent un par un, chacun jouant juste avant son départ contre tous ceux encore présents.

Dans la partie centrale, chaque joueur de \(X\) doit affronter chaque joueur de \(Y\). Notons \(S_1, \ldots, S_k\) les joueurs de \(X\) et \(T_1, \ldots, T_k\) ceux de \(Y\). Les \(T_j\) arrivent dans l'ordre \(T_1, T_2, \ldots, T_k\) ; dès son arrivée, \(T_j\) joue contre tous les \(S_i\) avec \(i > j\). Ensuite les joueurs \(S_k, S_{k-1}, \ldots, S_1\) partent dans cet ordre ; chaque \(S_i\) joue, juste avant son départ, contre tous les \(T_j\) avec \(i \leq j\), et \(S_k\) part le jour de l'arrivée de \(T_k\). Pour \(0 \leq s \leq k - 1\), le nombre de matchs joués entre l'arrivée de \(T_{k-s}\) et le départ de \(S_{k-s}\) est

\[\sum_{j=k-s}^{k-1} (k - j) + 1 + \sum_{j=k-s}^{k-1} (k - j + 1) = \frac{1}{2}s(s+1) + 1 + \frac{1}{2}s(s+3) = (s+1)^2.\]

Ainsi, si \(i > k\), le nombre de matchs joués entre l'arrivée de \(T_{i-k+1}\) (qui est \(b_{i+1}\)) et le départ de \(S_{i-k+1}\) (qui est \(e_{i+1}\)) vaut \((2k - i)^2\), c'est-à-dire \(e_{i+1} - b_{i+1} + 1 = (2k - i)^2\) : la seconde minoration est atteinte pour tout \(i > k\).

Si \(i \leq k\), les matchs entre les \(i\) joueurs présents avant \(b_{i+1}\) ont tous lieu dans la première partie ; il y en a \(\binom{i}{2}\) et \(b_{i+1} = \binom{i}{2} + 1\). De même, après \(e_{i+1}\) il reste \(i\) joueurs, les \(\binom{i}{2}\) matchs entre eux ont lieu dans la troisième partie, et \(e_{i+1} = \binom{2k}{2} - \binom{i}{2}\). La première minoration est donc atteinte pour tout \(i \leq k\).

Toutes les minorations sont atteintes simultanément : ce calendrier est optimal.

Calcul. Le coût du calendrier optimal est

\[\Sigma = \sum_{i=0}^{k} \left(k(2k - 1) - i(i - 1)\right) + \sum_{i=k+1}^{2k-1} (2k - i)^2 = (k+1)k(2k - 1) - \sum_{i=0}^{k} i(i - 1) + \sum_{j=1}^{k-1} j^2\]

\[= k(k+1)(2k - 1) - k^2 + \frac{1}{2}k(k+1) = \frac{1}{2}k(4k^2 + k - 1). \qquad \blacksquare\]

Solution 2¶

Considérons un calendrier quelconque. Numérotons les joueurs \(P_1, P_2, \ldots, P_{2k}\) dans l'ordre de leurs arrivées, puis à nouveau \(Q_{2k}, Q_{2k-1}, \ldots, Q_1\) dans l'ordre de leurs départs ; cela définit une permutation \(a_1, a_2, \ldots, a_{2k}\) de \(1, 2, \ldots, 2k\) par \(P_i = Q_{a_i}\).

On décrit d'abord un tournoi optimal pour une permutation \(a_1, \ldots, a_{2k}\) donnée, puis on cherche la permutation optimale.

Optimisation pour \(a_1, \ldots, a_{2k}\) fixés. Appelons coût du match entre \(P_i\) et \(P_j\) le nombre de joueurs présents le jour où il est joué. Chaque jour, le comité paie exactement le coût du match de ce jour : il s'agit donc de minimiser la somme des coûts de tous les matchs.

Le départ de \(Q_{2k}\) ne précède pas l'arrivée de \(P_{2k}\). Le nombre de joueurs présents croît donc (au sens large) jusqu'à atteindre \(2k\), puis décroît (au sens large). Ainsi, le meilleur moment pour le match entre \(P_i\) et \(P_j\) est soit l'arrivée de \(P_{\max(i,j)}\), soit le départ de \(Q_{\max(a_i, a_j)}\), et son coût est au moins \(\min\left(\max(i,j), \max(a_i, a_j)\right)\).

Réciproquement, si \(i > j\) et que ce match est joué entre les arrivées de \(P_i\) et de \(P_{i+1}\), son coût vaut exactement \(i = \max(i,j)\). De même, on peut lui donner le coût \(\max(a_i, a_j)\). Toutes ces conditions peuvent évidemment être satisfaites simultanément, donc le coût minimal pour une suite \(a_1, \ldots, a_{2k}\) fixée est

\[\Sigma(a_1, \ldots, a_{2k}) = \sum_{1 \leq i < j \leq 2k} \min\left(\max(i,j), \max(a_i, a_j)\right). \tag{1}\]

Optimisation de la suite \((a_i)\). Tout repose sur le lemme suivant.

Lemme. Si \(a \leq b\) et \(c \leq d\), alors

\[\min\left(\max(a,x), \max(c,y)\right) + \min\left(\max(b,x), \max(d,y)\right) \geq \min\left(\max(a,x), \max(d,y)\right) + \min\left(\max(b,x), \max(c,y)\right).\]

Preuve. Posons \(a' = \max(a,x) \leq \max(b,x) = b'\) et \(c' = \max(c,y) \leq \max(d,y) = d'\), et vérifions que \(\min(a',c') + \min(b',d') \geq \min(a',d') + \min(b',c')\) (vérification directe selon l'ordre des quatre nombres). \(\square\)

Considérons une permutation \(a_1, \ldots, a_{2k}\) telle que \(a_i < a_j\) pour certains \(i < j\). Échanger \(a_i\) et \(a_j\) ne modifie pas le terme d'indice \((i,j)\) dans (1) et, pour \(\ell \notin \{i, j\}\), la somme des termes d'indices \((i,\ell)\) et \((j,\ell)\) n'augmente pas, d'après le lemme. La valeur optimale n'augmente donc pas, tandis que le nombre d'inversions de la permutation augmente (monovariant). Ce processus s'arrête lorsque \(a_i = 2k + 1 - i\) pour tout \(i\), donc le minimum cherché vaut

\[\Sigma(2k, 2k-1, \ldots, 1) = \sum_{1 \leq i < j \leq 2k} \min\left(\max(i,j), \max(2k + 1 - i, 2k + 1 - j)\right) = \sum_{1 \leq i < j \leq 2k} \min(j, 2k + 1 - i).\]

Cette dernière somme se calcule sans difficulté et donne le résultat annoncé ; le livret officiel omet les détails. \(\blacksquare\)

Remarques¶

Remarque 1. Si le nombre de joueurs est impair, disons \(2k - 1\), le minimum cherché vaut \(k(k-1)(4k-1)/2\). Dans ce cas, on prend \(|X| = k\) et \(|Y| = k - 1\) ; l'argument est le même, avec quelques détails techniques supplémentaires.