|
La ville a quatre préposées au stationnement. Elles travaillent le matin et l'après-midi avec un même enthousiasme et une même efficacité. Les routes du matin ont des durées de x1 > x2 > x3 > x4 heures et les routes de l'après-midi ont des durées de y1 > y2 > y3 > y4 heures. Toute préposée qui travaille plus de H heures doit se faire payer le surplus en heures supplémentaires. Par une coïncidence remarquable, elles se rencontrent toutes pour bouffer au restaurant du coin, où les quatre marmitons font façe à une situation similaire: Pour venir au travail ils doivent stationner leurs scooters dans la rue, où les parcomètres imposent une durée maximale de H heures. Leurs journées consistent en corvées de cuisine le matin, de durées x1 > x2 > x3 > x4 heures et corvées de nettoyage l'après-midi de durées y1 > y2 > y3 > y4 heures. Le restaurant paie les amendes des marmitons dont la journée de travail dépasse H heures. Démontrez que pour minimiser le temps payé en heures supplémentaires, la ville peut répartir les routes du matin et de l'après-midi en combinant les durées x1 et y4, x2 et y3, x3 et y4, puis x4 et y1. Est-ce que cette solution minimise aussi nécessairement le nombre d'amendes à payer par le restaurant? Solution to MP36 Nous avons reçu une solution de Patrick LoPesti (Etats Unis), basée sur deux observations préliminaires: Observation 1. Soit une suite a1, a2, ..., an de nombres réels, à laquelle on applique la procédure suivante (dite de "tri naif''):
En répétant la procédure
autant de fois qu'il est nécéssaire, on obtient une
suite triée, c'est à dire où a1 ≤ a2 ≤ ...≤ an.
Observation 2. Si une solution envisagée au problème combine les parcours xi + yi' et xj + yj' où i < j et i' < j' (donc xi > xj et yi' > yj'), il n'y a pas de mal à interchanger les parcours de l'après-midi pour obtenir les combinaisons xi + yj' et xj + yi'. En effet, xi + yi' est plus long que xi + yj'. Soit s, la portion de la différence qui est payée en heures supplémentaires dans la solution proposée. Alors remplacer xi + yi' par xi + yj' permet de diminuer de s le temps payé en heures supplémentaires, alors que remplacer xj + yj' par xj + yi' l'augmente d'au plus s (puisque xj ≤ xi). Ainsi il n'y a pas de mal à effectuer la substitution. Ainsi, à partir de n'importe
quelle solution proposée au problème, on peut, sans
jamais faire pire, effectuer une modification telle que suggérée
par l'observation 2, aussi souvent qu'une telle modification est possible.
Selon l'observation 1, on obtient alors la solution x1 + y4, x2
+ y3, x3 + y2, x4 + y1. En réponse à la deuxième partie de la question, on note que cette solution n'est pas nécessairement la meilleure pour les marmitons. En effet, soit (x1,x2,x3,x4) = (y1,y2,y3,y4) = (5,4,3,2). Si H = 7 la solution est bien 5+2, 4+3, 3+4, 2+5, mais pour H = 6 on obtient 5+5, 4+2, 3+3, 2+4, ce qui donne une seule amende plutot que quatre. Notre problème est inspiré d'un problème de Introduction to Graph Theory par Douglas B. West. Dans un chapitre sur l'utilisation des graphes dans les problèmes de couplages à poids minimal, ce problème démontre qu'il n'est pas toujours nécessaire de se servir de toute une théorie pour résoudre un cas particulier. |